4.1.6 · Names need context

An environment gives a symbol its value.

Evaluation needs an explicit mapping from variable names in the expression to the values they denote.

Guiding question

Why can the same expression produce a different value in another environment?

Represent bindings as an association list
Look up symbols separately from evaluating numbers
Pass one environment through every recursive call

lookup searches an association list for a pair whose car is the requested symbol. The cdr of that pair is the value supplied by this environment.

evaluate does not attach one permanent meaning to x or y. It receives an environment with the expression, so the same expression tree can be reused with different bindings.

SICP code678 of 1,048,576 UTF-8 bytes

(begin
  (define (lookup name environment)
    (let ((binding (assoc name environment)))
      (if binding
          (cdr binding)
          (error "unbound variable" name))))
  (define (evaluate expression environment)
    (cond ((number? expression) expression)
          ((symbol? expression) (lookup expression environment))
          ((eq? (car expression) '+)
           (+ (evaluate (cadr expression) environment)
              (evaluate (caddr expression) environment)))
          ((eq? (car expression) '*)
           (* (evaluate (cadr expression) environment)
              (evaluate (caddr expression) environment)))))
  (evaluate '(+ x (* y 2)) '((x . 3) (y . 4))))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program binds x to 3 and y to 4, then returns 11.

Trace focus

Find the symbol cases for x and y and the assoc calls that resolve them. Both recursive branches receive the same environment value.

Try it yourself

Change the program and compare the result.

Change only the environment so that the first expression returns 25. Keep the quoted expression unchanged.

Show hint

The expression computes x plus twice y, so many different binding pairs can work.

Complete this lesson

0 of 23 lessons complete in this chapter0%