UP | HOME

Summary: PLAI Ch.3 — A First Look at Interpretation

Table of Contents

Key Claims

  • An interpreter is a function from AST to value; for arithmetic the value type is number.
  • The interpreter is naturally recursive over the recursive structure of the AST.
  • The template method (from HtDP) gives the structure of the interpreter for free: one case per variant, with recursive calls on sub-trees.
  • Semantics is not obvious: the meaning of + in a new language is whatever meaning the implementer gives it. Naively borrowing from the host language (Racket's +) adopts Racket's semantics by default.
  • Division is deliberately excluded because it introduces the question of legality (1/0), which is deferred.
  • The chapter ends by noting that the core language is minimal; extensions like subtraction and negation can be added without touching the interpreter (desugaring — covered in Ch.4).

Summary

Chapter 3 builds the first complete interpreter for the ArithC language introduced in Ch.2. The language has three forms: numbers, addition, multiplication.

The 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))]))

The template approach: sketch the structure (one branch per variant, recursive calls where sub-trees appear) then fill in the blanks. A naive first attempt writes (+ l r) instead of (+ (interp l) (interp r)), forgetting that l and r are ArithC nodes, not numbers.

Semantics

The chapter introduces the concept of semantics: the mapping from syntax to meaning. Writing (+ (interp l) (interp r)) means the language inherits Racket's numeric +. This includes Racket's handling of integer overflow, floating-point, etc. Different choices would yield different semantics (e.g. modular arithmetic, fixed-width integers).

The which-of-these-is-the-same question: 1 + 2 in two different languages may have the same syntax but different meanings. Semantics is what distinguishes them.

Tolk correspondence

Tolk's arithmetic interpreter (tolk/arith) directly implements this pattern using CLOS dispatch via defmethod-bind instead of type-case: 

(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 via inheritance; the stored op function slot holds #'+ or #'* respectively. This is a more elegant solution than type-case for this particular case because inheritance does the dispatch automatically.

Differences / Notes

  • PLAI's interp returns a bare number. Krishnamurthi notes this will be revisited later (a richer value type is eventually needed). Tolk already uses a structured ast-node value type from the start.

Related