如何实现一个“无栈”解释型语言？

Question

我正在制作一个类似Lisp的解释型语言，并希望进行尾调用优化。 我想从C堆栈中释放我的解释器，以便我可以管理自己的从函数到函数的跳转以及自己的堆栈魔法以实现TCO。（我并不是指无栈，只是调用不会向C堆栈添加帧。我想使用自己的堆栈，它不会随着尾部调用而增长）。就像 Stackless Python 一样，与 Ruby 或标准 Python 不同。

然而，由于我的语言是 Lisp 的衍生物，所有 s 表达式的评估目前都是递归完成的（因为这是我想到的最明显的方法来处理这个非线性、高度分层的过程）。我有一个 eval 函数，每次遇到函数调用时都会调用 Lambda::apply 函数。然后 apply 函数调用 eval 来执行函数体等操作。相互递归的堆栈消耗非常大。我目前唯一使用的迭代部分是对连续 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吗？我真的不知道。请耐心等待，我大部分是自学编程（通过互联网）。

- salvador p

Answer 1

一种解决方案是所谓的"跳板风格"。跳板是一个顶级循环，调度到执行一些小步骤计算并返回的小函数。

我坐在这里将近半个小时，试图构思一个好的、简短的例子。不幸的是，我只能以不太有帮助的方式为您发送一个链接：

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

这篇论文名为“Scheme: An Interpreter for Extended Lambda Calculus”，第5节实现了一个工作中的scheme解释器，使用了一个过时的lisp方言中的**CLINK**而不是栈。其他全局变量用于在实现函数之间传递数据，就像CPU的寄存器一样。建议忽略**QUEUE**、**TICK**和**PROCESS**，因为它们处理线程和虚假中断。 **EVLIS**和**UNEVLIS**被特定地用于评估函数参数。未评估的参数存储在**UNEVLIS**中，直到它们被评估并放入**EVLIS**。

需要注意的函数，附上一些小笔记：

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

SAVEUP：SAVEUP将所有寄存器连同**CLINK** cons到一起，这与C在函数调用之前将寄存器保存到堆栈中基本相同。 **CLINK**实际上是解释器的“连续体”（continuation）。 （连续体只是计算状态。保存的堆栈帧也是一个连续体。因此，一些Lisp将堆栈保存到堆中以实现call/cc。）

RESTORE：RESTORE将“寄存器”还原为在**CLINK**中保存的值。类似于在基于栈的语言中还原堆栈帧。所以，它基本上就是“返回”，只不过某些函数已经明确将返回值插入了**VALUE**中。（显然，RESTORE不会破坏**VALUE**。）另外请注意，RESTORE并不总是需要返回到调用函数。有些函数实际上会SAVEUP一个全新的计算，而RESTORE会愉快地“还原”它。

AEVAL：AEVAL是EVAL函数。

EVLIS：EVLIS的存在是为了评估函数参数，并将函数应用于这些参数。为避免递归，它SAVEUPs EVLIS-1。如果代码是递归方式编写的，则在函数应用之后，EVLIS-1将变成普通的旧代码。不过，为了避免递归和堆栈，它是一个单独的“续集”。

希望我能提供一些帮助。我只希望我的回答（和链接）更加简短。

- Daniel Ralston

Answer 2

你需要的是传递续延风格。这种风格在每个函数调用中添加了一个额外的项目（如果您愿意，可以将其视为参数），该项目指定要运行的下一个代码块（续延k可以被视为一个只接受单个参数的函数）。例如，您可以像这样使用CPS重写您的示例：

(defun f (x y k)
    (a x y k))

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

(f 1 2 print)

+的实现将计算x和y的总和，然后将结果传递给k，类似于(k sum)。

然后，您的主解释器循环根本不需要是递归的。它将在循环中依次应用每个函数应用程序，并传递继续执行。

需要一点努力才能理解这一点。我建议阅读一些材料，例如优秀的SICP。

- Greg Hewgill

---

我相信这是另一种编程风格。我想要的是在我的语言中添加一个特性（即TCO），就像Scheme一样，它要求所有实现都必须具备这个特性。但还是谢谢你，我一定会稍后查看这个CPS的；我已经在维基百科上看到过它，但是没有理解其中的内容 :) - salvador p

CPS不仅仅是另一种“编程风格”（尽管在某些情况下可以使用这些想法来编写代码）。我所说的实际上是一种解释器实现技术，它可以将任何程序源转换为CPS样式，以便解释器可以轻松地执行诸如TCO之类的操作。 - Greg Hewgill

好的，经过一番研究，我发现Stackless Python过去确实使用了continuations。我会继续阅读有关CPS的资料。 - salvador p

我不认为SICP真的大量涉及CPS或CPS转换，但我可能记错了。EOPL和Lisp In Small Pieces确实涵盖了它。尽管如此，推荐SICP仍然是一个很好的建议，因为这些其他书可能对那些没有阅读过SICP或类似水平的人来说太高级了。 - okonomichiyaki

Answer 3

尾递归可以理解为在调用者当前使用的栈帧中为被调用者重复利用。因此，您可以重新设置参数并跳转到函数的开头。

- Adam

---

我们以前在Forth中这样做。当我知道一个单词将返回到一个刚刚返回的单词时，我们从堆栈中弹出返回地址，然后返回，有效地返回给调用者。它很有效。 - zumalifeguard