OCaml Effects Tutorialの例題「Stateの実装」を追ってみる
OCaml Effect TutorialのStateの実装の話を見ていく。これはEffect.DeepとEffect.Shallowの違いを紹介するセクションの例題：
実際に示されているコードはHaskellでいうところのReaderモナドに似たもので、Stateを読むGetは定義されているがPutは定義されていない（Putの定義は演習問題）。
そのGetだけの例題からモジュールのopenを無くし、handlerを明示的に変数束縛するようにしたコード：
module type STATE = sig type t val get : unit -> t val run : (unit -> unit) -> init:t -> unit end module State (S : sig type t end) : STATE with type t = S.t = struct type t = S.t type _ Effect.t += Get : t Effect.t let get () = Effect.perform Get let run f ~init = let module Es = Effect.Shallow in let rec loop : type a r. t -> (a, r) Es.continuation -> a -> r = fun state k x -> let handler = { Es.retc = (fun result -> result); Es.exnc = (fun e -> raise e); Es.effc = (fun (type b) (eff : b Effect.t) -> match eff with | Get -> Some (fun (k: (b, r) Es.continuation) -> loop state k state) | _ -> None) } in Es.continue_with k x handler in loop init (Es.fiber f) () end module IS = State (struct type t = int end) module SS = State (struct type t = string end) let foo () : unit = let open Printf in printf "%d\n" (IS.get ()); printf "%d\n" (IS.get ()); printf "%d\n" (IS.get ()); printf "%s\n" (SS.get ()); printf "%s\n" (SS.get ()) let _ = IS.run (fun () -> SS.run foo ~init:"forty two") ~init:42
今回はこのコードの詳細を見ていく。
STATE signature
まずはSTATEモジュールシグニチャ：
module type STATE = sig type t val get : unit -> t val run : (unit -> unit) -> init:t -> unit end
保持されている状態を表す何らかの型t、その状態を取り出すための関数get、そしてその状態が存在しgetが実行できるコンテキストで走らせる処理を表すunit -> unit型の関数と、状態の初期設定init:tをとり、unitを返すrun関数。
現状ではHaskellのモナドと違ってStatefulなコンテキストで実行する関数の型に何ら注釈がつかないのでrunの第一引数の型はunit -> unitだ。今後Effect Systemが導入されると型にも反映されるようになるはず。
State functorとその使い方
「状態」の型に対してパラメトリック性を持つためにStateはただのモジュールではなく、状態型tにパラメトリックなファンクタとなる：
module State (S : sig type t end) : STATE with type t = S.t = struct ... end
ファンクタStateは引数として、t型が定義されているモジュールSを取り、STATE型のモジュール（ただしSTATEのtとSのtが合致する）を返す。ファンクタ構文は慣れてきて読めるようにはなったが、いつ見ても分かりにくく感じてしまう。かといって改善の提案があるわけではないのだが・・・。
以下のように特定の型を入れて使う：
module IS = State (struct type t = int end) module SS = State (struct type t = string end)
整数を「状態」として持つISモジュールと文字列を「状態」として持つSSモジュールを定義している。
run関数に渡す「状態を使う処理」foo関数の定義：
let foo () : unit = let open Printf in printf "%d\n" (IS.get ()); printf "%d\n" (IS.get ()); printf "%d\n" (IS.get ()); printf "%s\n" (SS.get ()); printf "%s\n" (SS.get ())
ISとSSの状態コンテキストでfooを実行する：
let _ = IS.run (fun () -> SS.run foo ~init:"forty two") ~init:42
上記のコードは、まず「文字列"forty two"が状態なコンテキストでfooを実行する」という処理を表す関数fun () -> SS.run foo ~init:"forty two"を作成し、それを「整数42が状態なコンテキストで実行」している。
結果としては以下のとおり：
$ ocaml state1.ml 42 42 42 forty two forty two
Getだけなのでつまらない結果ではある。
Stateの中身（冒頭）
まずはStateの中でのtの定義：
module State (S : sig type t end) : STATE with type t = S.t = struct type t = S.t
引数として渡されるモジュールSのt型と同一と定義している。
次にGetエフェクトの定義：
type _ Effect.t += Get : t Effect.t let get () = Effect.perform Get
以前の例や演習でも見てきたようにGADTなextensible variant typeであるEffect.tを拡張している。Getは0引数コンストラクタ（Getというエフェクトが生じるとき、そのエフェクトを処理するために必要な情報はハンドラ側に揃っており、発生した箇所からの情報はいらない）。
そして今定義したエフェクトを包んでEffect.performしているget関数を定義。
State.runの実装
今回の実装で複雑なのはrun関数である。
まずは全容：
let run f ~init = let module Es = Effect.Shallow in let rec loop : type a r. t -> (a, r) Es.continuation -> a -> r = fun state k x -> let handler = { Es.retc = (fun result -> result); Es.exnc = (fun e -> raise e); Es.effc = (fun (type b) (eff : b Effect.t) -> match eff with | Get -> Some (fun (k: (b, r) Es.continuation) -> loop state k state) | _ -> None) } in Es.continue_with k x handler in loop init (Es.fiber f) ()
STATEで定義された型はval run : (unit -> unit) -> init:t -> unit。なのでlet run f ~init = ...のfは状態のあるコンテキストで実行する処理を表すunit -> unit型の関数、initは初期状態を表すt型の値だ。
外側から見てみる：
let run f ~init = let module Es = Effect.Shallow in let rec loop : type a r. t -> (a, r) Es.continuation -> a -> r = ... in loop init (Es.fiber f) ()
まずこの関数の中でEffect.Shallowを多用するので短めのモジュール名Esに束縛し直す。
その上で再帰関数loopを定義し、それをloop init (Es.fiber f) ()と使う。その結果がrun関数自体の結果となる。
loop関数のシグニチャtype a r. t -> (a, r) Es.continuation -> a -> rはpolymorphic locally abstract typeを使っている。この言語機能については後述するとして、とりあえずこの時点ではt -> ('a, 'r) Es.continuation -> 'a -> 'rと同等なものとして扱う。
そうするとloopは
- t型の状態
('a, 'r) Es.continuationの限定継続- 限定継続に渡す'a型の値
を引数にとり、限定継続から帰ってくる結果である'r型の値を返す関数となる。
run関数の最後にloop init (Es.fiber f) ()している。ここでloopに渡している引数は
- 初期状態であるinit
(unit -> unit)型の関数fを限定継続に変換した(Es.fiber f)- その限定継続に最初に渡す値である()
である。
それではloopの実装：
let rec loop : type a r. t -> (a, r) Es.continuation -> a -> r = fun state k x -> let handler = { Es.retc = (fun result -> result); Es.exnc = (fun e -> raise e); Es.effc = (fun (type b) (eff : b Effect.t) -> match eff with | Get -> Some (fun (k: (b, r) Es.continuation) -> loop state k state) | _ -> None) } in Es.continue_with k x handler
前述のとおりtype a r. t -> (a, r) Es.continuation -> a -> rでaとrはloop関数全体で使える(locally abstract)なpolymorphic type variableとなっている。aは限定継続に渡す値の型、rは限定継続から帰ってくる値の型である。ここの構文と作用についてはもう少し掘り下げて調べたいので別の記事にしたい。
今回のStateエフェクトと、今まで見てきたExceptionやResumable Exceptionのエフェクトとの機能的な違いは「限定継続が実行されるごとに、それを取り巻くハンドラが変更される」というもの。loopの中で引数として渡されたstateを使ったハンドラが定義され、Effect.Shallow.continue_withでそのハンドラを使い限定継続が呼び出される：
Es.continue_with k x handler
ハンドラの中で
| Get -> Some (fun (k: (b, r) Es.continuation) -> loop state k state)
とloopが再帰的に呼び出されることで限定継続kが使われるわけだが、そのkが実際にEs.continue_withで呼び出されるコンテキストでのハンドラは再帰的に呼び出されたloopで新しく作成されたものである。ただし、Getの場合は現在の状態を参照するだけで変更はしない。loop state k stateという再帰呼び出しからわかる通り、第一引数である「状態」として渡しているのは今までのstate、そして第三引数（限定継続に渡す値）も同じくstateである。限定継続にstateを渡しているので期待通りGetエフェクトが発生した箇所に、現在のstateの値が返る。
Effect.Deepのmatch_withやtry_withが「関数、その引数、ハンドラ」の三つを引数にしているのに対してEffect.Shallowのcontinue_withでは「限定継続、その引数、ハンドラ」を引数にしている。なのでStateのようにエフェクトが発生するごとに限定継続を新しいハンドラと共に実行したい場合はEffect.Shallowを使う。
次回
次はStateに関連した演習問題であるPutの実装をやってみる。
