* * 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-functionThis is not a vacuous statement. It says (more precisely), suppose there is a mathematical partial functionapplywith the property that iffis an S-expression for an S-functionf′andargsis a list of arguments of the form (arg_{1},...,arg_{n}), wherearg_{1},...,arg_{n}are arbitrary S-expressions, thenapply[f;args] andf′[arg_{1},...,arg_{n}] are defined for the same values ofarg_{1},...,arg_{n}, and are equal when defined.

*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.
"Snow is white" is true if and only if snow is white. —Alfred Tarski

ReplyDelete