Skip to main content

From Interpretation to Compilation: Staging, Intermediate Representation

What This Concept Is​

An interpreter walks the source expression every time it runs. A compiler does the walking once, up front, and emits a lower-level program that a simpler runtime (or a CPU) can execute directly.

Between the two extremes live a small family of standard moves:

  • Syntactic analysis separated from execution (SICP §4.1.7). Instead of eval exp env, produce analyze(exp) -> λenv. result. The first phase walks the syntax; the second phase takes an environment and runs. Repeated runs skip the syntactic phase.
  • Intermediate representations (IRs). The AST is one IR; a core language (desugared subset) is another; a control-flow graph or SSA form is another; bytecode is another; machine code is the last. Each is a deliberate choice about what is easy and what is hard at that level.
  • Staging / partial evaluation. When some inputs are known earlier than others, bake the early ones in. (analyze exp) stages the interpreter: what depends only on exp runs now; what needs env runs at call time.
  • Compilation proper (SICP §5.5). Emit machine (or register-machine) code directly from the AST. No more tree-walking at run time.

This concept is SUPPORTING because the module's centre of gravity is writing the interpreter; compilation is the natural next step, not a demand for this module.

Why It Matters Here​

Three reasons to see the gradient now:

  1. Performance intuition. The speedup from tree-walking to bytecode is often 10-100×; from bytecode to native is another 2-10×. Knowing which level you are at explains the cost.
  2. Language design. Many real systems sit at a middle rung: CPython compiles to bytecode and interprets that; the JVM interprets bytecode and JIT-compiles hot paths. Knowing the rungs is how you read architecture docs of any mature runtime.
  3. Engineering leverage. Almost every production interpreter eventually moves toward "compile once, run many" -- template engines pre-compile templates; SQL engines build plans; regex libraries compile patterns. The staging move is universal.

Concrete Example​

SICP §4.1.7 contrasts the straightforward evaluator with an analyzed one:

;; straightforward
(define (eval exp env)
  (cond ((if? exp) (eval-if exp env)) ...))
(define (eval-if exp env)
  (if (eval (if-test exp) env)
      (eval (if-conseq exp) env)
      (eval (if-alt exp) env)))

;; analyzed / staged
(define (analyze exp)
  (cond ((if? exp) (analyze-if exp)) ...))
(define (analyze-if exp)
  (let ((pproc (analyze (if-test exp)))
        (cproc (analyze (if-conseq exp)))
        (aproc (analyze (if-alt exp))))
    (lambda (env)
      (if (pproc env) (cproc env) (aproc env)))))

Now (run prog) is ((analyze prog) env). Each time you re-run a program you pay only for the closures returned by analyze, not for re-dispatching on syntax. That single change makes SICP's evaluator many times faster for loops and recursive functions.

For a concrete compiler step, the same (+ 1 (* 2 x)) might progress through four IRs:

  • Source: (+ 1 (* 2 x))
  • AST: node(+, lit(1), node(*, lit(2), var(x)))
  • Three-address IR: t1 = 2 * x; t2 = 1 + t1;
  • Register machine / bytecode: LOAD_CONST 2; LOAD x; MUL; LOAD_CONST 1; ADD
  • x86: mov eax, 2; imul eax, [x]; add eax, 1

Each step drops a responsibility: the AST has lost the parentheses, the IR has lost the nesting, the bytecode has lost the names, the x86 has lost the platform.

Common Confusion / Misconception​

  1. "Compilation = fast, interpretation = slow." A well-engineered interpreter beats a poorly-engineered compiler. V8 interprets first, then JITs. Compilation buys specific things (elimination of dispatch, better codegen); it is not magic.
  2. "IR is one thing." Real compilers use several IRs back-to-back, each chosen for one optimization. LLVM alone goes through multiple SSA passes.
  3. "Once compiled, no more eval." Most real languages keep an eval-like fallback (eval in Python/JS/Lisp, reflection, plugins). The boundary is usually gradient, not binary.
  4. Confusing staging with caching. Caching memoizes results; staging commits to a cheaper residual program. The staged program still runs -- it just does less work.

How To Use It​

When optimizing an interpreter-shaped system:

  1. Profile first. Most eval-heavy systems spend their time in hot paths you can cache or pre-compile.
  2. Identify the earliest input. Anything that depends only on that can be lifted out of the inner loop. This is exactly SICP §4.1.7.
  3. If you still need speed, introduce a simple IR (e.g. bytecode) and move dispatch from strings to small ints.
  4. Consider a compile-to-host-closure strategy (like the analyzed evaluator): each source node becomes a Python/Scheme closure that can be invoked directly at run time.

When reading docs for a new language runtime, ask: what's the IR? Is there a bytecode? Is there a JIT? The answers tell you most of its performance story.

Check Yourself​

  1. What do you gain by running analyze once and eval many times?
  2. Name three common intermediate representations in a production compiler.
  3. Why is "separating syntactic analysis from execution" a form of partial evaluation?

Mini Drill or Application​

Take the evaluator from Concept 11. Add a one-pass analyze that returns a Python callable taking only env, mirroring SICP §4.1.7. Benchmark both versions on (fact 10) in a tight loop (say, 100 000 runs). Report the speedup. Then sketch -- without implementing -- what bytecode for (fact 10) might look like and where the next speedup would come from.

Read This Only If Stuck​