如何实现"无堆栈"解释语言？

Question

我正在制作自己的类似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？我真的不知道.请耐心等待,我主要是自编(Internet)教程.

Answer 1

一种解决方案是有时被称为"蹦床风格".trampoline是一个顶级循环,它调度到小函数,在返回之前执行一些小步骤的计算.

我坐在这里将近半个小时试图设计一个好的,简短的例子.不幸的是,我必须做无益的事情并发送给你一个链接:

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

该论文被称为"Scheme:扩展Lambda演算的解释器",第5节实现了一个过时的Lisp方言的工作方案解释器.秘诀在于他们如何使用**CLINK**而不是堆栈.其他全局变量用于在执行函数(如CPU的寄存器)之间传递数据.我会忽略**QUEUE**,**TICK**和**PROCESS**,因为那些涉及线程和假中断.**EVLIS**和**UNEVLIS**具体用于评估函数参数.未评估的args存储在**UNEVLIS**中,直到它们被评估并输出到**EVLIS**.

需要注意的功能,有一些小笔记:

MLOOP:MLOOP是解释器的主循环,或"蹦床".忽略**TICK**,它唯一的工作就是调用**PC**中的任何功能.一遍一遍又一遍.

SAVEUP:SAVEUP将所有寄存器都包含在**CLINK**中,这与在函数调用之前C将寄存器保存到堆栈时基本相同.**CLINK**实际上是口译员的"延续".(继续只是计算的状态.保存的堆栈帧在技术上也是连续的.因此,一些Lisps将堆栈保存到堆中以实现call/cc.)

RESTORE:RESTORE恢复"寄存器",因为它们保存在**CLINK**中.它类似于在基于堆栈的语言中恢复堆栈帧.所以,它基本上是"返回",除了一些函数已经明确地将返回值粘贴到**VALUE**中.(**VALUE**显然没有被RESTORE破坏.)另请注意,RESTORE并不总是必须返回到调用函数.一些函数实际上会保存一个全新的计算,RESTORE将很乐意"恢复".

AEVAL:AEVAL是EVAL功能.

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

我希望我能得到一些帮助.我只希望我的答案(和链接)更短.

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.

Answer 3

尾递归可以被认为是对被调用者重复使用当前用于调用者的相同堆栈帧.所以你可以重新设置参数并转到函数的开头.