apply[fn;x;a] =
     [atom[fn] → [eq[fn;CAR] → caar[x];
                  eq[fn;CDR] → cdar[x];
                  eq[fn;CONS] → cons[car[x];cadr[x]];
                  eq[fn;ATOM] → atom[car[x]];
                  eq[fn;EQ] → eq[car[x];cadr[x]];
                  T → apply[eval[fn;a];x;a]];
     eq[car[fn];LAMBDA] → eval[caddr[fn]; pairlis[cadr[fn];x;a]];
     eq[car[fn];LABEL] → apply[caddr[fn];x;cons[cons[cadr[fn];caddr[fn]];a]]]

2 of 20

apply

John McCarthy, 1960

M-expression notation, as written in the LISP 1.5 Programmer's Manual

Excerpt. The complete work is at the source.

In "Recursive Functions of Symbolic Expressions and Their Computation by Machine" McCarthy defined a handful of primitives (car, cdr, cons, atom, eq) and then did something no language paper had done: he wrote the interpreter for the language in the language itself. Two mutually recursive functions, eval and apply, take an expression and an environment of bindings and produce its value.

The brackets and arrows are McCarthy's M-expressions, the notation he meant programmers to use before everyone decided to write the S-expression data form directly. Because programs are data here, a program can read, build, and run other programs, which is the idea behind every interpreter, macro system, and dynamic language since. Alan Kay called this half page the Maxwell's equations of software. Steve Russell soon hand-translated eval into machine code, and the first Lisp interpreter existed.

Source: www-formal.stanford.edu
Rights: Excerpt from Communications of the ACM 3(4), ACM 1960, and the LISP 1.5 Programmer's Manual; reproduced for commentary