1. 首页
  2. 问答
  3. 如何实现延续？

如何实现延续？

2008-08-09 41 views
47

我正在研究用C语言编写的Scheme解释器。目前它使用C运行时栈作为它自己的栈，这对于实现延续提出了一个小问题。我目前的解决方案是将C堆栈手动复制到堆，然后在需要时将其复制回来。除了不是标准的C，这个解决方案并不理想。如何实现延续？

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

来源

2008-08-09 Kyle Cronin

回答

17

我记得看过一篇文章说可能是帮助你：Cheney on the M.T.A. :-)

方案的一些实施方案，我知道的，比如SISC，在堆上分配他们的呼叫帧。

@ollie：如果所有呼叫帧都在堆上，则不需要进行提升。当然，在性能方面存在折衷：提升的时间，与分配堆中所有帧所需的开销。也许它应该是解释器中的可调参数。 :-P

来源

2008-08-09 02:49:25

1

改为使用显式堆栈。

来源

2008-08-09 01:29:33 Patrick

+4

-1：显式堆栈是什么？一个堆分配的数据结构建模一个堆栈？堆分配的数据结构模拟堆用法的历史？问题的相关性？ – 2009-12-26 18:11:22

1

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

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

来源

2008-08-09 02:55:01 olliej

+0

但是，为了支持关闭，你不能只是做拉姆达？ – apg 2008-10-01 17:25:06

28

一个很好的总结，请在Implementation Strategies for First-Class Continuations，由克林格，Hartheimer，和OST的文章。我建议特别关注Chez计划的实施。

堆栈复制并不那么复杂，并且有许多可以提高性能的众所周知的技术。使用堆分配的框架也相当简单，但是您要为“正常”情况创建开销的权衡，因为您不使用显式延续。

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

来源

2008-08-31 05:02:30

7

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

来源

2008-09-25 17:59:39

12

如果你从头开始，你真的应该看看延续传递风格（CPS）转换。

良好的来源包括“小块LISP”和Marc Feeley's Scheme in 90 minutes presentation。

来源

2008-12-05 08:00:30

+0

Queinnec的书Lisp In Small Pieces *是*可用的（至少在Paracampus的法文版中） – 2016-01-30 12:20:02

7

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

目前最好的方法映射方案的面条栈到堆栈中使用的蹦床：基本上是额外的基础设施，以处理程序的非类C调用和退出。见Trampolined Style (ps)。

有some code说明这两种想法。

来源

2009-12-03 13:04:35

5

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

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

在Windows中的纤维使用CreateFiber/SwitchToFiber家庭电话来完成的。在POSIX兼容的系统 它可以与makecontext/swapcontext来完成。

的boost ::协程具有协同程序为C++，可以作为一个参考点为执行工作落实。

来源

2010-01-04 10:33:52

+2

*琐碎的实现...需要仔细的封装* - 这段文字有一定的张力。通过链接到一些代码可以改进这个答案。 – 2011-04-12 18:56:58

8

而且到目前为止，你已经得到了很好的答案，我建议安德鲁阿佩尔的Compiling with Continuations。它编写得非常好，虽然没有直接处理C，但它是编译器编写者非常好的想法的来源。

鸡Wiki也有，你会发现很有趣的网页，如internal structure和compilation process（其中CPS与汇编的实际例子解释）。

来源

2010-06-08 00:25:17 Jay

+2

我很喜欢Appel的书。一个好处是你可以参考SML/NJ编译器的源代码，这是Appel在书中描述的一个非常好的活动例子。 – 2015-03-19 01:00:14

9

看来Dybvig的论点是没有提到为止。 这是一个阅读的乐趣。基于堆的模型 是最容易实现的，但基于堆栈的 更高效。忽略基于字符串的模型。

肯特·代博维格。 “三项计划实施模式”。 http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

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

摘要如下：

本文提出了三种模式以推行该计划 计划 - 明语言。第一种是基于堆的模型，在大多数Scheme实现中的某些 表单中使用;第二个是基于堆栈的新模型，在执行大多数程序时比基于堆的模型更有效;第三种是基于字符串的新型号，旨在用于Scheme的多处理器实现 。

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

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

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

基于堆栈的模型是直接实用的模型;它是由作者的Chez Scheme系统使用的 模型，实现了Scheme的高性能 。一旦机器被实现，基于字符串的模型对于 将提供Scheme作为在FFP机器 上的FFP的高级别替代方案将是有用的。

来源

2011-10-30 15:31:12 soegaard

1

正如soegaard指出，主要参考保持this one

的想法是，继续是保持它的评估控制堆栈的封闭件。为了从使用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到100000的代码将花2秒，如果你的成长输入数字，你会崩溃。

来源

2017-10-25 08:17:27 alinsoar

相关问题

 相关问题