我正在制作自己的类似Lisp的解释语言,我想做尾部调用优化我想把我的解释器从c堆栈中解放出来,这样我就可以管理自己从一个函数到另一个函数的跳跃,以及自己的堆栈魔术来实现tco。(我真的不是指无堆栈本身,只是调用不会向c堆栈添加帧这一事实。我想用我自己的一个堆栈,它不会随着尾声而增长。就像无堆栈的Python,不像Ruby或者我猜是标准的蟒蛇。
但是,由于我的语言是lisp派生语言,所以目前对s表达式的所有求值都是递归进行的(因为这是我想到的最明显的方法来完成这个非线性、高度层次化的过程)。我有一个eval函数,每当遇到函数调用时,它都会调用lambda::apply函数。然后apply函数调用eval来执行函数体,依此类推互栈饥饿无尾C递归我目前使用的唯一迭代部分是对序列s表达式体进行求值。

(defun f (x y)
    (a x y)) ; tail call! goto instead of call.
             ; (do not grow the stack, keep return addr)

(defun a (x y)
    (+ x y))

; ...

(print (f 1 2)) ; how does the return work here? how does it know it's supposed to
                ; return the value here to be used by print, and how does it know
                ; how to continue execution here??

那么,如何避免使用C递归呢或者我可以用一种跨越c函数的goto吗?也许是龙吉普?我真的不知道请容忍我,我主要是自学(互联网)编程。

最佳答案

一种解决办法是有时被称为“蹦床风格”蹦床是一个顶级循环,在返回之前分派给执行一些小计算步骤的小函数。
我在这里坐了将近半个小时,试图想出一个好的、简短的例子不幸的是,我不得不做一些无用的事情,并发送给你一个链接:
http://en.wikisource.org/wiki/Scheme:_An_Interpreter_for_Extended_Lambda_Calculus/Section_5
本文称之为“Scheme:扩展Lambda演算的解释器”,第五节用Lisp的一种过时方言实现了一个工作方案解释器秘密在于他们如何使用“叮当”而不是堆栈。其他全局变量用于在实现函数(如cpu的寄存器)之间传递数据。我将忽略**queue**、**tick**和**process**,因为它们处理线程和伪中断。**evlis**和**unevlis**特别用于计算函数参数。未评估的参数存储在**unevlis**中,直到它们被评估并输出到**evlis**中。
需要注意的功能,附带一些小提示:
mloop:mloop是解释器的主循环,或“蹦床”。忽略**勾选**,它唯一的工作就是调用**pc**中的任何函数。一遍又一遍。
saveup:saveup将所有寄存器都保存到**clink**上,这与c在函数调用之前将寄存器保存到堆栈上基本相同。对口译员来说,**叮当声**实际上是一种“延续”。(延续只是计算的状态。保存的堆栈帧在技术上也是延续的。因此,一些lisp将堆栈保存到堆中以实现call/cc。)
还原:还原还原保存在**CLINK**中的“寄存器”这类似于在基于堆栈的语言中恢复堆栈帧所以,它基本上是“return”,只是有些函数显式地将返回值插入**value**(**VALUE**显然不受RESTORE的影响)还要注意,RESTORE并不总是必须返回到调用函数有些函数实际上会保存一个全新的计算,而restore会很高兴地“restore”。
AEVAL:AEVAL是eval函数。
EVLIS:EVLIS用于评估函数的参数,并将函数应用于这些ARG。为了避免递归,它保存EVLIS-1如果代码是递归编写的,evlis-1将只是函数应用程序之后的常规旧代码。但是,为了避免递归和堆栈,它是一个单独的“延续”。
我希望我能帮上忙。我只希望我的回答(和链接)简短些。

关于recursion - 如何实现一种“无堆栈”解释语言?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/5986058/

10-11 22:35
查看更多