关于C#：如何实施延续？

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

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

Clinger，Hartheimer和Ost的文章《一流的延续的实施策略》中有很好的摘要。我建议特别查看Chez Scheme的实施。

堆栈复制并不是那么复杂，并且有许多众所周知的技术可以用来提高性能。使用堆分配的帧也很简单，但是您需要权衡在不使用显式连续的"正常"情况下创建开销的方法。

如果将输入代码转换为延续传递样式(CPS)，则可以完全消除堆栈。但是，尽管CPS很优雅，但它在前端增加了另一个处理步骤，并且需要进行额外的优化来克服某些性能隐患。

我记得读过一篇对您可能有帮助的文章：切尼(M.T.A.) ：-)

我知道的Scheme的某些实现(例如SISC)在堆上分配其调用帧。

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

如果您是从头开始的，那么您确实应该查看Continuation Passing Style(CPS)转换。

好的资料包括90分钟演讲中的"小片段LISP"和Marc Feeley的计划。

看来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

摘要如下：

This dissertation presents three implementation models for the Scheme
Programming Language. The first 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 efficient 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 efficient 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 specifically 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 benefit; 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.

除了到目前为止您已经获得的不错的答案之外，我还建议您使用Andrew Appel的" Continuations with Continuations"。它写的很好，虽然不直接与C打交道，但却为编译器编写者提供了很多不错的主意。

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

连续性不是问题：您可以使用CPS实现具有常规高阶函数的连续性。天真的堆栈分配的问题是，尾部调用从未被优化，这意味着您不能成为方案。

将方案的意大利面条堆栈映射到堆栈上的最新最佳方法是使用蹦床：本质上是额外的基础结构，用于处理非C类的调用和过程的退出。请参见蹦床样式(ps)。

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

您可以查看的示例有：Chicken(Scheme实现，用C编写，支持延续)；保罗·格雷厄姆(Paul Graham)的《论Lisp》-在其中创建了一个CPS转换器，以在Common Lisp中实现延续的子集；和Weblocks-一个基于连续性的Web框架，该框架还在Common Lisp中实现了一种有限形式的连续性。

传统方法是使用setjmp和longjmp，尽管有一些注意事项。

这是一个很好的解释

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

使用纤维轻松实现连续化。 http://en.wikipedia.org/wiki/Fiber_(computer_science)
。唯一需要仔细封装的就是参数传递和返回值。

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

boost ::协程具有针对C的协程的有效实现，可以用作实现的参考点。

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

这个想法是，延续是一个闭包，它保留了其评估控制堆栈。为了使用call/cc。

创建延续之后的那一刻继续进行评估，需要控制堆栈。

通常调用延续会花费较长的时间，并用重复的堆栈填充内存。我写了这个愚蠢的代码来证明，在mit-scheme中，它会使方案崩溃，

代码将前1000个数字相加1+2+3+...+1000。

如果从1000切换到100000，代码将花费2秒钟，如果增加输入数字，它将崩溃。

Patrick是正确的，真正做到这一点的唯一方法是在解释器中使用显式堆栈，并在需要转换为延续时将相应的堆栈段提升到堆中。

这基本上与支持闭包的语言所需要的语言相同(闭包和延续在某种程度上是相关的)。

改为使用显式堆栈。