One-shot Algebraic Effects as Coroutines
Satoru Kawahara1,2 and Yukiyoshi Kameyama1,3
1

Department of Computer Science, University of Tsukuba, Japan2
sat@logic.cs.tsukuba.ac.jp
3kameyama@acm.org

Abstract. Algebraic effects and handlers are an emerging new feature
to model effectful computations and attract attention not only from researchers but also from programmers. They are implemented in various
ways as part of compilers, interpreters, or as libraries. We present a direct embedding of one-shot algebraic effects and handlers in a language
which has asymmetric coroutines. The key observation is that, by restricting the use of continuations to be one-shot, we obtain a simple andsufficiently general implementation via coroutines, which are available inmany modern programming languages. We have implemented our embedding as a library in Lua and Ruby, which allows one to write effectfulprograms in a modular way using algebraic effects and handlers.
Keywords: Algebraic Effects and Handlers · Coroutines · Continuations· Control Operators · One Shot

1

Introduction

Algebraic effects [13] and handlers [14] are an emerging new feature to model
effectful computations. They are gaining more and more attention not only fromresearchers but also from programmers. Algebraic effects and handlers are implemented as a feature in programming languages such as Eff [1], Multicore
OCaml [5], and Koka [10], as well as as a library in Haskell [7] [8], OCaml [9],and Scala [2] 4 5 , even in JVM bytecode [3] and C [11], and so on.
Algebraic effects and handlers are implemented in several ways based onstack manipulation, delimited control-operators, or free monad. Unfortunately,
all of them have shortcomings as follows. Implementations based on stack manipulation are used in JVM bytecode and C implementations, however, it highly
depends on the runtime which needs deep insight on language processors. Therefore implementation cost is rather high, which prevents the feature from being
implemented in various systems. Implementation via delimited control-operators
is used in OCaml implementation and one of Scala implementations. Although
it is a systematic and elegant way to implement algebraic effects and handlers using delimited control-operators since it does not need knowledge on
low-level features, unfortunately, few languages have delimited continuation as
45

https://github.com/atnos-org/eff
https://github.com/typelevel/cats-effect2Satoru Kawahara and Yukiyoshi Kameyama

built-in, and implementing delimited control-operators in a language is nontrivial. Free monad is another systematic way to implement computational effects, and Haskell and one of Scala implementations use it. With free-monad
implementation, we only have to concentrate on data structures, realizing theseparation of concerns. The demerits of using free monads are that a programmer
has to adopt monadic-style, also, to combine other effectful computations withalgebraic effects and handlers, we must use monad transformers and individual
control operators such as forM or replicateM, which is messy.
In this paper, we present a new embedding of algebraic effects and handlersthat is general, widely available, and easy to understand, compared to otherexisting ways of implementing them. The key of our embedding is to use coroutines which many languages already have as a built-in feature. Coroutines are lessexpressive than general delimited-control operators as the former cannot use (implicit) delimited continuations more than once, while the latter can use delimited
continuations multiple times. However, as we will see in this paper, coroutines
are as expressive as one-shot delimited control-operators, a restricted control
operator that is allowed to invoke a delimited continuation at most once [12]. It
is already known that one-shot delimited-control operators can be implemented
more efficiently than general, multi-shot ones, thanks to that fact that no copying of continuations is necessary [4]. Similarly, our target feature of algebraic
effect and handlers must use continuations at most once. We will show that using coroutines to implement algebraic effects and handlers have another merit:a programmer does not have to think about what data structures are used toembed algebraic effects. A programmer does not have to write delimited-control
operators from effect invocations explicitly because coroutines retrieve the continuation as the rest of a coroutine thread.
We have implemented one-shot algebraic effects and handlers in terms ofasymmetric coroutines. Our implementation is practical, as we have made algebraiceffect libraries for Lua 6 and Ruby7 based on this paper, both of which are alreadymade public. Our libraries have been used by several users, and interested users
have ported our libraries to other languages89 . Although implementations of algebraic effects using coroutines already exist such as 10 11 12 , each one has suchproblems as it does not provide a first-class continuation to the user, or is rather
complicated. Our libraries allow a user to access continuations, and each libraryis kept so simple that anyone can understand the implementation.
Our main contributions in this paper are the following.

6

https://github.com/nymphium/eff.lua
https://github.com/nymphium/ruff
8
https://github.com/MakeNowJust/eff.js
9
https://github.com/pandaman64/effective-rust
10
https://github.com/dry-rb/dry-effects
11
https://github.com/digital-fabric/affect12
https://github.com/briancavalier/forgefx
7One-shot Algebraic Effects as Coroutines

3– We show a new embedding of one-shot algebraic effects and handlers. We
use standard asymmetric coroutines only, and no special control features areneeded. Hence our embedding applies to various other languages.
– Our embedding does not force programmers to think about the internal data
structures. The implementation details are kept transparent.
– We do not use continuation-passing style nor user-level control operators. As
a consequence, our embedding is more performant in many cases than otherembeddings, including the one with free monads.
This paper is organized as follows. Section 2 shows typical examples using
algebraic effects and handlers and demonstrates our algebraic-effect library for
Lua. Section 3 describes the embedding method by defining the conversion fromλeff , a language with algebraic effect handlers, to λac , a language with asymmetric coroutines. Section 4 discusses the extension of our model definitions for
implementing our libraries in Lua and Ruby, and problems in actual use. Section 5 shows the performance evaluation of our embedding by comparing ourswith the embedding with free monads. Section 6 describes related work, andSection 7 concludes.

2

Effectful Programming with eff.lua

This section illustrates programming with algebraic effects and handlers by several examples. To express examples, we will use the programming language Lua
with our library eff.lua to write effectful programs. The library is based on ourembedding described in Section 3, which we detail in Section 4.
In the following examples, three functions inst, perform, and handler areused to express algebraic effect and handlers.
2.1

Exception

In our view, algebraic effects are regarded as resumable exceptions, as shown by
the following example.
The function inst in our library eff.lua creates a new effect.
local DivideByZero = inst()
We can invoke an effect by calling perform.
local div = function(x, y)
if y == 0 thenreturn perform(DivideByZero, nil)else
return x / y
end
end

4

Satoru Kawahara and Yukiyoshi Kameyama

div divides x by y except when y is 0. If y is 0, it performs the effect DivideByZero, and the corresponding handler catches the effect. By performing an effect, thecontrol is brought to the nearest handler, similarly to exception handling.
Our library provides the function handler to create a new handler.
local with_nil = handler {val = function(_) return nil end,
[DivideByZero] = function(_, _)return nil
end}
A handler captures an effect with an argument and the current (delimited) continuation from the effect invocation up to the handler. On the second line in
the code above, val is a value handler which is used when the handled computation returns the result value. The handler function for DivideByZero has
two arguments, the first of which receives the argument of the effect invocationand the second is a delimited continuation. In the example, the arguments are
ignored, and the whole computation returns nil. The code above expresses a
simple exception.
As the next step, we show resumable exceptions. We implement the handler that catches the effet DivideByZero with its continuation and resumes thecomputation from the point of “throwing an exception.”
local with_default_zero = handler {val = function(v) return v end,
[DivideByZero] = function(_, k)
if DEBUG thenreturn k(0)elsereturn nil
end
end
}
The implementation itself is simple, by simply passing 0 to the continuation. We
can use the handler with_default_zero as:
with_default_zero(function()
local v = div(3, 0)
return v + 20
end)
In this code, we pass 3 and 0 to div, and then the effect DivideByZero isperformed. with_default_zero catches the effect and captures the continuation
local v = ; return v + 20 with still handled by with_default_zero. The
effect handler passes 0 to its continuation, and the computation resumes fromOne-shot Algebraic Effects as Coroutines

5

the effect invocation. So div returns 0, and the entire computation results in
0 + 20 = 20 with the value handler, which is an identity function.

2.2

State

We can implement state by a parameter-passing handler without using reference
cells.
First, we define two effect operations:
local Get = inst()
local Put = inst()
To run stateful computations, we define the function run, which requires theinitial state and computation as a thunk:
local run = function(init, task)
local step = handler {val = function(_) return function() end end,[Get] = function(_, k)return function(s)return k(s)(s)end
end,[Put] = function(s, k)return function(_)
return k()(s)
end
end
}
return step(task)(init)
end
step is a handler that catches Get and Put. In order to follow the parameterpassing technuque, the value handler returns a function which itself returns
nothing. When the handler catches the effect Get, it returns the function that
requires a state. When the handler catches the effect Put with an actual parameter v, it binds v to s and returns a thunk which passes s to the continuation k
as a new state. After defining the handler, the above code runs the computation
with the initial state init.

6

Satoru Kawahara and Yukiyoshi Kameyama

2.3

Deferred functions

We can implement a simple deferred function like Go’s defer13 . Go allows afunction call on a deferred statement, and then its execution is deferred until
the end of the execution of its parent14 . From the tutorial 15 , it is written as:
package main
import "fmt"func main() {defer fmt.Println("world")
fmt.Println("hello")}
In the function main, we register the function call fmt.Println("world"). Aftercalling main and printing hello, the deferred function runs and prints world.
We can implement it using our library and here show part of it. Go can
execute deferred functions even if an exception occurs, but we suppress it for
simplicity.
We define the effect Defer as follows:
local Defer = inst()
and the corresponding handler:
local with_defer = handler {val = function(_) end,
[Defer] = function(proc, k)k()proc()
return nil
end}with_defer catches the effect Defer with the argument proc. Since Lua is a callby-value language and does not have a feature to defer computations, a deferredfunction is represented as a thunk. When the handler catches the effect Defer
for the first time, it runs the continuation. After running the continuation, it
wastes the result of the continuation and runs proc and returns nil.
We can use with_defer as:
13

https://golang.org/ref/spec#Defer statements
Although the syntax accepts any expressions, the de facto standard compiler go
rejects all expressions but function calls.
15
https://tour.golang.org/flowcontrol/12
14

One-shot Algebraic Effects as Coroutines

7

with_defer(function()
perform(Defer, function() print("world") end)
print("hello")end)
It returns nil with printing hello and world.
To implement the full functionality of defer in Go, one must write exception handlers around the continuation and rethrow a caught exception after thedeferred function.

3

Embedding Algebraic Effects with Coroutines

This section explains our embedding to implement one-shot algebraic effects andhandlers using asymmetric coroutines. For this purpose, we define λeff , a language which has one-shot algebraic effects, λac , a language which has asymmetriccoroutines, and then a program translation from λeff to λac .
3.1

λeff

λeff is an untyped language with algebraic effects and handlers based on Effy [15].
Syntax Figure 1 defines the syntax of λeff .

x ∈ Variables
eff ∈ Effects
v ::= x | h | λx. ee ::= v | v v | let x = e in e
| perform eff v | with v handle eh ::= handler eff (val x → e) ((x, x) → e)w ::= clos (λx.e, E) | closh (h, E)
F ::= ( e, E) | w | (let x =  in e, E)| (with w handle )eff| (with  handle e, E)
C ::= e | w
E ::= [] | (x = w) :: E
K ::= [] | F :: K

Fig. 1: Syntax and runtime representation of λeff

8Satoru Kawahara and Yukiyoshi Kameyama

The expression perform eff v invokes an effect eff with an argument v. A
usual let binding is written as let x = c1 in c2 .
The expression handler eff (val x → e1 ) ((y, k) → e2 ) creates a handler,
which catches the effect eff and returns e2 where y is bound to the argumentof the effect-performing operation, and k is bound to the delimited continuation
when the effect is performed (invoked). The expression val x → e1 gives a value
handler, namely, a handler which is used when the body of a handler returns
normally.
For simplicity, λeff can handle only one effect per handler, whereas handlers
in Effy can cope with multiple effects. Although this simplification restricts theusability of our language, we can easily extend it to allow multiple effect operations per handler. In fact, the actual implementation of our library provides
multiple handlers stated in Section 4.
The expression with h handle e is a handling expression, which sets thehandler h and then evaluates e under the handler.
The syntactic category w is a runtime value whereof clos (λx.e, E) andclosh (h, E). clos (λx.e, E) is a λ-term with a closing environment E, andclosh (h, E) is a handler with E.
The frame F is either an application, the let binding, or handling expressions, and C represents the “code” component in the CEK machine, and K
stands for a continuation, which consists of a stack of frames.
Semantics
Helper functions We introduce three helper functions for semantics in Figure 2:
K // eff returns a triple (K1 , F, K2 ) where F is the frame that handles the effectnamed by eff, and K = K1 :: [F ] :: K2 holds. If more than one frames handle(with w handle )eff :: K // eff = [] , (with w handle )eff , K(F :: K) // eff = F :: K 0 , F 0 , K 00
where F 6= (with w handle )effand K 0 , F 0 , K 00 = K // eff
LF :: KM = λx. LKM F [x]
L [] M = λx. x

K ∗ E = clos (λx.LKM x, E)

Fig. 2: Helper Functions for Semantics

the effect eff, the first one is selected, and if none have the named effect, theOne-shot Algebraic Effects as Coroutines

9

result is undefined. LKM converts a stack K to a continuation in functional form.
(K ∗ E) creates a closure with a stack frame K and an environment E.
Small-step semantics Figure 3 defines the small-step, call-by-value, left-to-rightsemantics (−→eff ) in the CEK-machine style. In the rule Lookup, E (x) is thevalue associated with the variable x in the environment E. The rules PushLet,
Bind, and Close, PushApp, PushArg, and App are more or less standard.
The rest of the rules are the one for algebraic effects and handlers. The rules
PushWithHandle and CloseHandler push or pop evaluation contexts tothe stack. The rule Handle manipulates a with-expression with h handle e: if
h evaluates to a handler value, then e is going to be evaluated under this handler.
The rule PushPerform pushes the frame of perform-ing an effect eff to thestack. The rules HandlePerform and HandleValue are the key rules foralgebraic handlers. In the rule HandlePerform, the code component is a value
w. Hence, the first frame in the stack perform eff  is retrieved and evaluated.
Then we look for a handler whose name is eff in the stack K, and if we find it,
we use the handler to cope with this effect where formal parameters y and k arebound to the value w and the delimited continuation K 0 under environment E.
eff
We adopt the deep handlers, hence the handler (with wh handle ) remains
in the stack after this step. The rule HandleValue is used when the handledexpression does not invoke an effect and returns a value w. Then the value
handler (val x → ev ) is used, and the handler is eliminated from the stack after
this step.
3.2

λac

The language λac is based on one of the calculi defined by de Moura and Ierusalimschy [12], namely, it is based on the calculus for stackful asymmetric coroutines. For practical reasons, we added to this language let with recursion, pattern matching, and comparison operators.
Syntax Figure 4 defines the syntax of λac . We will use λac as the target languageof program transformation from λeff , so it has several program constructs forthis purpose. Effects and each element correspond to the effects in λeff .
We added conditional expression, pattern matching, and (mutual) recursion−
to de Moura and Ierusalimschy’s calculi. f →x is an abbreviation of f x0 x1 · · · · · · xn−−−−−−
−−−→
→
−
→
−
−
−
and and g y = e is of and g0 y = e0 and g1 →y = e1 and · · · · · · and gm →y = em .
A similar abbreviation is applied to constructors and pattern matching.
Constructs for asymmetric coroutines are labels, labelled expression l : e,create, resume, and yield. A label is a reference to a coroutine, and a labelled
expression l : e is an expression e in the coroutine l.
K represents constructors; for instance, True and False are boolean constants. The expression match e with cases is for pattern matching. We add re−stricted guards to pattern matching so that cases may contain a form K →x when x =x → e. This restricted form is sufficient for our purpose.

10

Satoru Kawahara and Yukiyoshi Kameyama

hC; E; Ki −→eff hC 0 ; E 0 ; K 0 ihx; E; Ki −→eff hE (x) ; E; Ki(Lookup)hlet x = e in e0 ; E; Ki −→eff he; E; (let x =  in e0 , E) :: Ki (PushLet)
hw; E; (let x =  in e, E 0 ) :: Ki −→eff he; (x = w) :: E 0 ; Ki

(Bind)

hλx. e; E; Ki −→eff hclos (λx.e, E) ; E; Ki(Close)he e0 ; E; Ki −→eff he; E; ( e0 , E) :: Ki(PushApp)hw; E; ( e, E 0 ) :: Ki −→eff he; E 0 ; (w ) :: Ki(PushArg)

w; E; clos (λx.e, E)0  :: K −→eff he; (x = w) :: E 0 ; Ki

(App)hwith h handle e; E; Ki −→eff hh; E; (with  handle e, E) :: Ki(PushWithHandle)
hh; E; Ki −→eff hclosh (h, E) ; E; Ki(CloseHandler)
where h = handler eff (val x → ev ) ((x, k) → eeff )
*

+
*
+
e;
wh ;
0
E;
E;
−→eff (with  handle e, E) :: K
(with wh handle )eff :: K
where wh = closh (handler eff (val x → ev ) ((x, k) → eeff ) , E)
(Handle)hperform eff v; E; Ki −→eff hv; E; (perform eff ) :: Ki (PushPerform)
K // eff = K 0 , (with wh handle )eff , K 00
where wh = closh (handler eff (val x → ev ) ((y, k) → eeff ) , E 0 )
*
+
e ;
eff

hw; E; (perform eff ) :: Ki −→eff(y = w) :: (k = K 0 ∗ E) :: E 0 ;(with wh handle )eff :: K 00
(HandlePerform)

F = (with wh handle )eff
where wh = closh (handler eff (val x → ev ) ((y, k) → eeff ) , E 0 )hw; E; F :: Ki −→eff hev ; (x = w) :: E 0 ; Ki
(HandleValue)

Fig. 3: Semantics of λeff

One-shot Algebraic Effects as Coroutines

11x ∈ Variables
K ∈ {Eff , Resend , True, False}l ∈ Labels
eff ∈ Effects→
v ::= nil | eff | K −v ? | l | x | λx.e−→?
e ::= v | K e | l : e | e e | let x = e in e
| match e with cases| create e | resume he e | yield e i−−−−−−−−−→→→
letrec ::= let rec x −x = e and x −x = e? in e−−−−−−−−−−→
cases ::= pat [cond ] → e;cond ::= when x = x−→
pat ::= K pat ? | x
C ::=  | C e | v C | let x = C in e | let x = v in C→
| match C with cases | let rec f −x = e in C
| C = e | eff = C−−−−−−−−−→→→| let rec f −x = e and f −x = e? in C
| create C | resume C e | resume l C | yield C | l : C

Fig. 4: the syntax of λac

We define the semantics of the language λac in the same way as de Mouraand Ierusalimschy. Due to lack of space we state it in Section A in the appendix
of this paper.
3.3

Translating λeff to λac

In this section, we present a program translation from λeff to λac . Our translation
is syntax-directed and compositional. Figure 5 defines the translation. For aλeff -term e, its translation VeWη is a λac -term where η is a finite map from λeff variables to λac -values. The map η is used to translate free variables in e. We
assume that η is extended by the syntax η [x → x0 ], which maps x to x0 , and yto η (y) for any y in the domain of η.
The translation is homomorphic for several expressions, including variable
dereference, λ-abstraction, applications, and let. We map effects Veff W to thesame effect, based on the assumption that the source and target languages shareeffects (more precisely, effect names).
The translation maps perform to yield by the following observation. In
algebraic effects, when an effect invocation occurs, the control is transferred to ahandler corresponding to an effect, while, in coroutines, when a yield is called12

Satoru Kawahara and Yukiyoshi Kameyama

in a coroutine, the control is transferred to resume, which resumes the coroutine.
Hence we can emulate the behaviour of perform by yield. The translation wraps
the arguments of perform with the tag Eff and translates them.
The handling expression with h handle e is translated to a simple application because the handler is mapped to a function.
The translation for a handler (the last case) is highly non-trivial. We first
define a function handler in λac and pass the translated semantic objects to it.
The recursive function handler takes four arguments: eff as an effect, vh as
a value handler, effh as an effect handler, and th as a thunk of computation to
be handled. It creates a coroutine co by the thunk th, and also three functions
continue, rehandle, and handle.
The function continue requires an argument and passes it to resume co, so itruns the rest of the coroutine co, or we can say, continue runs the continuation.
Then continue passes the result of the continuation to handle. Handling theresult of the continuation makes the handler to be a deep handler.
The function rehandle creates a new handler with handling k arg. It uses
continue as a value handler, so the expression finally continues the computationof co.
The function handle receives r as an argument, which is a yielded value
by the handled expression. It pattern-matches the tag of r and dispatches thecontrol. The first arm of the pattern match (Eff eff 0 v when eff 0 = eff ) is tohandle an effect invocation. During the computation of the handled expression,
if an effect eff ’ is performed with the argument v, then r has the form Eff eff 0 v.
If eff 0 equals to eff , it is the effect this handler can handle, and it passes v andcontinues to the effect handler effh. The second arm is the case when this handler
cannot handle the effect, in which case the function yields Resend r continue
to re-invoke the effect. The third and fourth arms are to resolve effects thrownfrom the second arm above. The third is the case the handler can handle wheneff 0 equals to eff . It applies effh such as the first arm, except passing rehandle
k as a continuation. k is the continuation of the inner handler and continue isthe continuation of the expression the current handler handles. In order to run
the later continuation after the former continuation is executed, we wrap k withrehandle, which contains the “current” continuation.
rehandle also adjusts the layer of coroutines. In the second arm, handle calls
yield, so the control runs away from one coroutine. We could write λarg. handle (k arg)
instead of rehandle k, only to treat the return value of the continuation. If we
did it, the layer of coroutines would decrease, and finally, we would get an error
calling yield outside of coroutine. So rehandle encapsulates the expression withcoroutine internally and avoid to decreasing the layer of coroutines.
The fourth arm rethrows the effect which the handler cannot handle. Thiscase is almost the same as the second arm, but it modifies the continuation forthe same reason described in the third arm. The last arm accepts any other value
and passes the value to the value handler. After defining functions, handler runs
continue with the argument nil.

One-shot Algebraic Effects as Coroutines

13

VxWη = η (x)Vλx.eWη = λx0 .VeWη x 7→ x0

Vv1 v2 Wη = (Vv1 Wη) (Vv2 Wη)
Vlet x = e in e0 Wη = let x0 = VeWη in Ve0 Wη x 7→ x0
Veff Wη = eff

Vperform eff vWη = yield (Eff (Veff Wη) (VvWη))Vwith h handle eWη = VhWη (λ .VeWη)

Vhandler eff (val x → ev ) ((x, k) → eeff )Wη =let eff = Veff Wη in
let vh = λx0 .Vev Wη x 7→ x0 in
let effh = λx0 k0 .Veeff Wη x 7→ x0 , k 7→ k0 in
handler eff vh effh

where handler =let rec handler eff vh effh th =let co = create th inlet rec continue arg = handle (resume co arg)and rehandle k arg = handler eff continue effh (λ .k arg)and handle r =match r with
| Eff eff 0 v
when eff 0 = eff → effh v continue| Eff→ yield (Resend r continue)| Resend (Eff eff 0 v) k when eff 0 = eff → effh v (rehandle k)| Resend effv k→ yield (Resend effv (rehandle k))→ vh r|in continue nil
in handler

Fig. 5: Translation from λeff to λac

Although our translation looks complicated, we emphasize that our translation is compositional and local, syntax-directed, and does not rely on higherorder stores or other fancy features, but need only basic functionality of asymmetric coroutines. For this simplicity, we note that a few people have alreadyported our translation to other languages.

144

Satoru Kawahara and Yukiyoshi Kameyama

Implementation

We have implemented algebraic effects and handlers in Lua and Ruby basedon the translation described in Section 3. Since the translation is local andcompositional, and the variables can be managed on the host language, we canrealize our implementation as a library.
The implementations are simple and easy to understand, however, several
issues have arisen in the process of implementation we will address below.
Multiple Effect Handler In this paper, we put the restriction that a handler may
catch only one effect in λeff . However, this restriction is only for the presentation
purpose. In fact, we have eliminated this restriction in our actual implementation so that one handler may catch multiple effects and all examples (including
the examples in this paper) that use multiple effects per handler run without
problems. We also note that there is no critical performance downgrade of having
multiple effects per handler.
Dynamic Effect Creation In the language λeff , we have no way to create new
effect instances. Again this is due to simplicity, and we can eliminate this restriction in our actual implementation. The merit of allowing dynamic creationof effect instances is that a certain kind of effectful programs does need theuniqueness of effect instances, for instance, Kiselyov’s examples[9].
Conflict with Other Effects An assumption on our translation is that all effects
are written via algebraic effects and handlers. If our source program uses othereffects besides algebraic effects and handlers, it will cause a serious problem, sinceother effects may interfere with the internally used coroutines. For instance, if
we use our library in Lua, and simultaneously use Lua’s coroutine with algebraic
effects, yielding a value in the source program may be accidentally caught by aninternal coroutine. As consequence we must not use native coroutines with (ourimplementation of) algebraic effects and handlers. Representing coroutines andother effects using algebraic effects and handlers is possible, but tedious if thelanguage has coroutines from the beginning.
This problem can be solved as follows, thanks to the expressivity of algebraic
effects and handlers. See the following code.
local Yield = inst()
local yield = function(v)return perform(Yield, v)
end
local create = function(f)return { it = f, handled = false }endOne-shot Algebraic Effects as Coroutines

15

local resume = function(co, v)
if co.handled thenreturn co.it(v)elseco.handled = true
return handler({val = function(x) return x end,
[Yield] = function(u, k)co.it = kreturn u
end})(function()
return co.it(v)
end)
end
end
The code in the last half is an implementation of coroutines by algebraic effects
in Lua. The function yield should throw a value to resume, so yield should bean effect invocation and resume should be a handler. This correspondence is theinverse of the translation in Figure 5. The function create creates a referencecell by a table. We represent a coroutine as a reference cell, which is initialized
to the function f and the flag handled explained later. The handler of resume
catches the invocation of yield with an argument and a continuation. This
continuation is the rest of computation of the coroutine, so the handler storesthe continuation to the cell and returns the value u. Since we provide a deep
handler, it is not necessary to set the handler multiple times. The tag handled
is to assert if the function is handled by the handler or not. The function resume
checks the flag; if the flag is off, resume turns on the flag and runs the function
with the handler. Otherwise, resume runs the function only.
Although we know several solutions to this direction, clearly we need to do
more to combine different kinds of effects in a single program.

5

Evaluation

We have conducted experiments on microbenchmark using our library in Lua,and implementation in Lua based on free monads [15], and compare their performance. All the code for the benchmark is publicly available in the GitHub
repository16 . In the following figures, the symbol N represents the result of ours
library, and  does of the free-monad based implementation. One of the benchmarks compares to native coroutines of Lua and indicates the result as the
symbol ? in a graph. The experiments have been conducted on the environmentin Table 1.
Figure 6 is the result of the benchmark for emulating a state monad. The
16

https://github.com/nymphium/effs-benchmark

16Satoru Kawahara and Yukiyoshi Kameyama

Table 1: Environment for Benchmark
Arch LinuxOSCPUIntel Core i7-8565U
Main memory
16GB DDR4
Lua processor
LuaJIT 2.05

2time(sec)

1.5
param (105 ×)
1
2
3
4
5
free 0.3560 0.7199 1.1741 1.5449 2.0303
ours 0.0273 0.0521 0.0939 0.1811 0.2090

1
0.5
2

3

4
5
param ·105

Fig. 6: Result of onestate benchmark

benchmark uses the function count, cited from [7], adjusted for our library andfree monad, and recursively runs a simple computation consisting of one-layer
one-effect handlers for the number of times as the input parameter. The resultshows that our library is approx. 10 times faster than the free-monad based
implementation for this simple case. The reason why free monads are rather
slow is that the bind operator requires a continuation as the next action, but
the cost for creating function closures is rather high for imperative languages
such as Lua. Also, functional languages such as Haskell may offer optimization
for free monads, while the benchmark uses naive implementation. Nevertheless,the results are encouraging for our embedding.
In the next experiments in Figure 7, the benchmark program iterates countfunction 3,000 times in deeply nested handlers. The parameter in the tabletime(sec)
0.4
param (10×)
1
2
3
4
5
free 0.0174 0.0303 0.0508 0.1374 0.1594
ours 0.0572 0.1722 0.3181 0.4064 0.5041

0.2

20

30

40
param

50

Fig. 7: Result of multistate benchmark

One-shot Algebraic Effects as Coroutines

17

corresponds to the number of nested handlers/coroutines, hence 50 (the rightmost column) is already a rather unrealistic situation, but we included thisexperiment as an extreme. As expected, our library runs three times slower than
the free monad does for this case. The reason is that rehandle creates a new
coroutine, which is called every time an effect is caught from the other handler
shown in Figure 5, so it degrades the performance.
In the next experiment, the function looper performs algebraic effects in theiteration of the for loop, where the number of iteration is given as a parametershown in the table of Figure 8. The benchmark program invokes an effect in atime(sec)
0.8
0.6

param (105 ×)
1
2
3
4
5
free 0.1650 0.3455 0.5304 0.7204 0.9319
ours 0.0215 0.0416 0.0630 0.0844 0.1064

0.4
0.2
2

3

4
5
param ·105

Fig. 8: Result of looper benchmark

for-loop and set a handler out of the loop to catch the effect. Our library runs
9 times as fast as the free-monad based implementation. It should also be notedthat free monads require the forM-operator rather than the for-operator, which
has a particular overhead. Again an advanced compiler may be able to eliminate
all or part of this kind of monadic overhead.
Figure 9 shows the result of the benchmark, which solves the same-fringe
problem by using algebraic effects and coroutines. The benchmark creates a tree,time(sec)
0.4

param (104 ×)
1
2
3
4
5
free 0.0507 0.1837 0.3522 0.4761 0.5886
ours 0.0067 0.0127 0.0186 0.0252 0.0296
coroutines 0.0042 0.0082 0.0119 0.0158 0.0190

0.2

2

3

4
5
param ·104

Fig. 9: Result of same_fringe benchmark

18Satoru Kawahara and Yukiyoshi Kameyama

runs a solution for the same fringe problem, and measures the performance. The
benchmark gives the number of leaves as a parameter. We implement coroutines
to solve it, by algebraic effects with free monad, and our library, described in
Section 4. We also implement the solver with native coroutines of Lua. Our
library yields 18 times performance gain compared to the free-monad method.
Remarkably, our library is only 1.6 times slower than native coroutines.
In summary, our way of implementing algebraic effects and handlers is advantageous in several programming languages from the performance viewpoint.
We also want to emphasize that writing effectful programs using coroutines isharder than writing the same programs using algebraic effects and handlers,
which provide high-level abstraction.

6

Related Work and Discussion

In this section, we discuss closely related work which has not been mentioned inthis paper and picks up a few important issues for discussion.
Shallow Handler We have shown the embedding with deep handlers, which cancatch the effect invocation even during the execution of the continuation.
In the literature, there has been a discussion on deep vs shallow handlers [6],and it has its own merits. We have also implemented the shallow handler withcoroutines. The idea is simple; after the handler catches the effect, the handler always resends effects to the outer handler. We have explained the role ofrehandle in Figure 5 that it encapsulates the continuation with a coroutine toadjust the layer of coroutines, and rehandles the effect invocation in the continuation. In the shallow setting, it is also necessary to reset the number of thelayer of coroutines, which might degrade the performance. On the other hand,rehandling is not needed because it is shallow.
One-shot Continuations It should be noted that we are not the first to study
the one-shot variant of control operators. James and Sabry stated that the yield
operator for generator, which is a restricted variant of coroutines and can befound in various languages, is one-shot delimited continuations. They also defineda generalized yield operator which has multi-shot continuations and show theconnection between it and the delimited-control operators.
Multicore OCaml is a dialect of OCaml which natively supports algebraic
effects by runtime stack manipulation. Its motivation is to write concurrent
programming in direct-style[5]. They provide one-shot continuations due to theperformance problem, and if multi-shot continuations are needed, they allow
explicit copy for continuations.
React, a popular web framework for JavaScript has a utility called Hooks17 ,which makes components with side-effects modular. Abramov, who is one ofReact developers, stated the relevance between Hooks and algebraic effects in
17

https://reactjs.org/docs/hooks-reference.html

One-shot Algebraic Effects as Coroutines

19

his blog post18 . We think we can simulate the abilities of Hooks by one-shot
algebraic effects.

7

Conclusion

We have presented a novel embedding technique for algebraic effects and handlers
into asymmetric coroutines, and shown translation from the former to the latter as simple, direct, syntax-directed compositional translation. Compared withother embeddings or other ways, our technique can apply to many languages
which have coroutines due to the simplistic nature of our embedding. We havedemonstrated the applicability of our embedding by implementing the libraries
in Lua and Ruby. Our technique seems to be attractive for other researchers,
and some of them have implemented our translation for other languages such
as JavaScript and Rust. We expect that the simplicity of our implementation isadvantageous to be used by more people, more languages, and more applications.
The key of our development is the one-shotness restriction of continuations.
Our embedding uses the rest of the coroutine thread as a continuation, andthe status of the coroutine cannot be copied, so the limitation exists that acontinuation can be executed at most once. One-shotness is a dynamic property,
and its static approximation, liearly used (delimited) continuations, or linear
continuation-passsing style, are the target of active research in the past. We
hope that the formal foundation of this paper’s result is studied more deeply,
and coroutines and their connection with other control operators find a solid
theoretical foundation.

References
1. Bauer, A., Pretnar, M.: Programming with Algebraic Effects and Handlers.
Journal of Logical and Algebraic Methods in Programming 84,(03 2012).
https://doi.org/10.1016/j.jlamp.2014.02.001
2. Brachthäuser, J., Schuster, P.: Effekt: extensible algebraic effects in Scala (shortpaper). pp. 67–72 (10 2017). https://doi.org/10.1145/3136000.3136007
3. Brachthäuser, J., Schuster, P., Ostermann, K.: Effect handlers for the masses.
Proceedings of the ACM on Programming Languages 2, 1–27 (10 2018).
https://doi.org/10.1145/3276481
4. Bruggeman, C., Waddell, O., Dybvig, R.: Representing Control in
the Presence of One-Shot Continuations. vol. 31, p.
(02 1970).
https://doi.org/10.1145/249069.231395
5. Dolan, S., White, L., Madhavapeddy, A.: Multicore OCaml. In: OCaml Users andDevelopers Workshop (2014)
6. Hillerström, D., Lindley, S.: Shallow Effect Handlers. In: Asian Symposium on
Programming Languages and Systems. pp. 415–435. Springer (2018)
7. Kammar, O., Lindley, S., Oury, N.: Handlers in Action. vol. 48, pp. 145–158 (092013). https://doi.org/10.1145/2500365.2500590
18

https://overreacted.io/algebraic-effects-for-the-rest-of-us/

20

Satoru Kawahara and Yukiyoshi Kameyama

8. Kiselyov, O., Ishii, H.: Freer Monads, More Extensible Effects. ACM SIGPLAN
Notices 50, (03 2015). https://doi.org/10.1145/2887747.2804319
9. Kiselyov, O., Sivaramakrishnan, K.: Eff Directly in OCaml. Electronic
Proceedings in Theoretical Computer Science 285, 23–58 (12 2018).
https://doi.org/10.4204/EPTCS.285.2
10. Leijen, D.: Algebraic Effects for Functional Programming. Tech. rep., Technical
Report. 15 pages. (2016)
11. Leijen, D.: Implementing Algebraic Effects in C. pp. 339–363 (11 2017).
https://doi.org/10.1007/978-3-319-71237-6 17
12. Moura, A., Ierusalimschy, R.: Revisiting Coroutines. ACM Transactions on Programming Languages and Systems 31,(07 2004).
https://doi.org/10.1145/1462166.1462167
13. Plotkin, G., Power, J.: Algebraic Operations and Generic Effects. Applied Categorical Structures 11, 69–94 (02 2003). https://doi.org/10.1023/A:1023064908962
14. Plotkin, G., Pretnar, M.: Handling Algebraic Effects. Logical Methods in Computer
Science 9, (12 2013). https://doi.org/10.2168/LMCS-9(4:23)2013
15. Pretnar, M., Saleh, A.H., Faes, A., Schrijvers, T.: Efficient compilation of algebraic
effects and handlers. CW Reports, volume CW708 32 (2017)

A

Semantics of λac

Auxiliary functions Figure 10 defines two auxiliary functions for pattern matching of λac . FV p (pat) is the set of free variables in pat. matchable (v, pat) is a −→ [−→
FV p K pat =p ∈ pat.FV p (p)FV p (x) = {x}

−→
−→
→
→
v , p ∈ pat.matchable (v, p)
matchable K −v , K 0 pat = K =K K 0 ∧ ∀v ∈ −θ1 ⊕ θ2 = ∅−→→genstore K −v , K pat =∀x ∈ dom (θ1 ) .x ← θ1 (x) ,∀y ∈ dom (θ2 ) .y ← θ2 (y)Mgenstore (v, p)

−
→
−
v∈→
v ,p∈pat

genstore (v, x) = ∅ [x ← v]

Fig. 10: Auxiliary functions for the semantics of λac

One-shot Algebraic Effects as Coroutines

21

predicate to assert that,given a value v and a pattern pat, the value matches thepattern. The operator ⊕ concatenates two stores and ∅ is an empty store. The
function genstore creates a new store which consists of pairs of a variable anda value (which consists of constructors). For example, by calling genstore withthe arguments Resend (Eff w v) u (for some values w, v and u), and a nested
pattern Resend (Eff y x) k, we get a new store ∅ [y ← w , x ← v, k ← u].
Small-step Semantics Figure 11 shows the operational semantics of λac by thetransition (−→ac ) of the state he, θi, an expression e and a store θ. dom (θ) is
the domain of θ, and θ (x) is a value associated with the variable x. Note thateven if θ (l) = nil, we include l in dom (θ). In those cases such as introducing avariable or a label (App, Let, LetRec, Create, Match, and MatchWhen),
we identify α-equivalent terms and assume that we rename bound variables
appropriately for substitution to be defined at any time. The distinctive pattern
is similar to a variable but generates no binding after pattern matching, so weallow to be overwritten. The rules contain those for variable lookup (Lookup),
function application (App), let, and let rec (Let and LetRec). The function
Create is to make a new coroutine. It creates a fresh label l, binds the coroutine
to l, and returns its label to the context C. The function Resume produces alabelled expression, an application θ (l) v with a label l. θ (l) v is what finds
the body corresponding to the label l from θ and apply v. The created labelled
expression l : θ (l) v expresses the computation in the coroutine labelled byl. To prevent the rest of the coroutine from being referred, the rule Resume
invalidates the associatedvalue by setting it to nil. The function Yield suspends
the current computation of a coroutine and returns to the parent coroutinewith an argument. Since the target calculus represents asymmetric coroutines,
a coroutine can be a parent of another coroutine by resuming it. The function
LabelledReturn transfers the result of the computation v in the coroutine
l to its caller. The functions EqT and EqF compare two effect operations.
The operator =eff judges whether two given effects are the same. The functions
Match and MatchWhen are for pattern-matching. The second rule applies−
when K →v matches a pattern, and the match case has a guard c. This ruletransforms the guard to another match expression, with assigning the values tothe corresponding variables in the pattern. The assignment may affect patternvariables in the guard c. If a guard returns True, pattern matching is successful,and the body of the True clause is evaluated; otherwise, we go to match against
the rest of the patterns.

22

Satoru Kawahara and Yukiyoshi Kameyama

hC[x], θi −→ac hC[θ(x)], θi(Lookup)x∈/ dom (θ)(App)

hC [(λx.e) v] , θi −→ac hC [e] , θ [x ← v]ix∈/ dom (θ)(Let)
hC[let x = v in e0 ], θi −→ac hC[e], θ[x ← v]i
n
o
−−→
→
→
∀z ∈ f, −x , g, −y .z ∈/ dom (θ)
→#+ (LetRec)+*"*
let rec f −x = ef→f ← λ−
x .ef ,
−
−
−
−
−
−
−
−
−
→
→
 , θ −→ac C[e], θ −−−−−−−→C  and g −y = eg→g ← λ−
y .eg
in e
l∈
/ dom (θ)(Create)hC [create v] , θi −→ac hC [l] , θ [l ← v]i
hC [resume l v] , θi −→ac hC [l : θ (l) v] , θ [l ← nil]i(Resume)hC1 [l : C2 [yield v]] , θi −→ac hC1 [v] , θ [l ← λx.C2 [x]]i(Yield)hC [l : v] , θi −→ac hC [v] , θieff =eff eff(LabelledReturn)0hC [eff = eff 0 ] , θi −→ac hC [True] , θieff 6=eff eff 0
hC [eff = eff 0 ] , θi −→ac hC [False] , θi

(EqT)

(EqF)

→
¬matchable (K −v , pat) +*  match K −→v with→C  pat [cond ] → e;  , θ −→ac hC [match K −v with cases] , θi
cases
(MatchNext)→∀x ∈ FV p (pat) .x ∈/ dom (θ)
matchable (K −v , pat)→θ0 = θ ⊕ genstore (K −v , pat)(Match)→hC [match K −v with pat → e; cases] , θi −→ac hC[e], θ0 i→
∀x ∈ FV p (pat) .x ∈/ dom (θ)
matchable (K −v , pat)−→0θ = θ ⊕ genstore (K v , pat)match c with +*  match K −*→ True → e; +v with

 0

,θ


C pat when c → e;
, θ −→ac C  False →

−
→

cases
match K v with 
cases(MatchWhen)Fig. 11: Semantics of λac