如何实现“无堆栈”架构？解释性语言？

发布于 2024-11-07 02:41:40 字数 908 浏览 0 评论 0原文

我正在制作自己的类似 Lisp 的解释语言，并且我想做尾部调用优化。我想将我的解释器从 C 堆栈中解放出来，这样我就可以管理自己从一个函数到另一个函数的跳转以及我自己的堆栈魔法来实现 TCO。（我实际上并不是指无堆栈本身，只是调用不会将帧添加到 C 堆栈这一事实。我想使用我自己的堆栈，该堆栈不会随着尾部调用而增长）。就像 Stackless Python，与 Ruby 或……我猜是标准 Python 不同。

但是，由于我的语言是 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 吗？也许是longjmp？我真的不知道。请耐心听我说，我的编程大部分是自学（互联网）的。

原文

I am making my own Lisp-like interpreted language, and I want to do tail call optimization. I want to free my interpreter from the C stack so I can manage my own jumps from function to function and my own stack magic to achieve TCO. (I really don't mean stackless per se, just the fact that calls don't add frames to the C stack. I would like to use a stack of my own that does not grow with tail calls). Like Stackless Python, and unlike Ruby or... standard Python I guess.

But, as my language is a Lisp derivative, all evaluation of s-expressions is currently done recursively (because it's the most obvious way I thought of to do this nonlinear, highly hierarchical process). I have an eval function, which calls a Lambda::apply function every time it encounters a function call. The apply function then calls eval to execute the body of the function, and so on. Mutual stack-hungry non-tail C recursion. The only iterative part I currently use is to eval a body of sequential s-expressions.

(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??

So, how do I avoid using C recursion? Or can I use some kind of goto that jumps across c functions? longjmp, perhaps? I really don't know. Please bear with me, I am mostly self- (Internet- ) taught in programming.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

℉絮湮 2024-11-14 02:41:40

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

我在这里坐了将近半个小时，试图设计一个好的、简短的例子。不幸的是，我必须做无益的事情并将您发送到链接：

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

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

需要注意的函数，还有一些小注释：

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

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

RESTORE：RESTORE 恢复保存时的“寄存器”在 **CLINK** 中。它类似于在基于堆栈的语言中恢复堆栈帧。所以，它基本上是“返回”，除了某些函数明确地将返回值粘贴到 **VALUE** 中。（**VALUE** 显然不会被 RESTORE 破坏。）还要注意，RESTORE 并不总是必须返回到调用函数。有些函数实际上会保存一个全新的计算，RESTORE 会很高兴地“恢复”。

AEVAL：AEVAL 是EVAL 函数。

EVLIS：EVLIS 的存在是为了评估函数的参数，并将函数应用于这些参数。为了避免递归，它保存了 EVLIS-1。如果代码是递归编写的，那么 EVLIS-1 在函数应用之后将只是常规的旧代码。然而，为了避免递归，和堆栈一样，它是一个单独的“延续”。

我希望我能帮上一些忙。我只是希望我的答案（和链接）更短。

One solution is what is sometimes called "trampolined style". The trampoline is a top-level loop that dispatches to small functions that do some small step of computation before returning.

I've sat here for nearly half an hour trying to contrive a good, short example. Unfortunately, I have to do the unhelpful thing and send you to a link:

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

The paper is called "Scheme: An Interpreter for Extended Lambda Calculus", and section 5 implements a working scheme interpreter in an outdated dialect of Lisp. The secret is in how they use the **CLINK** instead of a stack. The other globals are used to pass data around between the implementation functions like the registers of a CPU. I would ignore **QUEUE**, **TICK**, and **PROCESS**, since those deal with threading and fake interrupts. **EVLIS** and **UNEVLIS** are, specifically, used to evaluate function arguments. Unevaluated args are stored in **UNEVLIS**, until they are evaluated and out into **EVLIS**.

Functions to pay attention to, with some small notes:

MLOOP: MLOOP is the main loop of the interpreter, or "trampoline". Ignoring **TICK**, its only job is to call whatever function is in **PC**. Over and over and over.

SAVEUP: SAVEUP conses all the registers onto the **CLINK**, which is basically the same as when C saves the registers to the stack before a function call. The **CLINK** is actually a "continuation" for the interpreter. (A continuation is just the state of a computation. A saved stack frame is technically continuation, too. Hence, some Lisps save the stack to the heap to implement call/cc.)

RESTORE: RESTORE restores the "registers" as they were saved in the **CLINK**. It's similar to restoring a stack frame in a stack-based language. So, it's basically "return", except some function has explicitly stuck the return value into **VALUE**. (**VALUE** is obviously not clobbered by RESTORE.) Also note that RESTORE doesn't always have to return to a calling function. Some functions will actually SAVEUP a whole new computation, which RESTORE will happily "restore".

AEVAL: AEVAL is the EVAL function.

EVLIS: EVLIS exists to evaluate a function's arguments, and apply a function to those args. To avoid recursion, it SAVEUPs EVLIS-1. EVLIS-1 would just be regular old code after the function application if the code was written recursively. However, to avoid recursion, and the stack, it is a separate "continuation".

I hope I've been of some help. I just wish my answer (and link) was shorter.

回复收藏 0 原文

清醇 2024-11-14 02:41:40

您正在寻找的内容称为继续传递样式。这种风格向每个函数调用添加一个附加项（如果您愿意，您可以将其视为参数），指定要运行的下一个代码位（延续 k code> 可以被认为是一个带有单个参数的函数）。例如，您可以在 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。

What you're looking for is called continuation-passing style. This style adds an additional item to each function call (you could think of it as a parameter, if you like), that designates the next bit of code to run (the continuation k can be thought of as a function that takes a single parameter). For example you can rewrite your example in CPS like this:

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

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

(f 1 2 print)

The implementation of + will compute the sum of x and y, then pass the result to k sort of like (k sum).

Your main interpreter loop then doesn't need to be recursive at all. It will, in a loop, apply each function application one after another, passing the continuation around.

It takes a little bit of work to wrap your head around this. I recommend some reading materials such as the excellent SICP.

回复收藏 0 原文