(DEFINE (EVAL EXP ENV PROCEDURES)
(COND ((ATOM EXP)
(COND ((EQ EXP 'NIL) 'NIL)
((EQ EXP 'T) 'T)
((NUMBERP EXP) EXP)
(T (VALUE EXP ENV))))
((EQ (CAR EXP) 'QUOTE)
(CADR EXP))
((EQ (CAR EXP) 'COND)
(EVCOND (CDR EXP) ENV PROCEDURES))
(T (APPLY (VALUE (CAR EXP) PROCEDURES)
(EVLIS (CDR EXP) ENV PROCEDURES)
PROCEDURES))))
(DEFINE (APPLY FUN ARGS PROCEDURES)
(COND ((PRIMOP FUN) (PRIMOP-APPLY FUN ARGS))
(T (EVAL (CADR FUN)
(BIND (CAR FUN) ARGS '())
PROCEDURES))))
(DEFINE (EVCOND CLAUSES ENV PROCEDURES)
(COND ((NULL CLAUSES) (ERROR))
((EVAL (CAAR CLAUSES) ENV PROCEDURES)
(EVAL (CADAR CLAUSES) ENV PROCEDURES))
(T (EVCOND (CDR CLAUSES) ENV PROCEDURES))))
(DEFINE (EVLIS ARGLIST ENV PROCEDURES)
(COND ((NULL ARGLIST) '())
(T (CONS (EVAL (CAR ARGLIST) ENV PROCEDURES)
(EVLIS (CDR ARGLIST) ENV PROCEDURES)))))
Figure 2 Evaluator for a Recursion Equations Interpreter
The evaluator proper (see Figure 2) is divided into two conceptual components: EVAL and APPLY. EVAL classifies expressions, and directs their evaluation. Simple expressions (such as constants and variables) can be evaluated directly. For the complex case of procedure invocations (technically called "combinations"), EVAL looks up the procedure definition, recursively evaluates the arguments (using ENLIS), and then calls APPLY. APPLY classifies procedures and directs their application. Simple procedures (primitive operators) are applied directly. For the complex case of user-defined procedures, APPLY uses BIND to build an environment, a kind of symbol table, associating the formal parameters from the procedure definition with the actual argument values provided by EVAL. The body of the procedure definition is then passed to EVAL, along with the environment just constructed, which is used to determine the values of
