3.2.1 · The environment model of evaluation

Evaluation follows expressions while lookup follows frame links.

Run a lexical lesson evaluator and frame operations so variable lookup, procedure creation, application, definition, and assignment appear in one model.

Guiding question

Which environment is used when an expression creates a procedure, and which environment is used when that procedure is later applied?

Represent an environment as an ordered list of frames
Search the nearest frame first during variable lookup
Capture the creation environment inside a compound procedure
Extend that captured environment with a fresh parameter frame on application
Distinguish definition in the first frame from assignment to an existing binding

model-eval handles the listed forms: self-evaluating values, variables, quote, lambda, and application. Evaluating lambda creates compound-procedure data containing parameters, body, and the current environment. Applying that value evaluates the body in a new parameter frame linked to the captured environment, so the inner y call can still find the outer x.

The second program makes frame mutation explicit. Lookup finds local x before global x. set-variable-value! changes the already existing local record, while define-variable! adds y to the first frame. Neither operation changes global x. This explanatory evaluator models the listed forms directly.

SICP code2,593 of 1,048,576 UTF-8 bytes

(begin
  (define (make-frame variables values)
    (if (null? variables)
        '()
        (cons (cons (car variables) (car values))
              (make-frame (cdr variables) (cdr values)))))
  (define (extend-environment variables values base)
    (cons (make-frame variables values) base))
  (define (lookup-variable-value variable environment)
    (if (null? environment)
        'unbound-variable
        (let ((record (assoc variable (car environment))))
          (if record
              (cdr record)
              (lookup-variable-value variable (cdr environment))))))
  (define (sum-values values)
    (if (null? values)
        0
        (+ (car values) (sum-values (cdr values)))))
  (define (product-values values)
    (if (null? values)
        1
        (* (car values) (product-values (cdr values)))))
  (define (apply-primitive name arguments)
    (cond ((eq? name 'primitive-plus) (sum-values arguments))
          ((eq? name 'primitive-times) (product-values arguments))
          (else 'unknown-primitive)))
  (define (eval-operands expressions environment)
    (if (null? expressions)
        '()
        (cons (model-eval (car expressions) environment)
              (eval-operands (cdr expressions) environment))))
  (define (model-apply procedure arguments)
    (if (and (pair? procedure)
             (eq? (car procedure) 'compound))
        (model-eval
          (caddr procedure)
          (extend-environment
            (cadr procedure)
            arguments
            (cadddr procedure)))
        (apply-primitive procedure arguments)))
  (define (model-eval expression environment)
    (cond ((or (number? expression)
               (string? expression)
               (boolean? expression))
           expression)
          ((symbol? expression)
           (lookup-variable-value expression environment))
          ((eq? (car expression) 'quote)
           (cadr expression))
          ((eq? (car expression) 'lambda)
           (list 'compound
                 (cadr expression)
                 (caddr expression)
                 environment))
          (else
           (model-apply
             (model-eval (car expression) environment)
             (eval-operands (cdr expression) environment)))))
  (define global-environment
    (list (list (cons '+ 'primitive-plus)
                (cons '* 'primitive-times))))
  (list
    (model-eval
      '((lambda (x)
          ((lambda (y) (+ x y)) 4))
        3)
      global-environment)
    (model-eval
      '(((lambda (x)
           (lambda (y) (+ x y)))
         5)
        8)
      global-environment)))

(begin
  (define (make-frame variables values)
    (if (null? variables)
        '()
        (cons (cons (car variables) (car values))
              (make-frame (cdr variables) (cdr values)))))
  (define (extend-environment variables values base)
    (cons (make-frame variables values) base))
  (define (lookup-variable-value variable environment)
    (if (null? environment)
        'unbound-variable
        (let ((record (assoc variable (car environment))))
          (if record
              (cdr record)
              (lookup-variable-value variable (cdr environment))))))
  (define (sum-values values)
    (if (null? values)
        0
        (+ (car values) (sum-values (cdr values)))))
  (define (product-values values)
    (if (null? values)
        1
        (* (car values) (product-values (cdr values)))))
  (define (apply-primitive name arguments)
    (cond ((eq? name 'primitive-plus) (sum-values arguments))
          ((eq? name 'primitive-times) (product-values arguments))
          (else 'unknown-primitive)))
  (define (eval-operands expressions environment)
    (if (null? expressions)
        '()
        (cons (model-eval (car expressions) environment)
              (eval-operands (cdr expressions) environment))))
  (define (model-apply procedure arguments)
    (if (and (pair? procedure)
             (eq? (car procedure) 'compound))
        (model-eval
          (caddr procedure)
          (extend-environment
            (cadr procedure)
            arguments
            (cadddr procedure)))
        (apply-primitive procedure arguments)))
  (define (model-eval expression environment)
    (cond ((or (number? expression)
               (string? expression)
               (boolean? expression))
           expression)
          ((symbol? expression)
           (lookup-variable-value expression environment))
          ((eq? (car expression) 'quote)
           (cadr expression))
          ((eq? (car expression) 'lambda)
           (list 'compound
                 (cadr expression)
                 (caddr expression)
                 environment))
          (else
           (model-apply
             (model-eval (car expression) environment)
             (eval-operands (cdr expression) environment)))))
  (define global-environment
    (list (list (cons '+ 'primitive-plus)
                (cons '* 'primitive-times))))
  (list
    (model-eval
      '((lambda (x)
          ((lambda (y) (+ x y)) 4))
        3)
      global-environment)
    (model-eval
      '(((lambda (x)
           (lambda (y) (+ x y)))
         5)
        8)
      global-environment)))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The lesson evaluator returns (7 13). The frame mutation program returns (3 4 7 10).

Trace focus

In the evaluator, separate lambda evaluation from procedure application and follow the parent environment captured by each compound value. In the frame program, find the nearest assoc hit, the set-cdr! that changes local x, and the set-car! that adds y to only the first frame.

Try it yourself

Change the program and compare the result.

Add if to model-eval, then evaluate a closure whose body chooses between a local parameter and a captured outer value. Also define a global y and confirm that a local definition shadows rather than mutates it.

Show hint

Evaluate only the selected if branch. A definition always targets the first frame of the supplied environment.

Complete this lesson

0 of 21 lessons complete in this chapter0%