TPK In Common Lisp

Yesterday I wrote about the Trabb Pardo Knuth algorithm and gave an implementation in Emacs Lisp. Elisp allows an nice implementation but was a bit frustrating because the Elisp interpreter handles overflows internally and never signals an overflow condition. Therefore, I decided to try it in Common Lisp to see how they differ and also to force an overflow.

You can’t get an integer overflow in Common Lisp because of the bignum support but you can with floating point calculations. Here’s my CL implementation of the TPK algorithm. I tried to make it as much like the Elisp version as possible.

(defun tpk ()
  (let ((s (make-array 11)))
    (dotimes (i 11)
      (princ "Enter number: " *query-io*)
      (setf (svref s i) (read *query-io*)))
    (map nil (lambda (n)
               (print (handler-case (expt 2.0 n)
                        (floating-point-overflow () "OVERFLOW"))))
         (reverse s))))

One nice thing about CL is that reverse works on any simple sequence and thus works on vectors. On the other hand, there isn’t a read-number function so I had to use read-line and parse-integer instead. Also, the CL mapc requires lists so I used map, which accepts vectors, instead.

When I ran tpk, I got gratifying results.

CL-USER> (tpk)
Enter number: 1
Enter number: 10
Enter number: 100
Enter number: 200
Enter number: 300
Enter number: 400
Enter number: 500
Enter number: 600
Enter number: 700
Enter number: 800
Enter number: 900

"OVERFLOW" 
"OVERFLOW" 
"OVERFLOW" 
"OVERFLOW" 
"OVERFLOW" 
"OVERFLOW" 
"OVERFLOW" 
"OVERFLOW" 
1.2676506e30 
1024.0 
2.0 
NIL

Update: Pascal Bourguignon pointed out that the specification said to read in numbers not integers so I’ve fixed the code above to use read rather than (parse-integer (read-line *query-io*)).