Register Machines and Compilation

44.1 Register Machines (SICP Chapter 5)

SICP 5 builds a register-machine simulator, an explicit-control evaluator (the metacircular evaluator rewritten as a machine with a stack, explaining tail calls at the machine level), garbage collection (stop-and-copy), and a compiler from Scheme to register-machine code.

;; GCD as a register machine (SICP 5.1)
;; (controller
;;  test-b
;;    (test (op =) (reg b) (const 0))
;;    (branch (label gcd-done))
;;    (assign t (op rem) (reg a) (reg b))
;;    (assign a (reg b))
;;    (assign b (reg t))
;;    (goto (label test-b))
;;  gcd-done)

44.2 Compiling Scheme: The Big Picture

Further reading: *An Incremental Approach to Compiler Construction* (Abdulaziz Ghuloum), *Essentials of Compilation* (Jeremy Siek), *Lisp in Small Pieces* (Queinnec), *Compiling with Continuations* (Appel), and Kent Dybvig's *Three Implementation Models for Scheme* (thesis) and Chez Scheme papers.

Source → read → macro expansion → core forms (lambda, if, set!, quote, application, letrec)
       → alpha renaming → CPS or ANF conversion → closure conversion → assignment conversion (boxes)
       → lambda lifting → code generation (assembly, C, bytecode, Wasm) → runtime (GC, tagging)

;; A tiny compiler from arithmetic expressions to stack-machine instructions
(define (compile-expr e)
  (cond ((number? e) (list (list 'push e)))
        ((pair? e)
         (append (compile-expr (cadr e))
                 (compile-expr (caddr e))
                 (list (list (case (car e) ((+) 'add) ((-) 'sub) ((*) 'mul))))))
        (else (error "unsupported" e))))

(define (run-vm code)
  (let loop ((code code) (stack '()))
    (if (null? code)
        (car stack)
        (let ((instr (car code)))
          (case (car instr)
            ((push) (loop (cdr code) (cons (cadr instr) stack)))
            ((add sub mul)
             (let ((b (car stack)) (a (cadr stack)) (rest (cddr stack)))
               (loop (cdr code)
                     (cons ((case (car instr) ((add) +) ((sub) -) ((mul) *)) a b) rest)))))))))

(compile-expr '(+ 1 (* 2 3)))   ; ((push 1) (push 2) (push 3) (mul) (add))
(run-vm (compile-expr '(+ 1 (* 2 3))))   ; 7