如何实现“无堆栈"?解释语言? [英] How does one implement a "stackless" interpreted language?

问题描述

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

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.

但是，由于我的语言是 Lisp 派生的，所以当前对 s 表达式的所有求值都是递归完成的(因为这是我想到的最明显的方式来完成这个非线性、高度分层的过程).我有一个 eval 函数，每次遇到函数调用时都会调用 Lambda::apply 函数.apply 函数然后调用 eval 来执行函数体，以此类推.相互渴望堆栈的非尾 C 递归.我目前使用的唯一迭代部分是评估一组连续的 s 表达式.

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

那么，如何避免使用 C 递归呢?或者我可以使用某种跳转到 c 函数的 goto 吗?longjmp，也许?我真的不知道.请多多包涵，我主要是自学(互联网)编程.

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.

推荐答案

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

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

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

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 是解释器的主循环，或蹦床".忽略**TICK**，它唯一的工作就是调用**PC** 中的任何函数.一遍又一遍.

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 将所有寄存器保存到**CLINK**，这与 C 在函数调用之前将寄存器保存到堆栈中的情况基本相同.**CLINK** 实际上是解释器的延续".(延续只是计算的状态.保存的堆栈帧在技术上也是延续.因此，一些 Lisps 将堆栈保存到堆以实现 call/cc.)

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 恢复寄存器"，因为它们保存在 **CLINK** 中.这类似于在基于堆栈的语言中恢复堆栈帧.因此，它基本上是返回"，除了某些函数已明确地将返回值固定在 **VALUE** 中.(**VALUE** 显然不会被 RESTORE 破坏.)还要注意 RESTORE 并不总是必须返回到调用函数.有些函数实际上会保存一个全新的计算，而 RESTORE 会很高兴地恢复".

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 是 EVAL 函数.

AEVAL: AEVAL is the EVAL function.

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

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.

这篇关于如何实现“无堆栈"?解释语言?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！