RLE and MIT Computation Center // Memo 39
一份来自 1962 年的备忘录，宣告了编程史上首个“自举”编译器的诞生。
作者: T. Hart & M. Levin
编译后的子程序比S-表达式解释执行快约40倍，这是数量级的提升。
编译后的代码体积通常仅为原始S-表达式定义的20-30%。
这个编译器完全由 LISP 语言编写。它的机器码版本是通过一个史无前例的过程获得的：让其自身的 LISP 源码（S-表达式）在解释器中运行，从而编译出它自己。
LISP 源码
执行环境
最终产物
1
对 S-表达式进行分析和重写。标记特殊变量、优化函数调用方式、并将部分递归改写为更高效的 PROG 迭代循环。
2
将优化后的 S-表达式生成为汇编语言。解决计算顺序、参数定位、存储分配和条件转移等核心问题。
3
LISP 汇编程序 (LISP Assembly Program)，将汇编代码转换为最终的可执行机器码子程序。
编译器和解释器可以自由混合使用，但必须正确声明“自由变量”（未在当前函数中绑定的变量）。这是确保代码正确性的关键。
当一个变量仅在编译函数之间作为自由变量使用时声明。
SPECIAL ((VAR1 VAR2...))当变量需要在编译函数和解释函数之间传递，或者作为函数参数时声明。
COMMON ((VAR1 VAR2...))为了实现编译/解释代码的无缝混合，编译器采用了一种巧妙的动态链接机制。
首次调用函数时:
STR (Store and Trap)
一个陷阱指令，执行被 LINK 捕获
LINK 处理后:
TSX (Transfer and Set Index)
指令被替换，后续直接调用机器码
如果目标是 LISP 源码 (EXPR)，LINK 会连接到解释器执行它。