4.1.3 · An evaluator in the language

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.

Guiding question

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.

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

(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))))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program interprets the quoted expression and returns 20.

Trace focus

Follow evaluate into the two nested operand trees. Each number reaches the direct-value case, while each list reaches an operator decision.

Try it yourself

Change the program and compare the result.

Add division to the operator cases, then interpret the expression (/ (+ 8 4) 3).

Show hint

The new case has the same recursive shape as addition and multiplication.

Complete this lesson

0 of 23 lessons complete in this chapter0%