c - 如何实现延续？

Question

我正在研究用 C 编写的 Scheme 解释器。目前它使用 C 运行时堆栈作为自己的堆栈，这在实现延续方面存在一个小问题。我目前的解决方案是将 C 堆栈手动复制到堆中，然后在需要时将其复制回来。除了不是标准的 C 之外，这种解决方案也不是很理想。

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

score 29 · Accepted Answer

Clinger、Hartheimer 和 Ost 的文章《Implementation Strategies for First-Class Continuations 》中有一个很好的总结。我建议特别查看 Chez Scheme 的实施。

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

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

score 18 · Accepted Answer

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

我知道的一些 Scheme 实现，例如SISC，在堆上分配它们的调用帧。

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

score 14 · Accepted Answer

如果您是从头开始，您真的应该考虑继续传递样式 (CPS) 转换。

好的资源包括“LISP in smallpieces”和Marc Feeley 的 90 分钟演示方案。

score 10 · Accepted Answer

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

R. Kent Dybvig。“方案的三种实施模式”。 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 程序被翻译成专门设计用于支持 Scheme 的 FFP 语言。这种语言的程序直接由 FFP 机器执行，FFP 机器是一种多处理器字符串缩减计算机。

基于堆栈的模型具有直接的实际好处；它是作者的 Chez Scheme 系统使用的模型，是 Scheme 的高性能实现。一旦机器实现，基于字符串的模型将有助于在 FFP 机器上提供 Scheme 作为 FFP 的高级替代方案。

score 8 · Accepted Answer

除了到目前为止你得到的很好的答案，我推荐 Andrew Appel 的 Compiling with Continuations。它写得很好，虽然不直接与 C 打交道，但它是编译器编写者非常好的想法的来源。

Chicken Wiki 还有一些您会发现非常有趣的页面，例如内部结构和编译过程（其中 CPS 以编译的实际示例进行解释）。

score 7 · Accepted Answer

传统的方法是使用setjmpand longjmp，尽管有一些警告。

这是一个相当不错的解释

score 7 · Accepted Answer

您可以查看的示例有：Chicken（一个 Scheme 实现，用 C 编写，支持延续）；Paul Graham 的On Lisp - 他创建了一个 CPS 转换器来实现 Common Lisp 中的延续子集；和Weblocks - 一个基于延续的 Web 框架，它还在 Common Lisp 中实现了有限形式的延续。

score 7 · Accepted Answer

延续不是问题：您可以使用 CPS 实现具有常规高阶函数的那些。天真的堆栈分配的问题是尾调用永远不会优化，这意味着你不能计划。

当前将方案的意大利面条堆栈映射到堆栈上的最佳方法是使用蹦床：本质上是额外的基础设施来处理非 C 类调用和过程退出。参见蹦床风格 (ps)。

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

score 5 · Accepted Answer

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

使用纤维很容易实现延续。http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 。唯一需要仔细封装的是参数传递和返回值。

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

boost::coroutine 有一个适用于 C++ 的协同程序的工作实现，可以作为实现的参考点。

score 2 · Accepted Answer

正如所soegaard指出的，主要参考仍然是 R. Kent Dybvig. "Three Implementation Models for Scheme".

这个想法是，延续是保持其评估控制堆栈的闭包。控制堆栈是必需的，以便从使用创建延续的那一刻起继续评估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 秒，如果您增加输入数字，它将崩溃。

score 1 · Accepted Answer

1

请改用显式堆栈。

于 2008-08-09T01:29:33.537 回答

score 1 · Accepted Answer

帕特里克是正确的，您真正可以做到这一点的唯一方法是在解释器中使用显式堆栈，并在需要转换为延续时将适当的堆栈段提升到堆中。

这与在支持闭包的语言中支持闭包所需的基本相同（闭包和延续有些相关）。

c - 如何实现延续？

12 回答 12

Related

Reference