如何实现延续？

Question

我正在使用C语言编写的Scheme解释器.目前它使用C运行时堆栈作为自己的堆栈,这实现了实现continuation的一个小问题.我目前的解决方案是手动将C堆栈复制到堆中,然后在需要时将其复制回来.除了不是标准C之外,这种解决方案并不理想.

在C中实现Scheme的延续的最简单方法是什么？

Answer 1

Clinger,Hartheimer和Ost的文章中提供了一个很好的总结,可用于实施一流延续的策略.我建议特别关注Chez Scheme的实施.

堆栈复制并不复杂,并且有许多易于理解的技术可用于提高性能.使用堆分配的帧也相当简单,但是您需要权衡为"正常"情况创建开销,而不使用显式延续.

如果您将输入代码转换为延续传递样式(CPS),那么您可以完全消除堆栈.然而,虽然CPS很优雅,但它在前端增加了另一个处理步骤,需要进行额外的优化以克服某些性能影响.

Answer 2

我记得读过一篇可能对你有帮助的文章:切尼在MTA上 :-)

我知道的方案I的一些实现,例如SISC,在堆上分配它们的调用帧.

@ollie:如果所有的调用框都在堆上,则不需要进行提升.当然还有性能上的权衡:提升的时间,以及在堆上分配所有帧所需的开销.也许它应该是解释器中的可调运行时参数.:-P

Answer 3

如果你是从头开始,你真的应该考虑继续传递风格(CPS)转换.

好消息来源包括"LISP in small pieces"和Marc Feeley's Scheme在90分钟的演示中.

Answer 4

到目前为止,似乎没有提到Dybvig的论文.阅读是一种乐趣.基于堆的模型是最容易实现的,但基于堆栈的效率更高.忽略基于字符串的模型.

R. Kent Dybvig."计划的三种实施模式". http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

另请参阅ReadScheme.org上的实施文件. http://library.readscheme.org/page8.html

摘要如下:

本文介绍了方案编程语言的三种实现模型.第一个是基于堆的模型,在大多数Scheme实现中以某种形式使用到目前为止; 第二个是基于堆栈的新模型,在执行大多数程序时比基于堆的模型更有效; 第三个是一个新的基于字符串的模型,旨在用于Scheme的多处理器实现.

基于堆的模型在堆中分配几个重要的数据结构,包括实际参数列表,绑定环境和调用帧.

基于堆栈的模型尽可能在堆栈上分配这些相同的结构.这导致更少的堆分配,更少的内存引用,更短的指令序列,更少的垃圾收集以及更有效的内存使用.

基于字符串的模型在程序文本中分配这些结构的版本,该文本表示为符号串.在基于字符串的模型中,Scheme程序被翻译成FFP语言,专门用于支持Scheme.这种语言的程序由FFP机器直接执行,这是一台多处理器的字符串缩减计算机.

基于堆栈的模型具有直接的实用性; 它是作者Chez Scheme系统使用的模型,是Scheme的高性能实现.一旦机器实现,基于字符串的模型将有助于将Scheme作为FFP机器上FFP的高级替代品.

Answer 5

除了你到目前为止的好答案,我推荐Andrew Appel的 Compiling with Continuations.它编写得很好,虽然没有直接处理C,但它是编译器编写者非常好的想法的来源.

鸡肉维基也有你会发现非常有趣的页面,例如 内部结构和编译过程(其中CPS用编译的实际例子来解释).

Answer 6

传统方式是使用setjmp和longjmp,虽然有一些警告.

这是一个相当不错的解释

Answer 7

您可以看到的示例有:Chicken(一个Scheme实现,用C语言编写,支持continuation); Paul Graham的On Lisp - 在那里他创建了一个CPS变换器来实现Common Lisp中的一系列延续; 和Weblocks - 一个基于延续的Web框架,它还在Common Lisp中实现了有限形式的延续.

Answer 8

延续不是问题:您可以使用CPS实现具有常规高阶函数的那些.天真堆栈分配的问题是尾部调用永远不会被优化,这意味着你不能成为方案.

将方案的意大利面条堆栈映射到堆栈上的最佳方法是使用trampolines:基本上是额外的基础设施来处理非C类调用和退出程序.参见Trampolined Style(ps).

有一些代码说明了这两种想法.

Answer 9

连续性基本上由堆栈的保存状态和上下文切换点处的CPU寄存器组成.至少,您不必在切换时将整个堆栈复制到堆中,您只能重定向堆栈指针.

使用光纤可以简单地实现连续性.http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 .唯一需要仔细封装的事情是参数传递和返回值.

在Windows中,光纤使用CreateFiber/SwitchToFiber系列调用完成.在符合Posix的系统中,可以使用makecontext/swapcontext完成.

boost :: coroutine有一个C++协程的工作实现,可以作为实现的参考点.