在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机器(PDF).

AP指令用于编译'let'绑定,而RAP指令用于编译'letrec'绑定.

'letrec'与'let'不同,因为你可以"看到"定义递归函数的环境,这样你就可以递归调用它(例如,你定义一个'factorial'函数,你可以调用它功能的主体).

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看起来不错,只是它没有运行.