在 SECD 机器中“说唱”是如何运作的？

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) 到底发生了什么？我发现维基百科的定义有点含糊，并且无法找到其他任何可以很好解释它的内容。

Answer 1

SECD 不是尾递归，尽管您可以构建尾递归 SECD 机器。

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

‘letrec’与‘let’不同，因为你可以‘看到’定义递归函数的环境，这样你就可以递归地调用它（例如，你定义了一个‘阶乘’函数，你可以调用它在函数体内）。

RAP通过调用rplaca（类似于Scheme中的setcar！）来修改环境。之前的 DUM 指令将一辆“虚拟”汽车添加到环境中（从未使用过），而 RAP 会在环境中删除此“虚拟”“汽车”，并将其替换为适当的汽车。

状态转换就像这样：

    ((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)

另请参阅重温 SECD 和 Lisp 的力量，引用：

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

和

当尝试在 Erlang 中实现 RAP 时，我陷入了困境，因为列表上没有破坏性操作。标准 API 中没有，系统 API 中似乎也没有。所以，Erlang SECD 看起来不错，只是它不能运行。

Answer 2

你真的应该读一本 Peter Henderson 的精彩小书《函数式编程应用与实现》。在其中，他精心描述并构建了一台 SECD 机器和 Lispkit Lisp。

Answer 3

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

rap

的解释。

环境（

E

中的

SECD

）存储所有持久化实体（函数、常量、变量等）。

E

本质上是一堆列表。

E

中的内容被加载到堆栈

S

中，然后由

C

中的命令执行或使用。

E

中的所有内容都会被赋予一个id，以便以后可以引用。该 ID 通常是一个元组

(x,y)

，其中

x

表示列表在堆栈上的位置，

y

表示该列表中的位置。

在典型的函数调用中，新列表被推送到

E

上，现在任何局部变量都可以具有类似

(|E|, y)

的 ID，其中

|E|

表示

E

的大小。然而，这对于递归函数来说是一个很大的问题，因为堆栈大小随着每次函数调用而增长，因此无法分配局部变量可用的 ID。

为了解决这个问题，

rap

做了

ap

所做的大部分事情，但它不是将新列表推送到环境堆栈上，而是用新环境列表替换

E

头部的任何内容。