摘要： 本文主张复兴协程作为一种通用的控制抽象。在提出一种新的协程分类后，我们引入了完全非对称协程的概念，并通过操作语义为其提供了精确的定义。然后，我们证明了完全协程具有与一次性（one-shot）续延和一次性部分续延等价的表达能力。我们还表明，完全非对称协程和一次性部分续延有许多相似之处，因此具有相当的优势。然而，协程更容易实现和理解，尤其是在过程式语言领域。最后，我们提供了一系列编程示例，展示了如何使用完全非对称协程来简洁直接地多种实用控制行为（如协作式多任务处理）。
Abstract: This paper defends the revival of coroutines as a general control abstraction. After proposing a new classification of coroutines, we introduce the concept of full asymmetric coroutines and provide a precise definition for it through an operational semantics. We then demonstrate that full coroutines have an expressive power equivalent to one-shot continuations and oneshot partial continuations. We also show that full asymmetric coroutines and one-shot partial continuations have many similarities, and therefore present comparable benefits. Nevertheless, coroutines are easier implemented and understood, specially in the realm of procedural languages. Finally, we provide a collection of programming examples that illustrate the use of full asymmetric coroutines to support direct and concise implementations of several useful control behaviors, including cooperative multitasking.
1. 引言 Introduction#
协程的概念于 1960 年代初被引入，是最早的通用控制抽象提案之一。它由 Conway 定义，他将协程描述为 “作为主程序行为的子程序”，并实现了这一构造以简化 COBOL 编译器中词法分析器和语法分析器之间的协作 [Conway 1963]。在接下来的二十年里，协程在表达多种有用控制行为方面的适用性在多个不同领域得到了广泛探索，包括模拟、人工智能、并发编程、文本处理以及各种数据结构操作 [Knuth 1968; Marlin 1980; Pauli and Soffa 1980]。然而，通用语言的设计者们却忽视了为程序员提供这种强大控制结构的便利性，只有少数例外，如 Simula [Birtwistle et al. 1980]、BCPL [Moody and Richards 1980]、Modula-2 [Wirth 1985] 和 Icon [Griswold and Griswold 1983]。
The concept of coroutines was introduced in the early 1960s and constitutes one of the oldest proposals of a general control abstraction. It is attributed to Conway, who described coroutines as "subroutines who act as the master program", and implemented this construct to simplify the cooperation between the lexical and syntactical analyzers in a COBOL compiler [Conway 1963]. The aptness of coroutines to express several useful control behaviors was widely explored during the next twenty years in several different contexts, including simulation, artificial intelligence, concurrent programming, text processing, and various kinds of data-structure manipulation [Knuth 1968; Marlin 1980; Pauli and Soffa 1980]. Nevertheless, designers of general-purpose languages have disregarded the convenience of providing a programmer with this powerful control construct, with rare exceptions such as Simula [Birtwistle et al. 1980], BCPL [Moody and Richards 1980], Modula-2 [Wirth 1985], and Icon [Griswold and Griswold 1983].
主流语言中缺少协程设施，部分原因可以归结为对这个概念缺乏统一的看法，它从未被精确定义过。Marlin 的博士论文 [Marlin 1980] 被广泛认为是该机制的参考，它将协程的基本特征概括如下：
The absence of coroutine facilities in mainstream languages can be partly attributed to the lacking of an uniform view of this concept, which was never precisely defined. Marlin's doctoral thesis [Marlin 1980], widely acknowledged as a reference for this mechanism, resumes the fundamental characteristics of a coroutine as follows:
- “协程的局部数据值在连续调用之间保持不变”；
- "the values of data local to a coroutine persist between successive calls";
- “当控制离开协程时，其执行被挂起，仅在稍后控制重新进入协程时才从中断处继续执行”。
- "the execution of a coroutine is suspended as control leaves it, only to carry on where it left off when control re-enters the coroutine at some later stage".
这种对协程的描述符合人们对该概念的普遍认知，但对于协程构造的一些相关问题却未作说明。除了保持状态的能力，我们可以确定三个区分协程设施的主要问题：
This description of coroutines corresponds to the common perception of the concept, but leaves open relevant issues with respect to a coroutine construct. Apart from the capability of keeping state, we can identify three main issues that distinguish coroutine facilities:
- 控制转移机制，可以提供对称或非对称协程；
- the control-transfer mechanism, which can provide symmetric or asymmetric coroutines;
- 协程在语言中是作为可以被程序员自由操作的一等对象（first-class objects）提供，还是作为受限的构造；
- whether coroutines are provided in the language as first-class objects, which can be freely manipulated by the programmer, or as constrained constructs;
- 协程是否是 “有栈”（stackful）构造，即它是否能够从嵌套调用中挂起其执行。
- whether a coroutine is a stackful construct, i.e., whether it is able to suspend its execution from within nested calls.
根据协程机制的预期用途，人们对上述问题采取了特定的解决方案。因此，发展出了相当不同的协程实现，例如 Simula 的实现。
Depending on the intended use for the coroutine mechanism, particular solutions for the preceding issues were adopted. As a consequence, quite different implementations of coroutines were developed, such as Simula's
以及 Modula 的协程设施、Icon 的生成器和协表达式，以及最近的 Python 生成器 [Schemenauer et al. 2001]。尽管所有这些构造都满足 Marlin 对协程的一般性描述，但它们在表达能力 ¹ 上提供了显著不同的程度。
and Modula's coroutine facilities, Icon's generators and co-expressions, and, more recently, Python generators [Schemenauer et al. 2001]. Although all these constructs satisfy Marlin's general characterization of coroutines, they provide significantly different degrees of expressiveness¹.
除缺乏精确定义外，一等续延（first-class continuations）的引入也极大地促成了对协程作为通用控制抽象研究兴趣的实际终结。与协程不同，一等续延具有明确定义的语义，并被广泛认为是一种富有表现力的构造，可用于实现多种有趣的特性，包括生成器、异常处理、回溯 [Felleisen 1985; Haynes 1987]、源级别的多任务处理 [Dybvig and Hieb 1989; Wand 1980]，以及协程本身 [Haynes et al. 1986]。然而，除了 Scheme [Kelsey et al. 1998]、ML 的某些实现 [Harper et al. 1991] 以及 Python 的一种替代实现 [Tismer 2000] 之外，一等续延通常不在编程语言中提供。
Besides the absence of a precise definition, the introduction of first-class continuations also greatly contributed to the virtual end of research interest in coroutines as a general control abstraction. Unlike coroutines, first-class continuations have a well-defined semantics and are widely acknowledged as an expressive construct that can be used to implement several interesting features, including generators, exception handling, backtracking [Felleisen 1985; Haynes 1987], multitasking at the source level [Dybvig and Hieb 1989; Wand 1980], and also coroutines [Haynes et al. 1986]. However, with the exception of Scheme [Kelsey et al. 1998], some implementations of ML [Harper et al. 1991], and an alternative implementation of Python [Tismer 2000], first-class continuations are not usually provided in programming languages.
将续延引入一门语言的一个障碍是难以高效地实现这个构造。这个困难主要是由于需要支持续延的多次调用，这通常需要在修改捕获的续延之前对其进行复制 [Hieb et al. 1990]。观察到在大多数情境中，续延实际上只被调用一次，这促使 Bruggeman 等人引入了一次性续延（one-shot continuations），这种续延仅限于单次调用，从而消除了与多次调用续延相关的复制开销。一次性续延在几乎所有有用的应用中都可以替代多次调用续延。特别是在多任务处理的实现中，一次性续延与多次调用续延相比，可以提供显著的性能优势 [Bruggeman et al. 1996]。
A relevant obstacle to the incorporation of continuations in a language is the difficulty to provide an efficient implementation of this construct. This difficulty is mainly due to the need of supporting multiple invocations of a continuation, which usually involves copying a captured continuation before it is modified [Hieb et al. 1990]. The observation that in most contexts continuations are actually invoked only once motivated Bruggeman et al. to introduce one-shot continuations, which are limited to a single invocation and thus eliminate the copying overhead associated with multi-shot continuations. One-shot continuations can replace multi-shot continuations in practically all their useful applications. Specially in the implementation of multitasking, one-shot continuations can provide significant performance benefits when compared to multi-shot continuations [Bruggeman et al. 1996].
除了效率问题，续延作为计算剩余部分的表示这一概念，难以管理和理解，尤其是在过程式语言的上下文中。续延调用的 “中止”（abortive）性质使得程序的结构相当复杂化；即使是经验丰富的程序员也可能难以理解大量使用续延的应用的控制流。限制续延范围并局部化其控制操作符效果的便利性，促使了部分续延（partial continuations）的引入 [Felleisen 1988; Johnson and Duggan 1988]，以及基于此概念的一系列构造的提出 [Queinnec 1993]。与传统续延不同，部分续延仅代表一个 “续延切片”[Queinnec 1993]，或一个子计算的续延 [Hieb et al. 1994]。部分续延不是中止性的；它们与当前续延组合，因此行为类似于常规函数。Danvy 和 Filinski，Queinnec 和 Serpette，以及 Sitaram 证明了基于部分续延的控制构造
Apart from efficiency issues, the concept of a continuation as a representation of the rest of a computation is difficult to manage and understand, specially in the context of procedural languages. The abortive nature of a continuation invocation complicates considerably the structure of programs; even experienced programmers may have difficulties to understand the control flow of continuation-intensive applications. The convenience of limiting the extent of continuations and localizing the effects of their control operators motivated the introduction of partial continuations [Felleisen 1988; Johnson and Duggan 1988] and the proposal of a series of constructs based on this concept [Queinnec 1993]. Unlike traditional continuations, partial continuations represent only a “continuation slice” [Queinnec 1993], or the continuation of a subcomputation [Hieb et al. 1994]. Partial continuations are not abortive; they are composed with the current continuation and thus behave like regular functions. Danvy and Filinski, Queinnec and Serpette, and Sitaram demonstrated that control constructs based
¹ 在本文中，我们使用由 Felleisen 定义的表达能力概念。
¹In this paper we use the concept of expressiveness as defined by Felleisen.
基于部分续延的机制可以为续延的经典应用，如生成器、回溯和多任务处理，提供更简洁和易于理解的实现。在所有这些应用中，施加于一次性续延的限制可以应用于部分续延，从而允许对这些构造进行更高效的实现。尽管它们相对于传统续延具有优势，但在编程语言的通用实现中，甚至在 Scheme 领域，也未提供部分续延。
on partial continuations can provide more concise and understandable implementations of the classical applications of continuations, such as generators, backtracking, and multitasking. In all these applications, the restriction imposed to one-shot continuations can be applied to partial continuations, allowing more efficient implementations of the constructs. Despite their advantages over traditional continuations, partial continuations are not provided in common implementations of programming languages, even in the realm of Scheme.
现代语言中缺少协程的另一个重要原因是，目前将多线程作为并发编程的事实标准。近年来，一些研究工作致力于探索替代的并发模型，这些模型可以支持更高效、更少出错的应用，例如事件驱动编程和协作式多任务处理。然而，像 Java 和 C# 这样的主流语言仍然将线程作为其主要的并发构造。
Another significant reason for the absence of coroutines in modern languages is the current adoption of multithreading as a de facto standard for concurrent programming. In the last years several research efforts have been dedicated to alternative concurrency models that can support more efficient and less error-prone applications, such as event-driven programming and cooperative multitasking. Nevertheless, mainstream languages like Java and C# still provide threads as their primary concurrency construct.
本文的目的是倡导复兴协程，将其作为一种强大的控制抽象，它能很好地融入过程式语言，并且易于实现和理解。我们论证并证明，与普遍看法相反，协程的表达能力并不远低于续延。相反，当协程作为一等对象提供并实现为有栈构造时 —— 即，当实现了一个完全协程机制时 —— 协程具有与一次性续延等价的能力。基于与部分续延提案中提出的类似论点 —— 易于管理和理解，以及对更结构化应用的支持 —— 我们特别倡导将完全非对称协程作为一种方便的语言可扩展性构造。
The purpose of this paper is to defend the revival of coroutines as a powerful control abstraction, which fits nicely in procedural languages and can be easily implemented and understood. We argue and demonstrate that, contrary to common belief, coroutines are not far less expressive than continuations. Instead, when provided as first-class objects and implemented as stackful constructs — that is, when a full coroutine mechanism is implemented — coroutines have equivalent power to that of one-shot continuations. Based on similar arguments as presented in the proposals of partial continuations mechanisms — easiness to manage and understand, and support for more structured applications — we specifically defend full asymmetric coroutines as a convenient construct for language extensibility.
本文的其余部分组织如下。第 2 节基于前面提到的三个问题提出了协程机制的分类，并讨论了它们对协程设施实用性的影响。第 3 节对我们关于完全非对称协程的概念进行了形式化描述，并通过一个实现了该机制的通用编程语言示例加以说明。在第 4 节中，我们展示了完全非对称协程不仅可以提供对称协程设施，还可以提供一次性续延和一次性部分续延。第 5 节包含了一系列编程示例，使用完全非对称协程来直接实现包括多任务处理在内的几种有用控制行为。最后，第 6 节总结了本文并提出了我们的结论。
The remainder of this paper is organized as follows. Section 2 proposes a classification of coroutine mechanisms based on the three issues mentioned earlier, and discusses their influence on the usefulness of a coroutine facility. Section 3 provides a formal description of our concept of full asymmetric coroutines and illustrates it with an example of a general-purpose programming language that implements this mechanism. In section 4 we show that full asymmetric coroutines can provide not only symmetric coroutine facilities but also one-shot continuations and one-shot partial continuations. Section 5 contains a collection of programming examples that use full asymmetric coroutines to provide direct implementations of several useful control behaviors, including multitasking. Finally, section 6 summarizes the paper and presents our conclusions.
2 协程的分类#
2 A Classification of Coroutines
在连续调用之间保持状态的能力构成了协程构造的一般且普遍接受的描述。然而，我们观察到协程机制的各种实现在其便利性和表达能力方面差异很大。在本节中，我们识别并讨论了三个最显著地区分协程机制并影响其有用性的问题。
The capability of keeping state between successive calls constitutes the general and commonly adopted description of a coroutine construct. However, we observe that the various implementations of coroutine mechanisms differ widely with respect to their convenience and expressive power. In this section we identify and discuss the three issues that most notably distinguish coroutine mechanisms and influence their usefulness.
2.1 控制转移机制#
2.1 Control Transfer Mechanism
协程的一个著名分类涉及其提供的控制转移操作，并区分了对称和非对称协程的概念。对称协程设施提供单一的控制转移操作，允许协程之间明确地传递控制权。非对称协程机制（更常被称为半对称或半协程[Dahl et al. 1972]）提供两种控制转移操作：一种用于调用协程，另一种用于挂起协程，后者将控制权返回给协程的调用者。对称协程在同一层级上操作，而非对称协程可以被看作是其调用者的从属，它们之间的关系有点类似于被调用例程和调用例程之间的关系。
A well-known classification of coroutines concerns the control-transfer operations that are provided and distinguishes the concepts of symmetric and asymmetric coroutines. Symmetric coroutine facilities provide a single control-transfer operation that allows coroutines to explicitly pass control between themselves. Asymmetric coroutine mechanisms (more commonly denoted as semi-symmetric or semi coroutines [Dahl et al. 1972]) provide two control-transfer operations: one for invoking a coroutine and one for suspending it, the latter returning control to the coroutine invoker. While symmetric coroutines operate at the same hierarchical level, an asymmetric coroutine can be regarded as subordinate to its caller, the relationship between them being somewhat similar to that between a called and a calling routine.
支持并发编程的协程机制通常提供对称协程来表示独立的执行单元，就像在 Modula-2 中一样。另一方面，旨在实现产生值序列的构造的协程机制通常提供非对称协程。这类构造的例子有迭代器 [Liskov et al. 1977; Murer et al. 1996] 和生成器 [Griswold and Griswold 1983; Schemenauer et al. 2001]。由 Simula 和 BCPL 实现的通用协程机制提供了两种类型的控制转移。在缺乏协程的正式定义的情况下，Simula 的机制 —— 一个真正复杂的协程实现 —— 实际上被采纳为通用协程机制的参考，并极大地促成了一种普遍的误解，即对称和非对称协程没有等价的能力。然而，很容易证明我们可以用其中一种来表达另一种；因此，一个通用的协程机制可以提供对称或非对称协程。提供两种构造只会使机制的语义复杂化，而不会增加其表达能力。
Coroutine mechanisms to support concurrent programming usually provide symmetric coroutines to represent independent units of execution, like in Modula-2. On the other hand, coroutine mechanisms intended for implementing constructs that produce sequences of values typically provide asymmetric coroutines. Examples of this type of construct are iterators [Liskov et al. 1977; Murer et al. 1996] and generators [Griswold and Griswold 1983; Schemenauer et al. 2001]. The general-purpose coroutine mechanisms implemented by Simula and BCPL provide both types of control transfer. In the absence of a formal definition of coroutines, Simula's mechanism, a truly complex implementation of coroutines, was practically adopted as a reference for a general-purpose coroutine mechanism and greatly contributed to the common misconception that symmetric and asymmetric coroutines have no equivalent power. However, it is easy to demonstrate that we can express any of these constructs in terms of the other; therefore, a general-purpose coroutine mechanism can provide either symmetric or asymmetric coroutines. Providing both constructs only complicates the semantics of the mechanism, with no increase in its expressive power.
尽管在表达能力上是等价的，但对称和非对称协程在使用便捷性上并不等价。处理和理解一个使用了哪怕是中等数量对称协程的程序的控制流，可能需要程序员付出相当大的努力。另一方面，非对称协程的行为类似于例程，因为控制权总是被转回给它们的调用者。由于即使是新手程序员也熟悉例程的概念，控制序列更容易管理和理解。此外，非对称协程允许开发更结构化的程序。
Although equivalent in terms of expressiveness, symmetric and asymmetric coroutines are not equivalent with respect to ease of use. Handling and understanding the control flow of a program that employs even a moderate number of symmetric coroutines may require a considerable effort from a programmer. On the other hand, asymmetric coroutines behave like routines, in the sense that control is always transfered back to their invokers. Since even novice programmers are familiar with the concept of a routine, control sequencing is simpler to manage and understand. Moreover, asymmetric coroutines allow the development of more structured programs.
2.2 一等对象协程与受限协程#
2.2 First-class versus constrained coroutines
一个显著影响协程机制表达能力的问题是协程是否作为一等对象提供。在一些协程实现中，特别是为特定用途设计的实现，协程对象被限制在文本边界内，不能被程序员直接操作。这种受限形式的协程的一个例子是迭代器抽象，它最初由 CLU 的设计者提出并实现，用于允许独立于其内部表示来遍历数据结构 [Liskov et al. 1977]。因为 CLU 迭代器在连续调用之间保留状态，他们将其描述为一种协程；实际上，迭代器符合 Marlin 对协程的一般性描述。然而，CLU 迭代器被限制在一个for循环内，该循环只能调用一个迭代器。这个限制对构造的使用施加了相当大的局限性；例如，并行遍历两个或多个数据集合是不可能的。受 CLU 迭代器启发的 Sather 迭代器 [Murer et al. 1996]，也被限制在循环构造中的单个调用点。每个循环调用的迭代器数量不像 CLU 那样受限，但如果任何一个迭代器终止，循环也会终止。虽然在单个循环中遍历多个集合是可能的，但像合并数据集合所要求的异步遍历，却没有简单的解决方案。Icon 的目标导向表达式求值 [Griswold and Griswold 1983] 是一种有趣的语言范式，其中回溯由另一种受限形式的协程支持，称为生成器—— 可能产生多个值的表达式。除了提供一系列内置生成器外，Icon 还支持用户定义的生成器，这些生成器通过挂起而非返回的程序实现。尽管不限于特定构造，Icon 生成器被限制在表达式内部，并且只能通过显式迭代或目标导向求值来调用。Icon 生成器比 CLU 和 Sather 迭代器更易于使用，但它们不足以强大到提供程序员定义的控制结构。只有当协程被实现为一等对象，可以被程序员自由操作并在任何地方调用时，才提供这种功能。例如，Icon 的协表达式以及由 Simula、BCPL 和 Modula-2 实现的协程设施提供了一等协程。
An issue that considerably influences the expressive power of a coroutine mechanism is whether coroutines are provided as first-class objects. In some implementations of coroutines, typically intended for particular uses, coroutine objects are constrained within a textual bound and cannot be directly manipulated by the programmer. An example of this restricted form of coroutine is the iterator abstraction, which was originally proposed and implemented by the designers of CLU to permit the traversal of data structures independently of their internal representation [Liskov et al. 1977]. Because a CLU iterator preserves state between successive calls, they described it as a coroutine; actually, an iterator fits Marlin's general characterization of coroutines. However, CLU iterators are confined within a for loop that can invoke exactly one iterator. This restriction imposes a considerable limitation to the use of the construct; parallel traversals of two or more data collections, for instance, are not possible. Sather iterators [Murer et al. 1996], inspired by CLU iterators, are also confined to a single call point within a loop construct. The number of iterators invoked per loop is not restricted as in CLU, but if any iterator terminates, the loop terminates. Although traversing multiple collections in a single loop is possible, asynchronous traversals, as required for merging data collections, have no simple solution. Icon's goal-directed evaluation of expressions [Griswold and Griswold 1983] is an interesting language paradigm where backtracking is supported by another constrained form of coroutines, named generators — expressions that may produce multiple values. Besides providing a collection of built-in generators, Icon also supports user-defined generators, implemented by procedures that suspend instead of returning. Despite not being limited to a specific construct, Icon generators are confined within an expression and can only be invoked by explicit iteration or goal-directed evaluation. Icon generators are easier to use than CLU and Sather iterators, but they are not powerful enough to provide for programmer-defined control structures. This facility is only provided when coroutines are implemented as first-class objects, which can be freely manipulated by the programmer and invoked at any place. First-class coroutines are provided, for instance, by Icon co-expressions and the coroutine facilities implemented by Simula, BCPL, and Modula-2.
2.3 有栈性#
2.3 Stackfulness
有栈（Stackful）协程机制允许协程从嵌套函数内部暂停其执行；下次协程恢复时，其执行将从它暂停的确切点继续。有栈协程机制的例子有 Simula、BCPL、Modula-2、Icon，
Stackful coroutine mechanisms allow coroutines to suspend their execution from within nested functions; the next time the coroutine is resumed, its execution continues from the exact point where it suspended. Stackful coroutine mechanisms are provided, for instance, by Simula, BCPL, Modula-2, Icon,
也包括 CLU 和 Sather 的迭代器。
and also by CLU and Sather's iterators.
目前在脚本语言中观察到协程的复苏，尤其是在 Python 和 Perl 中。在 Python [Schemenauer et al. 2001] 中，一个包含yield语句的函数被称为生成器函数。当被调用时，这个函数返回一个可以在程序中任何点恢复的对象，因此它的行为像一个非对称协程。尽管构成了一个一等对象，Python 生成器不是一个有栈的构造；它只能在控制栈与创建时处于同一级别时挂起其执行。换句话说，只有生成器的主体可以挂起。Perl 6 也提出了一个类似的设施 [Conway 2000]：增加一种新的返回命令，也叫做yield，它保留了调用它的子程序的执行状态。
A currently observed resurgence of coroutines is in the context of scripting languages, notably Python and Perl. In Python [Schemenauer et al. 2001], a function that contains an yield statement is called a generator function. When called, this function returns an object that can be resumed at any point in a program, so it behaves as an asymmetric coroutine. Despite constituting a first-class object, a Python generator is not a stackful construct; it can only suspend its execution when its control stack is at the same level that it was at creation time. In other words, only the main body of a generator can suspend. A similar facility has been proposed for Perl 6 [Conway 2000]: the addition of a new type of return command, also called yield, which preserves the execution state of the subroutine in which it is called.
Python 生成器和类似的无栈（non-stackful）构造允许开发简单的迭代器或生成器，但使更复杂的实现结构变得复杂。例如，如果在递归或辅助函数中产生项，就需要创建一个辅助生成器的层次结构，这些生成器依次产生（yield）值，直到达到原始调用点。这种类型的生成器也不足以实现用户级的多任务处理。
Python generators and similar non-stackful constructs permit the development of simple iterators or generators but complicate the structure of more elaborate implementations. As an example, if items are produced within recursive or auxiliary functions, it is necessary to create an hierarchy of auxiliary generators that yield in succession until the original invocation point is reached. This type of generator is also not powerful enough to implement user-level multitasking.
2.4 完全协程#
2.4 Full coroutines
基于前面的讨论，我们可以认为，根据我们的分类，有两个问题决定了协程设施的表达能力：协程是否是一等对象以及它们是否有栈。在缺少这些设施的情况下，协程机制无法支持一些有用的控制行为，特别是多任务处理，因此不能提供一个通用的控制抽象。我们因此引入完全协程的概念，作为一个一等、有栈的对象，我们稍后将证明，它可以提供与一次性续延相同的表达能力。
Based on the preceding discussion, we can argue that, according to our classification, two issues determine the expressive power of a a coroutine facility: whether coroutines are first-class objects and whether they are stackful constructs. In the absence of these facilities, a coroutine mechanism cannot support several useful control behaviors, notably multitasking, and, therefore, does not provide a general control abstraction. We then introduce the concept of a full coroutine as a first-class, stackful object, which, as we will demonstrate later, can provide the same expressiveness as obtained with one-shot continuations.
完全协程可以是 对称 或 非对称的；选择特定的控制转移机制不影响它们的表达能力。然而，非对称协程更容易管理，并且可以支持更简洁的用户定义构造的实现。因此，我们相信完全非对称协程机制比对称设施提供更方便的控制抽象。
Full coroutines can be either symmetric or asymmetric; the selection of a particular control-transfer mechanism does not influence their expressive power. However, asymmetric coroutines are more easily managed and can support more succinct implementations of user-defined constructs. Therefore, we believe that full asymmetric coroutines mechanisms provide a more convenient control abstraction than symmetric facilities.
3 完全非对称协程#
3 Full Asymmetric Coroutines
本节的目的是为我们关于完全非对称协程的概念提供一个精确的定义。我们首先介绍这种协程模型的基本操作符。
The purpose of this section is to provide a precise definition for our concept of full asymmetric coroutines. We begin by introducing the basic operators of this model of coroutines.
然后，我们通过为一个包含这些操作符的简单语言开发操作语义，来形式化这些操作符的语义。最后，我们提供一个编程语言的例子，它实现了一个完全非对称协程机制，并紧密遵循我们提出的语义。我们将在本文后面介绍的编程示例中使用这门语言。
We then formalize the semantics of these operators by developing an operational semantics for a simple language that incorporates them. Finally, we provide an example of a programming language that implements a full asymmetric coroutine mechanism that closely follows our proposed semantics. We will use this language in the programming examples later presented in this paper.
3.1 协程操作符#
3.1 Coroutine Operators
我们的完全非对称协程模型有三个基本操作符：create、resume和yield。操作符create创建一个新的协程。它接收一个过程参数，该参数对应于协程的主体，并返回对创建的协程的引用。创建一个协程并不会启动它的执行；一个新的协程开始时处于挂起状态，其续延点设置在其主体的第一条语句。
Our model of full asymmetric coroutines has three basic operators: create, resume, and yield. The operator create creates a new coroutine. It receives a procedural argument, which corresponds to the coroutine main body, and returns a reference to the created coroutine. Creating a coroutine does not start its execution; a new coroutine begins in suspended state with its continuation point set to the first statement in its main body.
resume 操作符 (重新) 激活一个协程。它接收的第一个参数是一个协程引用，该引用由之前的 create 操作返回。一旦被恢复，协程会从其保存的续延点开始执行，直到挂起或其主函数终止。无论哪种情况，控制权都会转移回协程的调用点。当其主函数终止时，该协程被认为是死的，不能再被恢复。
The operator resume (re)activates a coroutine. It receives as its first argument a coroutine reference, returned from a previous create operation. Once resumed, a coroutine starts executing at its saved continuation point and runs until it suspends or its main function terminates. In either case, control is transfered back to the coroutine's invocation point. When its main function terminates, the coroutine is said to be dead and cannot be further resumed.
yield 操作符挂起一个协程的执行。协程的续延点被保存下来，以便下次协程被恢复时，其执行能从挂起的那个确切点继续。
The operator yield suspends a coroutine execution. The coroutine's continuation point is saved so that the next time the coroutine is resumed, its execution will continue from the exact point where it suspended.
我们的协程操作符提供了一个方便的设施，允许协程和其调用者交换数据。协程第一次被激活时，传递给resume操作符的第二个参数会作为参数传递给协程的主函数。在协程的后续重新激活中，该第二个参数成为yield操作符的结果值。另一方面，当一个协程挂起时，传递给yield操作符的参数成为激活该协程的resume操作符的结果值。当一个协程终止时，其主函数返回的值成为其最后一次重新激活的结果值。
Our coroutine operators provide a convenient facility to allow a coroutine and its invoker to exchange data. The first time a coroutine is activated, a second argument given to the operator resume is passed as an argument to the coroutine main function. In subsequent reactivations of a coroutine, that second argument becomes the result value of the operator yield. On the other hand, when a coroutine suspends, the argument passed to the operator yield becomes the result value of the operator resume that activated the coroutine. When a coroutine terminates, the value returned by its main function becomes the result value of its last reactivation.
3.2 操作语义#
3.2 Operational Semantics
为了形式化我们关于完全非对称协程的概念，我们现在为这个机制开发一个操作语义。非对称协程和子续延（我们将在 4.3 节讨论）之间的许多相似性，使我们能够将此语义建立在 Hieb 等人描述的子续延的操作语义之上。我们从相同的核心语言开始，这是一个扩展了赋值的按值调用变体的 λ 演算。在这个核心语言中，表达式集合（用 e 表示）
In order to formalize our concept of full asymmetric coroutines, we now develop an operational semantics for this mechanism. The many similarities between asymmetric coroutines and subcontinuations (which we will discuss in Section 4.3) allow us to base this semantics on the operational semantics of subcontinuations described by Hieb et al.. We start with the same core language, a call-by-value variant of the A-calculus extended with assignments. In this core language, the set of expressions (denoted by e)
包括常量（c）、变量（x）、函数定义、函数调用和赋值：
includes constants (c), variables (x), function definitions, function calls, and assignments:
e → c | x | λx.e | e e | x := e
表示值的表达式（v）是常量和函数：
Expressions that denote values (v) are constants and functions:
v → c | λx.e
一个存储区 θ，将变量映射到值，被包含在核心语言的定义中以允许副作用：
A store 0, mapping variables to values, is included in the definition of the core language to allow side-effects:
θ: 变量 → 值
0: variables → values
核心语言的求值由一组重写规则定义，这些规则应用于表达式 - 存储对，直到获得一个值为止。求值上下文（Evaluation contexts）[Felleisen and Friedman 1986] 用于在每一步确定下一个要被求值的子表达式。核心语言定义的求值上下文（C）如下：
The evaluation of the core language is defined by a set of rewrite rules that are applied to expression-store pairs until a value is obtained. Evaluation contexts [Felleisen and Friedman 1986] are used to determine, at each step, the next subexpression to be evaluated. The evaluation contexts (C) defined for the core language are
C → □ | C e | v C | x := C
C→|Ce| v C | x := C
上述定义指定了应用的从左到右求值，因为只有当函数位置的项是一个值时，参数才能处于求值上下文中。求值核心语言的重写规则如下：
The preceding definition specifies a left-to-right evaluation of applications, because the argument can only be in an evaluation context when the term in the function position is a value. The rewrite rules for evaluating the core language are given next:
(C[(λα.ε)υ], θ) ⇒ (C[θ(x)], θ) (1)
(C[(λx.e)v], θ) ⇒ (C[e], θ[x ← v]), x ∉ dom(θ) (2)
(C[x := v], θ) ⇒ (C[v], θ[x ← v]), x ∈ dom(θ) (3)
(C[(λα.ε)υ], θ) ⇒ <C[0(x)], 0) (1)
<C[e], θ[x ← v]), x ∉ dom(0) (2)
〈C[v], θ[x ← v]), x ∈ dom(0) (3)
规则 1 指出，变量的求值结果是它在 θ 中存储的值。规则 2 描述了应用的求值；在这种情况下，假设进行了 α- 替换，以保证一个新鲜的变量 x 被插入到存储中。在规则 3 中，描述了赋值的语义，假设变量已经存在于存储中（即，它之前由一个抽象引入）。
Rule 1 states that the evaluation of a variable results in its stored value in 0. Rule 2 describes the evaluation of applications; in this case, a-substitution is assumed in order to guarantee that a fresh variable x is inserted into the store. In rule 3, which describes the semantics of assignments, it is assumed that the variable already exists in the store (i.e., it was previously introduced by an abstraction).
为了将非对称协程并入语言，我们用标签（l）、带标签的表达式（l : e）和协程操作符来扩展表达式集合：
In order to incorporate asymmetric coroutines into the language, we extend the set of expressions with labels (1), labeled expressions (l : e), and the coroutine operators:
e → c | x | λx.e | e e | x := e | l | l : e | create e | resume e e | yield e
e → c | x | xx.e | ee | x := e | 1 | 1 : e | create e | resume e e | yield e
在我们的扩展语言中，我们使用标签作为协程的引用，用带标签的表达式来表示当前活跃的协程。稍后我们将看到，标记一个协程上下文可以让我们在yield操作符被求值时，识别正在被挂起的协程。因为标签被用来
In our extended language, we use labels as references to coroutines, and labeled expressions to represent a currently active coroutine. As we will see later, labeling a coroutine context allows us to identify the coroutine being suspended when the operator yield is evaluated. Because labels are used to
引用协程，我们必须将它们包含在表示值的表达式集合中：
reference coroutines, we must include them in the set of expressions that denote values:
v → c | λx.e | l
v → c | Xx.e|l
我们还扩展了存储的定义，允许从标签到值的映射：
We also extend the definition of the store, allowing mappings from labels to values:
θ : (变量 ∪ 标签) → 值
0 : (variables Ulabels) → values
求值上下文的定义必须包括新的表达式。在这个新定义中，我们为resume操作符指定了从左到右的求值，因为只有当它的第一个参数（一个协程引用）被归约为一个标签值时，它的额外参数才会被检查：
The definition of evaluation contexts must include the new expressions. In this new definition we have specified a left-to-right evaluation for the operator resume, since only when its first argument (a coroutine reference) has been reduced to a label value its extra argument is examined:
C → □ | C e | v C | x := C | create C | resume C e | resume l C | yield C | l : C
C ← □| Ce | v C |x := C | create C | resume Ce | resumel C | yield C | 1 : C
我们实际上使用两种类型的求值上下文：完整上下文（用 C 表示）和子上下文（用 C' 表示）。子上下文是一个不包含标记上下文（l : C）的求值上下文。它对应于最内层的活动协程（即，其中没有嵌套协程发生的协程）。
We actually use two types of evaluation contexts: full contexts (denoted by C) and subcontexts (denoted by C'). A subcontext is an evaluation context that does not contain labeled contexts (l : C). It corresponds to an innermost active coroutine (i.e., a coroutine wherein no nested coroutine occurs).
描述协程操作符语义的重写规则如下：
The rewrite rules that describe the semantics of the coroutine operators are given next:
<C[create v], θ) ⇒ <C[l], θ[l ← v]), l ∉ dom(θ) (4)
<C[resume l v], θ) ⇒ (C[l : θ(l) v], θ[l ← ⊥]) (5)
<C₁[l : C₂[yield v]], θ) ⇒ (C₁[v], θ[l ← λx.C₂[x]]) (6)
<C[l : v], θ) ⇒ (C[v], θ) (7)
<C[create v], 0) ⇒ 〈C, 0[1 ← v]), 1 ∉ dom(0) (4)
(C[resume lv], 0) ⇒ (C[l : 0(1) v], 0[1 ← 1]) (5)
(C1[l : C2[yield v]], 0) ⇒ (C1[v], θ[l ← xx.C2[x]]> (6)
<C[l : v], θ) ⇒ (C[v], θ) (7)
规则 4 描述了创建协程的动作。它创建一个新标签来表示协程，并通过将此标签映射到协程主函数来扩展存储。
Rule 4 describes the action of creating a coroutine. It creates a new label to represent the coroutine and extends the store with a mapping from this label to the coroutine main function.
规则 5 显示，resume操作产生一个带标签的表达式，该表达式对应于从存储中获得的协程续延。这个续延通过传递给resume的额外参数被调用。为防止协程被重新激活，其标签被映射到一个无效值，用⊥表示。
Rule 5 shows that the resume operation produces a labeled expression, which corresponds to a coroutine continuation obtained from the store. This continuation is invoked with the extra argument passed to resume. In order to prevent the coroutine to be reactivated, its label is mapped to an invalid value, represented by 1.
规则 6 描述了挂起协程的动作。yield表达式的求值必须发生在一个由调用该协程的resume表达式求值产生的标记子上下文（C₂）内。这个限制保证了协程总是将控制权返回到其对应的调用点。传递给yield的参数成为恢复该协程所获得的结果值。被挂起协程的续延由一个函数表示，该函数的主体由相应的子上下文创建。这个续延保存在存储中，替换了该协程标签的映射。
Rule 6 describes the action of suspending a coroutine. The evaluation of the yield expression must occur within a labeled subcontext (C₂) that resulted from the evaluation of the resume expression that invoked the coroutine. This restriction guarantees that a coroutine always returns control to its correspondent invocation point. The argument passed to yield becomes the result value obtained by resuming the coroutine. The continuation of the suspended coroutine is represented by a function whose body is created from the corresponding subcontext. This continuation is saved in the store, replacing the mapping for the coroutine's label.
最后一条规则定义了协程终止的语义，并表明协程主函数返回的值成为协程最后一次激活所获得的结果值。协程标签到⊥的映射是在协程恢复时建立的，它阻止了对已死协程的重新激活。
The last rule defines the semantics of coroutine termination, and shows that the value returned by the coroutine main function becomes the result value obtained by the last activation of the coroutine. The mapping of the coroutine label to ⊥, established when the coroutine was resumed, prevents the reactivation of a dead coroutine.
3.3 一个完全非对称协程设施的例子#
3.3 An example of a full asymmetric coroutine facility
Lua [Ierusalimschy et al. 1996; Ierusalimschy 2003] 是一种在游戏行业广泛使用的脚本语言，这是一个协作式多任务处理是典型控制行为的应用领域。自 5.0 版本起，Lua 提供了一个协程设施，该设施紧密遵循我们刚刚描述的语义。
Lua [Ierusalimschy et al. 1996; Ierusalimschy 2003] is a scripting language widely used in the game industry, an application domain where cooperative multitasking is a typical control behavior. Since its version 5.0 Lua provides a coroutine facility that closely follows the semantics we have just described.
3.3.1 Lua 概述#
3.3.1 An Overview of Lua
Lua 是一种轻量级语言，支持通用过程式编程和数据描述功能。它是动态类型、词法作用域，并具有自动内存管理。
Lua is a light-weight language that supports general procedural programming with data description facilities. It is dynamically typed, lexically scoped, and has automatic memory management.
Lua 支持八种基本值类型：nil、boolean、number、string、userdata、thread、function 和 table。类型 nil、boolean、number 和 string 具有通常的含义。userdata 类型允许将任意 C 数据存储在 Lua 变量中。thread 类型代表一个独立的控制线程，用于实现协程。
Lua supports eight basic value types: nil, boolean, number, string, userdata, thread, function, and table. The types nil, boolean, number, and string have usual meanings. The type userdata allows arbitrary C data to be stored in Lua variables. The type thread represents an independent thread of control and is used to implement coroutines.
在 Lua 中，函数是一等值：它们可以存储在变量中，作为参数传递给其他函数，并作为结果返回。Lua 函数总是匿名的；语法
Functions in Lua are first-class values: they can be stored in variables, passed as arguments to other functions, and returned as results. Lua functions are always anonymous; the syntax
function foo(x) ... end
function foo(x) ... end
仅仅是以下写法的语法糖
is merely a syntactical sugar for
foo = function (x) ... end
foo = function (x) ... end
Lua 中的表是关联数组，可以用任何值作为索引；它们可以用来表示普通数组、符号表、集合、记录等。为了支持记录的方便表示，Lua 使用字段名作为索引，并提供a.name作为a["name"]的语法糖。Lua 表是通过构造表达式创建的。最简单的构造器（{}）创建一个新的空表。表构造器也可以指定选定字段的初始值，如{x = 1, y = 2}。
Tables in Lua are associative arrays and can be indexed with any value; they may be used to represent ordinary arrays, symbol tables, sets, records, etc. In order to support a convenient representation of records, Lua uses a field name as an index and provides a. name as syntactic sugar for a ["name"]. Lua tables are created by means of constructor expressions. The simplest constructor ({}), creates a new, empty table. Table constructors can also specify initial values for selected fields as in {x = 1, y = 2}.
Lua 中的变量可以是全局的或局部的。全局变量不被声明，并隐式地被赋予一个初始的nil值。局部变量是词法作用域的，并且必须被显式声明。
Variables in Lua can be either global or local. Global variables are not declared and are implicitly given an initial nil value. Local variables are lexically scoped and must be explicitly declared.
Lua 提供了一套几乎常规的语句集，类似于 Pascal 或 C 中的语句，包括赋值、函数调用和传统的控制结构（if、while、repeat和for）。Lua 还支持一些不太常规的特性，如多重赋值和多重结果。
Lua provides an almost conventional set of statements, similar to those in Pascal or C, including assignments, function calls, and traditional control structures (if, while, repeat and for). Lua also supports some not so conventional features such as multiple assignments and multiple results.
3.3.2 Lua 协程#
3.3.2 Lua Coroutines
Lua 协程设施实现了我们关于完全非对称协程的概念 [Moura et al. 2004]。遵循该机制的语义，提供了三个基本操作：create、resume和yield。与大多数 Lua 库一样，这些函数被打包在一个全局表（coroutine表）中。
Lua coroutine facilities implement our concept of full asymmetric coroutines [Moura et al. 2004]. Following the semantics of this mechanism, three basic operations are provided: create, resume, and yield, Like in most Lua libraries, these functions are packed in a global table (table coroutine).
coroutine.create函数为新协程分配一个独立的 Lua 栈。它接收一个代表协程主体的 Lua 函数作为参数，并返回一个协程引用（类型为thread的值）。通常，传递给coroutine.create的参数是一个匿名函数，像这样：
Function coroutine.create allocates a separate Lua stack for the new coroutine. It receives as argument a Lua function that represents the main body of the coroutine and returns a coroutine reference (a value of type thread). Quite often, the argument to coroutine.create is an anonymous function, like this:
co = coroutine.create(function() ... end)
CO = coroutine.create(function() ... end)
与函数一样，Lua 协程是一等值；它们可以存储在变量中，作为参数传递，并作为结果返回。没有明确的操作来删除 Lua 协程；与 Lua 中的任何其他值一样，协程由垃圾回收器丢弃。
Like functions, Lua coroutines are first-class values; they can be stored in variables, passed as arguments, and returned as results. There is no explicit operation for deleting a Lua coroutine; like any other value in Lua, coroutines are discarded by garbage collection.
coroutine.resume和coroutine.yield函数紧密遵循前面描述的resume和yield操作符的语义。然而，因为 Lua 函数可以返回多个结果，Lua 协程也提供了这个功能。这意味着coroutine.resume函数可以接收可变数量的额外参数，这些参数都会被相应的coroutine.yield函数调用返回。同样，当一个协程挂起时，相应的coroutine.resume调用会返回所有传递给coroutine.yield的参数。
Functions coroutine.resume and coroutine.yield closely follow the semantics of the operators resume and yield described before. However, because Lua functions can return multiple results, this facility is also provided by Lua coroutines. This means that function coroutine.resume can receive a variable number of extra arguments, which are all returned by the corresponding call to function coroutine.yield. Likewise, when a coroutine suspends, the corresponding call to function coroutine.resume returns all the arguments passed to coroutine.yield.
与coroutine.create类似，辅助函数coroutine.wrap创建一个新的协程，但它不返回协程本身，而是返回一个函数，当该函数被调用时，会恢复该协程。传递给该函数的任何参数都会作为额外参数传递给resume。该函数还返回coroutine.resume返回的所有值，除了第一个（一个布尔错误码）。通常，coroutine.wrap比coroutine.create更简单易用；它精确地提供了通常所需要的功能：一个恢复协程的函数。因此，在本文提供的所有编程示例中，我们将使用coroutine.wrap。
Like coroutine.create, the auxiliary function coroutine.wrap creates a new coroutine, but instead of returning the coroutine itself, it returns a function that, when called, resumes the coroutine. Any arguments passed to that function go as extra arguments to resume. The function also returns all the values returned by coroutine.resume, except the first one (a boolean error code). Usually, function coroutine.wrap is simpler to use than coroutine.create; it provides exactly what is typically needed: a function to resume a coroutine. Therefore, in all the programming examples provided in this paper we will be using coroutine.wrap.
为了说明 Lua 协程，让我们考虑一个经典的例子：一个以前序遍历二叉树的迭代器，如图 1 所示。在这个例子中，树节点由包含三个字段的 Lua 表表示：key、left和right。key字段存储节点值（一个整数）；left和right字段包含对节点各自子节点的引用。函数preorder_iterator接收一个二叉树的根节点作为参数，并返回一个迭代器，该迭代器依次产生树中存储的值。从嵌套调用内部产生（yield）值的可能性，使得树迭代器的实现非常简洁：树的遍历由一个辅助的递归函数（preorder）执行，该函数将产生的值
As an illustration of Lua coroutines, let us consider a classical example: an iterator that traverses a binary tree in pre-order, shown in Figure 1. In this example, tree nodes are represented by Lua tables containing three fields: key, left, and right. Field key stores the node value (an integer); fields left and right contain references to the node's respective children. Function preorder_iterator receives as argument a binary tree's root node and returns an iterator that successively produces the values stored in the tree. The possibility of yielding from inside nested calls allows a concise implementation of the tree iterator: the traversal of the tree is performed by an auxiliary recursive function (preorder) that yields the produced value
function preorder(node)
if node then
preorder(node.left)
coroutine.yield(node.key)
preorder(node.right)
end
end
-- create an iterator
function preorder_iterator(tree)
return coroutine.wrap(function()
preorder(tree)
return nil
end)
end
function preorder (node)
if node then
preorder (node.left)
coroutine.yield(node.key)
preorder (node.right)
end
end-- create an iterator
function preorder_iterator(tree)
return coroutine.wrap(function()
preorder (tree)
return nil
end)
end
图 1：用 Lua 协程实现的二叉树迭代器
Figure 1: A binary tree iterator implemented with Lua coroutines
直接传递给迭代器的调用者。遍历的结束通过一个nil值来表示，这是迭代器的主函数在终止时返回的。
directly to the iterator's caller. The end of a traversal is signalled by a nil value, returned by the iterator's main function when it terminates.
图 2 展示了二叉树迭代器的一个使用示例：合并两个二叉树。函数merge接收两个树的根节点作为参数。它首先为这两棵树创建迭代器（it1和it2），并收集它们的最小元素（v1和v2）。while循环打印出较小的值，并重新调用相应的迭代器以获取下一个元素，直到两棵树中的元素都耗尽为止。
Figure 2 shows an example of use of the binary tree iterator: merging two binary trees. Function merge receives as arguments the two trees' root nodes. It begins by creating iterators for the trees (it1 and it2) and collecting their smallest elements (v1 and v2). The while loop prints the smallest value and reinvokes the correspondent iterator for obtaining its next element, continuing until the elements in both trees are exhausted.
function merge(t1, t2)
local it1 = preorder_iterator(t1)
local it2 = preorder_iterator(t2)
local v1 = it1()
local v2 = it2()
while v1 or v2 do
if v1 ~= nil and (v2 == nil or v1 < v2) then
print(v1); v1 = it1()
else
print(v2); v2 = it2()
end
end
end
function merge(t1, t2)
local it1 = preorder_iterator(t1)
local it2 = preorder_iterator(t2)
local v1 = it1()
local v2 = it2()while v1 or v2 do
if v1 ~= nil and (v2 == nil or v1 < v2) then
print(v1); v1 = it1()
else
print(v2); v2 = it2()
end
end
end
图 2：合并两个二叉树
Figure 2: Merging two binary trees
4 表达替代性控制结构#
4 Expressing Alternative Control Structures
人们普遍认为协程的表达能力远不及一等续延（例如，[Friedman et al. 1984]），并且非对称协程的能力弱于对称协程。在本节中，我们通过展示一个包含完全非对称协程的语言不仅可以轻松提供对称协程，还可以提供一次性续延和一次性部分续延，来反驳这些误解。因此，任何由这些构造实现的控制结构都可以由完全非对称协程提供。
It is a common belief that coroutines are far less expressive than first-class continuations (e.g., [Friedman et al. 1984]) and, also, that asymmetric coroutines are less powerful than symmetric coroutines. In this section we contradict these misconceptions by showing that a language that incorporates full asymmetric coroutines can easily provide not only symmetric coroutines but also one-shot continuations and one-shot partial continuations. Therefore, any sort of control structure implemented by these constructs can be provided by full asymmetric coroutines.
4.1 对称协程#
4.1 Symmetric Coroutines
对称协程设施的基本特征是提供单一的控制转移操作，允许协程之间明确地传递控制权。Marlin 和 Pauli 与 Soffa 认为对称和非对称协程没有等价的能力，并且通用的协程设施应该同时提供这两种构造。然而，很容易证明我们可以用其中一种机制来实现另一种；因此，如果一种语言只提供非对称协程，并不会损失表达能力。
The basic characteristic of symmetric coroutine facilities is the provision of a single control-transfer operation that allows coroutines to pass control explicitly among themselves. Marlin and Pauli and Soffa argued that symmetric and asymmetric coroutines have no equivalent power and that general coroutine facilities should provide both constructs. However, it is easy to demonstrate that we can provide any of these mechanisms using the other; therefore, no expressive power is lost if only asymmetric coroutines are provided in a language.
在非对称设施之上实现对称协程是直接的。非对称协程之间的对称控制转移可以很容易地通过成对的yield-resume操作和一个作为中介的辅助调度循环来模拟，以在两个协程之间切换控制。当一个协程希望转移控制时，它yield到调度循环，该循环接着resume必须被重新激活的协程。
The implementation of symmetric coroutines on top of asymmetric facilities is straightforward. Symmetrical transfers of control between asymmetric coroutines can be easily simulated with pairs of yield-resume operations and an auxiliary dispatching loop that acts as an intermediary in the switch of control between the two coroutines. When a coroutine wishes to transfer control, it yields to the dispatching loop, which in turn resumes the coroutine that must be reactivated.
图 3 中显示的代码通过提供一个 Lua 库（coro）来说明这种机制，该库支持对称协程的创建及其控制转移规则。为了允许协程也能将控制转移给主程序，coro表提供了一个字段（main）来表示它，模拟一个协程引用。另一个辅助字段（current）用于存储当前活动协程的引用。
The code shown in Figure 3 illustrates this mechanism by providing a Lua library (coro) that supports the creation of symmetric coroutines and their control-transfer discipline. In order to allow coroutines to also transfer control to the main program, table coro provides a field (main) to represent it, simulating a coroutine reference. Another auxiliary field (current) is used to store a reference to the currently active coroutine.
当一个协程或主程序希望转移控制权时，它调用coro.transfer函数，传递要（重新）激活的协程；提供给这个函数的额外参数允许协程交换数据。如果主程序当前是活动的，调度循环将被执行；否则，将调用coroutine.yield来重新激活调度器。当控制权要转移到主程序时，coro.transfer函数返回。
When a coroutine, or the main program, wishes to transfer control, it calls function coro.transfer, passing the coroutine to be (re)activated; an extra argument provided to this function allows coroutines to exchange data. If the main program is currently active, the dispatching loop is executed; if not, function coroutine.yield is called to reactivate the dispatcher. When control is to be transfered to the main program, function coro.transfer returns.
在我们的实现中，我们遵循了 Modula 的协程终止语义，该语义规定，没有显式控制转移的协程终止构成一个运行时错误 [Wirth 1985]。为了实现这个语义，coro.create函数将协程体包装在一个函数中，当协程终止时，该函数会发出一个错误来终止主程序。
In our implementation, we followed Modula's semantics of coroutine termination, which specifies that the termination of a coroutine without an explicit transfer of control constitutes a run-time error [Wirth 1985]. In order to implement this semantics, function coro.create wraps the coroutine body in a function that issues an error to terminate the main program when the coroutine terminates.
coro = {}
coro.main = function() end
coro.current = coro.main
-- function to create a new coroutine
function coro.create(f)
local co = function(val)
f(val)
error("coroutine ended")
end
return coroutine.wrap(co)
end
-- function to transfer control to a coroutine
function coro.transfer(co, val)
if coro.current == coro.main then
return coroutine.yield(co, val)
end
-- dispatching loop
while true do
coro.current = co
if co == coro.main then
return val
end
co, val = co(val)
end
end
图 3：实现对称协程设施
Figure 3: Implementing symmetric coroutines facilities
4.2 一次性续延 (One-shot Continuations)#
4.2 One-shot Continuations
续延代表了计算中从给定点开始的剩余部分。当它们作为一等对象提供时，如在 Scheme [Kelsey et al. 1998] 和一些 ML 的实现 [Harper et al. 1991] 中，续延可以用来实现各种各样的控制结构，因此是语言可扩展性的一个强大工具。
A continuation represents the rest of a computation from a given point in the computation. When they are provided as first-class objects, as in Scheme [Kelsey et al. 1998] and some implementations of ML [Harper et al. 1991], continuations can be used to implement a wide variety of control structures and thus represent a powerful tool for language extensibility.
在 Scheme 中，call/cc过程使得当前续延被打包成一个一等对象。这个捕获的续延随后被传递给call/cc的参数，该参数必须是一个接受一个参数的过程。如果这个过程在不调用续延的情况下返回，其返回值
In Scheme, the procedure call/cc causes the current continuation to be packaged as a first-class object. This captured continuation is then passed to the argument of call/cc, which must be a procedure of one argument. If this procedure returns without invoking the continuation, its returned
值成为 call/cc 应用的值。如果在任何时候，捕获的续延被一个值调用，这个值会立即返回给原始 call/cc 应用的续延。
value becomes the value of the application of call/cc. If, at any time, the captured continuation is invoked with a value, this value is immediately returned to the continuation of the original call/cc application.
尽管传统的一等续延机制允许续延被多次调用，但在几乎所有其有用的应用中，续延都只被调用一次。受此事实的启发，Bruggeman 等人引入了一次性续延的概念和控制操作符call/1cc。一次性续延与多次调用续延的不同之处在于，调用一次性续延超过一次是错误的，无论是隐式地（通过从传递给call/1cc的过程返回）还是显式地（通过调用由call/1cc创建的续延）。
Although conventional first-class continuation mechanisms allow a continuation to be invoked multiple times, in virtually all their useful applications continuations are invoked only once. Motivated by this fact, Bruggeman et al. introduced the concept of one-shot continuations and the control operator call/1cc. One-shot continuations differ from multi-shot continuations in that it is an error to invoke a one-shot continuation more than once, either implicitly (by returning from the procedure passed to call/1cc) or explicitly (by invoking the continuation created by call/1cc).
Bruggeman 等人描述的一次性续延的实现揭示了此机制与对称协程之间的许多相似之处。在此实现中，控制栈表示为一个栈段的链表，这些栈段结构化为帧或活动记录的栈。当捕获一个一次性续延时，当前栈段被 “封装” 在续延中，并分配一个新的栈段来替换当前栈段。用对称协程的术语来说，这对应于创建一个新的协程并向其转移控制。当一个一次性续延被调用时，当前栈段被丢弃，控制返回到保存的栈段。这正是一个新的协程在任何时候将控制转移回其创建者时发生的情况。
The implementation of one-shot continuations described by Bruggeman et al. reveals the many similarities between this mechanism and symmetric coroutines. In this implementation, the control stack is represented as a linked list of stack segments, which are structured as stacks of frames or activation records. When a one-shot continuation is captured, the current stack segment is “encapsulated” in the continuation and a fresh stack segment is allocated to replace the current stack segment. In terms of symmetric coroutines, this corresponds to creating a new coroutine and transferring control to it. When a one-shot continuation is invoked, the current stack segment is discarded and control is returned to the saved stack segment. This is exactly what happens if the new coroutine, at any time, transfers control back to its creator.
一次性续延和对称协程之间的相似性使我们能够使用第 4.1 节中描述的对称协程设施来提供一个简洁的call/1cc实现。这个实现如图 4 所示。
The similarities between one-shot continuations and symmetric coroutines allow us to provide a concise implementation of call/1cc using the symmetric coroutine facility described in Section 4.1. This implementation is shown in Figure 4.
4.3 一次性子续延#
4.3 One-shot Subcontinuations
尽管它们表达能力强大，传统的续延，无论是多次调用还是一次性调用，都难以使用；除了一些琐碎的例子外，它们会使程序的结构大大复杂化 [Felleisen 1988; Danvy and Filinski 1990; Queinnec and Serpette 1991]。使用续延所涉及的大部分复杂性源于它们代表了计算的整个剩余部分。限制续延范围和局部化控制操作符效果的需求，推动了基于部分续延概念的几种控制抽象的提议 [Queinnec 1993]。这些抽象的本质是，调用捕获的部分续延不会中止当前的续延；相反，部分续延可以像常规函数一样组合。
Despite their expressive power, traditional continuations, either multi-shot or one-shot, are difficult to use; except for some trivial examples, they complicate considerably the structure of programs [Felleisen 1988; Danvy and Filinski 1990; Queinnec and Serpette 1991]. Most of the complexity involved in the use of continuations arise from the fact that they represent the whole rest of a computation. The need to constrain the extent of continuations and localize the effects of control operators motivated the proposal of several control abstractions based on the concept of partial continuations [Queinnec 1993]. The essence of these abstractions is that the invocation of a captured partial continuation does not abort the current continuation; instead, partial continuations can be composed like regular functions.
子续延 [Hieb et al. 1994] 是部分续延机制的一个例子。子续延代表了一个独立的局部计算（一个子计算）从该子计算中某一点开始的剩余部分。
Subcontinuations [Hieb et al. 1994] are an example of a partial continuation mechanism. A subcontinuation represents the rest of an independent partial computation (a subcomputation) from a given point in that subcom-
function call1cc(f)
-- save the continuation "creator"
local ccoro = coro.current
-- invoking the continuation transfers control
-- back to its creator
local cont = function(val)
if ccoro == nil then
error("one shot continuation called twice")
end
coro.transfer(ccoro, val)
end
-- when a continuation is captured,
-- a new coroutine is created and dispatched
local val
val = coro.transfer(coro.create(function()
local v = f(cont)
cont(v)
end))
-- when control is transfered back, the continuation
-- was "shot" and must be invalidated
ccoro = nil
-- the value passed to the continuation
-- is the return value of call1/cc
return val
end
图 4：用对称协程实现一次性续延
Figure 4: Implementing one-shot continuations with symmetric coroutines
计算。spawn操作符建立一个子计算的基或根。它接受一个过程作为参数（子计算），并向其传递一个控制器。如果控制器未被调用，spawn的结果值就是该过程返回的值。如果控制器被调用，它会捕获并中止从调用点回到（并包括）子计算根的续延。传递给控制器的过程随后应用于那个捕获的子续延。一个控制器仅在程序续延中存在相应的根时才有效。因此，一旦一个控制器被应用，只有在子续延被调用，重新建立子计算时，它才会再次有效。
putation. The operator spawn establishes the base, or root, of a subcomputation. It takes as argument a procedure (the subcomputation) to which it passes a controller. If the controller is not invoked, the result value of spawn is the value returned by the procedure. If the controller is invoked, it captures and aborts the continuation from the point of invocation back to, and including, the root of the subcomputation. The procedure passed to the controller is then applied to that captured subcontinuation. A controller is only valid when the corresponding root is in the continuation of the program. Therefore, once a controller has been applied, it will only be valid again if the subcontinuation is invoked, reinstating the subcomputation.
与一次性续延和对称协程一样，一次性子续延和完全非对称协程有许多相似之处。完全非对称协程可以被视为独立的子计算。调用子计算控制器类似于挂起一个非对称
Like one-shot continuations and symmetric coroutines, one-shot subcontinuations and full asymmetric coroutines have many similarities. Full asymmetric coroutines can be regarded as independent subcomputations. Invoking a subcomputation controller is similar to suspending an asymmetric
协程。调用一次性子续延对应于恢复一个非对称协程。与子续延一样，非对称协程可以被组合：它们的行为像常规函数，总是将控制权返回给它们的调用者。子续延和完全非对称协程之间的主要区别，以及子续延和其他类型的局部续延之间的区别是，物化的子续延不限于最内层的子计算。相反，子续延从控制器调用点延伸到被调用控制器的根，并且可能包括几个嵌套的子计算。
coroutine. Invoking a one-shot subcontinuation corresponds to resuming an asymmetric coroutine. Like subcontinuations, asymmetric coroutines can be composed: they behave like regular functions, always returning control to their invoker. The main difference between subcontinuations and full asymmetric coroutines, and also between subcontinuations and other types of partial continuations, is that the reified subcontinuation is not restricted to the innermost subcomputation. Instead, a subcontinuation extends from the controller invocation point up to the root of the invoked controller, and may include several nested subcomputations.
一次性子续延和完全非对称协程之间的相似性使我们能够用 Lua 协程来表达一次性子续延，并提供如图 5 所示的spawn操作符的实现。当spawn函数被调用时，会创建一个 Lua 协程（subc）来表示子计算。这个协程的主体调用spawn的函数参数（f），并向其传递一个局部定义的函数，该函数实现了子计算控制器。变量valid_controller指示调用控制器是否合法；它的值仅在相应的协程活动时为true。控制器函数通过挂起协程来创建一个子续延；变量shot指示这个子续延是否被调用（即协程是否被恢复）。当协程被恢复时，controller函数返回给它的调用者，从控制器调用点重新激活子计算。传递给子续延的参数（由coroutine.yield返回）成为控制器调用的结果值。
The similarities between one-shot subcontinuations and full asymmetric coroutines allow us to express one-shot subcontinuations in terms of Lua coroutines and provide the implementation of the operator spawn shown in Figure 5. When function spawn is invoked, a Lua coroutine (subc) is created to represent the subcomputation. This coroutine's main body invokes spawn's functional argument (f), passing to it a locally defined function that implements the subcomputation controller. Variable valid_controller indicates if it is legal to invoke the controller; its value is true only when the correspondent coroutine is active. The controller function creates a subcontinuation by suspending the coroutine; variable shot indicates whether this subcontinuation was invoked (i.e., whether the coroutine was resumed). When the coroutine is resumed, function controller returns to its caller, reactivating the subcomputation from the controller invocation point. The argument passed to the subcontinuation (returned by coroutine.yield) becomes the result value of the controller invocation.
函数subK负责生成和恢复子计算；它通过恢复相应的协程来做到这一点。如果子计算在没有调用控制器的情况下结束，协程主体会返回给它的调用点，这个值是从调用f得到的结果值和一个nil值（见图 5 中的第 6 行）。在这种情况下，subK函数终止（第 28 行），spawn返回给它的调用者，值为f返回的值。当控制器被调用时，协程调用（第 24 行）得到传递给控制器的参数（一个要应用于子续延的函数）以及对被调用控制器的引用。这个控制器引用，作为第二个参数传递给coroutine.yield（第 13 行），允许我们模拟一个由任意数量嵌套子计算组成的子续延 ²。当一个协程挂起时，返回的控制器引用被检查以验证它是否属于当前作用域（第 32 行）。如果是，传递给控制器的函数被应用于子续延。如果不是，这意味着被调用的控制器对应于一个外部子计算，所以当前协程调用coroutine.yield来重新激活它（第
Function subK is responsible for spawning and reinstating the subcomputation; it does so by resuming the correspondent coroutine. If the subcomputation ends without invoking the controller, the coroutine main body returns to its invocation point the result value obtained from calling f and a nil value (see line 6 in Figure 5). In this case, function subk terminates (line 28) and spawn returns to its caller the value returned by f. When the controller is invoked, the coroutine invocation (line 24) gets the argument passed to the controller (a function to be applied to the subcontinuation) and also a reference to the invoked controller. The controller reference, passed as the second argument to coroutine.yield (line 13), allows us to simulate a subcontinuation composed by an arbitrary number of nested subcomputations². When a coroutine suspends, the returned controller reference is checked to verify if it belongs to the current scope (line 32). If it does, the function passed to the controller is applied to the subcontinuation. If not, it means that the invoked controller corresponds to an outer subcomputation, so the current coroutine calls coroutine.yield to reactivate it (line
² 此行为也由一些部分续延机制的变体提供，这些变体使用标记 [Queinnec and Serpette 1991] 或标签 [Sitaram 1993] 来指定要具体化部分续延的上下文范围。
²This behavior is also provided by variants of some partial-continuation mechanisms that use marks [Queinnec and Serpette 1991] or tags [Sitaram 1993] to specify the context up to which a partial continuation is to be reified.
1 function spawn(f)
2 local controller, valid_controller, shot, subK
3
4 -- a coroutine represents a subcomputation
5 local subc = coroutine.wrap(function()
6 return f(controller), nil
7 end)
8
9 -- this function implements the subcomputation controller
10 function controller(fc)
11 if not valid_controller then error("invalid controller") end
12 shot = false
13 val = coroutine.yield(fc, controller)
14 shot = true
15 return val
16 end
17
18 -- this function spawns/reinstates a subcomputation
19 function subK(v)
20 if shot then error("subcontinuation called twice") end
21
22 -- invoke a subcontinuation
23 valid_controller = true
24 local ret, c = subc(v)
25 valid_controller = false
26
27 -- subcomputation terminated ?
28 if c == nil then return ret
29
30 -- if the local controller was invoked, apply
31 -- the function to the subcontinuation
32 elseif c == controller then return ret(subK)
33
34 -- the invoked controller corresponds to
35 -- an outer subcomputation
36 else
37 val = coroutine.yield(ret, c)
38 return subK(val)
39 end
40 end
41
42 -- spawn the subcomputation
43 shot = false
44 return subK()
45 end
图 5：实现 spawn
Figure 5: Implementing spawn
37）。这个过程会重复进行，直到到达控制器根部，这允许我们将所有挂起的子计算包含在捕获的子续延中。对称地，调用这个子续延将相继恢复挂起的协程，直到到达原始控制器调用点。
37). This process is repeated until the controller root is reached, allowing us to include all the suspended subcomputations in the captured subcontinuation. Symmetrically, invoking this subcontinuation will successively resume the suspended coroutines until the original controller invocation point is reached.
4.4 效率问题#
4.4 Efficiency issues
Haynes 等人证明了续延可以用来实现协程。Sitaram 表明协程也可以用部分续延来表达。我们刚刚展示了完全非对称协程可以用来表达一次性续延和一次性部分续延，这使我们能够论证完全非对称协程与这些抽象具有等价的表达能力。然而，用协程表达一次性续延和子续延以及反向操作在效率方面可能不等价。
Haynes et al. demonstrated that continuations can be used to implement coroutines. Sitaram showed that coroutines can also be expressed in terms of partial continuations. We have just shown that full asymmetric coroutines can be used to express both one-shot continuations and one-shot partial continuations, which allow us to argue that full asymmetric coroutines have equivalent expressive power to those abstractions. However, expressing one-shot continuations and subcontinuations with coroutines and the reverse operations may not be equivalent in terms of efficiency.
在 Bruggeman 等人描述的一次性续延的简单实现中，创建一个续延涉及将当前堆栈段转换为一个续延对象，并分配一个新的堆栈段来替换它。当一个一次性续延被调用时，当前段被丢弃，控制返回到保存的堆栈段。创建一个协程也涉及分配一个单独的堆栈。挂起和恢复一个协程的动作只比常规函数调用稍微昂贵一些。
In a simple implementation of one-shot continuations as described by Bruggeman et al., the creation of a continuation involves the conversion of the current stack segment into a continuation object and the allocation a new stack segment to replace it. When a one-shot continuation is invoked, the current segment is discarded and control is returned to the saved stack segment. The creation of a coroutine also involves the allocation of a separate stack. The actions of suspending and resuming a coroutine are just a little more expensive than regular function calls.
在我们的一次性续延实现中，创建一个单独的协程 —— 即一个单独的堆栈 “段”—— 足以实现一个续延。因此，通过一种实现了完全协程的语言，我们可以提供一次性续延机制，其性能与这种抽象的简单直接实现一样高效。另一方面，由 Haynes 等人开发的用续延实现协程的方法，通常要求每次协程挂起时捕获一个新的续延。因此，这种实现每次控制转移都涉及分配一个新的堆栈段，因此性能远低于直接实现协程，并且使用更多内存。
In our implementation of one-shot continuations, the creation of a single coroutine i.e., a single stack "segment" was sufficient to implement a continuation. Therefore, with a language that implements full coroutines we can provide one-shot continuation mechanisms that perform as efficiently as a simple direct implementation of this abstraction. On the other hand, the implementation of coroutines with continuations, as developed by Haynes et al., typically requires the capture of a new continuation each time a coroutine is suspended. This implementation thus involves the allocation of a new stack segment for each control transfer and, hence, performs much less efficiently and uses more memory than a direct implementation of coroutines.
Hieb 等人描述了一种可能的子续延实现，它使用一个带标签的堆栈的堆栈。为了确保效率，这个堆栈由一个标签 - 地址对的堆栈表示，每个地址指向存储在别处的堆栈段。调用spawn会导致向带标签的堆栈的堆栈中添加一个新的空堆栈；为这个新堆栈分配一个标签，以便将其与其对应的控制器关联起来。当控制器被调用时，所有堆栈，直到带有相关标签的那个堆栈，都从带标签的堆栈的堆栈中移除，并打包成一个子续延。当子续延被调用时，其保存的堆栈被推到当前带标签的堆栈的堆栈上。
Hieb et al. described a possible implementation of subcontinuations that uses a stack of labeled stacks. To ensure efficiency, this stack is represented by a stack of label-address pairs, with each address pointing to a stack segment stored elsewhere. Invoking spawn results in the addition of a new empty stack to the stack of labeled stacks; to this new stack a label is assigned in order to associate it with its correspondent controller. When the controller is invoked, all the stacks down to the one with the associated label are removed from the stack of labeled stacks, and packaged into a subcontinuation. When the subcontinuation is invoked, its saved stacks are pushed onto the current stack of labeled stacks.
在我们的一次性子续延实现中，生成一个子计算（即创建和激活一个协程）的成本与spawn的提议实现相当。当一个子续延只涉及单个子计算时（更常见的情况），子续延的捕获和调用至少可以与所描述的子续延直接实现一样高效。在更复杂的情况下，即一个子续延包含多个嵌套的子计算时，所涉及子计算的相继恢复会带来一些开销，但其成本不会比一连串的函数调用高很多。另一方面，用子续延实现协程也要求每次控制转移都捕获一个子续延，因此可以说比协程的简单直接实现效率更低。
In our implementation of one-shot subcontinuations, the cost of spawning a subcomputation (i.e., the creation and activation of a coroutine) is equivalent to that of the proposed implementation of spawn. When a subcontinuation involves a single subcomputation (the more usual case), the capture and invocation of a subcontinuation can perform at least as efficiently as the described direct implementation of subcontinuations. In the more complicated case, where a subcontinuation includes several nested subcomputations, the successive resumptions of the involved subcomputations impose some overhead, but with a cost no much higher than a succession of function calls. On the other hand, the implementation of coroutines with subcontinuations also requires the capture of a subcontinuation for each control transfer and, so, is arguably less efficient than a simple direct implementation of coroutines.
Kumar 等人描述了一种用线程实现一次性子续延的方法。他们的基本思想与我们的有些相似：一个子计算由一个子线程表示，该子线程在spawn被调用时创建。然后父线程进入睡眠状态，等待一个与子计算控制器关联的done条件。当控制器被调用时，子线程通过发信号给相应的done条件来唤醒根线程，然后通过创建并等待一个continue条件来挂起其执行。当一个子续延被调用时，相应的线程通过发信号给它的continue条件而被唤醒，调用者则进入睡眠状态，等待控制器的done条件。除了使用条件来允许线程的挂起和恢复（这与协程不同，不能明确地转移控制），还需要一个额外的同步机制（用mutex实现）来防止一个生成的子线程在父线程进入睡眠之前就发出done条件的信号 ³。
Kumar et al. described an implementation of one-shot subcontinuations in terms of threads. Their basic idea is somewhat similar to ours: a subcomputation is represented by a child thread, which is created when spawn is invoked. The parent thread is then put to sleep, waiting on a done condition, which is associated to the subcomputation controller. When the controller is invoked, the child thread wakes up the root thread by signalling the correspondent done condition, and then suspends its execution by creating and waiting on a continue condition. When a subcontinuation is invoked, the correspondent thread is woken by signalling its continue condition, and the invoker is put to sleep waiting on the controller's done condition. Besides the use of conditions to allow the suspension and resumption of threads (which, differently from coroutines, cannot explicitly transfer control), an additional synchronization mechanism (implemented with a mutex) is required to prevent a spawned child thread to signal the done condition before the parent thread is put to sleep³.
用线程实现子续延不涉及协程使用所需的嵌套子计算的相继挂起和恢复。然而，由于需要同步机制，使用线程会引入相当大的复杂性和开销。此外，捕获一个子续延需要创建一个新的条件，以及分配其相关的结构。除了在更一般的情况下更高效之外，用协程实现子续延更简单，而且可以说更不容易出错。
The implementation of subcontinuations with threads does not involve the successive suspensions and resumptions of nested subcomputations that the use of coroutines requires. However, the use of threads introduces a considerable complexity and overhead, due to the need of synchronization mechanisms. Moreover, the capture of a subcontinuation requires the creation of a new condition, and the allocation of its associated structures. Besides being more efficient in the the more general case, implementing subcontinuations with coroutines is simpler and arguably less error-prone.
³ 这实际上是 [Kumar et al. 1998] 中所示实现的简化描述。我们只考虑了非并发子续延实现的要求。
³This is actually a simplified description of the implementation shown in [Kumar et al. 1998]. We have considered only the requirements for an implementation of non-concurrent subcontinuations.
5 使用完全非对称协程编程#
5 Programming With Full Asymmetric Coroutines
在上一节中，我们展示了具有完全非对称协程的语言可以轻松提供一次性续延和一次性部分续延，因此，所有可以用这些抽象实现的控制行为都可以实现。在本节中，我们通过提供对不同控制行为的简洁优雅的实现，来补充我们对完全非对称协程表达能力的论证，包括一些使用续延的代表性例子。
In the previous section we showed that a language with full asymmetric coroutines can easily provide one-shot continuations and one-shot partial continuations and, therefore, all control behaviors that can be implemented with those abstractions. In this section we complement our demonstration of the expressiveness of full asymmetric coroutines by providing succinct and elegant implementations of different control behaviors, including some representative examples of the use of continuations.
5.1 生产者 - 消费者问题#
5.1 The Producer-Consumer Problem
生产者 - 消费者问题是使用协程的最典型的例子，并且在多种场景中构成了一种反复出现的模式。这个问题涉及两个独立计算的交互：一个产生一系列项目，另一个一次消费一个。这类交互的经典示例使用一对对称协程，控制在生产者和消费者之间明确地来回传递。然而，非对称协程提供了一个更简单、更结构化的解决方案：我们可以将消费者实现为一个常规函数，当需要下一个项目时，它会恢复生产者（一个非对称协程）⁴。
The producer-consumer problem is the most paradigmatic example of the use of coroutines and constitutes a recurrent pattern in several scenarios. This problem involves the interaction of two independent computations: one that produces a sequence of items and one that consumes them, one at a time. Classical illustrations of this type of interaction use a pair of symmetric coroutines, with control being explicitly transfered back and forth between the producer and the consumer. However, asymmetric coroutines provide a simpler and more structured solution: we can implement the consumer as a conventional function that resumes the producer (an asymmetric coroutine) when the the next item is required⁴.
生产者 - 消费者结构的一个方便的扩展是管道，即一个由初始生产者、一个或多个对传输项执行某些转换的过滤器，以及一个最终消费者组成的生产者 - 消费者链。非对称协程也为管道提供了简洁的实现。过滤器既像消费者又像生产者，可以由一个协程实现，该协程恢复其前驱以获取新值，并将转换后的值yield给其调用者（链中的下一个消费者）。过滤器的实现如图 6 所示。在一个单一的语句中，我们可以通过连接所需的组件并激活最终的消费者来创建一个管道：
A convenient extension of the producer-consumer structure is that of a pipeline, i.e., a producer-consumer chain consisting of an initial producer, one or more filters that perform some transformation on the transfered items, and a final consumer. Asymmetric coroutines provide a succinct implementation of pipelines too. A filter behaves both as a consumer and a producer, and can be implemented by a coroutine that resumes its antecessor to get a new value and yields the transformed value to its invoker (the next consumer in the chain). An implementation of a filter is shown in Figure 6. In a single statement we can create a pipeline by connecting the desired components and activating the final consumer:
consumer(filter(producer()))
consumer(filter(producer()))
5.2 生成器#
5.2 Generators
生成器是一种控制抽象，它产生一个值的序列，每次调用都向其调用者返回一个新值。实际上，生成器不过是生产者 - 消费者问题的一个特例，其中生成器扮演生产者的角色。
A generator is a control abstraction that produces a sequence of values, returning a new value to its caller for each invocation. Actually, generators are nothing more than a particular instance of the producer-consumer problem, with the generator behaving as the producer.
⁴这是一个消费者驱动设计的例子。在适当的情况下，也可以开发生产者驱动的解决方案。
⁴This is an example of a consumer-driven design. When appropriate, a producer-driven solution can also be developed.
function filter(ant)
return coroutine.wrap(function()
while true do
-- resume antecessor to obtain value
local x = ant()
-- yield transformed value
coroutine.yield(f(x))
end
end)
end
function filter(ant)
return coroutine.wrap(function
while true do
-- resume antecessor to obtain value
local x = ant()
-- yield transformed value
coroutine.yield(f(x))
end
end
end)
图 6：用非对称协程实现一个过滤器
Figure 6: Implementing a filter with asymmetric coroutines
生成器的一个典型用途是实现迭代器，这是一种相关的控制抽象，它允许独立于其内部实现来遍历数据结构。除了保持状态的能力，在转移控制时交换数据的可能性使得非对称协程成为实现迭代器非常方便的设施。一个用 Lua 协程实现的经典迭代器例子已在 3.3.2 节中展示。然而，生成器的用处不仅限于实现数据结构迭代器。下一节提供了一个在完全不同的场景中使用生成器的例子。
A typical use of generators is to implement iterators, a related control abstraction that allows traversing a data structure independently of its internal implementation. Besides the capability of keeping state, the possibility of exchanging data when transferring control makes asymmetric coroutines a very convenient facility for implementing iterators. A classical example of an iterator implemented with Lua coroutines was shown in Section 3.3.2. However, the usefulness of generators is not restricted to implementing data-structure iterators. The next section provides an example of the use of generators in a quite different scenario.
5.3 面向目标的编程#
5.3 Goal-oriented programming
面向目标的编程，如在模式匹配 [Griswold and Griswold 1983] 和类 Prolog 查询 [Clocksin and Mellish 1981] 中实现的，涉及解决一个问题或目标，这个目标要么是一个原始目标，要么是可替代目标的析取。这些可替代目标又可能是必须相继满足的子目标的合取，每个子目标都对最终结果贡献一个部分结果。在模式匹配问题中，匹配字符串字面量是原始目标，可替代模式是目标的析取，而模式序列是子目标的合取。在 Prolog 中，合一过程是原始目标的一个例子，一个关系构成一个析取，而规则是合取。在这种情况下，解决一个问题通常需要实现一个回溯机制，该机制相继尝试每个替代方案，直到找到一个足够的结果。
Goal-oriented programming, as implemented in pattern-matching [Griswold and Griswold 1983] and also in Prolog-like queries [Clocksin and Mellish 1981] involves solving a problem or goal that is either a primitive goal or a disjunction of alternative goals. These alternative goals may be, in turn, conjunctions of subgoals that must be satisfied in succession, each of them contributing a partial outcome to the final result. In pattern-matching problems, matching string literals are primitive goals, alternative patterns are disjunctions of goals, and sequences of patterns are conjunctions of subgoals. In Prolog, the unification process is an example of a primitive goal, a relation constitutes a disjunction, and rules are conjunctions. In this context, solving a problem typically requires the implementation of a backtracking mechanism that successively tries each alternative until an adequate result is found.
一些用续延实现的 Prolog 式回溯（例如，[Haynes 1987]）使用多发成功续延来产生值，并被用作一次性续延无法使用的场景的例子 [Bruggeman et al. 1996]。然而，这种类型的控制行为可以很容易地用作生成器的完全非对称协程来实现。
Some implementations of Prolog-style backtracking in terms of continuations (e.g., [Haynes 1987]) use multi-shot success continuations to produce values, and are used as examples of scenarios where one-shot continuations cannot be used [Bruggeman et al. 1996]. However, this type of control behavior can be easily implemented with full asymmetric coroutines used as
-- matching a string literal (primitive goal)
function prim(str)
return function(S, pos)
local len = string.len(str)
if string.sub(S, pos, pos+len-1) == str then
coroutine.yield(pos+len)
end
end
end
-- alternative patterns (disjunction)
function alt(patt1, patt2)
return function(S, pos)
patt1(S, pos)
patt2(S, pos)
end
end
-- sequence of sub-patterns (conjunction)
function seq(patt1, patt2)
return function(S, pos)
local btpoint = coroutine.wrap(function()
patt1(S, pos)
end)
for npos in btpoint do patt2(S, npos) end
end
end
图 7：面向目标的编程：模式匹配
Figure 7: Goal-oriented programming: pattern matching
生成器⁵。将一个目标包装在一个协程中，允许回溯器（一个简单的循环）相继地重试（resume）该目标，直到找到一个足够的结果。一个原始目标可以定义为一个在每次调用时yield一个结果的函数。一个析取可以实现为一个顺序调用其替代目标的函数。两个子目标的合取可以定义为一个迭代第一个子目标，并为每个产生的结果调用第二个子目标的函数。
generators⁵. Wrapping a goal in a coroutine allows a backtracker (a simple loop) to successively retry (resume) the goal until an adequate result is found. A primitive goal can be defined as a function that yields a result at each invocation. A disjunction can be implemented by a function that sequentially invokes its alternative goals. A conjunction of two subgoals can be defined as a function that iterates on the first subgoal, invoking the second one for each produced outcome.
举个例子，让我们考虑一个模式匹配问题。我们的目标是将字符串 S 与模式 patt 匹配，该模式可以通过组合代表替代匹配或子模式序列的子目标来表示。这种模式的一个例子是
As an example, let us consider a pattern-matching problem. Our goal is to match a string S with a pattern patt, which can be expressed by combining subgoals that represent alternative matchings or sequences of sub-patterns. An example of such a pattern is
("abc"|"de")."x"
("abc"|"de")."x"
⁵这种风格的回溯也可以用一次性部分续延来实现，如 Sitaram 所示，甚至可以用受限形式的协程，如 Icon 生成器来实现。
⁵This style of backtracking can also be implemented with one-shot partial continuations, as shown by Sitaram, or even with restricted forms of coroutines, such as Icon generators.
模式匹配的实现如图 7 所示。每个模式函数接收主题字符串和起始位置。对于每次成功的匹配，它会yield下一个要检查的位置。当它找不到更多匹配时，它返回nil。我们的原始目标对应于将 S 的子串与字符串字面量匹配。prim函数实现了这个目标；它接收一个字符串值作为参数，并返回一个函数，该函数尝试从给定位置开始将 S 的子串与其匹配。如果目标成功，紧跟在匹配后的 S 中的位置将被yield。prim函数使用了 Lua 字符串库中的两个辅助函数：string.len，返回字符串的长度，和string.sub，返回在给定位置开始和结束的子串。子串的替代模式对应于目标的析取。它们由alt函数实现，该函数接收两个替代目标作为参数，并返回一个通过调用这些目标来尝试在 S 中找到匹配的函数。如果找到了成功的匹配，被调用目标yield的新位置将直接传递给该函数的调用者。
The implementation of pattern matching is shown in Figure 7. Each pattern function receives the subject string and a starting position. For each successful matching, it yields the next position to be checked. When it cannot find more matchings, it returns nil. Our primitive goal corresponds to matching a substring of S with a string literal. Function prim implements this goal; it receives as argument a string value and returns a function that tries to match it with a substring of S starting at the given position. If the goal succeeds, the position in S that immediately follows the match is yielded. Function prim uses two auxiliary functions from Lua's string library: string.len, which returns the length of a string, and string.sub, which returns a substring starting and ending at the given positions. Alternative patterns for a substring correspond to a disjunction of goals. They are implemented by function alt, which receives as arguments the two alternative goals and returns a function that tries to find a match in S by invoking these goals. If a successful match is found, the new position yielded by the invoked goal goes directly to the function's caller.
将一个子串与一个模式序列匹配对应于子目标的合取，这由seq函数实现。生成的模式函数创建一个辅助协程（btpoint）来迭代第一个子目标。通过调用这个子目标获得的每个成功匹配都会在 S 中产生一个新的位置，在那里第二个子目标需要被满足。如果为第二个子目标找到了一个成功的匹配，它yield的新位置将直接传递给该函数的调用者。
Matching a substring with a sequence of patterns corresponds to a conjunction of subgoals, which is implemented by function seq. The resulting pattern function creates an auxiliary coroutine (btpoint) to iterate on the first subgoal. Each successful match obtained by invoking this subgoal results in a new position in S where the second subgoal is to be satisfied. If a successful match for the second subgoal is found, the new position yielded by it goes directly to the function's caller.
使用刚刚描述的函数，模式("abc"|"de")."x"可以定义如下：
Using the functions just described, the pattern ("abc"|"de")."x" can be defined as follows:
patt = seq(alt(prim("abc"), prim("de")), prim("x"))
patt = seq(alt(prim("abc"), prim("de")), prim("x"))
最后，match函数验证字符串 S 是否匹配此模式：
Finally, function match verifies if string S matches this pattern:
function match(S, patt)
local len = string.len(S)
local m = coroutine.wrap(function() patt(S, 1) end)
for pos in m do
if pos == len + 1 then
return true
end
end
return false
end
5.4 协作式多任务处理#
5.4 Cooperative Multitasking
协程最明显的用途之一是实现多任务处理。然而，主要由于在现代主流语言中广泛采用多线程，协程的这种合适用途目前被忽视了。
One of the most obvious uses of coroutines is to implement multitasking. However, due mainly to the wide adoption of multithreading in modern mainstream languages, this suitable use of coroutines is currently disregarded.
-- list of "live" tasks
tasks = {}
-- create a task
function create_task(f)
local co = coroutine.wrap(function() f(); return "ended" end)
table.insert(tasks, co)
end
-- task dispatcher
function dispatcher()
while true do
local n = table.getn(tasks)
if n == 0 then break end -- no more tasks to run
for i = 1,n do
local status = tasks[i]()
if status == "ended" then
table.remove(tasks, i)
break
end
end
end
end
图 8：实现协作式多任务
Figure 8: Implementing Cooperative Multitasking
一个有协程的语言不需要额外的并发构造：就像一个线程一样，一个协程代表一个有其私有局部数据的执行单元，同时与其他协程共享全局数据和其他资源。但是，线程的概念通常与抢占式多任务相关联，而协程提供了一种本质上是协作式的替代并发模型：一个协程必须明确请求被挂起，以允许另一个协程运行。
A language with coroutines does not require additional concurrency constructs: just like a thread, a coroutine represents a unit of execution with its private, local data while sharing global data and other resources with other coroutines. But while the concept of a thread is typically associated with preemptive multitasking, coroutines provide an alternative concurrency model which is essentially cooperative: a coroutine must explicitly request to be suspended to allow another coroutine to run.
抢占式调度以及因此需要复杂的同步机制，使得开发一个正确的多线程应用程序成为一项困难的任务。在某些情况下，例如操作系统和实时应用程序，及时的响应是至关重要的，因此，抢占是不可避免的。然而，大多数并发应用程序的时间要求并不严格。此外，大多数线程实现不提供任何实时保证。应用程序开发者通常也几乎没有或根本没有并发编程的经验。在这种情况下，一个协作式多任务环境，它消除了由于竞争条件引起的冲突，并最小化了同步的需求，似乎更为合适。
Preemptive scheduling and the consequent need for complex synchronization mechanisms make developing a correct multithreading application a difficult task. In some contexts, such as operating systems and real-time applications, timely responses are essential, and, therefore, preemption is unavoidable. However, the timing requirements for most concurrent applications are not critical. Moreover, most thread implementations do not provide any real timing guarantees. Application developers, also, have usually little or no experience in concurrent programming. In this scenario, a cooperative multitasking environment, which eliminates conflicts due to race conditions and minimizes the need for synchronization, seems much more appropriate.
用完全非对称协程实现协作式多任务是直接的，
The implementation of cooperative multitasking in terms of full asym-
协程的实现是直接的，如图 8 所示。并发任务由协程建模；当一个新任务被创建时，它被插入到一个活动任务列表中。一个简单的任务调度器由一个循环实现，该循环迭代这个列表，恢复活动任务并移除已经完成工作的任务（这个条件由协程主函数返回的预定义值标志）。偶尔出现的公平性问题，这些问题很容易识别，可以通过在耗时任务中添加挂起请求来解决。
metric coroutines is straightforward, as illustrated in Figure 8. Concurrent tasks are modeled by coroutines; when a new task is created, it is inserted in a list of live tasks. A simple task dispatcher is implemented by a loop that iterates on this list, resuming the live tasks and removing the ones that have finished their work (this condition is signalled by a predefined value returned by the coroutine main function). Occasional fairness problems, which are easy to identify, can be solved by adding suspension requests in time-consuming tasks.
协作式多任务的唯一缺点出现在使用阻塞操作时；例如，如果一个协程调用一个 I/O 操作并阻塞，整个程序都会阻塞直到操作完成。对于许多并发应用程序来说，这是不可接受的行为。然而，这种情况可以通过提供辅助函数来轻松避免，这些函数启动一个 I/O 操作，并在操作无法立即完成时挂起活动的协程。Ierusalimschy 展示了一个使用 Lua 协程并包含非阻塞设施的并发应用程序示例。
The only drawback of cooperative multitasking arises when using blocking operations; if, for instance, a coroutine calls an I/O operation and blocks, the entire program blocks until the operation completes. For many concurrent applications, this is an unacceptable behavior. However, this situation is easily avoided by providing auxiliary functions that initiate an I/O operation and suspend the active coroutine when the operation cannot be immediately completed. Ierusalimschy shows an example of a concurrent application that uses Lua coroutines and includes non-blocking facilities.
目前，人们对协作式多任务作为多线程的替代方案重新产生了兴趣 [Adya et al. 2002; Behren et al. 2003]。然而，在提议的环境中支持协作式多任务的并发构造通常由库或系统资源提供，如 Window 的纤程[Richter 1997]。有趣的是，尽管这些环境中使用的并发机制的描述不过是协程加上一个调度器，但 “协程” 这个词甚至没有被提及。
Currently, there is some renewal of interest in cooperative multitasking as an alternative to multithreading [Adya et al. 2002; Behren et al. 2003]. However, the concurrent constructs that support cooperative multitasking in the proposed environments are usually provided by libraries or system resources like Window's fibers [Richter 1997]. Interestingly, although the description of the concurrency mechanisms employed in these environments is no more than a description of coroutines plus a dispatcher, the term coroutine is not even mentioned.
5.5 异常处理#
5.5 Exception Handling
提供异常处理机制的语言通常实现两个基本原语：try和raise [Friedman et al. 2001]。try原语接收两个表达式：一个主体和一个异常处理器。当主体正常返回时，其返回值成为try的值，异常处理器被忽略。如果主体遇到异常情况，它会抛出一个立即发送给处理器的异常；在这种情况下，主体的任何未求值部分都会被忽略。异常处理器可以返回一个值，该值成为相关try的值，或者它可以抛出另一个异常，该异常被发送到下一个动态包围的处理器。
A language that provides an exception handling mechanism typically implements two basic primitives: try and raise [Friedman et al. 2001]. The try primitive gets two expressions: a body and and an exception handler. When the body returns normally, its returned value becomes the value of try, and the exception handler is ignored. If the body encounters an exceptional condition, it raises an exception that is immediately sent to the handler; in this case, any unevaluated portion of the body is ignored. An exception handler can either return a value, which becomes the value of the associated try, or it can raise another exception, which is sent to the next dynamically enclosing handler.
一个具有完全非对称协程的语言可以轻松支持异常处理。一个try原语可以实现为一个接收两个函数值（body和handler）的函数，并在一个协程中执行body。一个raise原语仅仅是一个yield一个异常的函数。
A language with full asymmetric coroutines can easily support exception handling. A try primitive can be implemented as a function that gets two function values (body and handler) and executes body in a coroutine. A raise primitive is merely a function that yields an exception.
-- save original version of coroutine.wrap
local wrap = coroutine.wrap
-- redefine coroutine.wrap
function coroutine.wrap(tag, f)
-- create a "tagged" coroutine
local co = wrap(function(v) return tag, f(v) end)
return function(v)
local rtag, ret = co(v) -- resume coroutine
while (rtag ~= tag) do
-- reactivate outer coroutine if tags do not match
v = coroutine.yield(rtag, ret)
-- reinstate inner coroutine
tag, ret = co(v)
end
-- tags match
return ret
end
end
图 9：避免控制行为之间的干扰
Figure 9: Avoiding Interference Between Control Actions
5.6 避免控制行为之间的干扰#
5.6 Avoiding Interference Between Control Actions
当非对称协程在单个程序中实现不同的控制结构，并且这些结构是嵌套的时，可能需要避免控制行为之间的干扰。例如，当一个迭代器在try结构中使用并抛出异常时，就可能出现不希望的干扰。
When asymmetric coroutines implement different control structures in a single program and these structures are nested, it may be necessary to avoid interferences between control actions. An undesirable interference may arise, for instance, when an iterator is used within a try structure and it raises an exception.
我们可以通过将每个控制结构与不同的标签（例如，一个字符串）关联起来，并实现一个支持标签的新版wrap函数来避免简单的干扰，如图 9 所示。此外，coroutine.yield函数需要一个必需的第一个参数（一个标签），以便我们能够匹配yield-resume对。请注意，这个解决方案的基本思想与我们在子续延实现中用于将子计算与其对应控制器匹配的方法类似（见第 4.3 节）。
We can avoid simple interferences if we identify pairs of control operations by associating each control structure with a different tag (a string, for instance) and implement a new version of function wrap that supports tags, as shown in Figure 9. In addition, function coroutine.yield takes a required first argument (a tag) in order to allow us to match yield-resume pairs. Notice that the basic idea of this solution is similar to that used for matching a subcomputation with its correspondent controller in our implementation of subcontinuations (see Section 4.3).
虽然用协程或续延避免简单干扰是微不足道的，但在存在控制行为之间的并发干扰以及一般的错误处理时，处理起来可能很困难 [Gasbichler et al. 2003]。然而，由于非对称协程的组合性质，当并发也由非对称协程实现时，处理错误并不会带来困难。
While avoiding simple interferences is trivial either with coroutines or continuations, in the presence of concurrency interferences between control actions, and error handling in general, can be hard to tackle [Gasbichler et al. 2003]. However, due to the compositional nature of asymmetric coroutines, handling errors does not present difficulties when concurrency is also
与非对称协程一起实施。
implemented with asymmetric coroutines.
6 结论#
6 Conclusions
在从 1960 年代中期到 1980 年代初的一段密集投入之后，对协程作为通用控制抽象的研究兴趣几乎停止了。除了这个概念缺乏精确定义，导致协程设施的实现差异很大之外，其他极大地促成这个有趣构造被抛弃的因素是第一类续延的引入（以及普遍认为它们比协程更具表现力），以及将线程作为 “标准” 并发构造的采纳。
After a period of intense investment, from the middle 1960s to the early 1980s, the research interest in coroutines as a general control abstraction virtually stopped. Besides the absence of a precise definition of the concept, which led to considerably different implementations of coroutine facilities, the other factors that greatly contributed to the discard of this interesting construct were the introduction of first-class continuations (and the general belief that they were far more expressive than coroutines), and the adoption of threads as a "standard" concurrent construct.
我们现在观察到对协程的兴趣正在复苏，特别是在两个不同的场景中。第一个对应于探索协作任务管理作为多线程替代方案优势的研究工作。在这种情况下，某些形式的协程由库或系统资源提供，并且仅作为并发构造使用。协程的另一次复苏是在脚本语言的背景下，如 Python 和 Perl。在这种情况下，受限形式的协程支持简单迭代器和生成器的实现，但它们不够强大，无法构成通用的控制抽象；特别是，它们不能用作并发构造。
We now observe a renewal of interest in coroutines, notably in two different scenarios. The first corresponds to research efforts that explore the advantages of cooperative task management as an alternative to multithreading. In this scenario, some forms of coroutines are provided by libraries, or system resources, and are solely used as concurrent constructs. Another resurgence of coroutines is in the context of scripting languages, such as Python and Perl. In this case, restricted forms of coroutines support the implementation of simple iterators and generators, but are not powerful enough to constitute a general control abstraction; in particular, they can not be used as a concurrent construct.
在本文中，我们主张复兴完全非对称协程，将其作为一种方便的通用控制构造，它可以用一个单一且更简单的概念取代一次性续延和多线程。为了支持这一主张，我们提供了下述贡献。
In this paper we argued in favor of the revival of full asymmetric coroutines as a convenient general control construct, which can replace both one-shot continuations and multithreading with a single, and simpler, concept. In order to support this proposition, we provided the contributions described next.
为了满足对协程概念进行充分定义的需要，我们提出了一个基于三个主要问题的协程分类：协程是 симметричные 还是 асимметричные，它们是否是一等对象，以及它们是否有栈。我们讨论了这些问题对协程设施表达能力的影响，并引入了完全协程的概念，即一等、有栈的对象。我们还讨论了完全 асимметричные 协程相对于完全 симметричные 协程的优势，后者在能力上是等价的，但在易用性上并非如此。
To fulfill the need of an adequate definition of the concept of a coroutine, we proposed a classification of coroutines based on three main issues: whether coroutines are symmetric or asymmetric, whether they are first-class objects, and whether they are stackful constructs. We discussed the influence of each of these issues on the expressive power of a coroutine facility, and introduced the concept of full coroutines as first-class, stackful objects. We also discussed the advantages of full asymmetric coroutines versus full symmetric coroutines, which are equivalent in power, but not in ease of use.
接着，我们为完全非对称协程构造提供了一个精确的定义，并为该机制开发了操作语义作为支持。然后，我们证明了完全非对称协程不仅可以提供对称协程，还可以提供一次性续延和一次性部分续延，并讨论了一次性续延和完全对称协程之间，以及一次性部分续延和完全非对称协程之间的相似之处。我们还表明，
Next we provided a precise definition of a full asymmetric coroutine construct, supported by the development of an operational semantics for this mechanism. We then demonstrated that full asymmetric coroutines can provide not only symmetric coroutines but also one-shot continuations and one-shot partial continuations, and discussed the similarities between one-shot continuations and full symmetric coroutines, and between one-shot partial continuations and full asymmetric coroutines. We also showed that,
尽管这些构造具有等价的能力，但它们在效率方面可能并不等价。
although these constructs have equivalent power, they may not be equivalent in terms of efficiency.
最后，我们提供了一系列编程示例，说明了使用完全非对称协程来支持对几种有用控制行为的简洁优雅的实现，包括一些续延使用的最相关示例。
Finally, we provided a collection of programming examples that illustrate the use of full asymmetric coroutines to support concise and elegant implementations of several useful control behaviors, including some of the most relevant examples of the use of continuations.
参考文献#
References
ADYA, A., HOWELL, J., THEIMER, M., BOLOSKY, W. J., AND DOUCER, J. R. 2002. Cooperative Task Management without Manual Stack Management. In Proceedings of USENIX Annual Technical Conference. USENIX, Monterey, CA.
BEHREN, R., CONDIT, J., AND BREWER, E. 2003. Why Events are a Bad Idea (for high-concurrency servers). In Proceedings of the 9th Workshop on Hot Topics in Operating Systems (HotOS IX). Lihue, HI.
BIRTWISTLE, G., DAHL, O.-J., MYHRHAUG, B., AND NYGAARD, K. 1980. Simula Begin. Studentlitteratur, Sweden.
BRUGGEMAN, C., WADDELL, O., AND DYBVIG, R. 1996. Representing control in the presence of one-shot continuations. In Proceedings of the ACM SIGPLAN’96 Conf. on Programming Language Design and Implementation (PLDI). ACM, Philadelphia, PA, 99–107. SIGPLAN Notices 31(5).
CLOCKSIN, W. AND MELLISH, C. 1981. Programming in Prolog. Springer-Verlag.
CONWAY, D. 2000. RFC 31: Subroutines: Co-routines. http://dev.perl.org/perl6/rfc/31.html.
CONWAY, M. 1963. Design of a separable transition-diagram compiler. Communications of the ACM 6, 7 (July), 396–408.
DAHL, O.-J., DIJKSTRA, E. W., AND HOARE, C. A. R. 1972. Hierarchical program structures. In Structured Programming, Second ed. Academic Press, London, England.
DANVY, O. AND FILINSKI, A. 1990. Abstracting control. In Proceedings of the 1990 ACM Conference on LISP and Functional Programming. ACM, Nice, France, 151–160.
DYBVIG, R. AND HIEB, R. 1989. Engines from continuations. Computer Languages 14, 2, 109–123.
FELLEISEN, M. 1985. Transliterating Prolog into Scheme. Technical Report 182, Indiana University.
FELLEISEN, M. 1988. The theory and practice of first-class prompts. In Proceedings of the 15th ACM Symposium on Principles of Programming Languages POPL’88. ACM, San Diego, CA, 180–190.
FELLEISEN, M. 1990. On the expressive power of programming languages. In Proceedings of 3rd European Symposium on Programming ESOP’90. Copenhagen, Denmark, 134–151.
FELLEISEN, M. AND FRIEDMAN, D. 1986. Control operators, the secd-machine, and the A-calculus. In Formal Description of Programming Concepts-III, M. Wirsing, Ed. North-Holland, 193–217.
FRIEDMAN, D., HAYNES, C., AND KOHLBECKER, E. 1984. Programming with continuations. In Program Transformation and Programming Environments, P. Pepper, Ed. Springer-Verlag.
FRIEDMAN, D., WAND, M., AND HAYNES, C. 2001. Essentials of Programming Languages, Second ed. MIT Press, London, England.
GASBICHLER, M., KNAUEL, E., AND SPERBER, M. 2003. How to add threads to a sequential language without getting tangled up. In Proceedings of the 4th Workshop on Scheme and Functional Programming. Cambridge, MA, 30–47.
GRISWOLD, R. AND GRISWOLD, M. 1983. The Icon Programming Language. PrenticeHall, New Jersey, NJ.
HARPER, R., DUBA, B., HARPER, R., AND MACQUEEN, D. 1991. Typing first-class continuations in ML. In Proceedings of the 18th ACM Symposium on Principles of Programming Languages POPL‘91. ACM, Orlando, FL, 163–173.
HAYNES, C. T. 1987. Logic continuations. J. Logic Programming 4, 157–176.
HAYNES, C. T., FRIEDMAN, D., AND WAND, M. 1986. Obtaining coroutines with continuations. Computer Languages 11, 3/4, 143–153.
HIEB, R., DYBVIG, R., AND ANDERSON III, C. W. 1994. Subcontinuations. Lisp and Symbolic Computation 7, 1, 83–110.
HIEB, R., DYBVIG, R., AND BRUGGEMAN, C. 1990. Representing control in the presence of first-class continuations. In Proceedings of the ACM SIGPLAN’90 Conf. on Programming Language Design and Implementation (PLDI). ACM, White Plains, NY, 66–77. SIGPLAN Notices 25(6).
IERUSALIMSCHY, R. 2003. Programming in Lua. Lua.org, ISBN 85-903798-1-7, Rio de Janeiro, Brazil.
IERUSALIMSCHY, R., FIGUEIREDO, L., AND CELES, W. 1996. Lua — an extensible extension language. Software: Practice & Experience 26, 6 (June), 635–652.
JOHNSON, G. AND DUGGAN, D. 1988. Stores and partial continuations as first-class objects in a language and its environment. In Proceedings of the 15th ACM Symposium on Principles of Programming Languages POPL’88. ACM, San Diego, CA.
KELSEY, R., CLINGER, W., AND REES, J. 1998. Revised⁵ report on the algorithmic language Scheme. ACM SIGPLAN Notices 33, 9 (Sept.), 26–76.
KNUTH, D. E. 1968. The Art of Computer Programming, Volume 1, Fundamental Algorithms. Addison-Wesley, Reading, MA.
KUMAR, S., BRUGGEMAN, C., AND DYBVIG, R. 1998. Threads yield continuations. Lisp and Symbolic Computation 10, 3, 223–236.
LISKOV, B., SNYDER, A., ATKINSON, R., AND SCHAFFERT, C. 1977. Abstraction mechanisms in CLU. Communications of the ACM 20, 8 (Aug.), 564–576.
MARLIN, C. D. 1980. Coroutines: A Programming Methodology, a Language Design and an Implementation. LNCS 95, Springer-Verlag.
MOODY, K. AND RICHARDS, M. 1980. A coroutine mechanism for BCPL. Software: Practice & Experience 10, 10 (Oct.), 765–771.
MOURA, A., RODRIGUEZ, N., AND IERUSALIMSCHY, R. 2004. Coroutines in lua. In 8th Brazilian Symposium of Progamming Languages (SBLP). SBC, Niteroi, RJ, Brazil.
MURER, S., OMOHUNDRO, S., STOUTAMIRE, D., AND SZYPERSKI, C. 1996. Iteration abstraction in Sather. ACM Transactions on Progamming Languages and Systems 18, 1 (Jan.), 1–15.
PAULI, W. AND SOFFA, M. L. 1980. Coroutine behaviour and implementation. Software: Practice & Experience 10, 3 (Mar.), 189–204.
QUEINNEC, C. 1993. A library of highr-level control operators. ACM SIGPLAN Lisp Pointers 6, 4 (Oct.), 11–26.
QUEINNEC, C. AND SERPETTE, B. 1991. A dynamic extent control operator for partial continuations. In Proceedings of the 18th ACM Symposium on Principles of Programming Languages POPL‘91. ACM, Orlando, FL, 174–184.
RICHTER, J. 1997. Advanced Windows, Third ed. Microsoft Press, Redmond, WA.
SCHEMENAUER, N., PETERS, T., AND HETLAND, M. 2001. PEP 255 Simple Generators. http://www.python.org/peps/pep-0255.html.
SITARAM, D. 1993. Handling control. In Proceedings of the ACM SIGPLAN’93 Conf. on Programming Language Design and Implementation (PLDI). ACM, Albuquerque, NM. SIGPLAN Notices 28(6).
SITARAM, D. 1994. Models of control and their implications for progamming language design. Ph.D. thesis, Rice University.
TISMER, C. 2000. Continuations and Stackless Python. In Proceedings of the 8th International Python Conference. Arlington, VA.
WAND, M. 1980. Continuation-based multiprocessing. In Proceedings of the 1980 Lisp Conference. ACM, Stanford, CA, 19–28.
WIRTH, N. 1985. Programming in Modula-2, Third, corrected ed. Springer-Verlag.