OCaml 5のEffect Handlerを調べてみる

:::note
[フューチャーAdvent Calendar 2022](https://qiita.com/advent-calendar/2022/future) の24日目です。
::: 

# はじめに
マルチコア対応のOCaml 5.0がリリースされましたね！[^1]
この記事ではOCaml 5.0でサポートされる目玉機能？の一つであるEffect Handlerについて調べてみました。

:::note
私はOCamlをほぼ何も知りません。
したがってOCamlそのものに関する記述の相当怪しいと思います。
指摘は大歓迎です。
:::

# Effect Handlerとは？
Effect Handlerとは一般化された例外です。何のことか分からないですよね。。

皆さんのよく知る例外ではハンドリングする側は例外クラスのインスタンスのような値を取れると思いまが、Effect Handlerでは値に加えて継続も受け取ることができます。継続という用語は聞き馴染みがない方も多いかも知れません。継続とは一言でいうと残りの計算のことです。昔に[しょぼい記事](https://qiita.com/hayao0727/items/5ae697fca2d6841709a2)を書いたのでよければご覧ください。

OCamlのEffect Handlerは継続といっても、`One shot delimited continuation`という継続を扱います。One shotというのはその継続は最大一回しか実行できないということです。delimitedというのは継続の範囲が区切られているということで、OCamlでは「`perform`(javaでいうthrowに相当)したところから、`perform`を呼んだ関数の終わりまで」です。delimitedでない継続というのは「`perform`されてからプログラムが終了するまで」を指します。よく分からないですよね。この後に紹介する例を見れば多少イメージがつくのではないかと思います。


## Effect Handlerの嬉しさ
さてEffect Handlerが何かはふんわり分かったとします。疑問に思うのがこれはなにが嬉しいのかということです。私は正直よく分かっていませんが、OCaml 5の開発を推進してきた[Sivaramakrishnan](https://kcsrk.info/)さんの[動画](https://www.youtube.com/watch?v=zJ4G0TKwzVc)によるとOne shot continautionsを使うと多くの並行処理のメカニズムを表現できるらしいです。相当表現力豊かなプリミティブということなのでしょう。

なのでEffect Handlerをベースに並行処理のライブラリを作ることができます。Ocaml 5ではそのようなライブラリが実際にいろいろ用意されているようです。SivaramakrishnanさんはOcaml 5の並行処理ライブラリについて以下のようなメリットがあると主張していました。

- GoやHaskellと違い、ランタイムに並行処理の仕組みを組み込まないことで、ランタイムの開発の負担になることを避けることができ、またケースバイケースで適したライブラリを使える。
- Effect Hanlderを使うと非同期IOをネイティブサポートできるらしく、それはRustやJavaScriptのasyncのように[同期、非同期の色](https://journal.stuffwithstuff.com/2015/02/01/what-color-is-your-function/)がつかない。


# Effect Handlerを使ったサンプル

## 環境
WSLの`Ubuntu 20.04.5 LTS (GNU/Linux 5.10.102.1-microsoft-standard-WSL2 x86_64)`でプログラムを実行しました。

環境構築は[チュートリアル](https://github.com/Sudha247/ocaml5-tutorial-icfp-22/#installation)のInstallationに習っています。チュートリアルでは`ocaml-base-compiler.5.0.0~alpha1`を使っていますが、私は`ocaml-base-compiler.5.0.0~beta1`で動作させました。

## 例外風に使う
```ocaml
open Effect
open Effect.Deep

type _ Effect.t += Foo: int -> int Effect.t

let f () =  1  + (perform (Foo 1))

let () = print_int (try_with f () {
    effc = fun (type a) (eff: a t) ->
        match eff with
        | Foo n-> Some (fun (k: (a, _) continuation) -> continue k (n+1))
        | _ -> None
})
```

こちらはSivaramakrishnanさんの[スライド](https://kcsrk.info/slides/handlers_edinburgh.pdf)に載っていた擬似コードを実際に動くように修正したものです。
上記は例外を投げている風のコードです。
fという関数を定義して、それを`try_with`関数に渡しています。
このコードを実行されると何が表示されるでしょうか？


前提知識を説明しながら、コードの動作を説明します。
```ocaml
type _ Effect.t += Foo: int -> int Effect.t
```
Effectを定義しているところが`type _ Effect.t += Foo: int -> int Effect.t`です。これは[`Extensible variant types`](https://kcsrk.info/webman/manual/extensiblevariants.html#s:extensible-variants)と呼ばれる構文のようです。私の理解ではこれは拡張可能なEnumです。拡張可能なので、未知のケースがあるかもしれず、そのためマッチするときは常に`_ ->`のケースが必要になるようです。

```ocaml
let f () =  1  + (perform (Foo 1))
```
次に注目するのはf関数内で呼ばれている`perform`です。`perform`はEffectを発生させる関数です。例外で言えば`raise`や`throw`に相当するものです。なので`perform`が呼ばれると制御がハンドリング側に移ります。このコードで言えば `try_with`です。
`perform`の型は`'a t -> 'a`です。Fooが`int -> int Effect.t`なので、Foo 1は`int Effect.t`、ゆえに`perform (Foo 1)`はintを返します。この値はその継続を実行するときに渡す値です。

```ocaml
let () = print_int (try_with f () {
    effc = fun (type a) (eff: a t) ->
        match eff with
        | Foo n-> Some (fun (k: (a, _) continuation) -> continue k (n+1))
        | _ -> None
})
```
`try_with`はtry-catchに相当するものようです。Ocaml lsp Serverを導入しているVSCodeでカーソルを当てると`try_with f v h runs the computation f v under the handler h`という説明が出てきます。try_withに渡す関数内で`perform (Foo 1)`とすることでeffはFoo 1になります。

`match eff with`部分で注目すべき点はkと`continue`です。kは`(a, _) continuation)`という型で、`perform`が呼ばれた時点から関数の終わりまでの継続です。具体的にいうと1と`peform (Foo 1)`の戻り値を足すという処理です。この継続は型aを引数にとって型_を返します。今回の場合はaはintで_もintです。

:::note
(type a)が何なのかや、`(a, _) continuation)`のアンダーバーがどういう意味なのかは分かっていません。
だれか教えてください。。
:::

`continue`は`('a, 'b) continuation -> 'a -> 'b`という型を持っています。継続に引数を渡して実行を再開し、戻り値を得ます。
`continue`にn+1(=2)を渡しているので、`perform (Foo 1)`の戻り値は2となり、継続の戻り値は1+2で3になります。
よって`try_with`の戻り値は3となり、`print_int 3`が実行されることになります。

まとめると、以下のような動作となります。
1. perform (Foo 1)がハンドリングされて1足されて2が返ってくる
1. 1+2で3になり、それが (continue k (n+1))の戻り値となる
1. よって3がプリントされる

継続がなんなのかふんわり分かったでしょうか？

## String Effect

```ocaml
open Effect
open Effect.Deep

type _ Effect.t += E : string Effect.t

let print () =
  print_string "0";
  print_string (perform E);
  print_string "3"

let main () =
  match_with print () {
    retc = (fun res -> res);
    exnc = raise;
    effc = fun (type a) (eff: a t) ->
      match eff with
      | E ->
          Some (fun (k: (a, _) continuation) ->
           print_string "1";
           continue k "2";
           print_endline "4")
      | _ -> None
  }

let () =
  main ()

```
こちらは[icfp22](https://icfp22.sigplan.org/)というカンファレンスで行われていたらしい[チュートリアル](https://github.com/Sudha247/ocaml5-tutorial-icfp-22/)の資料のコードの引用です。

:::message
`match_with`と`try_with`は似たようなものに見えますが、使い分けはよくわかりません。
:::

さてコードはなにを出力するでしょうか？
答えは`01234`です。

処理の動作を説明します。
- まずprint関数の`print_string "0";`が走るので0が出力されます。
- その後、`print_string (perform E)`が走るのでEffectが発生します。
- そしてEffectが`effc = fun (type a) (eff: a t) -> ~~`でハンドリングされます。
- 1が表示されて`continue k "2";`で継続に2を渡して実行します。
- すると`(perform E)`が2を返すので`print_string (perform E);`は2をプリントします。
- その後3を表示し、継続の実行を終了します。継続はunitを返して、`continue k "2";`の戻り値はunitになります。
- 最後に4を改行とともに出力して処理が終了します。


## Round-robin execution scheduler

最後にやや実用的な例を紹介して終わりにします。並行処理を実行するプログラムです。

```ocaml
open Effect
open Effect.Deep

type _ Effect.t += Fork : (unit -> unit) -> unit Effect.t
type _ Effect.t += Yield : unit Effect.t

let fork f = perform (Fork f)
let yield () = perform Yield

let run main =
  let run_q = Queue.create () in
    let enqueue k = Queue.push k run_q in
      let deque () =
        if Queue.is_empty run_q then ()
        else continue (Queue.pop run_q) ()
      in
      let rec spawn f =
        match_with f () {
          retc = (fun () -> deque ());
          exnc = (fun e ->
            print_string (Printexc.to_string e);
            deque ());
          effc = fun (type a) (e: a Effect.t) ->
            match e with
            | Yield -> Some (fun (k: (a, unit) continuation) -> enqueue k; deque ()) 
            | Fork f -> Some (fun (k: (a, unit) continuation) -> enqueue k; spawn f)
            | _ -> None
        }
          in
          spawn main

let log = Printf.printf

let rec f id depth =
  log "Starting number %i\n!" id;
  if depth > 0 then begin
    log "Forking number %i\n!" (id * 2 + 1);
    fork (fun () -> f (id * 2 + 1) (depth - 1));
    log "Forking number %i\n!" (id * 2 + 2);
    fork (fun () -> f (id * 2 + 2) (depth - 1));
  end else begin
    log "Yielding number %i\n!" id;
    yield ();
    log "Resumed number %i\n!" id;
  end;
  log "Finishing number %i\n!" id


let () = run (fun () -> f 0 2)

```

こちらは[Effect Hanlderの応用コードを紹介する記事](https://github.com/ocaml-multicore/effects-examples)から引用しています。

run関数の概要を説明します。
- Queueを持っていて、このQueueには継続を詰めていきます。
- enqueueとdequeueという関数が定義されています。enqueueは継続をpushします。dequeueは継続を取り出して実行します。
- メインの関数はspawnという関数です。このプログラムにわたす関数はForkとYieldを`perform`することが期待されていて、Yieldの場合は継続をqueueにいれてdequeueを呼び、Fork fの場合は継続をqueueに入れて、spawn fを再帰的に呼び出します。つまり処理を一旦やめて、Queueに詰まっている継続を実行したいときはYield、処理を一旦やめて新しい処理を呼びたい場合はFork fを`perform`します。


コード末尾の`let () = run (fun () -> f 0 2)`ではスケジュールプログラムを実行しています。
fという関数は上記のような木構造をforkしながら巡って、木の子供に達したらyieldするプログラムです。データ構造はなく、fに渡す数値で木のある位置にいると考えています。
以下のような木を走査しています。

```mermaid
graph TD;
  0 --> 1;
  0 --> 2;
  1 --> 3;
  1 --> 4;
  2 --> 5;
  2 --> 6;
```

実行結果は以下のようになります。並行して処理が実行できているのが分かると思います。私は紙にかきながら処理を辿っていましたが「Starting number 2」あたりで頭がこんがらがってきて辿るのをやめました。
```bash:実行結果
Starting number 0
!Forking number 1
!Starting number 1
!Forking number 3
!Starting number 3
!Yielding number 3
!Forking number 2
!Starting number 2
!Forking number 5
!Starting number 5
!Yielding number 5
!Forking number 4
!Starting number 4
!Yielding number 4
!Resumed number 3
!Finishing number 3
!Finishing number 0
!Forking number 6
!Starting number 6
!Yielding number 6
!Resumed number 5
!Finishing number 5
!Finishing number 1
!Resumed number 4
!Finishing number 4
!Finishing number 2
!Resumed number 6
!Finishing number 6
!⏎
```

ちなみに以下のようにQueueをStackにすると以下のように深さ優先探索でたどるようになります。

```diff ocaml
+ let run main =
+  let run_q = Stack.create () in
+    let enqueue k = Stack.push k run_q in
+      let deque () =
+        if Stack.is_empty run_q then ()
-  let run_q = Queue.create () in
-    let enqueue k = Queue.push k run_q in
-      let deque () =
-        if Queue.is_empty run_q then ()
-        else continue (Stack.pop run_q) ()
```

```bash:実行結果
Starting number 0
!Forking number 1
!Starting number 1
!Forking number 3
!Starting number 3
!Yielding number 3
!Resumed number 3
!Finishing number 3
!Forking number 4
!Starting number 4
!Yielding number 4
!Resumed number 4
!Finishing number 4
!Finishing number 1
!Forking number 2
!Starting number 2
!Forking number 5
!Starting number 5
!Yielding number 5
!Resumed number 5
!Finishing number 5
!Forking number 6
!Starting number 6
!Yielding number 6
!Resumed number 6
!Finishing number 6
!Finishing number 2
!Finishing number 0
!⏎
```
# おわりに
この記事ではOCaml 5で導入されるEffect Handlerについてざっと説明しました。
アプリケーション開発者レベルでもEffect Handlerを直接使う場面があるのかはよく分かっていないのですが、継続を扱えるというのが私にとっては新鮮で面白かったです。
OCaml 5はEffect Hanlder以外にも並列処理がネイティブサポートされたりとかなり有望に見えるので、この機会にOCamlを勉強したいなと思っています。(最近Real World Ocamlの[第2版](https://dev.realworldocaml.org/index.html)が公開されてかなり良さそうです)


# 参考文献
- https://github.com/ocaml-multicore/effects-examples
  - Effect Handlerを使っていろいろなものを実装しています。私は実力不足でほぼ理解できない。。
- https://www.youtube.com/watch?v=zJ4G0TKwzVc
  - OCaml 5の開発をリーディングされていた人の講演の動画です。
- https://dl.acm.org/doi/pdf/10.1145/3453483.3454039
  - OCaml 5の開発をリーディングされていた人が筆頭著者の論文です。
- https://kcsrk.info/slides/handlers_edinburgh.pdf
  - OCaml 5の開発をリーディングされていた人のスライドです。
- https://github.com/Sudha247/ocaml5-tutorial-icfp-22/
  - ICFPというConferenceで行われてたらしいOCaml 5のチュートリアルの資料です。

[^1]:https://discuss.ocaml.org/t/ocaml-5-0-0-is-out/10974