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.

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.


  2. Phil says:

    I really hate the filtering on this comment system.

    `"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?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>