7

我正在根据 Wikipedia 上的描述用 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) 究竟发生了什么？我发现 Wikipedia 的定义有点模棱两可，并且找不到任何其他可以很好地解释它的东西。

4

3 回答 3

8

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

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

'letrec' 与 'let' 不同，因为您可以“看到”定义递归函数的环境，因此您可以递归调用它（例如，您定义一个“阶乘”函数，然后可以调用它函数体）。

RAP 通过调用 rplaca（类似于 Scheme 中的 setcar!）来修改环境。之前的 DUM 指令向环境中添加了一辆“虚拟”汽车（从未使用过），RAP 会在环境中移除这个“虚拟”“汽车”并用适当的汽车替换它。

状态转换是这样的：

((c'.e')vs) e (AP.c) d =>
NIL (ve') c' (se cd)

((c'.e')vs) (?.e) (RAP.c) d =>
NIL (setcar!e',v) c' (se cd)

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

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

和

当尝试在 Erlang 中实现 RAP 时，我被卡住了，因为列表上没有破坏性操作。不在标准 API 中，似乎也不在系统 API 中。所以，Erlang SECD 看起来不错，只是它没有运行。
于 2011-10-02T06:32:53.583 回答
4

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

于 2011-10-02T17:21:42.947 回答
2

除了出色的公认答案之外，我还想提供更多关于为什么rap需要的解释。

环境（Ein SECD）存储所有持久化的实体（函数、常量、变量等）。E本质上是一堆列表。中的东西E被加载到堆栈上S，然后由 .中的命令执行或使用C。中的所有E内容都有一个 id，以便以后可以引用。此 ID 通常是一个 tuple (x,y)，其中x表示列表在堆栈上的y位置，并表示该列表中的位置。

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

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

于 2016-10-19T13:25:43.960 回答