如何实现延续?

c lisp scheme continuations

7336 观看

12回复

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

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

作者: Kyle Cronin 的来源 发布者: 2019 年 6 月 26 日

回应 (12)


17

决定

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

我知道的方案I的一些实现,例如SISC,在堆上分配它们的调用帧。

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

作者: Chris Jester-Young 发布者: 09.08.2008 02:49

28

Clinger,Hartheimer和Ost的文章中提供了一个很好的总结,可用于实施一流延续的策略。我建议特别关注Chez Scheme的实施。

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

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

作者: Josh Segall 发布者: 31.08.2008 05:02

12

如果你是从头开始,你真的应该考虑继续传递风格(CPS)转换。

好消息来源包括“LISP in small pieces”和Marc Feeley's Scheme在90分钟的演示中

作者: Joel Borggrén-Franck 发布者: 05.12.2008 08:00

9

到目前为止,似乎没有提到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而设计的FFP语言。这种语言的程序由FFP机器直接执行,这是一台多处理器的字符串缩减计算机。

基于堆栈的模型具有直接的实际效益; 它是作者Chez Scheme系统使用的模型,是Scheme的高性能实现。一旦机器实现,基于字符串的模型将有助于将Scheme作为FFP机器上FFP的高级替代品。

作者: soegaard 发布者: 30.10.2011 03:31

8

除了你到目前为止的好答案,我推荐Andrew Appel的 Compiling with Continuations。它编写得很好,虽然没有直接处理C,但它是编译器编写者非常好的想法的来源。

鸡肉维基也有你会发现非常有趣的页面,例如 内部结构编译过程(其中CPS用编译的实际例子来解释)。

作者: Jay 发布者: 08.06.2010 12:25

7

您可以看到的示例有:Chicken(一个Scheme实现,用C语言编写,支持continuation); Paul Graham的On Lisp - 在那里他创建了一个CPS变换器来实现Common Lisp中的一系列延续; 和Weblocks - 一个基于延续的Web框架,它还在Common Lisp中实现了有限形式的延续。

作者: Kyle Burton 发布者: 25.09.2008 05:59

7

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

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

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

作者: Charles Stewart 发布者: 03.12.2009 01:04

7

传统方式是使用setjmplongjmp,虽然有一些警告。

这是一个相当不错的解释

作者: Thomas Vander Stichele 发布者: 28.08.2008 10:05

5

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

使用光纤可以简单地实现连续性。http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 。唯一需要仔细封装的事情是参数传递和返回值。

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

boost :: coroutine有一个C ++协程的工作实现,可以作为实现的参考点。

作者: Stefan Dragnev 发布者: 04.01.2010 10:33

2

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

这个想法是,延续是一个保持其评估控制堆栈的闭包。需要控制堆栈才能从使用创建延续的那一刻开始继续评估call/cc

通常调用continuation会占用很长时间,并使用重复的堆栈填充内存。我写了这个愚蠢的代码来证明,在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秒,如果您增加输入数字,它将崩溃。

作者: alinsoar 发布者: 25.10.2017 08:17

1

请改用显式堆栈。

作者: Patrick 发布者: 09.08.2008 01:29

1

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

这基本上与支持它们的语言中的闭包所需的相同(闭包和延续有些相关)。

作者: olliej 发布者: 09.08.2008 02:55
32x32