在SECD机器中，“rap”是如何工作的？

Question

我正在使用C#编写SECD机器模拟器，参考了维基百科上的描述。我已经完成了基本操作，但是我不确定如何实现rap指令。

在维基百科上，关于rap的说明如下：

rap与ap类似，只是它用当前环境替换虚拟环境中的一个实例，从而使递归函数成为可能。

对于ap，维基百科的说明如下：

ap从堆栈中弹出一个闭包和一个参数值列表。通过将其环境作为当前环境安装到闭包中，将参数列表放在其前面，清空堆栈，并将C设置为闭包的函数指针来对参数应用闭包。将S、E的先前值和C的下一个值保存在转储中。

这是我的ap实现：

    public void ap() 
    { 
        Push(S, ref D); 
        Push(E, ref D); 
        Push(C, ref D); 
        List closure = Pop(ref S);
        List paramlist = Pop(ref S);
        E = closure.Tail;
        Push(paramlist, ref E);
        C = closure.Head;
        S = List.Nil;
    }

请注意，List是我实现的类似Lisp风格的“cons”单元。

我困惑的是rap和ap之间到底有什么区别？例如，环境寄存器（E）会发生什么事情？我发现维基百科的定义有点模糊，也没有找到其他解释得好的内容。

- cdiggins

Answer 1

SECD机器不支持尾递归，但可以构建一台支持尾递归的SECD机器（PDF）。

AP指令用于编译'let'绑定，而RAP指令用于编译'letrec'绑定。

'letrec'不同于'let'，因为你可以“看到”递归函数定义所在的环境，从而可以在函数体内递归调用它 (例如，你可以定义一个“阶乘”函数，然后在函数的主体中调用它)。

RAP通过调用rplaca（类似于Scheme中的setcar!）来修改环境。之前的DUM指令向环境添加了一个“虚拟”的car(其实是用来占位的)，而RAP会移除这个在环境里没有用的“虚拟”的car，并且替换成正确的函数名

状态转换如下:

((c'.e')v.s) e               (AP.c)  d         =>
NIL          (v.e')          c'      (s e c.d)
((c'.e')v.s) (?.e)           (RAP.c) d         =>
NIL          (setcar! e',v)  c'      (s e c.d)

另请参阅Revisiting SECD and the power of Lisp,引用:

RAP指令用于支持递归函数调用，并通过将先前创建的栈上的虚拟环境OMEGA替换为包含所有在递归作用域中可见的函数的环境来工作。规范使用RPLACA表示该替换操作，这也是我们在Lisp实现SECD时使用的操作：...

和

当我尝试在Erlang中实现RAP时，遇到了困难，因为列表上没有破坏性操作。不在标准API中，似乎在系统API中也没有找到。因此，Erlang SECD看起来很漂亮，但无法运行。

- user159987

Answer 2

你应该真的去买一本彼得·亨德森(Peter Henderson)的精彩小书“函数式编程应用和实现”。在书中，他详细地描述并构建了一个SECD机器和Lispkit Lisp。

- AshleyF

---

参考一下，这里是一个完整的 SECD 机器，用约 100 行 F# 编写，并在另外约 100 行中编译了 LispKit Lisp 和测试脚本。https://github.com/AshleyF/Lispkit/blob/master/Program.fs - AshleyF

Answer 3

除了优秀的被接受答案外，我想提供更多关于为什么需要 rap 的解释。

环境（在 SECD 中的 E）存储所有持久化实体（函数、常量、变量等）。E 本质上是一个列表的堆栈。在 E 中的内容被加载到堆栈 S 上，然后由命令在 C 中执行或使用。每个在 E 中的元素都被赋予一个 ID，以便稍后可以引用它们。这个 ID 通常是一个元组 (x, y)，其中 x 表示列表在堆栈上的位置，而 y 表示该列表中的位置。

在典型的函数调用中，一个新的列表被推送到 E 上，现在任何局部变量都可以有像 (|E|, y) 这样的 ID，其中 |E| 表示 E 的大小。但是对于递归函数来说，这是非常棘手的问题，因为随着每次函数调用，堆栈大小会增长，所以无法分配可用的局部变量 ID。

为了解决这个问题，rap 基本上做了大部分 ap 做的事情，但是它不是将一个新的列表推送到环境堆栈上，而是用新的环境列表替换头部的 E。

- Max