A compiler changes the representation of the work.
A small compiler can turn an expression tree into stack instructions that a separate machine executes later.
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.
(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 '()))))- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns the five emitted instructions and the executed value 17.
Separate the recursive compile calls from the later execute calls. During execution, each instruction consumes code while changing the stack.
Change the program before you read the hint.
Compile (+ 1 (* 2 (+ 3 4))). Write the instruction list before you execute it.
Show one hint
Each number emits const. Each compound expression emits its operator after both operands.