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 23

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 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 Lisp program can read, build, and run other programs, and the language can be defined in terms of itself. Alan Kay called this half page the Maxwell's equations of software.

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