如何实施延续?

uanimi 发布于 2018-03-09 c 最后更新 2018-03-09 01:06 559 浏览

我正在研究用C语言编写的Scheme解释器。目前它使用C运行时堆栈作为它自己的堆栈,这对于实现延续提出了一个小问题。我目前的解决方案是将C堆栈手动复制到堆,然后在需要时将其复制回来。除了不是标准的C,这个解决方案并不理想。 在C中实现Scheme的延续最简单的方法是什么?

已邀请:

xsint

赞同来自:

改为使用显式堆栈。

eomnis

赞同来自:

我记得阅读了一篇可能对您有所帮助的文章: Cheney on the M.T.A. :-) Scheme I知道的一些实现,例如SISC,在堆上分配它们的调用帧。 @ollie:如果所有的呼叫帧都在堆上,则不需要进行提升。当然,在性能方面存在折衷:提升的时间,与分配堆中所有帧所需的开销。也许它应该是解释器中的可调参数。 :-P

zvelit

赞同来自:

帕特里克是正确的,唯一可以做到这一点的方法是在解释器中使用显式堆栈,并在需要转换为延续时将相应的堆栈段提升到堆中。 这与为支持它们的语言支持闭包(闭包和连续有些相关)所需的基本相同。

baut

赞同来自:

传统的方式是使用setjmplongjmp,虽然有一些注意事项。 这是一个reasonably good explanation

sest

赞同来自:

Implementation Strategies for First-Class Continuations是Clinger,Hartheimer和Ost的一篇文章,其中有一篇很好的总结。我建议特别关注Chez计划的实施。 堆栈复制并不那么复杂,并且有许多可以提高性能的众所周知的技术。使用堆分配的框架也相当简单,但是您在为“正常”情况创建开销时进行了权衡,因为您不使用明确的延续。 如果您将输入代码转换为延续传球样式(CPS),那么您可以完全消除堆叠。然而,尽管CPS非常优雅,但它在前端增加了另一个处理步骤,并需要额外的优化来克服某些性能影响。

zvelit

赞同来自:

你可以看到的例子有:Chicken(一个用C编写的支持延续的Scheme实现); Paul Graham的On Lisp - 他创建了一个CPS变换器来实现Common Lisp中的延续子集;和Weblocks - 一个基于延续的Web框架,它也实现了Common Lisp中有限的延续形式。

verror

赞同来自:

如果你从头开始,你应该着眼于持续传递风格(CPS)转换。 良好的来源包括“小块LISP”和Marc Feeley's Scheme in 90 minutes presentation

pquis

赞同来自:

持续不是问题:您可以使用CPS实现具有常规高阶功能的那些功能。天真堆栈分配的问题是,尾部调用永远不会被优化,这意味着你不能成为方案。 将方案的意大利面条栈映射到堆栈上的最佳方法是使用蹦床:本质上是额外的基础设施来处理非C类调用并退出程序。请参阅Trampolined Style (ps)。 有some code说明这些想法。

adolor

赞同来自:

持续性基本上由上下文切换点处堆栈和CPU寄存器的保存状态组成。至少在切换时不必将整个堆栈复制到堆中,只能重定向堆栈指针。 使用光纤实现连续性。 http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 。唯一需要仔细封装的是参数传递和返回值。 在Windows中,光纤使用CreateFiber/SwitchToFiber系列调用完成。 在Posix兼容系统中,可以使用makecontext/swapcontext完成。 boost :: coroutine有一个可用作C++协程的工作实现,可以作为实现的参考点。

xnobis

赞同来自:

除了迄今为止所得到的好的答案,我还是建议Andrew Appel的Compiling with Continuations。它编写得非常好,虽然没有直接处理C,但它是编译器编写者非常好的想法的源泉。 鸡维基也有你会发现非常有趣的页面,比如internal structurecompilation process(其中CPS用一个实际编译的例子来解释)。

vfugit

赞同来自:

看来Dybvig的论文迄今尚未提及。 阅读是一种乐趣。基于堆的模型 是最容易实现的,但是基于堆栈 效率更高。忽略基于字符串的模型。 R. Kent Dybvig。 “三项计划实施模式”。 http://www.cs.indiana.edu/~dyb/papers/3imp.pdf 还请阅读ReadScheme.org上的实施文章。 http://library.readscheme.org/page8.html 摘要如下:

This dissertation presents three implementation models for the Scheme Program- ming Language. The rst is a heap-based model used in some form in most Scheme implementations to date; the second is a new stack-based model that is considerably more ecient than the heap-based model at executing most programs; and the third is a new string-based model intended for use in a multiple-processor implementation of Scheme. The heap-based model allocates several important data structures in a heap, including actual parameter lists, binding environments, and call frames. The stack-based model allocates these same structures on a stack whenever possible. This results in less heap allocation, fewer memory references, shorter instruction sequences, less garbage collection, and more ecient use of memory. The string-based model allocates versions of these structures right in the program text, which is represented as a string of symbols. In the string-based model, Scheme programs are translated into an FFP language designed specically to support Scheme. Programs in this language are directly executed by the FFP machine, a multiple-processor string-reduction computer. The stack-based model is of immediate practical benet; it is the model used by the author's Chez Scheme system, a high-performance implementation of Scheme. The string-based model will be useful for providing Scheme as a high-level alternative to FFP on the FFP machine once the machine is realized.

tvelit

赞同来自:

正如soegaard指出的那样,主要参考仍然是this one 这个想法是,一个延续是一个封闭,保持其评估控制堆栈。为了从使用call/cc创建延续的那一刻起继续进行评估,需要使用控制堆栈。 通常调用延续会导致很长的执行时间,并使用重复的堆栈填充内存。我写了这个愚蠢的代码来证明,在mit-scheme中它使计划崩溃, 该代码总计前1000个号码1+2+3+...+1000

(call-with-current-continuation 
 (lambda (break)
   ((lambda (s) (s s 1000 break))
    (lambda (s n cc)
      (if (= 0 n)
          (cc 0)
          (+ n
             ;; non-tail-recursive,
             ;; the stack grows at each recursive call
             (call-with-current-continuation
              (lambda (__)
                (s s (- n 1) __)))))))))
如果您从1000转换到100 000,代码将花费2秒钟,如果您增加输入数字,它将会崩溃。