SECD抽象机
SECD机是有高度影响力的一种虚拟机和抽象机器，它意图用作函数式编程语言编译器的编译目标。四个字母分别表示：Stack、Environment、Control、Dump，它们是这个机器的内部寄存器。寄存器Stack、Control和Dump指向堆栈（的某种实现），而Environment指向关联数组（的某种实现）。
这个机器是第一个专门设计用来求值lambda演算表达式的机器。它最初描述于Peter J. Landin的1964年论文《表达式的机器求值》中[1]。Landin发表的描述非常抽象，留下了很多实现选择待定（就像一种操作语义）。因此SECD机经常以一种更具体的形式出现，比如Peter Henderson的LispKit Lisp编译器，它自从1980年开始发行。自此它已经被用作了一些其他的实验编译器的目标。
在1989年卡尔加里大学的研究者制作了这个机器的一个硬件实现[2]。
Landin的贡献
[编辑]D. A. Turner在2012年指出，《ALGOL 60修订报告》（Peter Naur的1963年版）规定了依据复制规则的过程调用，这避免了具有对标识符的系统性改变的变量捕获[3]。这种方法被加入到了ALGOL 60实现之中，但是在函数是头等公民的函数式编程语言之中，自由变量在调用栈上可能被错误的解引用[4]。
D. A. Turner注意到，Peter J. Landin通过他的SECD机解决了这个问题，在这个机器中函数转而通过在堆中的闭包来表示[5]。
非正式描述
[编辑]在开始求值一个表达式的时候，这个表达式被装载为控制C的唯一元素。环境E、堆栈S转储D开始时为空。
在C的求值期间，表达式被转换成具有ap（就是apply）作为唯一算符的逆波兰表示法（RPN）。例如，表达式F (G X)（一个单一的列表元素）被转变为列表X:G:ap:F:ap。
C的求值进行得类似于其他的RPN表达式。如果在C中的第一个项目是值，把它压入堆栈S。更准确的说，如果这个项目是个标识符，刚压入到堆栈的这个值，将绑定于在当前环境E中的那个标识符。如果这个项目是个抽象，则构造一个闭包来保存它的自由变量的绑定（它们在E中），并把这个闭包压入堆栈。
如果这个项目是ap，从堆栈弹出两个值并完成应用（将第一个应用于第二个）。如果应用的结果是个值，把它压入堆栈。
但是，如果应用是将一个抽象（已表示为闭包）应用于一个值，它结果的那个lambda演算表达式，自身可能就是应用（而非一个值），因而不能压入堆栈。在这种情况下，S、E和C的当前内容被压入D （它是这些三元组的堆栈），S被重新初始化为空，而C被重新初始化为这次应用的结果，具有E包含针对这个表达式的自由变量的环境，增加上对这个应用的实际参数值的绑定。求值继续如上那样进行。
求值完成由C为空来指示，在这种情况下结果在堆栈S之上。接着弹出在D上的最近保存的求值状态，并把已经完成的计算的结果压入堆栈，位于从D恢复的内容之上。恢复状态的求值继续如上那样进行。
如果C和D二者为空，则整体求值完成，结果在堆栈S之上。
寄存器和内存
[编辑]SECD机是基于堆栈的。函数从堆栈得到它们的实际参数。在指令流之中给内建指令的实际参数立即编码在它们之后。
像所有内部数据结构一样，堆栈是个列表，具有S寄存器指向列表头部或开始处。由于列表数据结构，堆栈不需要连续的内存块，所以只要有一个单一空闲内存单元，就有堆栈空间可以获得。即使在所有单元都已经使用了时候，垃圾回收可能产生额外的空闲内存。明显的，SECD结构的特定实现者可以将堆栈实现为正规的堆栈结构，从而改进这个虚拟机的整体效能，假定在这个堆栈的尺寸上施加严格限定的话。
C寄存器指向要求值的代码或指令列表的头部。一旦这里的指令已经被执行，类似于常规机器中的“指令指针”（或程序计数器），C将指向在列表中的下一个指令，除非后续指令总是在执行期间指定而不缺省的包含在后续内存位置上，如在常规机器的情况下那样。
当前变量环境由E寄存器管理，它指向一个列表的列表。每个个体列表表示一个环境层级：当前函数的那些形式参数位于这个列表的头部，在当前函数中是自由的但受到外围函数所约束的那些变量，在E的另一个元素中。
D寄存器指向转储的头部， 它被用作其他寄存器的值临时存储，比如在函数调用期间。它可以比拟于其他机器的返回堆栈。
SECD机的内存组织，类似于多数函数式语言解释器所用的模型：一些内存单元，其中每个都持有要么一个“原子”（一个单一的值比如13），要么表示一个空或非空列表。在后者情况下，这个单元持有两个到其他单元的指针，一个标识第一个个元素，而另一个标识排除第一个元素的列表。这两个指针传统上分别叫做car和cdr，但是更现代的术语是“head”和“tail”经常用作其替代。一个单元可以持有的不同类型单元，可以用通过一个标志来区别。它还区分原子的常见不同类型（整数、字符串等）。
所以，持有数字1, 2, 3的列表，通常写为(1 2 3)，可以表示为如下：
地址 标志 内容（对于整数是值，对于列表是car和cdr）
9 [ integer | 2 ]
8 [ integer | 3 ]
7 [ list | 8 | 0 ]
6 [ list | 9 | 7 ]
...
2 [ list | 1 | 6 ]
1 [ integer | 1 ]
0 [ nil ]
内存单元3到5不属于这个列表，这个列表的那些单元可以随机的分布在内存中。单元2是这个列表的头部，它指向持有第一个元素值的单元1，和只包含2和3的列表（开始于单元6）。单元6指向持有2的单元和单元7，它表示只包含3的列表。它指向包含值3的单元8，并把指向空列表（nil）作为cdr。在SECD机中，单元0总是隐含的表示空列表，所有不需要特殊的标志来指示空列表（需要做的就是简单的指向单元0）。
在列表中cdr必须指向另一个列表就是一个约定。如果car和cdr二者都指向原子，则产生一个有序对，通常写为(1 . 2)。
指令
[编辑]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：将一个虚设（dummy）即空列表，压入到环境列表之前。rap：作用如同ap，只是它将出现的虚设环境替代为当前的环境，这使得递归函数成为可能。
还存在一些用于基本函数的指令，比如car、cdr、列表构造、整数加法、I/O等。它们都从堆栈得到任何必须的实际参数。
参见
[编辑]引用
[编辑]- ^ Landin, P. J. The Mechanical Evaluation of Expressions (PDF). The Computer Journal. January 1964, 6 (4): 308–320 [2022-11-16]. doi:10.1093/comjnl/6.4.308. （原始内容存档 (PDF)于2022-11-16）.
- ^ A paper on the design, SECD: DESIGN ISSUES is available.
- ^ D. A. Turner. Some History of Functional Programming Languages (PDF). in an invited lecture TFP12, St Andrews University. 12 June 2012 [2021-02-18]. （原始内容 (PDF)存档于2020-04-15）.
Algol 60 is not normally thought of as a functional language but its rules for procedures (the Algol equivalent of functions) and variable binding were closely related to those of λ-calculus.
The Revised Report on Algol 60 (Naur 1963) is a model of precise technical writing. It defines the effect of a procedure call by a copying rule with a requirement for systematic change of identifiers where needed to avoid variable capture — exactly like β-reduction.
Although formal parameters could be declared value the default parameter passing mode was call by name, which required the actual parameter to be copied unevaluated into the procedure body at every occurrence of the formal parameter. This amounts to normal order reduction (but not graph reduction, there is no sharing). The use of call by name allowed an ingenious programming technique: Jensen’s Device. - ^ D. A. Turner. Some History of Functional Programming Languages (PDF). in an invited lecture TFP12, St Andrews University. 12 June 2012 [2021-02-18]. （原始内容 (PDF)存档于2020-04-15）.
Algol 60 allowed textually nested procedures and passing procedures as parameters (but not returning procedures as results). The requirement in the copying rule for systematic change of identifiers has the effect of enforcing static (that is lexicographic) binding of free variables.
In their book “Algol 60 Implementation”, Randell and Russell (1964, Sect. 2.2) handle this by two sets of links between stack frames. The dynamic chain links each stack frame, representing a procedure call, to the frame that called it. The static chain links each stack frame to that of the textually containing procedure, which might be much further away. Free variables are accessed via the static chain.
This mechanism works well for Algol 60 but in a language in which functions can be returned as results, a free variable might be held onto after the function call in which it was created has returned, and will no longer be present on the stack. - ^ D. A. Turner. Some History of Functional Programming Languages (PDF). in an invited lecture TFP12, St Andrews University. 12 June 2012 [2021-02-18]. （原始内容 (PDF)存档于2020-04-15）.
Landin (1964) solved this in his SECD machine. A function is represented by a closure, consisting of code for the function plus the environment for its free variables. The environment is a linked list of name-value pairs. Closures live in the heap.
延伸阅读
[编辑]- Olivier Danvy. A Rational Deconstruction of Landin's SECD Machine （页面存档备份，存于互联网档案馆）. BRICS research report RS-04-30, 2004. ISSN 0909-0878
- Field, Anthony J. Field and Peter G. Harrison. 1988 Functional Programming. Addison-Wesley. ISBN 0-201-19249-7
- Graham, Brian T. 1992 "The SECD Microprocessor: A Verification Case Study". Springer. ISBN 0-7923-9245-0
- Henderson, Peter. 1980 Functional Programming: Application and Implementation. Prentice Hall. ISBN 0-13-331579-7
- Kogge, Peter M. The Architecture of Symbolic Computers. ISBN 0-07-035596-7
- Peter Landin. The next 700 programming languages (PDF). Comm. ACM. March 1966, 9 (3): 157–166 [2021-02-18]. doi:10.1145/365230.365257. （原始内容 (PDF)存档于2010-06-20）.