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

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

解决方案

回答

请改用显式堆栈。

回答

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

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

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

回答

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

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

回答

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

这是一个合理的解释

回答

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

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

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

回答

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

回答

如果我们是从头开始的，那么我们确实应该研究Continuation Passing Style(CPS)转换。

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

回答

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

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

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

回答

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

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

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

boost :: coroutine具有适用于C ++的coroutine的有效实现，可以用作实现的参考点。

回答

除了到目前为止我们已经获得的好答案之外，我还建议安德鲁·阿佩尔(Andrew Appel)撰写的《续编》。它写的很好，虽然不直接与C打交道，但却为编译器作者提供了很多不错的主意。

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