如何实现一种“无堆栈"的解决方案?解释语言? [英] 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，也许吗?我真的不知道请多多包涵，我主要是通过编程自学(Internet-).

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.

推荐答案

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

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 /a>

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

该论文被称为方案:扩展Lambda演算的解释器"，第5节在Lisp的一种过时的方言中实现了一个工作方案解释器.秘诀在于他们如何使用** CLINK **而不是堆栈.其他全局变量用于在实现功能(如CPU的寄存器)之间传递数据.我会忽略** QUEUE **，** TICK **和** PROCESS **，因为它们处理线程和伪中断. ** EVLIS **和** UNEVLIS **特别用于评估函数参数.未评估的参数会存储在** 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的存在是为了评估函数的参数，并将函数应用于这些args.为避免递归，它会保存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屋！