OCaml5 の Effect Handlers を試す

OCaml5.0 で Effect Handlers という機能が実装されました。
これは所謂 Algebraic Effects ……という事で良いのですかね……？
（正直 Algebraic Effects についてもほとんど知らないので何もわからない。）

理論的な側面はともかく、どんなことができるのか、何ができるのかという点についてちょっと調べてみましょう。

この Tutorial を参考に、色々コードを書いてみました。
https://github.com/ocamllabs/ocaml-effects-tutorial

なお、この Effect Handlers は現状ではあくまで実験的な機能らしいです。
将来的にインターフェイスが変更されることはあり得る（というか多分確実？）とのことなので、利用にはご注意ください。

### この記事について

上に書いたとおり、 OCaml5.0 の Effect Handlers について私が試したことを纏めています。

本当は Haskell や Scala でのモナドを使った副作用分離との比較みたいなことをしたかったのですが、調べれば調べるほど自分が何も分かっていない事を自覚したので自重しました。
誰か助けて。

## Effect Handlers の使い方

「復帰可能な例外」と説明される事が多そうで、私もそんな感じに理解している。
「復帰可能」が何を意味するかだが、 effect （例外は raise で投げるが、 effect は perform で投げる）がその発生位置からの限定継続を保持していて、ハンドリングした側で再度その継続を評価することで元の処理に戻ることができる、というわけだ。
ただし、この限定継続には1度しか評価できないという条件が付けられている。この制約によって、 perform 後の処理が高々1度しか走らないことが約束される。「高々」というのが大切で、継続を使わないこともできる。つまり、処理が中断できるというわけだ。
（そもそも継続を使わない、という中断方法の他にも、 discontinue という関数で perform した位置で例外を発生させることもできる。必要に応じて使い分けることができるようだ。）

### 基本

公式ドキュメントのコードを読んでみよう（ちょっと変えてある）。

```ocaml
open Effect
open Deep

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

let comp () = perform (Xchg 0) + perform (Xchg 1)

try_with comp () {
effc= fun (type a) (eff : a Effect.t) ->
    match eff with
    | Xchg n -> Some (fun (k : (a, _) continuation) -> continue k (n + 1))
    | _ -> None
}
```

最後の式は `3` を返す。
一つずつ見ていこう。

```ocaml
open Effect
open Deep
```

モジュールを open しているだけである。
OCaml5.0 の Effect Handlers には Deep と Shallow があり、投げられた effect を何度ハンドリングするか、に違いがあるらしい。
Deep は毎回ハンドリングし、 Shallow は一度しかハンドリングしない。

```ocaml
type _ Effect.t += Xchg : int -> int Effect.t
```

`'a Effect.t` に対してコンストラクタを追加する。 Extensible variant types という機能で、後からコンストラクタを追加することができる。またこの時追加された `Xchg` は GADTs （雑に説明すると、コンストラクタ毎に異なる型引数を取れる機能）で int 型の値を取る。

```ocaml
let comp () = perform (Xchg 0) + perform (Xchg 1)
```

定義した effect を実際に利用する。
perform 関数に引数として渡すと、渡した `'a Effect.t` 型の型引数 `'a` の値が、つまりこの場合は int 型の値が返ってくる。
さて、 perform 関数はこの値をどこから持ってくるのか。処理としては、例外の raise と同様にこの時点で effect が発生し、どこかでハンドルされるまで遡っていく。
そしてその effect をハンドルするのが、次の部分。

```ocaml
try_with comp () {
effc= fun (type a) (eff : a Effect.t) ->
    match eff with
    | Xchg n -> Some (fun (k : (a, _) continuation) -> continue k (n + 1))
    | _ -> None
}
```

`try_with` は `Effect.Deep` モジュールに定義された関数で、第一引数として与えられた関数に第二引数として与えられた値を渡し、そしてその実行中に発生した effect 全てを、第三引数でレコードとして定義されたハンドラでハンドリングしてくれる。
つまりこのレコードがハンドラだ。

```ocaml
{
effc= fun (type a) (eff : a Effect.t) ->
    match eff with
    | Xchg n -> Some (fun (k : (a, _) continuation) -> continue k (n + 1))
    | _ -> None
}
```

`try_with` 関数に渡されるハンドラは `effc` というフィールドを持っていればいい。
effect を受け取りその値をハンドリングするのだが、ハンドリングしないこともできる。このハンドリングするかしないかを、 Option 型の返り値で表す。 Some を返すなら処理し、 None を返すならそのまま次のハンドラに渡すというわけだ。
処理する場合は継続を受け取り、その継続の結果の型の値を返さなければならない。「継続の結果の型の値」を返せば良いので、その継続を処理する必要はない、と言うのがポイントとなる。
今回の処理はどうだろうか。

```ocaml
Xchg n -> Some (fun (k : (a, _) continuation) -> continue k (n + 1))
```

Xchg コンストラクタの引数として与えられた値に1足したものを継続に渡している（継続を評価する場合は `continue` 関数に渡す）。これで、 effect が投げられた位置から復帰してくれる。
その位置はここだった。

```ocaml
perform (Xchg 0)
```

つまり今回は、 perform 関数は `1` を返すということになる。

続いて、もう1つの effect が発生する。

```ocaml
perform (Xchg 1)
```

こちらも同様に処理が行われて、 `1 + 1 = 2` なので `2` が返ってくる。
よって、

```ocaml
let comp () = perform (Xchg 0) + perform (Xchg 1)
```

は最終的に `3` を返し、もうこれ以上 effect は発生しないので、この `3` が最終的な

```ocaml
try_with comp () {
effc= fun (type a) (eff : a Effect.t) ->
    match eff with
    | Xchg n -> Some (fun (k : (a, _) continuation) -> continue k (n + 1))
    | _ -> None
}
```

の式の返り値になる、という仕組みだ。

要するに、

1. effect を定義する
2. perform でその effect を投げる
3. ハンドラがその effect を捕捉して処理
4. （継続が評価されるなら）ハンドラで与えられた値を持って処理が perform の場所に戻る
5. 関数内の全ての処理が終われば、値が返る

というような動きをすると考えて良さそう。

では、もう少し具体的な effect と handler を考えてみよう。

### 状態を保持する

ステートモナドみたいなものの Effect Handler 版を考えてみる。
上記した、参考にした資料だと `Effect.Shallow` と再帰を利用した実装が例として載っていたのだが、ここでは可変な変数を使って実装してみようと思う。
また、状態として持てる値の型についても、変更可能にしてみたい。
で、以下のような実装となった。

```ocaml
open Effect
open Deep

module Make(S : sig type t end) = struct
  type t = S.t

  type _ Effect.t +=
    | Get : t Effect.t
    | Set : t -> unit Effect.t

  let get () = perform Get
  let set s = perform (Set s)

  let run ~(init : t) f arg =
    let state = ref init in
    match_with f arg {
      retc= (fun res -> res, state);
      exnc= raise;
      effc= fun (type c) (eff : c Effect.t) ->
        match eff with
        | Get -> Some (fun (k : (c, _) continuation) -> continue k !state)
        | Set s -> Some (fun (k : (c, _) continuation) ->
            state := s;
            continue k ()
        )
        | _ -> None
    }
end

module StringState = Make(struct type t = string end)

let _ =
  let main () =
    let s = StringState.get () in
    print_endline s;
    StringState.set "fuga";
    let s = StringState.get () in
    print_endline s;
    let t = StringState.get () in
    print_endline t
  in
  let (_, s) = StringState.run ~init:"hoge" main () in
  print_endline s
```

これも順に見ていこう。

```ocaml
module Make(S : sig type t end) = struct
  type t = S.t
```

OCaml の Functor を利用して、状態として扱う型に応じてモジュールを作成できるようにした。
使う時は下の行にあるように、

```ocaml
module StringState = Make(struct type t = string end)
```

として具体的な型を指定してモジュールを作る。


```ocaml
  type _ Effect.t +=
    | Get : t Effect.t
    | Set : t -> unit Effect.t

  let get () = perform Get
  let set s = perform (Set s)
```

状態を管理するための effect を定義する。
現在の状態を指定するための `Get` と、新しい状態に差し替えるための `Set` 。
毎回 `perform` 関数を書いたりコンストラクタを書いたりするのは煩わしいので、便利関数も定義しておく。

ハンドラの定義は以下の通り。

```ocaml
  let run ~(init : t) f arg =
    let state = ref init in
    match_with f arg {
      retc= (fun res -> res, state);
      exnc= raise;
      effc= fun (type c) (eff : c Effect.t) ->
        match eff with
        | Get -> Some (fun (k : (c, _) continuation) -> continue k !state)
        | Set s -> Some (fun (k : (c, _) continuation) ->
            state := s;
            continue k ()
        )
        | _ -> None
    }
```

長いのでこれも少しずつ見ていく。

```ocaml
  let run ~(init : t) f arg =
```

`~(init : t)` はラベル付き引数である（他の言語でいう名前付き引数）。名前の通り、状態の初期値を与える。

```ocaml
    let state = ref init in
```

「現在の状態」を参照で保持しておく。参照というのは可変な変数だ。
関数型言語で可変な変数を使うと驚く方もいるかもしれないが、 OCaml だと安全な箇所では割と使われている印象がある。
例えば今回の処理のように破壊的な変更が関数の中に閉じているのであれば、危険性は低いのではないだろうか。

```ocaml
    match_with f arg {
```

`match_with` 関数は先使った `try_with` 関数に似ているけれど、ハンドラの形が少し違う。 `try_with` が要求した `effc` に加えて、 `retc` と `exnc` フィールドを要求してくる。これはそれぞれ「最終的な結果をハンドリング」する関数と「例外をハンドリング」する関数が渡される。

```ocaml
      retc= (fun res -> res, state);
```

結果、つまり全ての effect を処理し、関数が返してきた結果を引数に適用される関数である。
この場合は、結果を取って、「結果と状態とのタプル」を返している。
これは、ステートモナドを走らせた結果では最終的な状態も一緒に返ってくる、という挙動に合わせた形だ。

```ocaml
      exnc= raise;
```

例外に対するハンドラは、受け取った例外をそのまま投げるだけの事をしている。
これは、このハンドラは例外には関知しない、ということだ。

```ocaml
      effc= fun (type c) (eff : c Effect.t) ->
        match eff with
        | Get -> Some (fun (k : (c, _) continuation) -> continue k !state)
        | Set s -> Some (fun (k : (c, _) continuation) ->
            state := s;
            continue k ()
        )
        | _ -> None
```

effect に対するハンドラは、先のコードと同じく effect の種類に応じて処理を変える。

`Get` の場合は、現在の状態を受け取った継続に渡しているだけだ。 `!` 演算子は参照から値を取り出す。

`Set` の場合、 effect で渡された値を新たな状態として代入してから、継続を実行している。
`state := s;` が参照への代入だ。
`Set` の型は `Set : t -> unit Effect.t` だったので、継続に渡す値は unit で良いというわけだ。

では、実際にこの effect と handler とを使って処理を組み立ててみよう。

```ocaml
module StringState = Make(struct type t = string end)

let main () =
  let main () =
    let s = StringState.get () in
    print_endline s;
    StringState.set "fuga";
    let s = StringState.get () in
    print_endline s;
    let t = StringState.get () in
    print_endline t
  in
  let (_, s) = StringState.run ~init:"hoge" main () in
  print_endline s
```

既に述べたように、実際に利用する状態の型に応じてモジュールを作成する。
もし int 型の状態が欲しければ、

```ocaml
module IntState = Make(struct type t = int end)
```

のように作れば良い。

```ocaml
  let main () =
    let s = StringState.get () in
    print_endline s;
    StringState.set "fuga";
    let s = StringState.get () in
    print_endline s;
    let t = StringState.get () in
    print_endline t
```

状態を取り出す時は `StringState.get` 関数を、状態を更新する時は `StringState.set` 関数を利用する。
それぞれ返り値は string 型、 unit 型になるので、それらの値を利用して（あるいは無視して）コードを組み立てる。
……それで終わりである。

この処理を実行する際は、

```ocaml
  let (_, s) = StringState.run ~init:"hoge" main () in
  print_endline s
```

のように、 `run` 関数を使う。 `init` ラベルの引数に与えた値が初期状態となる。
このコードを実行すれば、

```
hoge
fuga
fuga
fuga
```

のような、想像通りの結果が返ってくるだろう。

### 関数に印が付かない

さて、同じようなことは Haskell や Scala でモナドを利用して行うこともできる。
（というか、最初に書いた通りこのエフェクト自体がステートモナドを真似したものだ。）

例えば Scala なら

```scala
val s = for {
  s <- State.get[String]
  _ = println(s)
  _ <- State.set("fuga")
  t <- State.get[String]
  _ = println(t)
  u <- State.get[String]
  _ = println(u)
} yield ()

val (t, _) = s.run.value
println(t)
```

のようなコードを書けば同様の処理が実装可能だろう。
しかし effect handlers を使う場合特徴的なのは、 effect を利用したコードは利用していないコードと自由に混ぜて使うことができる点だと思う。
上の Scala のコードだと、

```scala
val s = for {
  s <- State.get[String]
  ...
} yield ()
```

の部分の型は `State[String, Unit]` のような型になっているはずで、ステートモナドの中に値が閉じ込められている。
一方で effect handlers を使ったコードは、

```ocaml
  let main () =
    let s = StringState.get () in
    ...
```

の部分の型は `unit -> unit` であり、 effect に関する情報は型に全く現れない。
よって、プレーンなコードや異なる effect を使ったコードを自然に、簡単に合成することができる。
ハンドラも、単純にネストさせればそれぞれのエフェクトを適切にハンドルすることができる。

上の Scala と OCaml 例だと「文字列の出力」という副作用を持つ機能を雑に用いているが、 Haskell で同様の事を行おうと思うとそうはいかない。出力処理は IO モナドに包まなければならず、その場合はステートモナドと IO モナドという2種類のモナドを扱わなければならないからだ。
Scala の場合でも、さらにモナドの種類が増えると同じようにモナドを組み合わせる仕組みを導入する必要がある。モナドトランスフォーマや Extensible Effects 等の手法がよく知られている。
そしてこれらの計算を利用する箇所でも、同様に値をモナドに包んで返す必要が出てくる。

しかし OCaml5 と Effect Handlers を用いるならば、例えば標準出力も同様に effect で行うとしても、

```ocaml
  let main () =
    let s = StringState.get () in
    IO.print_endline s;
    StringState.set "fuga";
    let s = StringState.get () in
    IO.print_endline s;
    let t = StringState.get () in
    IO.print_endline t
  in
  StringState.run ~init:"hoge" (fun () -> IO.run main ()) ()
```

のように書けば良いだろう。
そしてこの main 関数の返値は、単なる unit 型である。

これはモナドだけではなく、最近多くの言語で取り入れられている async/await 構文などとも比較可能な点である。
TypeScript などで多用される async/await 構文では、 await するためには関数に async を付与せねばならず、またその関数を使う関数にも async が必要で……と、連鎖的に属性を変えていかねばならない。
Rust の `?` 演算子などにも同じ事が言え、 `?` 演算子を使うとその関数の返り値は必ず Option 型か Result 型でなければならない。

しかし Effect Handlers を使う場合は、関数に「印」を付ける必要は無い。

### エフェクト安全性

で、これを聞いて大抵の人が不安に思うだろう。
「返り値で型が変わらないなら、どんな effect が飛んでくるか分からないじゃん」と。
そう、 OCaml5.0 における effect は非検査例外と同じようなものなので、その関数がどんな effect を投げるのか分からないのだ。
では、 catch されなかった例外よろしく、ハンドルされなかった effect はどうなってしまうのだろうか？

残念ながら、これは実行時エラーとなる。
`Effect.Unhandled` 例外が投げられることとなる。

この辺りが、 OCaml5 において Effect Handlers が実験的な機能になっている理由らしい。
「 perform された effect が全てハンドルされる事をコンパイル時に保証できる性質」を「エフェクト安全性」と表現するようだが、この「エフェクト安全性」を保証してくれている言語も既に存在するらしいので、将来的には OCaml の型システムを拡張して、ハンドルされない effect が残っている場合にコンパイルエラーとしてくれるようになるかもしれない。

参考: https://discuss.ocaml.org/t/multicore-ocaml-september-2021-effect-handlers-will-be-in-ocaml-5-0/8554

## まとめ

OCaml5 に入った Effect Handlers を軽く触ってみた感想を書いてみました。
実装までしっかり読み込んで調査したわけではないので、事実誤認や勘違いも多いかもしれません。どうかご容赦いただきたい。

記事中では触れませんでしたが、 Effect Handlers は実行速度などにも注意して実装されているらしいです。
既存のコードでベンチマークを取って極端に速度が遅くならないことを確かめたと言うことですので、期待しても良いのではないですかね。

しかし最後の節で触れた「ハンドルされない effect があると実行時エラーになる」というのは、実用的なコードを書く際には割と問題になりそうな気がするので、もう少し様子見をしても良いかな……というのが正直な感想だったり。

ただ実用面はさて置いても、 Effect Handlers のような機能が比較的メジャーな言語で提供されているのはとても面白いと思うので、皆さん是非とも触ってみて欲しいです。

色々書いてみたコードはこの辺に置いておきます。
https://github.com/cedretaber/ocaml5_effect_exer