How do you
implement
Algebraic Effects?
びしょ〜じょeffect system 勉強会

May 26, 2019

やること

Algebraic Effects
and Handlersのさまざまなインプリ方法について考える。

Table of Contents

Who talks
Introduction
Low-level Manipulations
Coroutines

Multiprompt shift/reset
Free Monad
N-Barrelled CPS
Good Point as Libraries
Conclusion

Who talks
こんにちは、びしょ〜じょです。

I 筑波大学大学院 M2
プログラム言語や型とか検証などの研究室でプログラム変換の研究� � � NymphiumWho talks

1/21

Introduction
Algebraic Effects の様々な実装

Introduction

2/21

Introduction
Algebraic Effects の様々な実装
I ライブラリ� eff.lua
� Effekt� libhandler• etc.

Introduction2/21

Introduction
Algebraic Effects の様々な実装
I ライブラリ� eff.lua
� Effekt� libhandler• etc.

I 言語 (処理系)� Eff
� Multicore OCaml� Koka• etc.

Introduction

2/21

Introduction
Algebraic Effects の様々な実装
I ライブラリ� eff.lua
� Effekt� libhandler• etc.

I 言語 (処理系)

どうやって実装されているの??

� Eff
� Multicore OCaml� Koka• etc.

Introduction

2/21

Low-level Manipulations
e.g.) � libhandler, implemented in C

Low-level Manipulations

3/21

Low-level Manipulationse.g.) � libhandler, implemented in C
Algebraic Effects
effect invocation
effect handler
continuation

Low-level Manipulations

7→
libhandler
7→
longjmp7→
stack frame + ip
7→
stack frame + ip

3/21

pros/cons

Low-level Manipulations.pros/cons

4/21

pros/cons

低レベル実装• FFI で様々な言語から呼び出せる• 速い

Low-level Manipulations.pros/cons

4/21

pros/cons

低レベル実装• FFI で様々な言語から呼び出せる• 速い

実装が大変かつ限定的

Low-level Manipulations.pros/cons

4/21

pros/cons

低レベル実装• FFI で様々な言語から呼び出せる• 速い

実装が大変かつ限定的⇓{処理系, ライブラリ}バックエンド向けか

Low-level Manipulations.pros/cons

4/21

Coroutines
� Multicore OCaml, implementedwith fiber, in C [DWS+ 15]e.g.)� eff.lua , implemented with coroutine,in Lua

Coroutines

5/21

Coroutines
� Multicore OCaml, implementedwith fiber, in C [DWS+ 15]e.g.)� eff.lua , implemented with coroutine,in Lua
Algebraic Effects
effect invocation
effect handler
continuation

Coroutines

7→
7→
7→
7→

Coroutines
yieldcreate & resume
coroutine

5/21

Coroutines
Algebraic Effects
effect invocation
effect handler
continuation

Coroutines

7→
7→
7→
7→

Coroutines
yieldcreate & resume
coroutine

6/21

Coroutines
Algebraic Effects
effect invocation
effect handler
continuation

Coroutines

7→7→
7→7→

Coroutines
yieldcreate & resume
coroutine

6/21

Coroutines
Algebraic Effects
何回も呼び出したいけどeffect invocation
effect handler
continuation

Coroutines

7→
7→
7→
7→

Coroutines
状態をコピーできないyield
create & resume
coroutine

6/21

Coroutines
Algebraic Effects
何回も呼び出したいけどeffect invocation
effect handler
continuation

7→
7→
7→
7→

Coroutines
状態をコピーできないyield
create & resume
coroutine

coroutines をコピーするような操作がなければ継続はワンショットに限定される

Coroutines

6/21

pros/consCoroutines.pros/cons

7/21

pros/cons

さまざまな言語で実装可能
Coroutines を持ってる言語は多い
Lua, Ruby, JS, Kotlin, Python, etc.

Coroutines.pros/cons

7/21

pros/cons

さまざまな言語で実装可能
Coroutines を持ってる言語は多い
Lua, Ruby, JS, Kotlin, Python, etc.

継続はワンショット
非決定計算とかは書けない

Coroutines.pros/cons

7/21

pros/cons

さまざまな言語で実装可能
Coroutines を持ってる言語は多い
Lua, Ruby, JS, Kotlin, Python, etc.

継続はワンショット
非決定計算とかは書けない
coroutine を複製する操作があれば……
Multicore OCaml の Obj.clone_continuation の実装

Coroutines.pros/cons

7/21

Multiprompt shift/reset

Multiprompt shift/reset

8/21

Multiprompt shift/resete.g.)racket/control in Racket( reset(+ 2 ( reset(+ 3 ( shift _k 4)))));; →? ( reset (+ 2 4)) →? 6

Multiprompt shift/reset

8/21

Multiprompt shift/resete.g.)racket/control in Racket( let (( p ( make - continuation - prompt - tag ))(q ( make - continuation - prompt - tag )))( reset - at p(+ 2 ( reset - at q(+ 3 ( shift - at p _k 4))))));; →? ( reset - at p (+ 2 ( shift - at p _k 4)));; →? 4Multiprompt shift/reset

8/21

Multiprompt shift/resete.g.)racket/control in Racket
対応する prompt まで飛んでいく( let (( p ( make - continuation - prompt - tag ))(q ( make - continuation - prompt - tag )))( reset - at p(+ 2 ( reset - at q(+ 3 ( shift - at p _k 4))))));; →? ( reset - at p (+ 2 ( shift - at p _k 4)));; →? 4Multiprompt shift/reset

8/21

Multiprompt shift/resete.g.) � Effekt, implemented in Scala

Multiprompt shift/reset

9/21

Multiprompt shift/resete.g.) � Effekt, implemented in Scala
Algebraic Effects 7→
effect operation
effect invocation
effect handler
continuation

Multiprompt shift/reset

7→7→
7→7→Multiprompt
shift/reset
prompt tag
shift-atreset-at
continuation

9/21

pros/consMultiprompt shift/reset.pros/cons

10/21

pros/cons

直感的で素直な対応
実装しやすいeffect の dynamic instantiation も対応
multi-state など

Multiprompt shift/reset.pros/cons

10/21

pros/cons

直感的で素直な対応
実装しやすいeffect の dynamic instantiation も対応
multi-state など
あまり一般的でない実装が少ない

Multiprompt shift/reset.pros/cons

10/21

Free Monad

Free Monad

11/21

Free Monadtype 'a free =| Pure : 'a → 'a free
| Impure : ' arg * (' res → 'a free ) → 'a free
let rec (=) op f =match op with| Pure x → f x| Impure (x , k ) →Impure (x , fun y → k y = f)

Free Monad

11/21

Free Monade.g.) � Eff, implemented in OCaml

Free Monad

12/21

Free Monade.g.) � Eff, implemented in OCaml
Algebraic Effects
effect invocation
effect handler
continuation

Free Monad

7→ Free Monad
7→
Impure7→
run7→
rhs of (=)

12/21

pros

Free の資産が使える[PSF+ 17] では equation rules や type-directed
optimisation などを駆使して実行効率の良いコードを生成Free Monad.pros

13/21

cons

ただの Free Monad
monadic な書き方ができないとちょっとつらいHaskell の do, F#の computation expression, Scala の for,etc.

Free Monad.cons

14/21

N-Barrelled CPS
Double-Barrelled CPS [Thi02] を拡張するといい感じに使えるのでは？

N-Barrelled CPS

15/21

N-Barrelled CPS
Double-Barrelled CPS [Thi02] を拡張するといい感じに使えるのでは？
sort(pure) CPS
CPS + Exception

N-Barrelled CPS

number ofcontinuations
1
2

15/21

N-Barrelled CPS
Double-Barrelled CPS [Thi02] を拡張するといい感じに使えるのでは？
number ofcontinuations(pure) CPS
1
CPS + Exception
2
CPS + Algebraic Effects 1 + number ofeffect handlers
sort

N-Barrelled CPS

15/21

N-Barrelled CPS

handler| effect ( Foo x) k -> k (x + x)
| effect ( Bar y) k -> k (y * y)
| v -> v * 20

N-Barrelled CPS

16/21

N-Barrelled CPS
handler| effect ( Foo x) k -> k (x + x)
| effect ( Bar y) k -> k (y * y)
| v -> v * 20⇓[( Value , fun v k -> k (v * 20))
( Foo , fun x k -> k (x + x ));( Bar , fun b k -> k (b * b ))]N-Barrelled CPS

16/21

N-Barrelled CPS

Algebraic Effects
effect handlereffect invocation
handler nesting

N-Barrelled CPS7→
N-Barrelled CPS
7→(effect-id * handler) list
7→
lookup &run
7→
list concatenation

17/21

N-Barrelled CPS
N Barrels
Algebraic Effects 7→
N-Barrelled CPS
effect handler 7→ ::::::::::::(effect-id ::* :::::::::::handler):::::
list
effect invocation 7→
lookup &runhandler nesting 7→
list concatenation

N-Barrelled CPS

17/21

N-Barrelled CPS
例
handle ( perform ( Foo 5)) with| effect ( Foo x) k → k (x + x)
| effect ( Bar b) k → k (b * b)
| (* value*) v → v * 20

N-Barrelled CPS

18/21

N-Barrelled CPS
例
handle ( perform ( Foo 5)) with| effect ( Foo x) k → k (x + x)
| effect ( Bar b) k → k (b * b)
| (* value*) v → v * 20

⇓ 雰囲気で変換 �( fun k 0 h 0 →( fun k 1 h 1 → k 1 5) ( fun v 1 →( lookup eff h 0 Foo v 1 ) ( fun res Foo →( lookup val h 0 res Foo k 0 ))) h 0) ( fun x → x)
[ ( VALUE , fun v k → k (v * 20));( Foo , fun x k → k (x + x ));( Bar , fun b k → k (b - b )) ]N-Barrelled CPS

18/21

pros/cons

N-Barrelled CPS.pros/cons

19/21

pros/cons
CPS の資産が得られるかも

N-Barrelled CPS.pros/cons

19/21

pros/cons
CPS の資産が得られるかもグローバルな変換が必要

N-Barrelled CPS.pros/cons

19/21

pros/cons
CPS の資産が得られるかもグローバルな変換が必要⇓
処理系の中間表現向けかな

N-Barrelled CPS.pros/cons

19/21

pros/cons
CPS の資産が得られるかもグローバルな変換が必要⇓
処理系の中間表現向けかな

related) � Koka
compililing to JS or C# via type-directedselective CPS [Lei16]

N-Barrelled CPS.pros/cons

19/21

Good Point as Libraries

Good Point as Libraries

20/21

Good Point as Libraries
様々なコントロール抽象を Algebraic Effects という 1 つのインターフェースに落とし込める

Good Point as Libraries

20/21

Good Point as Libraries
様々なコントロール抽象を Algebraic Effects という 1 つのインターフェースに落とし込める
Delimited
Continuations
Coroutines(Free) Monad??

Good Point as Libraries

20/21

Good Point as Libraries
様々なコントロール抽象を Algebraic Effects という 1 つのインターフェースに落とし込める

Algebraic
Effects

Delimited
Continuations
Coroutines(Free) Monad??

Good Point as Libraries

20/21

Conclusion

Conclusion

21/21

Conclusion
I Algebraic Effects の実装方法は様々

Conclusion

21/21

Conclusion
I Algebraic Effects の実装方法は様々
I 実装言語などに応じて使い分ける

Conclusion

21/21

Conclusion
I Algebraic Effects の実装方法は様々
I 実装言語などに応じて使い分ける
I ライブラリ化することでコントロール抽象の抽象化

Conclusion

21/21

Conclusion
I Algebraic Effects の実装方法は様々
I 実装言語などに応じて使い分ける
I ライブラリ化することでコントロール抽象の抽象化

Conclusion

もっといろいろな言語でAlgebraic Effects
を!!

21/21

参考文献
[DWS+ 15] Stephen Dolan et al. Effective
concurrency through algebraic effects.
In: OCaml Workshop. 2015, p. 13.
[Lei16]

Daan Leijen. Algebraic Effects for
Functional Programming. Tech. rep.
MSR-TR-2016-29, 2016, p. 15.

[PSF+ 17]

Matija Pretnar et al. Efficient compilationof algebraic effects and handlers. In: CW
Reports, volume CW708 32 (2017).

[Thi02]

Hayo Thielecke. Comparing control
constructs by double-barrelled CPS. In:
Higher-Order and Symbolic Computation