Skip to main content

What an Interpreter Is: eval and apply

What This Concept Is​

An interpreter for a language is a program that takes a piece of source and runs it directly, producing the value that source denotes. SICP's central claim in Chapter 4 is that the heart of this program is a pair of mutually recursive procedures:

  • eval(exp, env) -- given an expression and an environment, return the value.
  • apply(proc, args) -- given a procedure value and a list of already-evaluated argument values, return the result of running the procedure on those arguments.

Everything in the language falls out of those two. Constants evaluate to themselves; variable lookup asks the environment; if dispatches on a test expression; lambda builds a procedure value that pairs the body with the current environment; a combination (f a b) recursively evals f, a, b and then calls apply on the resulting procedure and arguments.

SICP calls the evaluator metacircular when the host language is the same as the implemented language: Scheme writing Scheme, interpreting itself. Norvig's lis.py is a tiny Python analogue. Nystrom's Crafting Interpreters builds a bigger example in Java and C.

Why It Matters Here​

This concept is the high point of the module, and arguably of SICP:

  • Every abstraction move from Clusters 1-3 (procedural, data, HOFs, closures, tail calls, environments) finally meets its honest shadow here. A closure is represented by apply as a pair; an environment is the argument eval passes around; tail position is a decision eval makes about which expression to recurse into.
  • It is the most concrete possible proof that programs are data. The same '(+ 1 2) that prints on your screen is a list the evaluator inspects and dispatches on.
  • It is the direct stepping stone to Concept 11 (writing one) and Concept 12 (compiling instead of interpreting).

An engineer who has built a small interpreter once is calibrated for life on questions like "what is the cost of a function call," "what does garbage collection do," "why is eval slow," "what is a debugger doing when it sets a breakpoint."

Concrete Example​

A Scheme-ish pseudocode of the core (SICP §4.1.1, simplified):

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) (eval-sequence (begin-actions exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else (error "unknown expression type"))))

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else (error "unknown procedure type"))))

Read slowly. Every line is either a syntactic case or a base case (primitives, environments). Notice two things:

  1. eval never runs imperative machinery -- it just inspects the shape of exp and recurses.
  2. apply contains the one place where environments are extended: the body of a compound procedure is run in a new frame that binds its parameters to the arguments -- and that new frame's parent is the procedure's defining environment (the closure), not the caller's. Lexical scope, made mechanical.

Common Confusion / Misconception​

  1. "eval runs the code." Not quite. eval decides what to do next based on the syntax of exp. The "running" happens when primitive applications bottom out in host-language operations (+, print).
  2. "The evaluator has variables." It has representations of environments. It does not use Scheme's own variables to hold user variables. That separation is what lets one running Scheme host many independent interpreter worlds.
  3. "Eval and apply are one function." They are mutually recursive for a reason: eval interprets syntax; apply interprets a procedure value on a list of already-evaluated values. Keeping them separate makes both trivially small.
  4. Confusing "metacircular" with "bootstrapped." Metacircular means using the same language; bootstrapped means a compiler can compile itself. They are independent.

How To Use It​

Treat the eval/apply skeleton as a template for every dispatcher-shaped piece of code:

  • Any time you have "a piece of structured data that must be walked," you are writing an eval.
  • Any time the walk reaches a callable thing with arguments, you are writing an apply.

This shape shows up in:

  • query evaluators (SQL planners, GraphQL resolvers)
  • rule engines
  • config-DSL evaluators (terraform, jq)
  • shell interpreters
  • templating engines
  • regex engines

All of them are eval/apply in disguise.

Check Yourself​

  1. Why is eval mutually recursive with apply rather than one function?
  2. Why must apply's new frame parent the procedure's defining environment, not the calling one?
  3. Give two pieces of software you use every week that are basically eval/apply over some small DSL.

Mini Drill or Application​

On paper, trace eval and apply for this program:

(define (square x) (* x x))
(square 3)

Explicitly name the environments, frames, and intermediate values. Then repeat for:

(define (make-adder n) (lambda (x) (+ x n)))
((make-adder 5) 10)

Note carefully which environment becomes the parent of the lambda's frame when the inner lambda is finally applied.

Read This Only If Stuck​