# 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
else
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"))))
s))
```

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.

### 4 Responses to The Trabb Pardo Knuth Algorithm in Elisp

1. Phil says:

Yeah, that seems odd. An arithmetic overflow error exists, but all the documentation seems to suggest it would never be used.

`overflow-error\’
`\

2. Phil says:

I really hate the filtering on this comment system.

``` `overflow-error' `"Arithmetic overflow error"' This is a subcategory of `domain-error'.```

``` -- (elisp) Standard Errors The range of values for integers in Emacs Lisp is -536870912 to 536870911 (30 bits; i.e., -2**29 to 2**29 - 1) on typical 32-bit machines. (Some machines provide a wider range.) Emacs Lisp arithmetic functions do not check for overflow. Thus `(1+ 536870911)' is -536870912 if Emacs integers are 30 bits. -- (elisp) Integer Type It is important to note that in Emacs Lisp, arithmetic functions do not check for overflow. Thus `(1+ 536870911)' may evaluate to -536870912, depending on your hardware. -- (elisp) Arithmetic Operations The function `lsh', like all Emacs Lisp arithmetic functions, does not check for overflow, so shifting left can discard significant bits and change the sign of the number. For example, left shifting 536,870,911 produces -2 in the 30-bit implementation: -- (elisp) Bitwise Operations Function: expt x y This function returns X raised to power Y. If both arguments are integers and Y is positive, the result is an integer; in this case, overflow causes truncation, so watch out. -- (elisp) Math Functions ```

3. Phil says:

In fact, those “domain-error” errors are accompanied by the following description:

``` The following kinds of error, which are classified as special cases of `arith-error', can occur on certain systems for invalid use of mathematical functions. *Note (elisp) Math Functions ```

but nothing there claims to signal overflow-error.

4. Razvan says:

But is an overflow really necessary? or could a division by zero also suffice? I mean, all that is required there is to treat an exceptional situation, right?