We now explain a number of points a bout these deﬁnitions.
5
1. apply itself forms an expression representing the value of the function
applied to the arguments, and puts the work of evaluating this expression onto
a function eval. It uses appq to put quotes around each of the arguments, so
that eval will regard them as standing for themselves.
2. eval[e; a] has two arguments, an expression e to b e evaluated, and a list
of pairs a. The ﬁrst item of each pair is an atomic symbol, and the second is
the expression fo r which the symbol stands.
3. If the expression to be evaluated is atomic, eva l evaluates whatever is
paired with it ﬁrst on the list a.
4. If e is not atomic but car[e] is atomic, then the expression has one of the
forms (QUOT E, e) or (AT OM, e) or (EQ, e
1
, e
2
) or (CON D, (p
1
, e
1
), · · · , (p
n
, e
n
)),
or (CAR, e) or (CDR, e) or (CONS, e
1
, e
2
) or (f, e
1
, · · · , e
n
) where f is an
atomic symbol.
In the case (QU OT E, e) the expression e, itself, is taken. In the case of
(AT OM, e) or (CAR, e) or (CDR, e) the expression e is evaluated and the
appropriate function taken. In the case of (EQ, e
1
, e
2
) or (CONS, e
1
, e
2
) two
expressions have to be eva luated. In the case of (CON D, (p
1
, e
1
), · · · (p
n
, e
n
))
the p’s have to be evaluated in order until a true p is found, and then the
corresponding e must be evaluated. This is accomplished by evcon. Finally, in
the case o f (f, e
1
, · · · , e
n
) we evaluate the expression that results from replacing
f in this expression by whatever it is paired with in the list a.
5. The evaluation of ((LABEL, f, E), e
1
, · · · , e
n
) is accomplished by eval-
uating (E, e
1
, · · · , e
n
) with the pairing (f, (LABEL, f, E)) put on the front of
the previous list a of pairs.
6. Finally, the evaluation of ((LAMBDA, (x
1
, · · · , x
n
), E), e
1
, · · · e
n
) is ac-
complished by evaluating E with the list of pairs ((x
1
, e
1
), · · · , ((x
n
, e
n
)) put
on the front of the previous list a.
The list a could be eliminated, and LAMBDA and LABEL expressions
evaluated by substituting the arguments for the variables in the expressions
E. Unfortunately, diﬃculties involving collisions of bound variables arise, but
they are avoided by using the list a.
5
1995: This version isn’t quite right. A comparison of this and other versions of eval
including what was actually implemented (and debugged) is given in “The Inﬂuence of the
Designer on the Design” by Herbert Stoyan and included in Artiﬁcial Intelligence and Math-
ematical Theory of Computation: Papers in Honor of John McCarthy, Vladimir Lifschitz
(ed.), Academic Press, 1991
18