A program can inspect a program as data.
Once an expression is represented by lists and symbols, an ordinary Scheme procedure can decide what that expression means.
What must an evaluator do to turn expression data into a value?
- Distinguish source data from the evaluator executing it
- Dispatch on an operator symbol
- Evaluate a nested expression recursively
The quoted list is data, so the host evaluator does not apply its leading plus symbol. Our evaluate procedure inspects that symbol and chooses the operation itself.
Numbers evaluate directly. A compound expression asks evaluate to interpret both nested operands before combining their values. The evaluator follows the expression tree one node at a time.
(begin
(define (evaluate expression)
(if (number? expression)
expression
(let ((operator (car expression))
(left (cadr expression))
(right (caddr expression)))
(cond ((eq? operator '+)
(+ (evaluate left) (evaluate right)))
((eq? operator '-)
(- (evaluate left) (evaluate right)))
((eq? operator '*)
(* (evaluate left) (evaluate right)))))))
(evaluate '(+ (* 3 4) (- 10 2))))- Output
- —
- Value
- —
- Diagnostic
- —
The first program interprets the quoted expression and returns 20.
Follow evaluate into the two nested operand trees. Each number reaches the direct-value case, while each list reaches an operator decision.
Change the program before you read the hint.
Add division to the operator cases, then interpret the expression (/ (+ 8 4) 3).
Show one hint
The new case has the same recursive shape as addition and multiplication.