In AI Memo 8 of the MIT Research Laboratory of Electronics (March 4, 1959), John McCarthy gives a definition of the universal
S-function apply
:
apply is defined by apply[f;args]=eval[combine[f;args]] eval is defined by eval[e]=[ first[e]=NULL→[null[eval[first[rest[e]]]]→T;1→F] first[e]=ATOM→[atom[eval[first[rest[e]]]]→T;1→F] first[e]=EQ→[eval[first[rest[e]]]=eval[first[rest[rest[e]]]]→T; 1→F] first[e]=QUOTE→first[rest[e]]; first[e]=FIRST→first[eval[first[rest[e]]]]; first[e]=REST→rest[eval[first[rest[e]]]; first[e]=COMBINE→combine[eval[first[rest[e]]];eval[first[rest[rest [e]]]]]; first[e]=COND→evcon[rest[e]] first[first[e]]=LAMBDA→evlam[first[rest[first[e]]];first[rest[rest [first[e]]]];rest[e]]; first[first[e]]=LABELS→eval[combine[subst[first[e];first[rest [first[e]]];first[rest[rest[first[e]]]]];rest[e]]]] where: evcon[c]=[eval[first[first[c]]]=1→eval[first[rest[first[c]]]]; 1→evcon[rest[c]]] and evlam[vars;exp;args]=[null[vars]→eval[exp];1→evlam[ rest[vars];subst[first[vars];first[args];exp];rest[args]]]McCarthy asserts that “if f is an S-expression for an S-function φ and args is a list of the form (arg1, …, argn) where arg1, ---, argn are arbitrary S-expressions then
apply[f,args]
and φ(arg1, …, argn) are defined for the same values of arg1, … argn
and are equal when defined.”
I find it hard to puzzle through these equations, so I've transcribed them into S-expressions to get the following:
;;; Hey Emacs, this is -*- Lisp -*- (in-package "CL-USER") ;; Don't clobber the system definitions. (shadow "APPLY") (shadow "EVAL") (defun apply (f args) (eval (combine f args))) (defun eval (e) (cond ((eq (first e) 'NULL) (cond ((null (eval (first (rest e)))) t) (1 nil))) ((eq (first e) 'ATOM) (cond ((atom (eval (first (rest e)))) t) (1 nil))) ((eq (first e) 'EQ) (cond ((eq (eval (first (rest e))) (eval (first (rest (rest e))))) t) (1 nil))) ((eq (first e) 'QUOTE) (first (rest e))) ((eq (first e) 'FIRST) (first (eval (first (rest e))))) ((eq (first e) 'REST) (rest (eval (first (rest e))))) ((eq (first e) 'COMBINE) (combine (eval (first (rest e))) (eval (first (rest (rest e)))))) ((eq (first e) 'COND) (evcon (rest e))) ((eq (first (first e)) 'LAMBDA) (evlam (first (rest (first e))) (first (rest (rest (first e)))) (rest e))) ((eq (first (first e)) 'LABELS) (eval (combine (subst (first e) (first (rest (first e))) (first (rest (rest (first e))))) (rest e)))))) (defun evcon (c) (cond ((eval (first (first c))) (eval (first (rest (first c))))) (1 (evcon (rest c))))) (defun evlam (vars exp args) (cond ((null vars) (eval exp)) (1 (evlam (rest vars) (subst (first args) (first vars) exp) (rest args)))))We just have to add a definition for
combine
as a synonym for cons
and this should
run:* (eval '(eq (first (combine 'a 'b) (combine 'a 'c)))) T
As Steve “Slug” Russell observed, eval
is an interpreter for Lisp. This version of eval
uses an interesting evaluation strategy. If you look carefully, you'll see that there is no conditional clause for handling variables. Instead, when a lambda expression appears as the operator in a combination, the body of the lambda expression is walked and the bound variables are substituted with the expressions (not the values!) that represent the arguments. This is directly inspired by β-reduction from lambda calculus.
This is buggy, as McCarthy soon discovered. In the errata published one week later, McCarthy points out that the substitution process doesn't respect quoting, as we can see here:
* (eval '((lambda (name) (combine 'your (combine 'name (combine 'is (combine name nil))))) 'john)) (YOUR 'JOHN IS JOHN)With a little thought, we can easily generate other name collisions. Notice, for example, that the substitution will happily substitute within the bound variable list of nested lambdas.
Substitution like this is inefficient. The body of the lambda is walked once for each bound variable to be substituted, then finally walked again to evaluate it. Later versions of Lisp will save the bound variables in an environment structure and substitute them incrementally during a single evaluation pass of the lambda body.