The metacircular evaluator from Ch.14, compiled down to register machine instructions. Makes explicit what the high-level interpreter hides: stack saves, register assignments, goto dispatch.
The dispatcher — eval-dispatch
The evaluator’s core is a dispatch loop. It reads the expression type and jumps to the right handler. In the metacircular evaluator this was a cond inside eval. Here it’s explicit: test the tag, branch to a label.
Scheme
; eval-dispatch: classify expression, jump to handler.; This is the register-machine version of the metacircular eval's cond.
(define (eval-dispatch exp env)
(cond ((number? exp) (cons 'self-eval exp))
((symbol? exp) (cons 'variable (eval-variable exp env)))
((pair? exp)
(let ((tag (car exp)))
(cond ((eq? tag 'quote) (cons 'quoted (cadr exp)))
((eq? tag 'if) (cons 'conditional exp))
((eq? tag 'define) (cons 'definition exp))
((eq? tag 'lambda) (cons 'lambda exp))
(else (cons 'application exp)))))
(else (cons 'unknown exp))))
(define test-env '((x . 10) (y . 20)))
(define (eval-variable name env)
(let ((binding (assoc name env)))
(if binding (cdr binding) '*unbound*)))
; Test each dispatch path
(display (eval-dispatch 42 test-env)) (newline)
(display (eval-dispatch 'x test-env)) (newline)
(display (eval-dispatch '(quote hello) test-env)) (newline)
(display (eval-dispatch '(if#t12) test-env)) (newline)
(display (eval-dispatch '(+ x y) test-env))
Python
# eval_dispatch: classify expression, route to handlerdef eval_dispatch(exp, env):
ifisinstance(exp, (int, float)):
return ('self-eval', exp)
ifisinstance(exp, str):
return ('variable', env.get(exp, '*unbound*'))
ifisinstance(exp, list) and exp:
tag = exp[0]
if tag == 'quote': return ('quoted', exp[1])
if tag == 'if': return ('conditional', exp)
if tag == 'define': return ('definition', exp)
if tag == 'lambda': return ('lambda', exp)
return ('application', exp)
return ('unknown', exp)
env = {'x': 10, 'y': 20}
print(eval_dispatch(42, env))
print(eval_dispatch('x', env))
print(eval_dispatch(['quote', 'hello'], env))
print(eval_dispatch(['if', True, 1, 2], env))
print(eval_dispatch(['+', 'x', 'y'], env))
Evaluating simple expressions
Self-evaluating expressions (numbers, strings) go straight to the val register. Variables require an environment lookup. Quoted expressions strip the quote tag and return the datum. No stack needed — these are leaves of the expression tree.
Scheme
; Simple expression evaluation: no stack, no recursion.; The register machine just assigns val and continues.
(define val '*unassigned*)
(define env '((pi . 3.14159) (e . 2.71828) (msg . "hello")))
; Self-evaluating
(define (eval-self-evaluating exp)
(set! val exp)
val)
; Variable lookup
(define (eval-variable exp)
(let ((binding (assoc exp env)))
(set! val (if binding (cdr binding) '*unbound*))
val))
; Quoted
(define (eval-quoted exp)
(set! val (cadr exp))
val)
(display "self-eval 42: ") (display (eval-self-evaluating 42)) (newline)
(display "variable pi: ") (display (eval-variable 'pi)) (newline)
(display "variable e: ") (display (eval-variable 'e)) (newline)
(display "quoted: ") (display (eval-quoted '(quote (a b c)))) (newline)
(display "variable msg: ") (display (eval-variable 'msg))
Python
# Simple expression evaluation โ leaf cases
val = None
env = {'pi': 3.14159, 'e': 2.71828, 'msg': 'hello'}
def eval_self(exp):
global val
val = exp
return val
def eval_variable(exp):
global val
val = env.get(exp, '*unbound*')
return val
def eval_quoted(exp):
global val
val = exp[1]
return val
print(f"self-eval 42: {eval_self(42)}")
print(f"variable pi: {eval_variable('pi')}")
print(f"variable e: {eval_variable('e')}")
print(f"quoted: {eval_quoted(['quote', ['a', 'b', 'c']])}")
print(f"variable msg: {eval_variable('msg')}")
Evaluating combinations — the operand loop
Combinations require evaluating the operator and each operand, then applying. The explicit-control evaluator must save registers before recursing into subexpressions. The operand loop pushes each evaluated argument onto a list (argl), building the argument list one element at a time.
Scheme
; Evaluating (+ 3 (* 2 5)): explicit save/restore.; Shows what the metacircular evaluator does implicitly.
(define stack '())
(define (save! v) (set! stack (cons v stack)))
(define (restore!) (let ((v (car stack))) (set! stack (cdr stack)) v))
(define val 0)
(define argl '())
; Step-by-step evaluation trace
(display "Evaluating (+ 3 (* 2 5))") (newline)
(display "---") (newline)
; 1. Evaluate operator: +
(define proc +)
(display "1. operator = +") (newline)
; 2. Start operand loop
(set! argl '())
; 3. Evaluate first operand: 3 (self-evaluating)
(set! val 3)
(set! argl (cons val argl))
(display "2. after eval 3, argl = ") (display argl) (newline)
; 4. Save argl before evaluating subexpression (* 2 5)
(save! argl)
(save! proc)
(display "3. saved argl and proc to stack") (newline)
; 5. Evaluate (* 2 5) โ this is a recursive eval
(set! val (* 25))
(display "4. eval (* 2 5) = ") (display val) (newline)
; 6. Restore and add to argl
(set! proc (restore!))
(set! argl (restore!))
(set! argl (cons val argl))
(display "5. restored, argl = ") (display argl) (newline)
; 7. Apply
(set! val (apply proc (reverse argl)))
(display "6. apply + to ") (display (reverse argl))
(display " = ") (display val)
Python
# Evaluating (+ 3 (* 2 5)) with explicit stack
stack = []
val = 0
argl = []
print("Evaluating (+ 3 (* 2 5))")
print("---")
# 1. Evaluate operatorimportoperator
proc = operator.add
print("1. operator = +")
# 2-3. Evaluate first operand
argl = []
val = 3
argl.append(val)
print(f"2. after eval 3, argl = {argl}")
# 4. Save before subexpression
stack.append(list(argl))
stack.append(proc)
print("3. saved argl and proc to stack")
# 5. Evaluate subexpression
val = 2 * 5print(f"4. eval (* 2 5) = {val}")
# 6. Restore
proc = stack.pop()
argl = stack.pop()
argl.append(val)
print(f"5. restored, argl = {argl}")
# 7. Apply
val = proc(argl[0], argl[1])
print(f"6. apply + to {argl} = {val}")
Sequence evaluation and tail recursion
A tail call is a call in return position — nothing left to do after it returns. The explicit-control evaluator recognizes this: it skips the save of the continuation register. No save means the stack doesn’t grow. This is why Scheme guarantees tail-call optimization — the evaluator’s structure makes it free.
Scheme
; Tail recursion: iterative factorial with explicit stack tracking.; The stack never grows because each call is in tail position.
(define stack-depth 0)
(define max-depth 0)
(define (save-track!)
(set! stack-depth (+ stack-depth 1))
(if (> stack-depth max-depth) (set! max-depth stack-depth)))
(define (restore-track!)
(set! stack-depth (- stack-depth 1)))
; Tail-recursive factorial โ no saves needed
(define (fact-iter n acc)
; In explicit-control: this is a goto, not a call
(if (= n 0)
acc
(fact-iter (- n 1) (* acc n))))
(display "fact(10) = ") (display (fact-iter 101)) (newline)
(display "stack depth stayed at: ") (display max-depth) (newline)
; Non-tail-recursive โ each call saves continuation
(set! max-depth 0)
(set! stack-depth 0)
(define (fact-rec n)
(if (= n 0)
1
(begin
(save-track!) ; simulate saving continuation
(let ((result (* n (fact-rec (- n 1)))))
(restore-track!)
result))))
(display "fact-rec(10) = ") (display (fact-rec 10)) (newline)
(display "max stack depth: ") (display max-depth)
Python
# Tail recursion vs non-tail: stack depth trackingimport sys
sys.setrecursionlimit(200)
# Tail-recursive (Python doesn't optimize this, but the logic is the same)def fact_iter(n, acc=1):
if n == 0:
return acc
return fact_iter(n - 1, acc * n)
# Non-tail-recursive
call_depth = [0]
max_depth = [0]
def fact_rec(n):
if n == 0:
return1
call_depth[0] += 1
max_depth[0] = max(max_depth[0], call_depth[0])
result = n * fact_rec(n - 1)
call_depth[0] -= 1return result
print(f"fact_iter(10) = {fact_iter(10)}")
print(f"(Python can't optimize tail calls โ but Scheme can)")
print(f"fact_rec(10) = {fact_rec(10)}")
print(f"max stack depth: {max_depth[0]}")
Conditionals and assignments
Conditionals evaluate the predicate, then branch to the consequent or alternative. The explicit-control evaluator saves the environment and unevaluated branches on the stack before evaluating the predicate. Assignments use set-variable-value! to mutate the environment — the only place the evaluator writes to the environment frame.
Scheme
; Explicit conditional evaluation with environment.
(define env '((x . 5) (y . 10)))
(define (lookup var env)
(let ((b (assoc var env)))
(if b (cdr b) (error "Unbound" var))))
(define (eval-if pred-val consequent alternative env)
; In the real evaluator: save env, eval predicate,; then branch. Here we simulate the flow.
(display " predicate = ") (display pred-val) (newline)
(if pred-val
(begin (display " -> consequent") (newline) consequent)
(begin (display " -> alternative") (newline) alternative)))
; (if (> x 3) "big" "small")
(display "eval (if (> x 3) big small):") (newline)
(display " result = ")
(display (eval-if (> (lookup 'x env) 3) "big""small")) (newline)
; Assignment: (set! x 99)
(display "Before set!: x = ") (display (lookup 'x env)) (newline)
(set! env (cons (cons 'x 99) env)) ; shadow old binding
(display "After set!: x = ") (display (lookup 'x env)) (newline)
; (if (> x 50) "big" "small") โ now x is 99
(display "eval (if (> x 50) big small):") (newline)
(display " result = ")
(display (eval-if (> (lookup 'x env) 50) "big""small"))
Python
# Explicit conditional and assignment
env = {'x': 5, 'y': 10}
def eval_if(pred_val, consequent, alternative):
print(f" predicate = {pred_val}")
if pred_val:
print(" -> consequent")
return consequent
else:
print(" -> alternative")
return alternative
# if x > 3 then "big" else "small"print("eval (if (> x 3) big small):")
print(f" result = {eval_if(env['x'] > 3, 'big', 'small')}")
# Assignmentprint(f"Before set!: x = {env['x']}")
env['x'] = 99print(f"After set!: x = {env['x']}")
# if x > 50print("eval (if (> x 50) big small):")
print(f" result = {eval_if(env['x'] > 50, 'big', 'small')}")
Notation reference
Register Machine / SICP
Python
Meaning
eval-dispatch
eval()
Main dispatch loop
(save continue)
stack.append(return_addr)
Save return address
(restore continue)
return_addr = stack.pop()
Restore return address
ev-if / ev-assignment
visit_If / visit_Assign
Handler labels (like AST visitor methods)
argl
args = []
Accumulator for evaluated operands
tail position → no save
(not optimized in CPython)
Tail-call optimization
Translation notes
The explicit-control evaluator is the bridge between the high-level metacircular evaluator (Ch.14) and real machine code. Every implicit operation — function calls, argument evaluation order, stack management — becomes a visible instruction. CPython’s ceval.c is structurally the same: a giant switch statement dispatching on bytecode opcode, with an explicit value stack. Tail-call optimization is a property of the evaluator’s structure, not a compiler trick: if the evaluator doesn’t push a frame, the stack doesn’t grow.
Neighbors
Other reading pages
SICP Ch.14 — the metacircular evaluator this chapter compiles down
Control flow