14

在 1990 年代和 2000 年代,编程语言爱好者几乎没有讨论过定界延续的话题。它最近重新成为编程语言讨论中的重要内容。

我希望有人至少可以权威地说明 Rakudo 的延续(与 Raku 相比)是否具有下面列出的六个特征中的每一个。我多说一点关于列表之后我希望得到的那种答案。

从在线消息[1]中逐字引用(带有格式修饰),该消息由推动向 JVM 添加延续工作的人员编写:

  • 非对称:当延续暂停或产生时,执行返回到调用者(的Continuation.run())。对称延续没有调用者的概念。当他们屈服时,他们必须指定另一个延续来将执行转移到。对称延拓和不对称延拓都没有比另一个更强大,并且每个都可以用来模拟另一个。

  • Stackful:延续可以在调用堆栈中的任何深度暂停,而不是在同一子例程中,当延续为无堆栈时(如 C# 中的情况),定界上下文开始。即延续有它自己的堆栈而不是一个单一的子程序帧。堆叠延续比无堆叠延续更强大。

  • Delimited:延续捕获以特定调用开始的执行上下文(在我们的例子中,是某个可运行的主体),而不是整个执行状态一直到main(). 定界延续严格来说比无定界延续更强大(http://okmij.org/ftp/continuations/undelimited.html),后者被认为“没有实际用处”(http://okmij.org/ftp/continuations/against-调用cc.html)。

  • 多提示:可以嵌套延续,调用堆栈中的任何位置,任何封闭的延续都可以暂停。这类似于 try/catch 块的嵌套,并抛出某种类型的异常,将堆栈展开到处理它的最近的 catch 而不仅仅是最近的 catch。嵌套延续的一个示例可以是在虚拟线程中使用类似 Python 的生成器。生成器代码可以执行阻塞 IO 调用,这将暂停封闭线程的继续,而不仅仅是生成器:https ://youtu.be/9vupFNsND6o?t=2188

  • One-shot/non-reentrant:每次我们继续一个暂停的延续时,它的状态都会发生变化,我们不能多次从同一个暂停状态继续它(即我们不能及时返回)。这与可重入延续不同,每次我们挂起它们时,都会返回一个表示特定挂起点的新的不可变延续对象。即延续是一个时间点,每次我们继续它时,我们都会回到那个状态。可重入的延续比不可重入的延续更强大;即,他们可以做一些仅靠一次性延续绝对不可能的事情。

  • 可克隆:如果我们能够克隆一次性延续,我们可以提供与可重入延续相同的能力。即使每次我们继续它都会改变延续,我们可以在继续创建该时间点的快照之前克隆它的状态,以便稍后返回。


Aiui 延续没有直接暴露在 Raku 中,所以与 Raku 相关的正确答案(相对于 Rakudo)可能是“没有延续”。但这对我来说并不清楚,所以在下面,如果我很幸运,我会在其中描述我希望答案中的内容,我会假装在两个 Raku 的背景下谈论它们是有意义的和乐道作为两个不同的领域。

这是我想象的可能的答案(尽管我只是有点疯狂地猜测什么是真的):

  • “作为“100 年”的语言设计,Raku当前的底层语义 [执行?] 模型至少需要无堆栈的一次性多提示分隔的延续。

  • 从理论上的观点来看,Raku 的设计永远不能扩展到要求延续是可克隆的,但理论上它可以扩展到要求它们是可堆叠的。

  • Rakudo 实现了当前需要的延续语义。

  • MoarVM 内置了对这些语义的支持,并且如果 Raku 的设计如此扩展,则可以实际跟踪理论上可能的需求扩展。

  • JVM 和 JS 后端有合适的 shims 来实现相同的目标,尽管会以性能为代价。JVM 后端可以切换到使用 JVM 原生的 continuation 似乎是合理的,如果它得到它们,当然前提是它们满足要求,但我目前的印象是它可能实际上可能是十年在我们需要考虑过那座桥之前,我们必须离开,或者更多。”

(或类似的东西。)

如果答案还提供了有关上述内容的更多详细信息,也许是一些代码链接,那将是一个特别棒的补充。

类似地,如果答案包括几个简短的例子,说明这种持续能力如何在当前 Raku 功能中出现,以及关于它可能如何在某一天(比如 10 年后)出现在其他功能中的猜测,那么答案就会变得过于——最出色的一个。

PS。感谢@Larry,他对事物的理解足够深入,知道延续需要成为图片的一部分;感谢 Stefan O'Rear 的贡献,包括我认为一次性多提示分隔延续的初步实现;并感谢 jnthn 让梦想成真。

脚注

1将延续作为第一类构造引入 JVM 的工作正在进行中。这一努力的主要推动者是 Ron Pressler。以上是基于他在 11 月写的一条消息

4

1 回答 1

12

Rakudo 使用延续作为两个特性的实现策略:

  • gather/ take- 用于实现惰性迭代器
  • 使await线程池成为非阻塞的

实现的延续的特性遵循这些语言特性的要求。我将按照与上面略有不同的顺序来介绍它们,因为它便于解释。

  • Stackful - 是的,因为我们需要能够在调用堆栈中相对于线程池工作循环的任何深度执行或take。例如,您可以在 a 内编写递归图遍历算法,然后再编写每个遇到的节点。对于,这是 Raku与许多其他语言之间差异的核心:您不必一直重构调用堆栈。awaitgathergathertakeawaitawaitawait
  • 分隔- 是的。延续重置操作会安装一个标签(或“提示”),当我们执行延续控制操作时,我们会在此分隔符处对堆栈进行切片。我无法想象您将如何实现所涉及的 Raku 功能而不对其进行分隔。
  • 多提示- 是的,这是必需的,因为您可以迭代由gather另一个gather实现内部提供的一个数据源,或者awaitgather.
  • 不对称- 在继续执行之后,执行在reset指令之后继续。在这种await情况下,我们去工作任务队列中寻找另一个任务,在这种take情况下,我们回到pull-one迭代器的方法中并且可以返回获取的值。我认为这种方法非常适合只有少数功能使用延续的语言。
  • 一次性/不可重入- 是的,至少在 MoarVM 中,运行时的内存安全取决于此属性。它由原子比较和交换操作强制执行,因此如果两个线程竞相调用延续,则只有一个线程可以成功。没有 Raku 功能需要可重入延续所暗示的额外复杂性。
  • 可克隆- 不,因为没有 Raku 功能需要它。从理论上讲,就说“是的,我们可以做到”而言,这在 MoarVM 中实施并不太糟糕,但我怀疑它会引发很多问题,例如“应该克隆多深”。如果您只是克隆了所有调用记录和类似记录,您仍然会在克隆之间共享Scalar容器、Arrays 等。

据我了解——尽管我从远处追随——JVM 延续至少部分针对 Rakuawait机制所在的相同设计空间,所以如果他们最终没有提供 Raku 需要的东西,我会感到惊讶. 这显然会简化 Raku 代码到 JVM 的编译(目前它像代码生成一样进行全局 CPS 转换,奇怪的是结果比我预期的要简单),而且它几乎肯定会执行得更好,因为需要转换从 JIT 编译器的角度来看,可能会掩盖很多事情。

就代码而言,您可以看到当前的 continuation 实现,它使用continuation 数据结构,该结构又具有各种内存管理位。在撰写本文时,这些都已作为正在进行的调度程序工作所需的新调用堆栈表示的一部分进行了重大重构;这些更改确实使处理延续的工作更有效率,但不会改变整个操作集。

于 2020-07-09T16:59:54.337 回答