Yemen, National Day

# TrabbPardoKnuth

Trabb Pardo Knuth algorithm (TPK) reads an array of 11 numbers, applies a function to each value, checks for overflow and writes the result in reverse order. It is meant to show the variation in expression of different programming languages.

Here’s how to do it in Emacs Lisp with an interactive command ‘M-x tpk’. Emacs Lisp has well-designed input and output facilities and can easily handle sequences. Support for numerical operations is shallow. Overflow needs to be manually checked.

(defun f (n)  "Check for overflow since Emacs Lisp won't."
;; Expression: (+ (sqrt (abs n)) (* 5 n n n))
;; Registers:
(let (r0 ;; (abs n)
r1 ;; (sqrt r0)
r2 ;; (* 5 n)
r3 ;; (* r2 n)
r4 ;; (* r3 n)
r5) ;; (+ r1 r4)
(setq r0 (abs n))
(when (or (< r0 0) (> n r0))
(signal 'overflow-error (list (list 'abs n) r0)))
(setq r1 (sqrt r0))
(when (or (< r1 0) (< r0 r1)) ;!
(signal 'overflow-error (list (list 'sqrt r0) r1)))
(setq r2 (* 5 n))
(when (or (and (< n 0) (>= r2 0))
(and (> n 0) (<= r2 0))
(and (< n 0) (>= r2 n))
(and (> n 0) (<= r2 n)))
(signal 'overflow-error (list (list '* 5 n) r2)))
(setq r3 (* r2 n))
(when (or (and (< r2 0) (< n 0) (<= r3 0))
(and (> r2 0) (> n 0) (<= r3 0))
(and (< r2 -1) (< n -1) (<= r3 1))
(and (> r2 0) (< n 0) (>= r3 0))
(and (< r2 0) (> n 0) (>= r3 0)))
(signal 'overflow-error (list (list '* r2 n) r3)))
(setq r4 (* r3 n))
(when (or (and (< r3 0) (< n 0) (<= r4 0))
(and (> r3 0) (> n 0) (<= r4 0))
(and (< r3 -1) (< n -1) (<= r4 1))
(and (> r3 0) (< n 0) (>= r4 0))
(and (< r3 0) (> n 0) (>= r4 0)))
(signal 'overflow-error (list (list '* r3 n) r4)))
(setq r5 (+ r1 r4))
(when (or (and (< r1 0) (< r4 0) (> r5 0))
(and (> r1 0) (> r4 0) (< r5 0))
(and (> r1 0) (> r4 0) (or (< r5 r1) (< r5 r4)))
(and (< r1 0) (< r4 0) (or (> r5 r1) (> r5 r4))))
(signal 'overflow-error (list (list '+ r1 r4) r5)))
r5))

(let ((S (make-vector n nil)))
(dotimes (i n S)
(aset S i (read-number (format "Number %d: " (1+ i)))))))

(defun reverse-vector (vector)
"Reverse VECTOR."
(vconcat (nreverse (append vector nil))))

(defun tpk (n S)
"From ``Early Development of Programming Languages'', 1977."
(interactive
(let ((n (truncate (read-number "How many numbers? " 11))))
;; Ask for 11 numbers to be read into a sequence S
;; Reverse S
(setq S (reverse-vector S))
;; For each number in S
(dotimes (i n)
(let ((x (aref S i)))
(report-errors (format "Alert for %d is %%s" x)
(let ((result (funcall 'f x)))
;; else
(message "Result for %d is %s" x result))))))

Here’s example output:

(tpk 13 [1152921504606846975 -1152921504606846976
536870911 -536870912
107374183
16384 909 910 -475 -476 0 -1 1])
Result for 1 is 6.0
Result for -1 is -4.0
Result for 0 is 0.0
Alert for -476 is (overflow-error (* 1132880 -476) 534490944)
Result for -475 is -535859353.2055053
Alert for 910 is (overflow-error (* 4140500 910) -527112296)
Result for 909 is 534221703.14962685
Alert for 16384 is (overflow-error (* 268435456 16384) 0)
Alert for 107374183 is (overflow-error (* 5 107374183) -536870909)
Alert for -536870912 is (overflow-error (abs -536870912) -536870912)
Alert for 536870911 is (overflow-error (* 5 536870911) 536870907)
Result for -1152921504606846976 is -7.662477704329444e+054
Result for 1152921504606846976 is 7.662477704329444e+054

Knuth, Donald Ervin, and Luis Trabb Pardo. The early development of programming languages. In Encyclopedia of Computer Science and Technology, Marcel Dekker, New York, 1977, pages 419-96.

Well, the examples for other languages shown at WikiPedia:Trabb Pardo-Knuth algorithm are not comparable to what you’ve written for EmacsLisp above. This much simpler code is comparable. Compare, for example, the Scheme code shown on that Wikipedia page.