🦋

EffでAlgebraic Effectsに触れてみよう

5 min read

Algebraic Effectsについて調べていて,それに関する日本語記事が少なかったようなので書くことにしました.
間違ったことが書いてあった場合IssueやPR等で指摘していただけると嬉しいです.また,理解が難しい記述やわからないことがあった場合は質問してほしいです.

概要

Algebraic Effects は 日本語に訳すと代数的効果となります.このEffectsというのは,副作用のことを指しています.
代数的副作用と訳したほうがわかりやすいかもしれないです.最近巷で流行り始めてます.

Algebraic Effectsで追加される機能は,Effects & Handler です.この2つさえあれば,return, yeild, async/await, try-catch などの副作用がある機能を書くことができるのです.これらはほとんどの言語では,特殊な機能として存在していますよね.それらをEffects & Handler だけで表すことができるので,Effects & Handlerは非常に強力です.そして,Effects & Handler は型安全です[1] [2]

Haskellなどの関数型言語では,副作用を伴う操作は通常モナドを使って型付けをします.
しかし,それは複雑で,複数の副作用が絡む処理にはモナド変換子を使う必要があります.そしてそれは少し面倒臭いです.僕はHaskellやモナドについて明るくないので,詳しいことは[びしょ〜じょさんの記事 https://nymphium.github.io/2020/03/15/ae-ee.html]を参照してください.
しかし,Algebraic Effectsを使うことによって,モナドより簡潔に副作用の結合を書くことができます[3]

まあ難しい説明は置いておいて,実際にコードを見ていきましょう.

Effについて

EffはAlgebraic Effectsを実装した実験的な言語です.この言語に関する論文[4]が起爆剤となりAlgebraic Effectsが流行ったそうです[5].今回はこれを使って説明していきたいと思います.

Eff の実行方法

webで実行する(簡単だからおすすめ)

https://www.eff-lang.org/try/

インストールして動かす

https://github.com/matijapretnar/eff

yieldの実装

effect Yield: int -> unit

let iter_handler action = handler
  | effect (Yield x) k -> action(x); k ()
;;
 
let for_each iter_func action =
  with iter_handler action handle
  iter_func(3)
;;

let iter_func x =
  perform (Yield x - 1);
  perform (Yield x - 2);
  perform (Yield x - 3);
  ()
;;

let action x = print(x);;

for_each iter_func action
;;
 val iter_handler : (int -> 'a) -> unit => unit = <fun>
 val for_each : (int -> unit) -> (int -> 'a) -> unit = <fun>
 val iter_func : int -> unit = <fun>
 val action : 'a -> unit = <fun>
 2
 1
 0
 - : unit = ()

iter_funcYieldを呼ぶたびに,数字が出力されています
このコードについて解説していきたいと思います.

Effectの定義

effect Yield: int -> unit

effect-typeを定義しています.
ここでは,Yieldintを受け取ってunitを返す副作用のある関数という定義をしています.
ここでは,型を定義するだけで,実際にどういった値もしくは処理を持つかは,別のところで決めます.
別のところというのは,handlerのことを指しています.
つまり,形式的な定義と処理の定義は別々にしているのです.

Handlerの定義

let iter_handler action = handler
  | effect (Yield x) k -> action(x); k ()
;;

handlerを定義しています.正確にいうと,actionという引数を取って,handlerを返す関数です.
| effect (F x) k -> ... で,副作用のある関数F が呼ばれた時にする処理を(...の部分に)書きます.
k というのは継続です.

Yieldの場合は,任意の関数actionxを渡して,その後の処理を継続すると言う処理になっています.

継続について

継続というのは,この場合Yeildが呼ばれた後の処理を指しています.
例えば以下のコードを実行した場合

perform (Yield 10);
print("hello")

kには次のような関数が入ると考えるとわかりやすいかもしれないです(実際には関数とは違うので注意,あくまでもイメージです).

let k x =
  x;
  print("hello")

継続についての詳しく解説している記事を貼っておきます.詳しくはこちらをご覧ください.

Effects & Handler

let for_each iter_func action =
  with iter_handler action handle
  iter_func(3)
;;

注目するべきは with iter_handler action handle ... の部分です.

with H handle ... という構文について説明します.
...は副作用が発生し得る処理です.副作用が発生した場合,Hに定義される処理に従って,副作用を処理します.

このコードで言うと,H(iter_handler action)...iter_func(3)となります.
iter_func(3)の中で,Yieldと言う副作用がでた場合は,iter_handle action effect (Yield x) k -> action(x); k ()が発火すると言う感じです.

どのように動くか

ここまでは,定義について見てみましたが,実際にそれらを使用してその動きを追ってみましょう.

let iter_func x =
  perform (Yield x - 1);
  perform (Yield x - 2);
  perform (Yield x - 3);
  ()
;;
 
let action x = print(x);;
 
for_each iter_func action

これをrubyで書くとこうなると思います.

def iter_func(x)
  yield x - 1
  yield x - 2
  yield x - 3
end

iter_func(3) { |x| puts x }

まず,action(3)が実行されます.
perform (Yield 3 - 1) が実行されます
effect (Yield 3) k -> action(3); k () でそれがハンドリングされます
action(2)が実行されます.
print(2)が実行されます.
k ()が実行されます.
perform (Yield x - 2)が実行されます.
それが続く

と言う感じです.

Algebraic Effectsの機能 Effects & HandlerによってYieldが実装できました.
他にも,raise, state, try-catch, async/await などを実装することができます.

まとめ

いかがでしたでしょうか?
まあかなり雑な記事です.それでもAlgebraic Effects について少しでも興味を持ったのならば幸いです.
興味を持たれたのであれば,https://www.eff-lang.org にもっとサンプルコードが載ってあるので,ぜひ見てください.
RubyやPythonなどの色々な言語で,Algebraic Effectsを実装したライブラリがあるのでそれらを使ってみるのもありです.
関連リンク集を載せましたので,ぜひそちらも見てみてください.

関連リンク集

https://scrapbox.io/myazakky/EffでAlgebraic_Effectsに触れてみよう
https://nymphium.github.io/tags.html
https://medium.com/@kuy/algebraic-effects-自習用資料まとめ-e589fa74607d
https://github.com/yallop/effects-bibliography
https://misreading.chat/2019/06/23/episode-63-programming-with-algebraic-effects-and-handlers/
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/08/algeff-tr-2016-v2.pdf
https://overreacted.io/ja/algebraic-effects-for-the-rest-of-us/
脚注
  1. An Introduction to Algebraic Effects and Handlers, Theorem 4.2
    URL: https://www.eff-lang.org/handlers-tutorial.pdf ↩︎

  2. polymophic effectsを導入した場合,型安全でなくなることが一般に知られています. ↩︎

  3. Programming with Algebraic Effects and Handlers, Introduce
    URL: https://arxiv.org/pdf/1203.1539.pdf ↩︎

  4. Programming with Algebraic Effects and Handlers
    URL: https://arxiv.org/pdf/1203.1539.pdf ↩︎

  5. https://misreading.chat/2019/06/23/episode-63-programming-with-algebraic-effects-and-handlers/ のどこかでそんな話をしている ↩︎

GitHubで編集を提案

Discussion

ログインするとコメントできます