Compilation

Abelson & Sussman · 1996 · SICP §5.5

A compiler translates Scheme to register machine code ahead of time. The compiled code is faster because decisions made at compile time don’t repeat at runtime. The compiler itself is a Scheme program.

Structure of the compiler

The compiler mirrors the evaluator’s structure: dispatch on expression type, generate instructions for each case. But instead of executing, it returns a sequence of instructions to be executed later. The instruction sequences carry metadata: which registers they need and which they modify.

Scheme

; Instruction sequences: (needs modifies instructions)
; The compiler tracks register usage for optimization.

(define (make-instruction-seq needs modifies instructions)
  (list needs modifies instructions))

(define (registers-needed seq) (car seq))
(define (registers-modified seq) (cadr seq))
(define (instructions seq) (caddr seq))

; A self-evaluating expression: needs nothing, modifies val
(define seq1
  (make-instruction-seq
    '()           ; needs no registers
    '(val)        ; modifies val
    '((assign val (const 42)))))

(display "needs: ") (display (registers-needed seq1)) (newline)
(display "modifies: ") (display (registers-modified seq1)) (newline)
(display "code: ") (display (instructions seq1)) (newline)

; A variable lookup: needs env, modifies val
(define seq2
  (make-instruction-seq
    '(env)
    '(val)
    '((assign val (op lookup) (reg env) (const x)))))

(display "needs: ") (display (registers-needed seq2)) (newline)
(display "modifies: ") (display (registers-modified seq2))

; Instruction sequences: (needs modifies instructions)
; The compiler tracks register usage for optimization.

(define (make-instruction-seq needs modifies instructions)
  (list needs modifies instructions))

(define (registers-needed seq) (car seq))
(define (registers-modified seq) (cadr seq))
(define (instructions seq) (caddr seq))

; A self-evaluating expression: needs nothing, modifies val
(define seq1
  (make-instruction-seq
    '()           ; needs no registers
    '(val)        ; modifies val
    '((assign val (const 42)))))

(display "needs: ") (display (registers-needed seq1)) (newline)
(display "modifies: ") (display (registers-modified seq1)) (newline)
(display "code: ") (display (instructions seq1)) (newline)

; A variable lookup: needs env, modifies val
(define seq2
  (make-instruction-seq
    '(env)
    '(val)
    '((assign val (op lookup) (reg env) (const x)))))

(display "needs: ") (display (registers-needed seq2)) (newline)
(display "modifies: ") (display (registers-modified seq2))

Compiling expressions

compile dispatches on expression type, just like eval. Each clause returns an instruction sequence. compile-self-evaluating loads a constant into val. compile-variable emits a lookup instruction. The target parameter says which register to put the result in — not always val.

Scheme

; compile: dispatch on expression type, return instruction list.

(define (compile exp target)
  (cond ((number? exp)  (compile-self-eval exp target))
        ((string? exp)  (compile-self-eval exp target))
        ((symbol? exp)  (compile-variable exp target))
        ((pair? exp)
         (let ((tag (car exp)))
           (cond ((eq? tag 'quote)  (compile-quoted exp target))
                 ((eq? tag 'if)     (compile-if exp target))
                 (else              (compile-application exp target)))))
        (else (list (list 'error "Unknown expression" exp)))))

(define (compile-self-eval exp target)
  (list (list 'assign target (list 'const exp))))

(define (compile-variable exp target)
  (list (list 'assign target (list 'op 'lookup-variable) (list 'const exp))))

(define (compile-quoted exp target)
  (list (list 'assign target (list 'const (cadr exp)))))

(define (compile-if exp target)
  (let ((pred (cadr exp))
        (con  (caddr exp))
        (alt  (cadddr exp)))
    (append
      (compile pred 'val)
      (list '(test (op false?) (reg val)))
      (list '(branch (label false-branch)))
      (compile con target)
      (list '(goto (label after-if)))
      (list 'false-branch)
      (compile alt target)
      (list 'after-if))))

(define (compile-application exp target) '((todo-application)))

; Compile some expressions
(display "--- compile 42 ---") (newline)
(for-each (lambda (inst) (display "  ") (display inst) (newline))
          (compile 42 'val))

(display "--- compile x ---") (newline)
(for-each (lambda (inst) (display "  ") (display inst) (newline))
          (compile 'x 'val))

(display "--- compile (if x 1 2) ---") (newline)
(for-each (lambda (inst) (display "  ") (display inst) (newline))
          (compile '(if x 1 2) 'val))

; compile: dispatch on expression type, return instruction list.

(define (compile exp target)
  (cond ((number? exp)  (compile-self-eval exp target))
        ((string? exp)  (compile-self-eval exp target))
        ((symbol? exp)  (compile-variable exp target))
        ((pair? exp)
         (let ((tag (car exp)))
           (cond ((eq? tag 'quote)  (compile-quoted exp target))
                 ((eq? tag 'if)     (compile-if exp target))
                 (else              (compile-application exp target)))))
        (else (list (list 'error "Unknown expression" exp)))))

(define (compile-self-eval exp target)
  (list (list 'assign target (list 'const exp))))

(define (compile-variable exp target)
  (list (list 'assign target (list 'op 'lookup-variable) (list 'const exp))))

(define (compile-quoted exp target)
  (list (list 'assign target (list 'const (cadr exp)))))

(define (compile-if exp target)
  (let ((pred (cadr exp))
        (con  (caddr exp))
        (alt  (cadddr exp)))
    (append
      (compile pred 'val)
      (list '(test (op false?) (reg val)))
      (list '(branch (label false-branch)))
      (compile con target)
      (list '(goto (label after-if)))
      (list 'false-branch)
      (compile alt target)
      (list 'after-if))))

(define (compile-application exp target) '((todo-application)))

; Compile some expressions
(display "--- compile 42 ---") (newline)
(for-each (lambda (inst) (display "  ") (display inst) (newline))
          (compile 42 'val))

(display "--- compile x ---") (newline)
(for-each (lambda (inst) (display "  ") (display inst) (newline))
          (compile 'x 'val))

(display "--- compile (if x 1 2) ---") (newline)
(for-each (lambda (inst) (display "  ") (display inst) (newline))
          (compile '(if x 1 2) 'val))

Python

# compile: dispatch on expression type
def compile_exp(exp, target='val'):
    if isinstance(exp, (int, float)):
        return compile_self_eval(exp, target)
    if isinstance(exp, str) and not exp.startswith('('):
        return compile_variable(exp, target)
    if isinstance(exp, list):
        tag = exp[0]
        if tag == 'quote':
            return [('assign', target, ('const', exp[1]))]
        if tag == 'if':
            return compile_if(exp, target)
        return [('todo-application',)]
    return [('error', 'unknown', exp)]

def compile_self_eval(exp, target):
    return [('assign', target, ('const', exp))]

def compile_variable(exp, target):
    return [('assign', target, ('op', 'lookup'), ('const', exp))]

def compile_if(exp, target):
    _, pred, con, alt = exp
    code = compile_exp(pred, 'val')
    code += [('test', ('op', 'false?'), ('reg', 'val'))]
    code += [('branch', ('label', 'false-branch'))]
    code += compile_exp(con, target)
    code += [('goto', ('label', 'after-if'))]
    code += ['false-branch']
    code += compile_exp(alt, target)
    code += ['after-if']
    return code

print("--- compile 42 ---")
for inst in compile_exp(42):
    print(f"  {inst}")

print("--- compile 'x' ---")
for inst in compile_exp('x'):
    print(f"  {inst}")

print("--- compile (if x 1 2) ---")
for inst in compile_exp(['if', 'x', 1, 2]):
    print(f"  {inst}")

# compile: dispatch on expression type
def compile_exp(exp, target='val'):
    if isinstance(exp, (int, float)):
        return compile_self_eval(exp, target)
    if isinstance(exp, str) and not exp.startswith('('):
        return compile_variable(exp, target)
    if isinstance(exp, list):
        tag = exp[0]
        if tag == 'quote':
            return [('assign', target, ('const', exp[1]))]
        if tag == 'if':
            return compile_if(exp, target)
        return [('todo-application',)]
    return [('error', 'unknown', exp)]

def compile_self_eval(exp, target):
    return [('assign', target, ('const', exp))]

def compile_variable(exp, target):
    return [('assign', target, ('op', 'lookup'), ('const', exp))]

def compile_if(exp, target):
    _, pred, con, alt = exp
    code = compile_exp(pred, 'val')
    code += [('test', ('op', 'false?'), ('reg', 'val'))]
    code += [('branch', ('label', 'false-branch'))]
    code += compile_exp(con, target)
    code += [('goto', ('label', 'after-if'))]
    code += ['false-branch']
    code += compile_exp(alt, target)
    code += ['after-if']
    return code

print("--- compile 42 ---")
for inst in compile_exp(42):
    print(f"  {inst}")

print("--- compile 'x' ---")
for inst in compile_exp('x'):
    print(f"  {inst}")

print("--- compile (if x 1 2) ---")
for inst in compile_exp(['if', 'x', 1, 2]):
    print(f"  {inst}")

Compiling combinations

Compiling (f a b) means: compile the operator, compile each operand, then emit an apply. The compiler can see at compile time how many arguments there are and whether saves are needed — the evaluator figures this out fresh every time. This is where compilation wins.

Scheme

; Compiling (f a b): operator + operands + apply.
; The compiler decides at compile time what to save.

(define (compile-application exp target)
  (let ((operator (car exp))
        (operands (cdr exp)))
    (append
      ; 1. Compile operator -> proc register
      (compile-expr operator 'proc)
      ; 2. Save proc if operands might clobber it
      (if (not (null? operands))
          '((save proc))
          '())
      ; 3. Compile each operand, building argl
      (compile-operand-loop operands)
      ; 4. Restore proc and apply
      (if (not (null? operands))
          '((restore proc))
          '())
      (list (list 'assign target '(op apply) '(reg proc) '(reg argl))))))

(define (compile-expr exp target)
  (cond ((number? exp) (list (list 'assign target (list 'const exp))))
        ((symbol? exp) (list (list 'assign target (list 'op 'lookup) (list 'const exp))))
        (else (list (list 'assign target (list 'compile exp))))))

(define (compile-operand-loop operands)
  (if (null? operands)
      '((assign argl (const ())))
      (let ((first (car operands))
            (rest (cdr operands)))
        (append
          '((assign argl (const ())))
          (compile-expr first 'val)
          '((assign argl (op adjoin-arg) (reg val) (reg argl)))
          (if (null? rest) '()
              (append
                (compile-expr (cadr operands) 'val)
                '((assign argl (op adjoin-arg) (reg val) (reg argl)))))))))

; Compile (+ 3 7)
(display "--- compile (+ 3 7) ---") (newline)
(for-each (lambda (inst) (display "  ") (display inst) (newline))
          (compile-application '(+ 3 7) 'val))

; Compiling (f a b): operator + operands + apply.
; The compiler decides at compile time what to save.

(define (compile-application exp target)
  (let ((operator (car exp))
        (operands (cdr exp)))
    (append
      ; 1. Compile operator -> proc register
      (compile-expr operator 'proc)
      ; 2. Save proc if operands might clobber it
      (if (not (null? operands))
          '((save proc))
          '())
      ; 3. Compile each operand, building argl
      (compile-operand-loop operands)
      ; 4. Restore proc and apply
      (if (not (null? operands))
          '((restore proc))
          '())
      (list (list 'assign target '(op apply) '(reg proc) '(reg argl))))))

(define (compile-expr exp target)
  (cond ((number? exp) (list (list 'assign target (list 'const exp))))
        ((symbol? exp) (list (list 'assign target (list 'op 'lookup) (list 'const exp))))
        (else (list (list 'assign target (list 'compile exp))))))

(define (compile-operand-loop operands)
  (if (null? operands)
      '((assign argl (const ())))
      (let ((first (car operands))
            (rest (cdr operands)))
        (append
          '((assign argl (const ())))
          (compile-expr first 'val)
          '((assign argl (op adjoin-arg) (reg val) (reg argl)))
          (if (null? rest) '()
              (append
                (compile-expr (cadr operands) 'val)
                '((assign argl (op adjoin-arg) (reg val) (reg argl)))))))))

; Compile (+ 3 7)
(display "--- compile (+ 3 7) ---") (newline)
(for-each (lambda (inst) (display "  ") (display inst) (newline))
          (compile-application '(+ 3 7) 'val))

Python

# Compiling function application (f a b)
def compile_application(exp, target='val'):
    operator = exp[0]
    operands = exp[1:]
    code = []

    # 1. Compile operator
    code += compile_simple(operator, 'proc')

    # 2. Save proc if needed
    if operands:
        code.append(('save', 'proc'))

    # 3. Compile operands
    code.append(('assign', 'argl', ('const', [])))
    for operand in operands:
        code += compile_simple(operand, 'val')
        code.append(('assign', 'argl', ('op', 'adjoin-arg'), ('reg', 'val'), ('reg', 'argl')))

    # 4. Restore and apply
    if operands:
        code.append(('restore', 'proc'))
    code.append(('assign', target, ('op', 'apply'), ('reg', 'proc'), ('reg', 'argl')))
    return code

def compile_simple(exp, target):
    if isinstance(exp, (int, float)):
        return [('assign', target, ('const', exp))]
    return [('assign', target, ('op', 'lookup'), ('const', exp))]

print("--- compile (+ 3 7) ---")
for inst in compile_application(['+', 3, 7]):
    print(f"  {inst}")

# Compiling function application (f a b)
def compile_application(exp, target='val'):
    operator = exp[0]
    operands = exp[1:]
    code = []

# 1. Compile operator
    code += compile_simple(operator, 'proc')

# 2. Save proc if needed
    if operands:
        code.append(('save', 'proc'))

# 3. Compile operands
    code.append(('assign', 'argl', ('const', [])))
    for operand in operands:
        code += compile_simple(operand, 'val')
        code.append(('assign', 'argl', ('op', 'adjoin-arg'), ('reg', 'val'), ('reg', 'argl')))

# 4. Restore and apply
    if operands:
        code.append(('restore', 'proc'))
    code.append(('assign', target, ('op', 'apply'), ('reg', 'proc'), ('reg', 'argl')))
    return code

def compile_simple(exp, target):
    if isinstance(exp, (int, float)):
        return [('assign', target, ('const', exp))]
    return [('assign', target, ('op', 'lookup'), ('const', exp))]

print("--- compile (+ 3 7) ---")
for inst in compile_application(['+', 3, 7]):
    print(f"  {inst}")

Lexical addressing

The compiler knows the structure of the environment at compile time. Instead of searching by name at runtime, it can emit a lexical address: (frame-number, offset). Frame 0 is the current frame, frame 1 is the enclosing one. This replaces a linear search with a direct index.

Scheme

; Lexical addressing: compile-time variable resolution.
; A variable's position is (frame-number . offset).

(define (find-variable var compile-env)
  (define (scan-frame frame offset)
    (cond ((null? frame) #f)
          ((eq? (car frame) var) offset)
          (else (scan-frame (cdr frame) (+ offset 1)))))
  (define (scan-env env depth)
    (if (null? env)
        (cons 'global var)  ; not found lexically
        (let ((offset (scan-frame (car env) 0)))
          (if offset
              (cons depth offset)
              (scan-env (cdr env) (+ depth 1))))))
  (scan-env compile-env 0))

; Compile-time environment: list of frames, each a list of variable names
(define cenv '((x y)        ; frame 0: current lambda
               (a b c)      ; frame 1: enclosing lambda
               (top)))      ; frame 2: top-level

(display "x -> ") (display (find-variable 'x cenv)) (newline)
(display "y -> ") (display (find-variable 'y cenv)) (newline)
(display "b -> ") (display (find-variable 'b cenv)) (newline)
(display "top -> ") (display (find-variable 'top cenv)) (newline)
(display "z -> ") (display (find-variable 'z cenv))

; Lexical addressing: compile-time variable resolution.
; A variable's position is (frame-number . offset).

(define (find-variable var compile-env)
  (define (scan-frame frame offset)
    (cond ((null? frame) #f)
          ((eq? (car frame) var) offset)
          (else (scan-frame (cdr frame) (+ offset 1)))))
  (define (scan-env env depth)
    (if (null? env)
        (cons 'global var)  ; not found lexically
        (let ((offset (scan-frame (car env) 0)))
          (if offset
              (cons depth offset)
              (scan-env (cdr env) (+ depth 1))))))
  (scan-env compile-env 0))

; Compile-time environment: list of frames, each a list of variable names
(define cenv '((x y)        ; frame 0: current lambda
               (a b c)      ; frame 1: enclosing lambda
               (top)))      ; frame 2: top-level

(display "x -> ") (display (find-variable 'x cenv)) (newline)
(display "y -> ") (display (find-variable 'y cenv)) (newline)
(display "b -> ") (display (find-variable 'b cenv)) (newline)
(display "top -> ") (display (find-variable 'top cenv)) (newline)
(display "z -> ") (display (find-variable 'z cenv))

Interfacing compiled code with the evaluator

Compiled code and interpreted code must interoperate. The compiler produces register machine instructions that use the same register conventions as the explicit-control evaluator. A compiled procedure can call an interpreted one and vice versa. The entry point protocol — arguments in argl, result in val — is the interface contract.

Scheme

; Compiled vs interpreted: same calling convention.
; Both put arguments in argl, result in val.

(define val 0)
(define argl '())
(define proc #f)

; "Compiled" factorial — just a Scheme procedure
; but using the register-machine calling convention
(define (compiled-fact n)
  (if (= n 0) 1 (* n (compiled-fact (- n 1)))))

; "Interpreted" double — simulating the eval dispatch
(define (interpreted-double x)
  ; The evaluator would: look up 'double, eval args, apply
  (* 2 x))

; Interface: compiled calls interpreted
(display "compiled fact(5) = ")
(display (compiled-fact 5)) (newline)

(display "interpreted double(21) = ")
(display (interpreted-double 21)) (newline)

; Mixed: compile a procedure that uses an interpreted helper
(define (compiled-fact-double n)
  (interpreted-double (compiled-fact n)))

(display "compiled-fact-double(5) = ")
(display (compiled-fact-double 5)) (newline)
(display "compiled-fact-double(6) = ")
(display (compiled-fact-double 6)) (newline)

; The calling convention makes this seamless:
; argl carries arguments, val carries results,
; whether the callee was compiled or interpreted.
(display "Interface: same registers, different execution paths")

; Compiled vs interpreted: same calling convention.
; Both put arguments in argl, result in val.

(define val 0)
(define argl '())
(define proc #f)

; "Compiled" factorial — just a Scheme procedure
; but using the register-machine calling convention
(define (compiled-fact n)
  (if (= n 0) 1 (* n (compiled-fact (- n 1)))))

; "Interpreted" double — simulating the eval dispatch
(define (interpreted-double x)
  ; The evaluator would: look up 'double, eval args, apply
  (* 2 x))

; Interface: compiled calls interpreted
(display "compiled fact(5) = ")
(display (compiled-fact 5)) (newline)

(display "interpreted double(21) = ")
(display (interpreted-double 21)) (newline)

; Mixed: compile a procedure that uses an interpreted helper
(define (compiled-fact-double n)
  (interpreted-double (compiled-fact n)))

(display "compiled-fact-double(5) = ")
(display (compiled-fact-double 5)) (newline)
(display "compiled-fact-double(6) = ")
(display (compiled-fact-double 6)) (newline)

; The calling convention makes this seamless:
; argl carries arguments, val carries results,
; whether the callee was compiled or interpreted.
(display "Interface: same registers, different execution paths")

Notation reference

Scheme / SICP	Python	Meaning
(compile exp target linkage)	compile(ast) → bytecode	Translate expression to instructions
target register	destination variable	Where to put the result
linkage (next / return / goto)	fall-through / return / jump	What to do after this code
lexical address (d . o)	LOAD_FAST / LOAD_DEREF	Compile-time variable position
preserving	register allocation	Save only if needed (optimization)
compiled-apply / interp-apply	CALL_FUNCTION	Unified calling convention

Translation notes

The SICP compiler targets the register machine from Ch.19. CPython’s compiler targets the CPython VM bytecode. The structural parallel is exact: compile_self_evaluating emits LOAD_CONST, compile_variable emits LOAD_NAME or LOAD_FAST, compile_application emits CALL_FUNCTION. Lexical addressing in SICP is what CPython does with LOAD_FAST (local variables at known offsets). The preserving combinator — only save registers that the next sequence actually needs — is the simplest form of register allocation.

Neighbors