UP | HOME

Interpreter

Table of Contents

Definition

An interpreter is a function (or program) that takes an AST and returns its value — the result of evaluating the program the AST represents. For PLAI's arithmetic language, the interpreter has type ArithC → number.

The interpreter is naturally recursive: evaluating a compound expression requires evaluating its sub-expressions first, then combining the results.

The Template Pattern

From How to Design Programs (HtDP), cited in PLAI Ch.3: the structure of the recursive function is given by the structure of the recursive datatype. For ArithC with three variants, the template has three cases: 

(define (interp [a : ArithC]) : number
  (type-case ArithC a
    [numC (n)   ...]   ; base case — no recursive call
    [plusC (l r) ... (interp l) ... (interp r) ...]   ; two recursive calls
    [multC (l r) ... (interp l) ... (interp r) ...])) ; two recursive calls

Note in particular the use of natural recursion; l and r are of type ArithC so we can apply interp to each of them. When we ask ourselves what (interp l) gives us (not how it gives it), and ditto for (interp r), we see how we can combine those two results.

Filling in the blanks yields the complete interpreter: 

(define (interp [a : ArithC]) : number
  (type-case ArithC a
    [numC (n) n]
    [plusC (l r) (+ (interp l) (interp r))]
    [multC (l r) (* (interp l) (interp r))]))

Common Mistake

Writing (+ l r) instead of (+ (interp l) (interp r)) — forgetting that l and r are ArithC nodes, not numbers. The Design Recipe template with natural recursion makes this mistake less likely by making the recursive calls explicit in the skeleton.

Tolk Implementation

Tolk uses CLOS dispatch instead of type-case, via defmethod-bind: 

(defmethod-bind interpret ((num n))
    ()
  n)

(defmethod-bind interpret ((arith-binary-op op l r))
    ()
  (funcall op (interpret l) (interpret r)))

The arith-binary-op method handles both plus and mult through the class hierarchy. funcall op ... applies the stored function (#'+ or #'*) to the interpreted sub-values. This is more concise than PLAI's two separate cases.

Advprog Jotter Progression

The 2026-04-20 jotter shows the same interpreter in three styles:

  1. cond with consp / numberp predicates (explicit, verbose)
  2. cond + case / ecase on the operator symbol (cleaner dispatch)
  3. ematch with quasiquote patterns (idiomatic Common Lisp)

All three produce the same results; the progression is pedagogical.

Sources

Related