Expressive Power of One-Shot Control Operators and Coroutines

Kentaro Kobayashi, Yukiyoshi Kameyama · 2025

Read Expressive Power of One-Shot Control Operators and Coroutines by Kentaro Kobayashi, Yukiyoshi Kameyama (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-11901.txt.

Introduction

Some language features can use a captured continuation at most once. They are called one-shot control operators. Kentaro Kobayashi and one co-author rank their power with care in 2025. Exceptions, effect handlers, and coroutines all package effects neatly. Yet the one-shot family had mostly escaped formal comparison.

The yardstick is Felleisen's macro-expressiveness. The authors confirm a piece of folklore. One-shot effect handlers can be macro-expressed by asymmetric coroutines. One-shot delimited control can be too. The reverse fails in both cases. On the way, they show why an older informal proof of that claim breaks down. They repair it into a valid macro-translation. Language designers get a firm map of what these tools can and cannot mimic.

Catalog record

CREATORKentaro Kobayashi, Yukiyoshi Kameyama
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE216 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-11901

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Expressive Power of One-Shot Control Operators and Coroutines Kentaro Kobayashi, Yukiyoshi Kameyama Abstract Control operators, such as exceptions and effect handlers, provide a means of representing computational effects in programs abstractly and modularly. While most theoretical studies have focused on multi-shot control operators, one-shot control operators – which restrict the use of captured continuations to at most once – are gaining attention for their balance between expressiveness and efficiency. This study aims to fill the gap. We present a mathematically rigorous comparison of the expressive power among one-shot control operators, including effect handlers, delimited continuations, and even asymmetric coroutines. Following previous studies on multi-shot control operators, we adopt Felleisen’s macro-expressiveness as our measure of expressiveness. We verify the folklore that one-shot effect handlers and one-shot delimited-control operators can be macro-expressed by asymmetric coroutines, but not vice versa. We explain why a previous informal argument fails, and how to revise it to make a valid macro-translation. yhlargesymbols"0B yhlargesymbols"0A 1 Introduction Control operators are powerful tools for representing computational effects. Exceptions and coroutines are classic control operators, implemented in many languages. Delimited-control operators (e.g., shift/reset) have been extensively studied in the literature. The last decade has seen growing interest in effect handlers, which support modular abstraction of computational effects [ 13 , 14 ] . This paper studies the theoretical foundation of one-shot variants of control operators, where captured continuations are restricted to at most one use. While most studies 1 1 1 A notable exception is Berdine et al., who proposed linearly-used continuations [ 2 ] . on control operators focused on unrestricted (i.e., multi-shot ) control operators, one-shot variants have been recently gaining attention. There are several reasons to consider one-shot variants: First, they can be implemented more efficiently than multi-shot, as they avoid stack copying [ 3 ] . Second, they may alleviate the verification burden by reducing the complexity of reasoning about sensitive resources [ 15 ] . Third, one-shotness is key to relating control operators based on continuations to classic ones found in many dynamic languages. For instance, a recent example in the former category is one-shot effect handlers in OCaml Version 5.x, 2 2 2 https://ocaml.org while the latter category includes coroutines and the yield operator, both of which are intrinsically one-shot. 3 3 3 James and Sabry argued that a multi-shot variant of the yield operator is as expressive as delimited-control operators [ 8 ] . Despite these advantages, few authors have studied the theoretical foundation of one-shot control operators. Indeed, it is folklore that results for multi-shot control operators carry over easily to their one-shot counterparts; however, this is not the case. Since one-shotness is a dynamic property, a formal calculus for one-shot control operators should track the validity of each continuation, complicating both the semantics and precise reasoning about them. Among the few authors, de Moura and Ierusalimschy demonstrated a connection between one-shot delimited-control operators and coroutines [ 12 ] . However, this correspondence relies heavily on mutable states that can store higher-order functions, which, in our view, obscures the raw expressive power of these control operators. We note that comparing the expressiveness of control operators is surprisingly difficult. For the case of one-shot control operators, the expressiveness results in the literature often lacked correctness proofs (e.g., [ 9 ] ), or were incorrect. In this paper, we explain why a simple and seemingly correct translation from delimited-control operators to coroutines fails to preserve semantics. This paper studies the relative expressiveness among three one-shot control operators: one-shot effect handlers, one-shot delimited-control operators, and asymmetric coroutines [ 12 ] . We adopt macro-expressibility [ 5 ] as the basis for our comparison, since it is well-established in the literature, particularly in the study of control operators, such as Forster, Kammar, Lindley and Pretnar [ 7 ] . To our knowledge, this is the first systematic study to rigorously analyze the expressiveness of one-shot control operators. Our contributions are threefold: 1. We prove that one-shot delimited-control operators can be macro-expressed by asymmetric coroutines. 2. We also prove that one-shot effect handlers can be macro-expressed by asymmetric coroutines. 3. We show that the converse direction does not hold: asymmetric coroutines cannot be macro-expressed by either one-shot delimited-control operators or one-shot effect handlers. One-shot effect handler One-shot delimited-control operator Asymmetric coroutine {\lx@inpgf@ignorespaces\nexists} {\lx@inpgf@ignorespaces\nexists} Figure 1: Macro-expressibility among control operators. Solid lines indicate the existence of a macro-translation; dashed lines indicate its non-existence. Figure 1 illustrates the macro-expressibility results established in this paper. The remainder of this paper is organized as follows. Section 2 introduces macro-translations and the core calculus. Sections 3 and 4 present three extensions to the core calculus and establish the macro-expressibility results, while Section 5 disproves the macro-expressibility of the converse direction. Section 6 concludes the paper. 2 Macro-expressibility and Core Calculus 2.1 Macro-expressibility Felleisen [ 5 ] formalized the notion of macro-expressibility to compare the expressive power of two programming languages when one is an extension of the other. The notion has later been adjusted to compare two languages when both are extensions of a common language [ 7 ] . Below, we show a definition based on operational semantics, in the spirit of Felleisen’s formalization. We assume that a programming language \mathscr{L} is equipped with a set of \mathscr{L} -phrases, a set of \mathscr{L} -programs, which is a non-empty subset of \mathscr{L} -phrases, and an evaluation function \mathrm{Eval}_{\mathscr{L}}\left(\cdot\right) that maps \mathscr{L} -programs to (suitably defined) values. Phrases and programs may be distinct in some languages. For instance, phrases can contain runtime values such as references. An n -hole syntactic abstraction in \mathscr{L} is an \mathscr{L} -phrase that has n holes. Definition 1 Let \mathscr{L}_{1} and \mathscr{L}_{2} be conservative extensions 4 4 4 The formal definition of a conservative extension is provided in Appendix 0.A . of \mathscr{L} . A partial map \phi from \mathscr{L}_{1} -phrases to \mathscr{L}_{2} -phrases is a macro-translation if and only if all the following conditions are satisfied: 1. If M is an \mathscr{L}_{1} -program, \phi(M) is defined and an \mathscr{L}_{2} -program. 2. If F is an n -ary function symbol of \mathscr{L} , for any \mathscr{L}_{1} -phrases M_{1},\ldots,M_{n} , \phi(F(M_{1},\ldots,M_{n}))=F(\phi(M_{1}),\ldots,\phi(M_{n})) . 3. For each n -ary function symbol F\in\mathscr{L}_{1}\setminus\mathscr{L} , there is an n -hole syntactic abstraction A in \mathscr{L}_{2} such that \phi(F(M_{1},\ldots,M_{n}))=A[\phi(M_{1}),\ldots,\phi(M_{n})] for any \mathscr{L}_{1} -phrases M_{1},\ldots,M_{n} . 4. \mathrm{Eval}_{\mathscr{L}_{1}}\left(M\right) terminates if and only if \mathrm{Eval}_{\mathscr{L}_{2}}\left(\phi(M)\right) terminates. We say \mathscr{L}_{1} is (strongly) macro-expressible in \mathscr{L}_{2} if a macro-translation from \mathscr{L}_{1} to \mathscr{L}_{2} exists. We can define a weak macro-translation by replacing the “if and only if”-clause in the last condition by “only if”. An example of macro-expressibility is the let-construct in call-by-value lambda calculus. We can define a macro-translation \phi in such a way that \phi(\mathbf{let}\;\mathit{x}=M\;\mathbf{in}\;N)=(\lambda\mathit{x}.\;\phi(N))\;\phi(M) holds. Macro-expressibility is transitive: the composition of macro-translations is also a macro-translation. 2.2 Core Calculus \mathbf{MAM} We use the language \mathbf{MAM} (multi-adjunctive language) by Forster et al. [ 7 ] , which was designed after Levy’s Call-By-Push-Value calculus [ 10 ] . It serves as the common core calculus for our extensions. V,W ::= value | x\in\mathscr{V} variable | \mathtt{()} unit M,N ::= computation | \mathbf{case}\;V\;\mathbf{of}\;(x_{1},x_{2})\mapsto M product matching | \mathbf{case}\;V\;\mathbf{of}\;\{(\mathbf{inj}_{\mathrm{L_{\mathnormal{i}}}}\,x_{i}\mapsto M_{i})_{i}\} variant matching | V! force | \mathbf{return}\;V returner |

Read the complete text