Compiling Lisp

Interpretation vs compilation: an interpreter walks the s-expression tree every time. A compiler translates code once into a faster form (closures, bytecode, or machine code).

Compilation pipeline for a Lisp: Read text into s-expressions.

Macroexpand until only core forms remain.

Analyze: resolve variables to lexical addresses (frame, offset), detect free variables for closures.

Transform: CPS conversion or A-normal form (ANF), closure conversion, assignment conversion (boxes for set! variables).

Generate code: bytecode, C (Chicken, Gambit, ECL), LLVM (Clasp, Jank), JVM bytecode (Clojure, ABCL, Kawa), or native machine code (SBCL, Chez).

Closure compilation (SICP 4.1.7 "analyze"): pre-analyze syntax into closures so evaluation skips repeated dispatch.

Further study: SICP chapter 5 (register machines, an explicit-control evaluator, a compiler), *An Incremental Approach to Compiler Construction* (Ghuloum: Scheme to x86 step by step), *Essentials of Compilation* (Racket/Python), and Kent Dybvig's Chez Scheme papers.

(define (analyze exp)
  (cond ((number? exp) (lambda (env) exp))
        ((symbol? exp) (lambda (env) (lookup exp env)))
        ((eq? (car exp) 'if)
         (let ((test (analyze (cadr exp)))
               (conseq (analyze (caddr exp)))
               (alt (analyze (cadddr exp))))
           (lambda (env) (if (test env) (conseq env) (alt env)))))
        (else
         (let ((fproc (analyze (car exp)))
               (aprocs (map analyze (cdr exp))))
           (lambda (env)
             (m-apply (fproc env) (map (lambda (a) (a env)) aprocs)))))))