The Evaluator's Fundamental Design and the Eval-Apply Cycle

Key Insight

The most fundamental concept in programming is that the evaluator, which assigns meaning to programming language expressions, is itself a program. This perspective merges the technology for managing large-scale computer systems with the methodology for building new computer languages, defining computer science as the discipline dedicated to constructing suitable descriptive languages. The text describes using Lisp as a base language to implement evaluators as Lisp procedures, leveraging Lisp's capability to represent and manipulate symbolic expressions, thereby demonstrating how languages are implemented.

The evaluator for Lisp is implemented as a Lisp program, a design known as a metacircular evaluator. This design is fitting because evaluation is a process, and Lisp is a tool designed for describing processes. This metacircular evaluator encapsulates the environment model of evaluation, which consists of two primary rules: for combinations (compound expressions), subexpressions are evaluated, and the operator's value is applied to the operands' values; for compound procedures, the body is evaluated in a new environment constructed by extending the procedure's environment with a frame binding formal parameters to arguments.

The core evaluation process is an interplay between two critical procedures: `eval` and `apply`. `eval` takes an expression and an environment, classifies the expression's syntactic type, and directs its evaluation. Examples include returning self-evaluating expressions (like numbers), looking up variables, handling quoted text, evaluating conditionals, transforming lambda expressions into procedures, executing sequences of expressions, and passing procedure applications to `apply`. `apply` takes a procedure and arguments, either invoking `apply-primitive-procedure` for primitives or evaluating the body of a compound procedure within an environment extended to bind parameters to the provided arguments.