Skip to main content

Evaluation Models Workshop

Trace real programs -- on paper or in a doc -- through the substitution model and the environment model. Spot the exact point where the two disagree. Do this workshop before the interpreter clinic; it directly sets up the mental model you will implement there.

Retrieval Prompts​

Answer closed-book:

  1. State the substitution rule for a procedure application in one sentence.
  2. State the environment-model rule for a procedure application in one sentence.
  3. When do the two models disagree?
  4. In the environment model, what does a procedure value actually contain?

Part A -- Pure Programs, Both Models Agree​

Trace each program in the substitution model, step by step, until you reach a value. Then trace the same program in the environment model, drawing every frame and its parent pointer.

Program A1: Square of Sum​

(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y)))
(sum-of-squares (+ 1 2) (* 3 4))
  • Substitution trace: show every reduction step (applicative order).
  • Environment trace: draw GLOBAL with square and sum-of-squares bound, then a frame for the sum-of-squares call, then the two nested square frames.

Program A2: Tail Recursion​

(define (iter count acc)
  (if (= count 0) acc (iter (- count 1) (* count acc))))
(iter 4 1)
  • Substitution: each reduction should reuse one slot, not grow.
  • Environment: frames should not stack -- the tail call reuses the frame.

Part B -- Closures, Where Substitution Starts To Strain​

Program B1: make-adder​

(define (make-adder n) (lambda (x) (+ x n)))
(define a5 (make-adder 5))
(define a7 (make-adder 7))
(+ (a5 10) (a7 10))
  • In the environment model: draw GLOBAL with make-adder, a5, a7 bound. Each a5 / a7 points to a frame that holds n. Follow the chain for (a5 10) and confirm n resolves to 5.
  • In the substitution model: substitute aggressively. Notice that to explain a5, you must treat it as the expression (lambda (x) (+ x 5)). You can limp through because there is no mutation.

Part C -- Mutation, Where Substitution Breaks​

Program C1: Counter​

(define (make-counter)
  (let ((n 0))
    (lambda () (set! n (+ n 1)) n)))
(define c1 (make-counter))
(define c2 (make-counter))
(c1) (c1) (c2) (c1)
  • Environment trace: draw all frames. Confirm c1 and c2 point at different frames; mutations to one do not affect the other.
  • Substitution: attempt a trace. You will fail. Write a one-sentence description of where you got stuck.

Program C2: Shared State​

(define n 0)
(define (tick) (set! n (+ n 1)) n)
(tick) (tick) (tick)
  • Environment trace: one frame, three mutations. Easy.
  • Substitution: attempt. Fail. Articulate why in one sentence.

Part D -- Applicative vs Normal Order​

(define (try p q) (if (= p 0) 1 q))
(try 0 (/ 1 0))
  • Applicative order: show what happens. (It explodes.)
  • Normal order: show what happens. (It returns 1.)
  • Rewrite try to take two thunks ((lambda () 1), (lambda () (/ 1 0))) so that applicative order is safe. Trace once more.

Part E -- Quiz-Prep Trace​

Trace this program fully in the environment model. At each step, note which procedure is in tail position and which is not.

(define (fact n)
  (if (= n 0) 1 (* n (fact (- n 1)))))
(define (fact-iter n acc)
  (if (= n 0) acc (fact-iter (- n 1) (* n acc))))
(fact 3)
(fact-iter 3 1)

Predict which of the two runs in constant space. Confirm by looking at your drawn frames.

Evidence Check​

This workshop is complete only if:

  • For A1 and A2 you have two traces each, one in each model.
  • For B1 your environment diagram shows two separate frames, one per make-adder call.
  • For C1 and C2 you have written, in plain English, why substitution fails.
  • For D you have the two contrasting traces and the thunked rewrite.
  • For E you have identified the tail-position call in fact-iter and confirmed that the environment model predicts constant space.