recursion - 如何实现 "stackless"解释型语言？

Question

我正在制作自己的类 Lisp 解释型语言，我想做尾调用优化。我想将我的解释器从 C 堆栈中解放出来，这样我就可以管理我自己的函数到函数的跳转以及我自己的堆栈魔术来实现 TCO。 (我真的不是指无堆栈本身，只是调用不会将帧添加到 C 堆栈的事实。我想使用我自己的堆栈，它不会随着尾调用而增长)。像 Stackless Python，不像 Ruby 或……我猜是标准 Python。

但是，由于我的语言是 Lisp 的衍生语言，所有 s-表达式的计算目前都是递归完成的(因为这是我想到的执行这种非线性、高度分层过程的最明显的方法)。我有一个 eval 函数，它在每次遇到函数调用时调用一个 Lambda::apply 函数。 apply 函数然后调用 eval 来执行函数体，依此类推。 Mutual stack-hungry non-tail 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 吗？ longjmp，也许？我真的不知道。请耐心等待，我主要是自学(互联网-)编程。

Answer 1

一种解决方案有时被称为“蹦床式”。 trampoline 是一个顶层循环，它分派(dispatch)给在返回之前执行一些小步骤计算的小函数。

我在这里坐了将近半个小时，试图设计一个好的、简短的例子。不幸的是，我不得不做一些没有帮助的事情，然后将您发送到一个链接:

http://en.wikisource.org/wiki/Scheme:_An_Interpreter_for_Extended_Lambda_Calculus/Section_5

这篇论文名为“方案:扩展 Lambda 演算的解释器”，第 5 节使用过时的 Lisp 方言实现了一个工作方案解释器。秘诀在于他们如何使用 **CLINK** 而不是堆栈。其他全局变量用于在实现函数之间传递数据，例如 CPU 的寄存器。我会忽略 **QUEUE**、**TICK** 和 **PROCESS**，因为它们处理线程和假中断。 **EVLIS** 和 **UNEVLIS** 专门用于评估函数参数。未计算的 args 存储在 **UNEVLIS** 中，直到它们被计算并输出到 **EVLIS** 中。

需要注意的功能，附上一些小提示:

MLOOP:MLOOP 是解释器的主循环，或“蹦床”。忽略 **TICK**，它唯一的工作就是调用 **PC** 中的任何函数。一遍又一遍。

SAVEUP:SAVEUP将所有的寄存器cons到**CLINK**，这和C在函数调用前将寄存器存入栈基本相同。 **CLINK** 实际上是解释器的“延续”。 (continuation 只是计算的状态。保存的堆栈帧在技术上也是 continuation。因此，一些 Lisps 将堆栈保存到堆中以实现 call/cc。)

RESTORE:RESTORE 恢复保存在 **CLINK** 中的“寄存器”。它类似于在基于堆栈的语言中恢复堆栈帧。所以，它基本上是“返回”，除了一些函数明确地将返回值插入**VALUE**。 (**VALUE** 显然不会被 RESTORE 破坏。)另请注意，RESTORE 并不总是 返回调用函数。有些函数实际上会保存一个全新的计算，而 RESTORE 会很高兴地“恢复”。

AEVAL:AEVAL 是 EVAL 函数。

EVLIS:EVLIS 的存在是为了评估函数的参数，并将函数应用于这些参数。为了避免递归，它保存了 EVLIS-1。如果代码是递归编写的，EVLIS-1 将只是函数应用程序之后的常规旧代码。但是，为了避免递归，和堆栈，它是一个单独的“continuation”。

希望对您有所帮助。我只是希望我的回答(和链接)更短。