4.1.5 · Data structures for the evaluator

Frames, procedures, booleans, and argument lists are evaluator data.

Construct the records that connect evaluator control, from mutable frames and lexical environment chains to tagged procedures and argument lists.

Guiding question

What information must the evaluator retain so a procedure can be applied later in the environment where it was created?

Represent one frame as variable-value records behind a private marker
Search an ordered environment chain from the nearest frame outward
Store parameters, body, and creation environment in a compound procedure record
Tag host primitive implementations separately from compound procedures
Treat only #f as false in the guest truth predicate
Preserve operand order while constructing an argument-value list

The first program constructs a global frame containing x = 10 and a local frame containing x = 3 and y = 4. Lookup finds the nearest x without changing the global record. A compound-procedure record then stores one parameter z, one body expression, and the complete local environment chain, so later application can extend the same lexical context.

The second program tags a host + procedure as primitive data and applies it after unwrapping its implementation. list-of-values records left-to-right operand evaluation with explicit probes. The guest truth predicate returns false for #f, so zero and a quoted symbol both count as true. Together these records define the lesson evaluator protocol for frames, procedures, arguments, and truth tests.

SICP code1,217 of 1,048,576 UTF-8 bytes

(begin
  (define (pair-bindings variables values)
    (if (null? variables)
        '()
        (cons (cons (car variables) (car values))
              (pair-bindings (cdr variables) (cdr values)))))
  (define (make-frame variables values)
    (cons '*frame* (pair-bindings variables values)))
  (define (extend-environment variables values base)
    (cons (make-frame variables values) base))
  (define (lookup variable environment)
    (if (null? environment)
        'unbound
        (let ((record (assoc variable (cdr (car environment)))))
          (if record
              (cdr record)
              (lookup variable (cdr environment))))))
  (define (make-procedure parameters body environment)
    (list 'compound parameters body environment))
  (define global-environment
    (list (make-frame '(x) '(10))))
  (define local-environment
    (extend-environment '(x y) '(3 4) global-environment))
  (define procedure
    (make-procedure '(z) '((+ x y z)) local-environment))
  (list (lookup 'x local-environment)
        (lookup 'x global-environment)
        (lookup 'y local-environment)
        (car procedure)
        (cadr procedure)
        (length (caddr procedure))
        (length (cadddr procedure))))

(begin
  (define (pair-bindings variables values)
    (if (null? variables)
        '()
        (cons (cons (car variables) (car values))
              (pair-bindings (cdr variables) (cdr values)))))
  (define (make-frame variables values)
    (cons '*frame* (pair-bindings variables values)))
  (define (extend-environment variables values base)
    (cons (make-frame variables values) base))
  (define (lookup variable environment)
    (if (null? environment)
        'unbound
        (let ((record (assoc variable (cdr (car environment)))))
          (if record
              (cdr record)
              (lookup variable (cdr environment))))))
  (define (make-procedure parameters body environment)
    (list 'compound parameters body environment))
  (define global-environment
    (list (make-frame '(x) '(10))))
  (define local-environment
    (extend-environment '(x y) '(3 4) global-environment))
  (define procedure
    (make-procedure '(z) '((+ x y z)) local-environment))
  (list (lookup 'x local-environment)
        (lookup 'x global-environment)
        (lookup 'y local-environment)
        (car procedure)
        (cadr procedure)
        (length (caddr procedure))
        (length (cadddr procedure))))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The environment program returns (3 10 4 compound (z) 1 2). The protocol program returns (primitive + 12 (first second third) #f #t #t).

Trace focus

Follow lookup through the local frame before the global frame, then inspect the environment object stored in the compound record. In the second program, separate procedure tagging from application and confirm that the observation list follows the argument list order exactly.

Try it yourself

Change the program and compare the result.

Add define-variable! and set-variable-value! to the frame model. Define a local w, assign the nearest x, and return both the local and global x values plus the captured procedure environment length.

Show hint

Definition targets the first frame. Assignment searches outward and changes the first existing matching record.

Complete this lesson

0 of 23 lessons complete in this chapter0%