An environment gives a symbol its value.
Evaluation needs an explicit mapping from variable names in the expression to the values they denote.
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.
(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))))- Output
- —
- Value
- —
- Diagnostic
- —
The first program binds x to 3 and y to 4, then returns 11.
Find the symbol cases for x and y and the assoc calls that resolve them. Both recursive branches receive the same environment value.
Change the program before you read the hint.
Change only the environment so that the first expression returns 25. Keep the quoted expression unchanged.
Show one hint
The expression computes x plus twice y, so many different binding pairs can work.