5.5.8 · From tree to instructions

A compiler changes the representation of the work.

A lesson compiler can turn an expression tree into stack instructions that a separate machine executes later.

Guiding question

How does an expression tree become a linear instruction sequence?

Emit constant and arithmetic instructions from syntax data
Preserve operand order in stack code
Separate compilation from machine execution

compile emits the left operand code, then the right operand code, and finally one arithmetic instruction. Recursion flattens the nested expression into a linear list.

execute pushes constants. An arithmetic instruction pops the right and left values, combines them, and pushes the result. When no code remains, the stack top is the program value.

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

(begin
  (define (operator-instruction operator)
    (cond ((eq? operator '+) 'add)
          ((eq? operator '-) 'sub)
          ((eq? operator '*) 'mul)))
  (define (compile expression)
    (if (number? expression)
        (list (list 'const expression))
        (append (compile (cadr expression))
                (append (compile (caddr expression))
                        (list (operator-instruction (car expression)))))))
  (define (execute code stack)
    (if (null? code)
        (car stack)
        (let ((instruction (car code)))
          (if (pair? instruction)
              (execute (cdr code) (cons (cadr instruction) stack))
              (let ((right (car stack)) (left (cadr stack)))
                (execute
                  (cdr code)
                  (cons (cond ((eq? instruction 'add) (+ left right))
                              ((eq? instruction 'sub) (- left right))
                              ((eq? instruction 'mul) (* left right)))
                        (cddr stack))))))))
  (let ((code (compile '(+ (* 3 4) 5))))
    (list code (execute code '()))))

(begin
  (define (operator-instruction operator)
    (cond ((eq? operator '+) 'add)
          ((eq? operator '-) 'sub)
          ((eq? operator '*) 'mul)))
  (define (compile expression)
    (if (number? expression)
        (list (list 'const expression))
        (append (compile (cadr expression))
                (append (compile (caddr expression))
                        (list (operator-instruction (car expression)))))))
  (define (execute code stack)
    (if (null? code)
        (car stack)
        (let ((instruction (car code)))
          (if (pair? instruction)
              (execute (cdr code) (cons (cadr instruction) stack))
              (let ((right (car stack)) (left (cadr stack)))
                (execute
                  (cdr code)
                  (cons (cond ((eq? instruction 'add) (+ left right))
                              ((eq? instruction 'sub) (- left right))
                              ((eq? instruction 'mul) (* left right)))
                        (cddr stack))))))))
  (let ((code (compile '(+ (* 3 4) 5))))
    (list code (execute code '()))))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program returns the five emitted instructions and the executed value 17.

Trace focus

Separate the recursive compile calls from the later execute calls. During execution, each instruction consumes code while changing the stack.

Try it yourself

Change the program and compare the result.

Compile (+ 1 (* 2 (+ 3 4))). Write the instruction list before you execute it.

Show hint

Each number emits const. Each compound expression emits its operator after both operands.

Complete this lesson

0 of 23 lessons complete in this chapter0%