TrabbPardoKnuth

Last edit

Summary: Simpler version that corresponds to the other-language examples cited.

Added:

> [new:DrewAdams:2013-01-22 03:49 UTC]
> 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.
> (defun read-nums (n)
> (and (not (zerop n)) (cons (read-number "Number: ") (read-nums (1- n)))))
> (defun f (x) (+ (sqrt (abs x)) (* 5 x x x)))
> (dolist (z (reverse (read-nums 11)))
> (let ((res (funcall #'f z)))
> (message "Result for %3s is %s" z (if (> res 400) "TOO LARGE" res))))
> It all depends on what you are trying to show (which is not clear). If the purpose is "''to show the variation in expression of different programming languages''" then this simple example can be compared to those cited for other languages. -- DrewAdams


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))
  
  (defun read-number-vector (n)
    "Read N numbers from user."
    (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
       (list n (read-number-vector n))))
    ;; 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.

  (defun read-nums (n)
    (and (not (zerop n))  (cons (read-number "Number: ") (read-nums (1- n)))))
  (defun f (x)  (+ (sqrt (abs x)) (* 5 x x x)))
  (dolist (z  (reverse (read-nums 11)))
    (let ((res  (funcall #'f z)))
      (message "Result for %3s is %s" z (if (> res 400) "TOO LARGE" res))))

It all depends on what you are trying to show (which is not clear). If the purpose is “to show the variation in expression of different programming languages” then this simple example can be compared to those cited for other languages. – DrewAdams


CategoryCode