One-shot
Algebraic Effects
asCoroutines@TFP 2020
Satoru Kawahara and Yukiyoshi Kameyama
University of Tsukuba, Japan

Algebraic Effects & Handlers
I Modular way to write computational effects
I Intuition: Resumable exception

1/18

Algebraic Effects & Handlers
Exceptions CANNOT resume the rest of computation.
exception Error : int → exn
let handle_error th =try th () with| Error i → i
handle_error (fun () →(raise (Error 2)) + 3)

2/18

Algebraic Effects & Handlers
Exceptions CANNOT resume the rest of computation.
exception Error : int → exn
let handle_error th =try th () with
| Error i → i
handle_error (fun () →(raise (Error 2)) + 3)

2/18

Algebraic Effects & Handlers
Exceptions CANNOT resume the rest of computation.
exception Error : int → exn
let handle_error th =try th () with
| Error i → irest of computation
handle_error (fun () →(raise (Error 2)) + 3)3

2/18

Algebraic Effects & Handlers
Algebraic Effect CAN resume the rest of computation.
effect Defer : (() → ()) → ()let handle_defer th =handle th () with| Defer f k → k (); f ()handle_defer (fun () →(#Defer (fun () → puts "world"));puts "hello")
3/18

Algebraic Effects & Handlers
Algebraic Effect CAN resume the rest of computation.
effect Defer : (() → ()) → ()let handle_defer th =handle th () with| Defer f k → k (); f ()handle_defer (fun () →(#Defer (fun () → puts "world"))"world"));puts "hello")
3/18

Algebraic Effects & Handlers
Algebraic Effect CAN resume the rest of computation.
effect Defer : (() → ()) → ()let handle_defer th =handle th () with| Defer f k → k (); f ()handle_defer (fun () →;(#Defer (fun () → puts "world"))"world"));"hello"puts "hello")
3/18

Algebraic Effects & Handlers
Algebraic Effect CAN resume the rest of computation.
effect Defer : (() → ()) → ()let handle_defer th puts=
"hello"handle th () with| Defer f k → k (); f ()handle_defer (fun () →;(#Defer (fun () → puts "world"))"world"));"hello"puts "hello")
3/18

Algebraic Effects & Handlers
I Modular way to define computational effects
I Intuition: Resumable exception
Hot topic for Researchers• theoretical development• implementing various control abstractions:delimited controls, monads, concurrency,
probabilistic/reactive programming, etc.

4/18

Algebraic Effects & Handlers
I Modular way to define computational effects
I Intuition: Resumable exception
Hot topic for Researchers• theoretical development• implementing various control abstractions:delimited controls, monads, concurrency,
probabilistic/reactive programming, etc.

But is it hot topic for Programmers?
4/18

Algebraic Effects for Programmers

Yes!

5/18

Algebraic Effects for Programmers

Yes!
However, we must solve these problems:
I Only research languages have AE as a built-in
I Few languages can implement AE as a library

5/18

Algebraic Effects for Programmers
Is there any way to implement AE ?
I available in popular languages
I without siginificant overhead

6/18

Our solution

One-shot Algebraic Effects
as Coroutines

7/18

Our solution

One-shot Algebraic Effects
as Coroutines
widely available in those which have coroutines
shallow embedding: withouth large overhead

7/18

Our solution

One-shot Algebraic Effects
as Coroutines
widely available in those which have coroutines
shallow embedding: withouth large overhead

only with one-shot restriction

7/18

Technically
To implement AE by coroutines……

8/18

Technically
To implement AE by coroutines……
1. define two languages• λeff · · · · · · λ with One-shot Algebraic Effects• λac · · · · · · λ with Asymmetric Coroutines

8/18

Technically
To implement AE by coroutines……
1. define two languages• λeff · · · · · · λ with One-shot Algebraic Effects• λac · · · · · · λ with Asymmetric Coroutines
2. define a translation from λeff to λac

8/18

Technically
To implement AE by coroutines……
1. define two languages• λeff · · · · · · λ with One-shot Algebraic Effects• λac · · · · · · λ with Asymmetric Coroutines
2. define a translation from λeff to λac
based on macro expressibility [Felleisen 1991]
local and compositional

8/18

Technically
To implement AE by coroutines……
1. define two languages• λeff · · · · · · λ with One-shot Algebraic Effects• λac · · · · · · λ with Asymmetric Coroutines
2. define a translation from λeff to λac
based on macro expressibility [Felleisen 1991]
local and compositional

8/18

Connection between two controls……
handle… (#Op x) ……
………………………

Coroutines
resume co; resume coco… (yield x) ……
…………………………

……

……

Algebraic Effects

9/18

Connection between two controls……
handle… (#Op x) ……
………………………

Coroutines
resume co; resume coco… (yield x) ……
…………………………

……

……

Algebraic Effects

9/18

Connection between two controls
Algebraic Effects…… k o; k uhandle… (#Op x) ……
………………………

Coroutines
resume co; resume coco
… (yield x) ……
…………………………

……

……
9/18

Connection between two controls
Algebraic Effects…… k o; k uhandle… (#Op x) ……
………………………

Coroutines
resume co; resume coco… (yield x) ……
…………………………

……

……
9/18

Connection between two controls
Algebraic Effects…… k o; k uhandle… (#Op x) ……
………………………

Coroutines
resume co; resume coco
… (yield x) ……
…………………………

……

……
9/18

Connection between two controls
Algebraic Effects…… k o; k uhandle… (#Op x) ……
………………………

Coroutines
resume co; resume coco… (yield x) ……
…………………………

……

……
9/18

Connection between two controls
One-Shot
Algebraic Effects…… k o; k uhandle… (#Op x) ……
………………………

Coroutines
resume co; resume coco… (yield x) ……
…………………………

……

……
9/18

Translation
One-shot
Algebraic Effects→Asymmetric
Coroutines

10/18

Translation
One-shot
Algebraic Effects→Asymmetric
Coroutines⇓V−W :

λeff → λac• simple …… easy to implement•local…… as library
10/18

Going to real world
Our translation as libraries
Luapublished on � GitHub
Ruby

11/18

Going to real world
Our translation as libraries
Luapublished on � GitHub
Ruby
JavaScript
implemented by other users
based on ours
Rust

11/18

Going to real world
Our translation as libraries
Luapublished on � GitHub
Ruby
JavaScript
implemented by other users
based on ours
Rust◦

the fruits of versatility and simplicity
11/18

Going to real world
Lua: 200 lines
local Choice = inst()
local always_right = handler {[Choice] = function(k, l, r)
return k(r)end}always_right(function()
perform(Choice(1, 2)) + 3end)

Ruby: 340 lines
Choice = Effect.new
always_right = Handler.new.on(Choice){|k, l, r| k[r] }always_right.run {Choice.perform(1, 2) + 3}

12/18

Evaluation
We compare the performance in Lua:
N our library based on the translation
 implementation based on Free Monad

13/18Evaluation
We compare the performance in Lua:
N our library based on the translation
 implementation based on Free MonadFreesmaller is fasterMonad Ours
onestate
10.10
multistate 1
3.16
looper
10.11
same-fringe 1
0.04
13/18

onestate• invoking effect inside a rec fun• catching by handler outside the funSingle effect◦time(sec)
2
1.5
1
0.5
2N

Ours
Free Monad

34
param

5·105

10x fasterI Ours:continuations as coroutines
I Free Monad:
continuations as function
closures14/18

multistate• onestate with fixed parameter• catching the outermost handler

Nested handlertime(sec)
0.4

0.2

20NOursFree Monad3040
param

50

× 0.3x but……
I Free Monad also slows
down
0.6〜0.07x of onestate
I Nesting 50 is extreme
and will not be a real
problem
15/18

looper• invoking effect inside of loop
• catching them outside of loop

Iteration◦time(sec)

9x faster
I Ours: built-in for loop
I Free Monad:
forM with function closures

0.8
0.6
0.4
0.2
2N

34
param

5·105

Ours
Free Monad
16/18

same fringe
Re-implementing
native effects
time(sec)
0.150.1• re-implementing coroutine• solving same-fringe problem◦◦

5 · 10−22?
N34
paramLua native coroutine
Ours
Free Monad

5·10418x than Free Monad
0.65x than NativeCoroutines
It can be run without large
overhead

17/18

Summary
A new Algebraic Effects implementation
using Coroutines:
I relate one-shot AE with Coroutines
I define macro-expressible translation
I implement the translation as a library
I resolve existing problems
widely available in those which have coroutines
shallow embedding: withouth large overhead
direct-style without special syntax or transpilation
18/18

One-shot continuation/AE
expressive power copying stack

continuation

multi-shotstrongnecessary

one-shotweakunnecessary

weakunnecessary

continuation
coroutines

I No copying makes it run efficiently◦

Exception, State, Concurrent, DI
× Nondet, Backtracking

Translation
macro
expressible

w/o state
impl

w/ state

λeff withmulti-shot

λac
⊇

⊇

λeff

V−W

λ

non-standard

λac withsnapshotConflics with existing effects
Our translation V−W is defineddisregard for the effects of host language
coroutines, exceptions, etc.

re-implement them with AE
to resolve the conflict
enables to mix in their effects