logo标签列表

如何实现continuations？

clispschemecontinuations
54

我正在开发一个用C语言编写的Scheme解析器。目前，它使用C运行时栈作为自己的栈，这在实现continuations时会出现一些小问题。我目前的解决方案是手动将C堆栈复制到堆上，然后在需要时再将其复制回来。除了不符合标准C之外，这个解决方案也远非理想。

在C语言中，如何最简单地实现Scheme的continuations?

12个回答
30

一篇很好的摘要被列出在Implementation Strategies for First-Class Continuations这篇文章中，作者是Clinger、Hartheimer和Ost。建议特别关注Chez Scheme的实现。

栈复制并不复杂，有很多技术可以提高性能。使用堆分配帧也相对简单，但你需要在“正常”情况下创建开销，即没有使用显式 continuation 的情况。

如果将输入代码转换为 continuation passing style (CPS)，则可以完全消除堆栈。然而，虽然 CPS 很优雅，但它会在前端增加另一个处理步骤，并需要额外的优化来克服某些性能影响。

19

我记得阅读过一篇可能对你有所帮助的文章：关于M.T.A.的Cheney文章 :-)

我知道一些Scheme的实现，比如SISC，会在堆上分配它们的调用框架。

@ollie: 如果所有的调用框架都在堆上分配，那么你就不需要进行提升。当然，这涉及到性能方面的权衡：提升所需的时间与在堆上分配所有框架所需的开销之间的平衡。也许这应该是解释器中可调节的运行时参数。:-P

15
Queinnec的书《Lisp In Small Pieces》是可以获取的（至少在其法语版Paracampus出版社有售）。 - Basile Starynkevitch
10

目前为止，似乎还没有提到Dybvig的论文。这是一篇令人愉悦的阅读。基于堆的模型最容易实现，但基于栈的模型更有效率。忽略基于字符串的模型。

R. Kent Dybvig. "Scheme的三种实现模型"。 http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

还可以查看ReadScheme.org上的实现论文。 https://web.archive.org/http://library.readscheme.org/page8.html

摘要如下：

这篇论文介绍了Scheme编程语言的三种实现模型。第一种是基于堆的模型，迄今为止大多数Scheme实现中都使用了这种模型; 第二种是一种新的基于栈的模型，比基于堆的模型在执行大多数程序时效率更高; 第三种是一种新的基于字符串的模型，旨在用于Scheme的多处理器实现。基于堆的模型在堆中分配了几个重要的数据结构，包括实际参数列表、绑定环境和调用帧。基于栈的模型在尽可能情况下在栈上分配这些相同的结构。这导致较少的堆分配、较少的内存引用、较短的指令序列、较少的垃圾收集和更有效的内存使用。基于字符串的模型直接在程序文本中（表示为符号字符串）分配这些结构的版本。在基于字符串的模型中，Scheme程序被翻译成一种名为FFP的语言，该语言专门设计用于支持Scheme。在FFP机器上，这种语言的程序将直接由FFP机器执行，FFP机器是一台多处理器字符串约简计算机。基于栈的模型具有直接实用价值，它是作者的Chez Scheme系统所使用的模型，这是Scheme的高性能实现。基于字符串的模型将有助于在FFP机器上提供Scheme作为高级替代方案，一旦该机器实现。
8
除了你已经得到的好答案，我推荐阅读Andrew Appel的 Compiling with Continuations。它写得非常好，虽然没有直接涉及C语言，但对于编译器编写者来说是一个非常好的创意来源。
Chicken Wiki也有一些页面非常有趣，比如 internal structure和 compilation process（其中用一个实际的编译示例解释了CPS）。
2
我非常喜欢Appel的书。一个额外的好处是，你可以参考SML/NJ编译器的源代码，这是一个相当不错的实例，展示了Appel在书中所描述的过程。 - Nate C-K
7

Continuations不是问题：使用CPS可以使用常规高阶函数实现这些。天真的堆栈分配的问题在于尾调用从未被优化，这意味着您无法成为scheme。

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

有一些代码说明这两个想法。

7
你可以参考以下示例：Chicken（一个用C编写的Scheme实现，支持continuation）；Paul Graham的On Lisp - 在其中他创建了一个CPS变换器来实现Common Lisp中的continuations的子集；以及Weblocks - 一种基于continuation的Web框架，它也在Common Lisp中实现了一种有限的continuation形式。
1
请问你指的是《On Lisp》的哪一章？ - Will Ness
第20章是关于Continuations的 - 具体来说是20.3。 - Kyle Burton
7
传统的方法是使用setjmp和longjmp，但是存在注意事项。
这里有一个合理的解释。
5

Continuations（续体）基本上包括在上下文切换点处的堆栈和CPU寄存器的保存状态。至少，在切换时，您不必将整个堆栈复制到堆中，只需重定向堆栈指针即可。

使用Fiber可以轻松实现continuations。参考：http://en.wikipedia.org/wiki/Fiber_%28computer_science%29。唯一需要仔细封装的是参数传递和返回值。

在Windows中，可以使用CreateFiber/SwitchToFiber族调用来执行Fiber。在符合Posix标准的系统中，可以使用makecontext/swapcontext实现。

boost::coroutine提供了一个C ++协程的工作实现，可以作为实现的参考点。

2
“trivially implemented ... needs careful encapsulation” - 这段话存在一定的紧张感。如果附上代码链接，这个答案会更好。 - Charles Stewart
2
正如 soegaard 所指出的那样，主要参考文献仍然是 R. Kent Dybvig. "Three Implementation Models for Scheme"。
思路是，一个 continuation 是一个闭包，它保留了它的评估控制栈。控制栈是必需的，以便从使用 call/cc 创建 continuation 的那一刻开始继续评估。
经常调用 continuation 会使执行时间很长，并且用重复的栈填充内存。我写了这个愚蠢的代码来证明，在 mit-scheme 中，它会导致 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增加到100000，代码将需要2秒钟才能完成，而且如果你增加输入的数字，它将会崩溃。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接