SECD抽象机
函数式编程语言编译器目标的虚拟机
SECD 机是非常有影响的意图作为函数式编程语言编译器目标的虚拟机。SECD 分别是这个机器的内部寄存器的名字的首字母:Stack, Environment, Code, Dump。这些寄存器指向在内存中链表。
寄存器和内存
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)”这样。
指令
存在一些基本函数的补充指令如 car, cdr,列表构造,整数加法,I/O,等等。它们都必须从栈上取得形式参数。
参考资料
最新修订时间:2022-08-25 16:31
目录
概述
寄存器和内存
参考资料