0から知った気になる
Algebraic Effects
2019/09/30
びしょ〜じょ本日の内容Algebraic Effectsを知った気にさせる自己紹介
こんにちは､びしょ～じょです● 筑波大学大学院M2
Algebraic Effectsからコルーチンに変換する研究● 株式会社HERPでエンジニア
TSとかたまにHaskellを書いてる

We're hiring!

まずはじめに皆さんはAlgebraic Effects知ってますか? 🙋● 知ってるし書いたことがある● 名前は聞いた● 知らないAlgebraic Effectsを一言でいうと限定継続が取得できる例外およびハンドラ

限定継続🤔❓

継続

継続は分かりますか?🙋
● わたしはschemerです● はいはいコールバック関数ね● 知らない継続

コールバック関数です!!!!! (完)継続
例: ファイルを読み込み､結果をコールバック関数に渡す

readFile(file, res ⇒ { ...... })継続
例: ファイルを読み込み､結果をコールバック関数に渡すこれ継続
readFile(file, res ⇒ { ...... })継続

readFile(file, res ⇒ { ...... })継続

readFile(file, res ⇒ { ...... })const res = await promisify(readFile)(file);......

継続
readFile(file, res ⇒ { ...... })const res = await promisify(readFile)(file);......

promisify(readFile)(file).then(res ⇒ {......});

継続
readFile(file, res ⇒ { ...... })const res = await promisify(readFile)(file);......

promisify(readFile)(file).then(res ⇒ {......});

継続
前の計算結果を使って実行する残りの計算
const t = f(10);const u = g(t);const v = h("aaa");......

継続
前の計算結果を使って実行する残りの計算
const t = f(10);const u = g(t);const v = h("aaa");......
継続渡しスタイルx ▷ k ≡ k(x)f(10)▷ ((t) ⇒ g(t)▷ ((u) ⇒ h("aaa")▷ ((v) ⇒ ......
)))

継続
前の計算結果を使って実行する残りの計算
const t = f(10);const u = g(t);const v = h("aaa");......
継続渡しスタイルx ▷ k ≡ k(x)f(10)▷ ((t) ⇒ g(t)▷ ((u) ⇒ h("aaa")▷ ((v) ⇒ ......
)))

継続
前の計算結果を使って実行する残りの計算
const t = f(10);const u = g(t);const v = h("aaa");......
継続渡しスタイルx ▷ k ≡ k(x)f(10)▷ ((t) ⇒ g(t)▷ ((u) ⇒ h("aaa")▷ ((v) ⇒ ......
)))

継続
前の計算結果を使って実行する残りの計算
const t = f(10);const u = g(t);const v = h("aaa");......
継続渡しスタイルx ▷ k ≡ k(x)f(10)▷ ((t) ⇒ g(t)▷ ((u) ⇒ h("aaa")▷ ((v) ⇒ ......
)))

継続
継続が使えると…
コントロールを扱う機能がユーザレベルで実装できる● バックトラック● マルチスレッドなどなど

継続 - call/cc (call with current-continuation)⚠ しばらくRacketで行きます継続 - call/cc (call with current-continuation)⚠ しばらくRacketで行きます(call/cc fn)呼ばれた位置からの継続を関数としてfnに渡す
継続が呼ばれたあとはcall/ccには戻ってこない継続 - call/cc (call with current-continuation)(let [(x (call/cc (λ (k)(+ 2 (k 4)))))]x)継続 - call/cc (call with current-continuation)(let [(x (call/cc (λ (k)(+ 2 (k 4)))))]
x)☑呼ばれた位置からの継続を関数として渡す

継続 - call/cc (call with current-continuation)(let [(x (call/cc (λ (k)(+ 2 (k 4)))))]x)⇒ (let [(x 4)] x)⇒ returns 4☑呼ばれた位置からの継続を関数として渡す☑継続が呼ばれたあとはcall/ccには戻ってこない継続 - call/ccと大域脱出(define (div-fail xs fallback)(call/cc (λ (k)(map (λ (e)(if (= e 0)
呼ばれた位置からの継続に(k fallback)
継続を取得fallbackを(/ e 2)))xs))))渡して脱出継続 - call/ccと大域脱出(let[(x (div-fail '(3 4 5 6) '(1)))]x)

継続 - call/ccと大域脱出(let[(x (div-fail '(3 4 5 6) '(1)))]x)⇒ returns '(3/2 2 5/2 3)

継続 - call/ccと大域脱出(let[(y (div-fail '(1 2 0 3) '(1)))]y)継続 - call/ccと大域脱出(let[(y (div-fail '(1 2 0 3) '(1)))]y)div-failから見た継続継続 - call/ccと大域脱出(let[(y (div-fail '(1 2 0 3) '(1)))]y)⇒ (let [(y '(1))] y)⇒ returns '(1)

限定 継続限定 継続- call/cc
プログラムの残りすべてを継続として利用

限定 継続- call/cc
プログラムの残りすべてを継続として利用⇒ ちょっと使いづらい😅

限定 継続- call/cc- 限定継続プログラムの残りすべてを継続として利用

プログラムの残りの特定の範囲を継続として利用⇒ ちょっと使いづらい😅

⇒ 取り回しが良い🙆限定 継続 - shift/reset

限定 継続 - shift/reset(shift k e)
式eのスコープ内で継続kを利用する

限定 継続 - shift/reset(shift k e)
式eのスコープ内で継続kを利用する
new(reset e)
継続の範囲をe内に限定する

限定 継続 - shift/reset(shift k e)式eのスコープ内で継続kを利用する
new(reset e)
継続の範囲をe内に限定する

その他の限定継続演算子: control/prompt, cupto, etc.

限定 継続 - shift/reset(let [(f {reset(string-append(shift k (λ () (k "hello")))" world")})](f))

浅井健一, shift/resetプログラミング入門 を参考

限定 継続 - shift/reset
継続の範囲を限定(let [(f (reset(string-append(shift k (λ () (k "hello")))" world")))](f))

浅井健一, shift/resetプログラミング入門 を参考

限定 継続 - shift/reset(let [(f (reset(string-append(shift k (λ () (k "hello")))" world")))](f))

shiftの結果が返る⇒ (let [(f (λ () (string-append"hello" " world")))](f))
浅井健一, shift/resetプログラミング入門 を参考

限定 継続 - shift/reset(let [(f (reset(string-append(shift k (λ () (k "hello")))" world")))](f))⇒ (let [(f (λ () (string-append"hello" " world")))](f))⇒ returns "hello world"
浅井健一, shift/resetプログラミング入門 を参考

限定 継続
限定継続が使えると…

● call/cc !!
● 型付きprintf● Stateモナド

限定 継続
限定継続が使えると…

● call/cc !!
● 型付きprintf● Stateモナド

モナド全般

例外+ハンドラ

例外+ハンドラ - try-catch

皆さん例外は分かりますか?🙋
● MonadError● もちろん知ってる例外+ハンドラ - try-catch
これは皆さんご存知try-catch (OCamlではtry-with)try 3 + raise Not_found with
| Not_found →print_endline "not found"例外+ハンドラ - try-catch
これは皆さんご存知try-catch (OCamlではtry-with)● 例外が起きるとハンドラにジャンプする● 例外発生位置からの残りの計算は破棄される
try 3 + raise Not_found with
| Not_found →print_endline "not found"Algebraic Effects

Algebraic Effectsを一言でいうと(再)限定継続が取得できる例外およびハンドラ

Algebraic Effects = 限定継続 + 例外&ハンドラ● 計算エフェクトを例外のthrowのように発生● ハンドラにジャンプ● ハンドラのスコープ内の継続を同時に取得してエフェクト発生位置から復帰できる
正しくは Algebraic Effects and Handlers
Algebraic Effects(2003) + Effect Handlers(2012)

略して "Algebraic Effects" または "Algebraic Effect Handlers"Algebraic Effects - Option Monad
effect Option : 'a option → 'ahandle
let ox = lookup "key" map inlet x = perform (Option ox) in
Some (x + 5)
with
| effect (Option (Some v)) k → k v| effect (Option None) _k → None

Algebraic Effects - Option Monad
effect Option : 'a option → 'a
エフェクトを定義
handlelet ox = lookup "key" map inlet x = perform (Option ox) in
Some (x + 5)
with| effect (Option (Some v)) k → k v| effect (Option None) _k → None

Algebraic Effects - Option Monad
effect Option : 'a option → 'a
エフェクトを定義
handleエフェクトを発生
let ox = lookup "key" map inlet x = perform (Option ox) in
Some (x + 5)
with
| effect (Option (Some v)) k → k v| effect (Option None) _k → None

Algebraic Effects - Option Monad
effect Option : 'a option → 'a
エフェクトを定義
handleエフェクトを発生
let ox = lookup "key" map inlet x = perform (Option ox) in
Some (x + 5)
Someを剥がしてwith
継続に値を渡す| effect (Option (Some v)) k → k v| effect (Option None) _k → None

Algebraic Effects - Option Monadeffect Option : 'a option → 'a
エフェクトを定義
handleエフェクトを発生
let ox = lookup "key" map inlet x = perform (Option ox) in
Some (x + 5)
継続を破棄
with
(c.f.例外処理)| effect (Option (Some v)) k → k v| effect (Option None) _k → None

Algebraic Effects - ハンドラのネストと合成性
エフェクトはtry-catch同様に該当するハンドラで捕捉される⇒ ハンドラのネストで複数のエフェクトをハンドル可能
👍エフェクトのハンドリングがcomposable におこなえる

Algebraic Effects - ハンドラのネストと合成性
effect GetLine : () → string
let with_stdin th =handle th () with| effect (GetLine ()) k →
標準入力k (get_line ())
から読む
let with_option th = ......

Algebraic Effects - ハンドラのネストと合成性
2種類のエフェクトを発生

let read_int () =let line = perform (GetLine ()) in
perform (Option (int_of_string_opt line))
let int_of_string_opt: string → int option= ......

Algebraic Effects - ハンドラのネストと合成性
let plus_two_lines () =let a = read_int () inlet b = read_int () inSome (a + b)

Algebraic Effects - ハンドラのネストと合成性
let plus_two_lines () =let a = read_int () inlet b = read_int () inSome (a + b)
let main () =with_option (fun () →with_stdin plus_two_lines)

Algebraic Effectsで何ができる?

● Dependency Injection● async/await● 論理プログラミングなどなど

Algebraic Effectsを使おう● 言語(,処理系)○○○○

EffKoka
Multicore OCaml
Frankなどなど● ライブラリ○○○○

eff.lua for Lua (拙作)rufffor Ruby (拙作)effective-rust for Rustgauche-effects for Scheme

Algebraic Effectsを実装しよう
様々な実装方法● コールスタックを直接触るlibhandler● 限定継続gauche-effects, effekt, 『Eff Directly in OCaml』● コルーチンeff.lua, ruff, effective-rust, 弊研究まとめ● Algebraic Effectsは限定継続の取れる例外● Algebraic Effectsはなんか色々できて強い● Algebraic Effectsは実はすぐに触れる

まとめ

話してないこと:● value handler● 型システム● 『What is algebraic …… ?』などなど

まとめ

話してないこと:!
!
!
すで題● value handler
宿● 型システム● 『What is algebraic …… ?』などなど

参考文献
●
●
●
●
●
●

Andrej Bauer and Matija Pretnar. Programming with algebraic effects and handlers. In:
Journal of Logical and Algebraic Methods in Programming 84.1 (2015), pp. 108–12
浅井健一. shift/resetプログラミング入門. In: ACM SIG-PLAN Continuation Workshop 2011(2011)
びしょ～じょ. How do you implement algebraic effects?. In: effect system勉強会 (2019)
R. Kent Dybvig, Simon Peyton Jones, and Amr Sabry. A monadic framework for delimited
continuations. In: Journal of Functional Programming 17.6 (2007), pp. 687-730.
Andrej Bauer. What is algebraic about algebraic effects and handlers?. In: arXiv preprint
arXiv:1807.05923 (2018)
Oleg Kiselyov and KC Sivaramakrishnan. Eff directly in OCaml. In: ACM SIGPLAN Workshop
on ML 2016 Sep. (2016)

Q&A

計算エフェクトa.k.a. 副作用 誤解を与えかねないのでしばしば言い換えられる
やりたい計算(Num a ⇒ a)に対して本道でないもの(Maybe)
Num a ⇒ a⇔

Num a ⇒ Maybe a

モナドを使うと計算エフェクトの操作を隠蔽できる
class Applicative m ⇒ Monad m where(≫＝) :: m a → (a → m b) → m b
return :: a → m a

Extensible Effectsとの関連性
type-directedなAlgebraic Effectsの実装方法だと思う⇔ 限定継続､コルーチンはexpression-directed
Extensible Effects 限定継続

コルーチン

強い型システム

asymmetriccoroutines

multi-prompt
shit/resetReact Hooksとの関連性……🤔
無さそう､AEで実装できるがメリットが少ない● Reactが隠蔽していた実装を自分でやる必要がある● 一般に､言語レベルで扱える継続はコストが高い● 継続を末尾位置で必ず呼ぶ(i.e. 複製､破棄などしない)ので旨
味がない
React Hooks→ Algebraic Effects

useHoge→ Hogeエフェクトの発生(React内部実装)→ ハンドラ

次のレンダリング?

→ 継続

Algebraic Effects - Dependency Injection🤯
- Dependency Injection
インタフェースに対して実装をあとから入れる- Algebraic Effects
エフェクトのシグネチャ(インタフェース)に対してハンドラ(実装)をあとから入れる

Algebraic Effects - Dependency Injection🤯
effect GetUsers : () → user list
let mock_get_users th =handle th () with| effect (GetUsers ()) k →k (List.create ~size:10 ~val:dummy_data)
let prod_get_users th =handle th () with| effect (GetUsers ()) k → k(DB.get_users ())

Algebraic Effects - Dependency Injection🤯
effect GetUsers : () → user list
ユーザを取得する
let mock_get_users th =エフェクトを定義
handle th () with| effect (GetUsers ()) k →ダミーデータを渡す
k (List.create ~size:10 ~val:dummy_data)
let prod_get_users th =実際のデータを渡す
handle th () with| effect (GetUsers ()) k → k(DB.get_users ())

Algebraic Effects - Dependency Injection🤯
let app () =let users = perform (GetUsers ()) in......

let test_main () =mock_get_users app
let prod_main () =prod_get_users app

ハンドラの切り替えで実装を選べる