Tuesday, March 1, 2011

Fifty Years Ago

*
*      EVALQ   A SUCCESSOR TO THE APPLY OPERATOR, THE GRAND NEW
*              (AS OF 1 MARCH 1961) THE EVALQUOTE OPERATOR.
*
A universal Turing machine is an abstract ‘machine’ that can simulate any other Turing machine.
A universal function is the mathematical analogue of a universal Turing machine. A universal function is a computable function that can be parameterized to compute any other computable function. The fact that universal functions exist (by the utm theorem) means that one can write an interpreter. (Alternatively, an interpreter for a Turing complete language can be easily shown to be a universal function.)
In Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (there is no Part II), McCarthy states:
There is an S-function apply with the property that if f is an S-expression for an S-function f′ and args is a list of arguments of the form (arg1,...,argn), where arg1,...,argn are arbitrary S-expressions, then apply[f;args] and f′[arg1,...,argn] are defined for the same values of arg1,...,argn, and are equal when defined.
This is not a vacuous statement. It says (more precisely), suppose there is a mathematical partial function f′ which is computable for some arguments. Then, there is a program (called f), which will compute exactly the same answers as the abstract mathematical partial function f′. Furthermore, the LISP program apply, when given the program f and some particular arguments, computes the exact same thing as if the function f′ were directly called on the arguments. In other words, LISP I's apply operator is universal.

By March 1 1961 it was realized that although apply is universal, it is not necessarily primitive. The user version of apply is trivially defined as:
(defun quote-args (arglist)
  (map 'list (lambda (arg) (cons 'quote arg)) arglist))

(defun lisp1-apply (f arglist)
  (eval (cons f (quote-args arglist))))
This is the origin of the evalquote operator.

In February 1961, Dan Edwards recoded OVERLORD (the original batch-mode ‘REPL’) to use EVALQUOTE rather than APPLY for top-level execution.
EVALQUOTE — Reads pairs of LISP statements (atoms or atomic symbols) and considers the first as a function and the second as a list of quoted arguments for the function. Pairs are read in until a card with the atomic symbol STOP is encountered or a READ error is found. The pairs are then evaluated one at a time and the results printed.
— Lisp 1.5 Programmer's Manual
Here is a LISP program from about this time:
DEFINE ((
(MEMBER (LAMBDA (A X) (COND ((NULL X) F)
     ((EQ A (CAR X)) T) (T (MEMBER A (CDR X))) )))
(UNION (LAMBDA (X Y) (COND ((NULL X) Y) ((MEMBER
     (CAR X) Y) (UNION (CDR X) Y)) (T (CONS (CAR X)
     (UNION (CDR X) Y))) )))
(INTERSECTION (LAMBDA (X Y) (COND ((NULL X) NIL)
     ((MEMBER (CAR X) Y) (CONS (CAR X) (INTERSECTION
     (CDR X) Y))) (T (INTERSECTION (CDR X) Y)) )))
))
INTERSECTION ((A1 A2 A3) (A1 A3 A5))
UNION ((X Y Z) (U V W X))
The commas have disappeared, the main loop now uses the two-argument EVALQUOTE rather than the three-argument APPLY, and some rudimentary indentation is present.

1 comment:

John Cowan said...

"Snow is white" is true if and only if snow is white. —Alfred Tarski