The Trabb Pardo Knuth Algorithm in Elisp

The latest Programming Praxis Exercise is interesting. Back in 1973, Luis Trabb Pardo and Don Knuth published an algorithm that was meant to assess the power of a programming language. The algorithm was

Ask for 11 numbers to be read into a sequence S
Reverse S
For each number in S
  Call some function to do a mathematical operation on the number
  If the result overflows
    Alert the user
    Print the result

That seems simple enough but notice how it involves arrays (lists would be more natural in Lisp but the intent was to use arrays), indexing, I/O, iteration, general functions, mathematical functions, and error detection. Be implementing the algorithm in a language you get a good feel for how the language handles common programming tasks.

Naturally, I had to try it out in Lisp. I used Emacs Lisp as a sort of minimal Lisp but still got a very nice and concise implementation.

(require 'cl)
(let ((s (make-vector 11 0)))
  (dotimes (i 11)
    (aset s i (read-number "Enter a number: ")))
  (coerce (reverse (coerce s 'list)) 'vector)
  (mapc (lambda (n)
          (print (condition-case nil (expt 2 n) ((overflow-error) "OVERFLOW"))))

If I had used a list instead of an array, I wouldn't have needed the two calls to coerce but I would have needed two reverses if I filled the list in the most natural way.

The condition-case is like try/except from other languages. It performs the exponentiation and returns the result unless an overflow error occurs in which case it returns OVERFLOW. Whatever is returned is then printed. The only problem I had was getting an overflow. Generating an overflow is hard in most Lisps because of their bignum facilities. Emacs Lisp doesn't use bignums but it does handle overflows in the interpreter. A sexpr like (expt 10 1000) just returns 0. If you use (expt 10.0 1000) it returns 1.0e+INF. Division by zero does generate an error but its an arith-error not an overflow-error. If anyone knows how to generate an overflow in Elisp, leave a comment.

This entry was posted in Programming and tagged , . Bookmark the permalink.