[科普中国]-SECD抽象机

SECD 机是非常有影响的意图作为函数式编程语言编译器目标的虚拟机。SECD 分别是这个机器的内部寄存器的名字的首字母：Stack, Environment, Code, Dump。这些寄存器指向在内存中链表。

这种机器最初明确设计用来计算 lambda 演算表达式。最初 Peter J. Landin 在1963年把它作为他的 ISWIM编程语言定义的一部分描述。Landin 出版的描述非常抽象，（象一种操作语义那样）留下很多实现选择开放着。所以 SECD 机经常以更具体的形式出现，比如 Peter Henderson 的 Lispkit Lisp 编译器，它自1980年开始发行。此后它已经被用做多个其他实验编译器的目标。

在1989年在卡尔加里大学的研究者制作了这种机器的一个硬件实现。

寄存器和内存SECD 机是基于栈的，函数从栈中取得它们的形式参数（parameter）。与之相对，指令的实际参数（argument）跟在指令之后。

栈同所有内部数据结构一样是个列表，S寄存器指向这个列表的头部或开始端。由于列表结构，栈不需要连续成块的内存，所以只要有一个单一空闲内存单元栈空间就是可获得的。即使在所有单元都已经使用了时候，垃圾收集仍可以产生额外的空闲内存。

C寄存器指向要计算的代码或指令列表的头部。一旦指令已经被执行，C就指向在列表中的下一个指令—它类似于常规机器中的“指令指针”（或程序计数器），除了后续指令不需要在后续内存位置上之外。

E寄存器管理当前变量环境，它指向一个列表的列表。每个单独列表都代表一个环境级别：当前函数的形式参数位于列表的头部，在当前函数中自由但受外围函数约束（bound）的变量在E的其他元素中。

D寄存器指向转储（dump）的头部，它被用做其他寄存器的值的临时存储，例如在函数调用期间。它联系于其他机器的返回栈。

SECD 机的内存组织类似于大多数函数式编程语言解释器所用的模型：一些内存单元，每个都持有要么一个“原子”（一个简单值例如“13”），或表示一个空或非空列表。在后者情况，单元持有到其他单元的两个指针，一个表示第一个元素，另一个表示除去第一个元素之外的列表。这两个指针传统上分别叫做car和cdr— 现在更常使用现代术语“头”和“尾”。单元持有值的不同类型由一个“标志”来区分。原子的不同类型（整数、字符串等等）经常是同样可区分的。

内存单元 3 到 5 不属于这个列表，它的单元可以在内存中随机分布。单元 2 是这个列表的头部，它指向持有第一个元素的值的单元 1，和只包含“2”和“3”的（开始于单元 6）列表。单元 6 指向持有“2”的单元，和表示只包含“3”的列表的单元 7。它接着指向持有值“3”的单元 8，和指向空列表（nil）作为 cdr。在 SECD 机中，单元 0 总是暗含表示空列表，所以不需要特殊的标志值来指示空列表（只需要简单的指向单元 0）。

在列表的单元中 cdr 必须指向另一个列表的原则只是个约定。如果 car 和 cdr 二者都指向原子，则生成一个点对，通常写为如“（1 . 2）”这样。1

指令nil把一个 nil（空）指针压入栈顶

ldc把一个常量实际参数压入栈顶

ld把一个变量的值压入栈顶。这个变量是由实际参数指示的一个点对。这个点对的 car 指定级别，cdr 指定位置。所以“（1 . 3）”给出当前函数（级别 1）的第三个形式参数。

sel期望两个列表实际参数，并从栈顶弹出一个值。如果弹出的值非 nil 在执行第一个列表，否则执行第二个列表。在这些列表指针之一被作为新的C寄存器之前，保存到随后sel的指令的指针到转储上。

join从转储中弹出一个列表引用并把它作为C寄存器的新值。这个指令出现在sel的两个选择二者的结束处。

ldf接受表示函数的一个列表实际参数。它构造一个闭包（包含函数和当前环境的一个点对）并把它压入栈顶。

ap从栈顶弹出一个闭包和形式参数值的一个列表。通过安装这个闭包的环境为当前环境，把形式参数列表压在它的上面，清空栈，并设置C寄存器为这个闭包的函数指针，这样就把闭包应用于形式参数之上。S,E寄存器以前的值和C寄存器的下一个值被保存到转储上。

ret从栈顶弹出返回一个值，从转储中恢复S,E和C寄存器，并把这个返回值压入现在当前的栈顶。

dum把一个“哑元”也就是空列表压入环境列表的顶部。

rap如ap那样工作，唯一不同的是它把哑环境的出现替代为当前环境，因此使递归成为可能。

存在一些基本函数的补充指令如 car, cdr，列表构造，整数加法，I/O，等等。它们都必须从栈上取得形式参数。

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学