OCaml Effects Tutorialの演習「StateのHistory実装」をやってみる
前回に続いてState関連の演習問題を解いていく。
問題
今回は今までのStateの履歴をリストとして返すHistoryエフェクトの実装。
まずはSTATEシグニチャに追加：
module type STATE = sig type t val get : unit -> t val put : t -> unit val history : unit -> t list 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 type _ Effect.t += Put : t -> unit Effect.t type _ Effect.t += History : t list Effect.t let get () = Effect.perform Get let put x = Effect.perform (Put x) let history () = Effect.perform History let run f ~init = let module Es = Effect.Shallow in let rec loop : type a r. t list -> (a, r) Es.continuation -> a -> r = fun states 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 states k (List.hd states)) | Put x -> Some (fun (k: (b, r) Es.continuation) -> loop (x::states) k ()) | History -> Some (fun (k: (b, r) Es.continuation) -> loop states k (List.rev states)) | _ -> None) } in Es.continue_with k x handler in loop [init] (Es.fiber f) () end
状態の内部表現がstate : tだったのがstates : t listに置き換わっている。
Getではそのリストの先頭をとって限定継続に渡す（状態はstatesのまま）：
| Get -> Some (fun k ... -> loop states k (List.hd states))
Putはそのリストにappendして新しい状態とする（限定継続には()を渡す）：
| Put x -> Some (fun k ... -> loop (x::states) k ())
そして今回追加したHistoryはそのリストを逆順にして限定継続に渡す（状態はstatesのまま）：
| History -> Some (fun k ... -> loop states k (List.rev states))
今回の変更の主要なポイントとしては大体これくらいなので、非常に簡単に拡張できた印象。
使ってみる
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 ()); IS.put 4; printf "%d\n" (IS.get ()); IS.put 2; printf "%s\n" (SS.get ()); SS.put "hello"; printf "%s\n" (SS.get ()); assert ([42; 4; 2] = IS.history ()); assert (["forty two"; "hello"] = SS.history ()) let _ = IS.run (fun () -> SS.run foo ~init:"forty two") ~init:42
ocaml state.mlと実行すると新しく追加したassert部分も失敗することなくコードが走る。
次回
OCaml 5.0のEffectsにはLocally abstract typesが多用されるので、そこら辺をもう少し理解したいということで調べる。
OCaml Effects Tutorialの演習「StateのPut実装」をやってみる
前回見たStateの実装はGetのみで、どちらかというとHaskellのReaderモナドに近いものだった。
Stateを更新するPutと、過去のStateの履歴を見るHistoryの実装が演習問題として提示されている：
問題
今回はStateを更新する機能としてPutの追加をやっていく。HIstoryも追加しようと思うと内部表現を多少変える必要があるので、まずは変更の少ないPutだけやって「ハンドラが複数Effectを処理できるようにする」という点に集中する。
具体的にはまずSTATEシグニチャを以下のように変えていく：
module type STATE = sig type t val get : unit -> t val put : t -> unit val run : (unit -> unit) -> init:t -> unit end
putは新しい状態を受けとり、コンテキストの状態を更新してunitを返す。
あとはStateファンクタでこのシグニチャを実装するだけ。
実装
まずはPutも追加したStateファンクタの全容：
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 type _ Effect.t += Put : t -> unit Effect.t let get () = Effect.perform Get let put x = Effect.perform (Put x) 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) | Put x -> Some (fun (k: (b, r) Es.continuation) -> loop x k ()) | _ -> None) } in Es.continue_with k x handler in loop init (Es.fiber f) () end
変更点を見ていく。
type _ Effect.t += Put : t -> unit Effect.t
PutというコンストラクタをEffect.tに追加。これはt型（つまり新しい状態）を引数にとるコンストラクタで、t型を包んだ値の型はunit Effect.t、つまりPut xをperformした場合返ってくる値はunit型だ。
put関数ではそのPutを包んでEffect.performしている：
let put x = Effect.perform (Put x)
xはt型、Put xはunit Effect.t型なのでputはシグニチャ通りt -> unitな関数となる。
これでシグニチャに追加した関数は実装できたわけだが、新しく追加したPutエフェクトを正しく処理できるようにハンドラを変更する必要がある。
run関数のなかのハンドラ：
let run f ~init = ... let handler = { ... Es.effc = (fun (type b) (eff : b Effect.t) -> match eff with | Get -> Some (fun (k: (b, r) Es.continuation) -> loop state k state) | Put x -> Some (fun (k: (b, r) Es.continuation) -> loop x k ()) | _ -> None) } ...
生じたエフェクトeffに対してのパターンマッチで、GetケースだけだったところにPut xケースも追加している。このケースでは限定継続kをとってloop x k ()している。
loopの型はtype a r. t -> (a, r) Es.continuation -> a -> rで定義はfun state k x -> ...だ。第一引数は新しい状態、第二引数は限定継続、そして第三引数は限定継続に渡す値である。
このPutケースの処理を追っていくと、パターンPut xの引数部分xが「新しい状態」となる値、(k: (b, r) Es.continuation)の部分がPutエフェクトが生じた箇所の限定継続。loop関数の再帰的呼び出しloop x k ()ではstate引数はx、限定継続はk、そしてその限定継続に渡すための引数部分に当たる第三引数は()となる。loop関数の中では、新しいstateを使ってhandlerが再定義され、そのハンドラを使ってEffect.Shallow.continue_withで限定継続kに()を渡して実行している。
面白い点としては
(fun (type b) (eff : b Effect.t) -> match eff with | Get -> Some (fun (k: (b, r) Es.continuation) -> loop state k state) | Put x -> Some (fun (k: (b, r) Es.continuation) -> loop x k ())
のb型がGetとPutで違う型だということ。Getはt Effect.t、Putはunit Effect.tで、限定継続に渡す値の型はtとunitだと決まっている。locally abstract typeを使得ことで、ハンドラを多相にした上でeffの型と限定継続の型の制約を表現している。
これはエフェクトごとに限定継続が期待している「返ってくる値」の型が違うというケースで、Stateのように複数のEffect.tの相互作用で実装するエフェクトでは頻出するパターンだろう。
使ってみる
前回の使用例に少し手を加えてputを追加してみる：
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 ()); IS.put 0; printf "%d\n" (IS.get ()); printf "%s\n" (SS.get ()); SS.put "hello"; printf "%s\n" (SS.get ()) let _ = IS.run (fun () -> SS.run foo ~init:"forty two") ~init:42
実行してみる：
$ ocaml state2.ml 42 42 0 forty two hello
期待通りにIS.getやSS.getの結果がそれ以前に行われるIS.put, SS.putによって変わっていく。
次回
次はStateのHistoryを実装する。
OCamlのlocally abstract typeに関するメモ１ （基本的な疑問）
「EffectでState実装」の記事で何故Stateエフェクトのためにpolymorphic locally abstract typeが使われる必要があったのかを掘り下げたいと書いた。それに関して@dico_lequeさんからこのようにご教示いただいた（ありがとうございます！）：
loopの型が再帰呼び出しごとに変わるので多相型アノテーションが必要なのと（多相再帰は推論はできないけれど型アノテーションをつければ書ける）、導入した型変数を関数の本体部分でも参照するために局所抽象型が必要だから、かな
— でこれき (@dico_leque) December 26, 2022
明示的な多相の型注釈に関しては自分としても少しはわかるものの、そこにlocally abstract typesが加わるとなかなか追えなくなってしまうのはそもそもlocally abstract types自体の理解があやふやだからだと考えられる。なのでちょっと調べた。
まず公式リファレンスでの説明：
この文章何回か流し読みで読んだことがあるのだが、正直なところイマイチピンときていなかった。冒頭の文
The expression
fun ( type typeconstr-name ) -> exprintroduces a type constructor namedtypeconstr-namewhich is considered abstract in the scope of the sub-expression, but then replaced by a fresh type variable.
について、「なんでいきなりtype constructor？」「considered abstractってどういうこと？」「but thenっていつ？」などと気になる点を放置していたので仕方ない・・・ 今回の記事はこの三つの超基本的な疑問について。
（ちなみにこの公式リファレンスの説明は上記の「locally abstract typesとは何か」そして「locally abstract typesのさまざまな構文」「locally abstract typesはどういう時に使うものか」と論理的には三項目にわかれているのだが、文章構成的にはわかりにくい気がする・・・ 例えば「This construction is useful because ...」で始まる文が直前に論じられていた構文についてではなくてlocally abstract typeすべてについて語っているということは、ある程度読み進めないと判断できない）
Locally abstract typesについての話題はReal World OCamlでも「First Class Modules」の章で出てくる：
こちらでは実例を伴ってよりわかりやすく説明されている：
One of the key properties of locally abstract types is that they’re dealt with as abstract types in the function they’re defined within, but are polymorphic from the outside. Consider the following example:
let wrap_in_list (type a) (x:a) = [x];; val wrap_in_list : 'a -> 'a list = <fun>
The type a is used in a way that is compatible with it being abstract, but the type of the function that is inferred is polymorphic.
If, on the other hand, we try to use the type a as if it were equivalent to some concrete type, say, int, then the compiler will complain.
let double_int (type a) (x:a) = x + x;; Line 1, characters 33-34: Error: This expression has type a but an expression was expected of type int
ちなみにabstract typeについての公式な解説はこれが良さそう：
Abstract type: no equation, no representation. When appearing in a module signature, this definition specifies nothing on the type constructor, besides its number of parameters: its representation is hidden and it is assumed incompatible with any other type.
これを踏まえて基本的な疑問に答えると：
Q: considered abstractってどういうこと？
A: Moduleによって隠蔽されたabstract typeと同じで、他の型と単一化してはいけない独立した型として扱う
Q: "but then replaced by a fresh type variable"の"but then"っていつ？
A: 関数のスコープから出たら。ある関数内で(type t)というlocally abstract typeが導入されている場合、関数外からはその関数の型においてtがすべて型変数'tに置き換えられている（ただし'tはフレッシュな型変数とする）
となる。
残っている「なんでいきなりtype constructor？」という質問に関しては以下のRedditスレッドでGabriel Scherer(gasche)が答えていた：
The OCaml type language distinguishes type variables, like 'a, and type constructors, like t, or list (a parametrized constructor that is not a valid type expression in itself). ... The type-checker would not know how to introduce equations on type variables, and adding this would be a sizeable/invasive change, so we rely on locally-abstract types instead, which are basically constructors that feel like variables.
なるほど・・・ struct type t = int endでtのことを型変数と呼びたくなってしまうが、正確にはこれはtype constructorであってtype variableではない。確かにTaPLでもそんな用語の使い方だったな・・・。type variableはあくまで'aのように単一化（あるいは汎化）を待つものなわけだ。ここら辺はType ConstructorとType Variableのリファレンスにも詳しい。
次回はlocally abstract typeの構文とユースケースについて見ていく。
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の実装をやってみる。
OCaml Effects Tutorialの第一演習「Exceptionの再実装」をやってみる２
前回の締めで書いたとおり、以下のException再実装は結果こそ期待通りに返ってくるものの、内容的には不満が残る：
open Effect open Effect.Deep type _ Effect.t += Raise_exception : exn -> _ Effect.t let raise (e : exn) : 'a = perform (Raise_exception e) let try_with (f : unit -> 'a) (h : exn -> 'a) : 'a = let handler = { effc = (fun (type c) (eff : c Effect.t) -> match eff with | Raise_exception e -> Some (fun (k : (c,_) continuation) -> h e) | _ -> None); exnc = (fun e -> raise e); retc = (fun e -> e) } in match_with f () handler
というわけで段階的に改善していく。
openの除去
冒頭のopenを何とかしたい。
とりあえずEffectモジュールはtype tとval performしか入っていない。そしてtype tに関してはOCaml effect tutorialでは一貫してEffect.tとして使っている。なのでopen Effectはperformの先頭のモジュールアクセスを省略するためにしか使っていない。
というわけで省く：
open Effect.Deep type _ Effect.t += Raise_exception : exn -> _ Effect.t let raise (e : exn) : 'a = Effect.perform (Raise_exception e) let try_with (f : unit -> 'a) (h : exn -> 'a) : 'a = let handler = { effc = (fun (type c) (eff : c Effect.t) -> match eff with | Raise_exception e -> Some (fun (k : (c,_) continuation) -> h e) | _ -> None); exnc = (fun e -> raise e); retc = (fun e -> e) } in match_with f () handler
次にEffect.Deepモジュールだが、よくみるとこのモジュールの中身を使っているのはtry_with関数の定義の中だけだ。なのでこの関数内で1文字変数名のモジュールにしてしまう：
type _ Effect.t += Raise_exception : exn -> _ Effect.t let raise (e : exn) : 'a = Effect.perform (Raise_exception e) let try_with (f : unit -> 'a) (h : exn -> 'a) : 'a = let module D = Effect.Deep in let handler = { D.effc = (fun (type c) (eff : c Effect.t) -> match eff with | Raise_exception e -> Some (fun (k : (c,_) D.continuation) -> h e) | _ -> None); D.exnc = (fun e -> raise e); D.retc = (fun e -> e) } in D.match_with f () handler
変更としては
- Effect.Deepモジュールに一文字変数Dを束縛
- match_with関数はEffect.Deepから来ているのでD.match_withに
- handlerの型は
('a, 'b) Effect.Deep.handlerなのでそのフィールド名すべてにDをつける - continuation型もEffect.Deepから来ているのでD.continuationに
と、Effect.Deep由来の関数・型が明示的になって個人的にはかなり嬉しい。
match_withとtry_with
これまでEffect.Deepのmatch_with関数を使ってきた。それに渡すために('a, 'b') Effect.Deep.handler型のレコードを作成する。これはeffc、exnc、retcの３フィールドが存在し、それぞれ
- effectが生じた時のハンドラ
- 普通のOCaml例外が生じた時のハンドラ
- 関数が普通に結果を返した時のハンドラ
の三関数となる。
今回のケースを見ると、ロジックらしいロジックがあるのはeffcだけで、他の二つは「そのまま例外を投げる」「そのまま値を返す」という処理になっている。こういうケースは非常に多いだろうことは想像に難くない。
というわけでeffectだけのロジックを書ける専用関数とレコード型が存在する。
Effect.Deep.try_withと'a Effect.Deep.effect_handlerだ（このtry_withは「演習問題の一部として定義しないといけない関数」と同名でややこしいがまったく別物である）。これらについてはモジュールのドキュメント参照のこと。
これらを使うと以下のようになる：
type _ Effect.t += Raise_exception : exn -> _ Effect.t let raise (e : exn) : 'a = Effect.perform (Raise_exception e) let try_with (f : unit -> 'a) (h : exn -> 'a) : 'a = let module D = Effect.Deep in let handler = { D.effc = fun (type c) (eff : c Effect.t) -> match eff with | Raise_exception e -> Some (fun (k : (c,_) D.continuation) -> h e) | _ -> None } in D.try_with f () handler
ボイラープレートが減って少々スッキリする。
handlerの整理
handlerの部分を見直してみる：
let handler = { D.effc = fun (type c) (eff : c Effect.t) -> match eff with | Raise_exception e -> Some (fun (k : (c,_) D.continuation) -> h e) | _ -> None }
まずSome (fun (k : (c,_) D.continuation) -> h e)の部分でkに言及する必要がないのがわかる。なぜなら使わないので。というわけでここはSome (fun _ -> h e)でいい。
次にfun (type c) (eff : c Effect.t) -> ...の部分。(k : (c,_) D.continuation)の部分が消えたのでlocally abstract typeのcを導入する必要がなくなった。なのでここはfun (eff : _ Effect.t) -> ...でいい。
そしてfun (eff : _ Effect.t) -> match eff with | Raise_exception e -> ...となっているということはeffが_ Effect.tであることは推論できるのでその部分の型注釈もいらない。つまりfun eff -> match eff with | Raise_exception e -> ...。そしてそれはさらに単純化してfunction | Raise_exception e -> ...にできる。
以下のようになる：
type _ Effect.t += Raise_exception : exn -> _ Effect.t let raise (e : exn) : 'a = Effect.perform (Raise_exception e) let try_with (f : unit -> 'a) (h : exn -> 'a) : 'a = let module D = Effect.Deep in let handler = { D.effc = function | Raise_exception e -> Some (fun _ -> h e) | _ -> None } in D.try_with f () handler
今回の構文の整理が可能なのはエフェクトの処理で限定継続をまったく使わないからだ。ハンドラ内で限定継続を使う場合、その「限定継続に渡す値の型」と「エフェクトが返す値の型」が合致しているという制約を明示的に書く必要が生じ、その結果locally abstract typesが必要になる。（正直「なぜこの制約を明示しないといけないのか・よしなに推論してくれないのか」については理解できていないが・・・）
何はともあれ例題のコードのどの部分がどのモジュールから来ていて、どういう意図を持ち、どういう状況で必要・不必要になるのか、色々考えることができたので大変ありがたい演習だった。このままtutorialをすすめていく。
余談
前回気になっていた以下のwarningが出る件：
33 | (fun Invalid_argument -> Printf.printf "Invalid_argument to sqrt\n")
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
考えたけどあまりうまい手が思いつかなかったのでsolutionを見てみた：
ここのコードが：
(fun Invalid_argument -> Printf.printf "Invalid_argument to sqrt\n")
以下のように書きかわっていた：
(function | Invalid_argument -> Printf.printf "Invalid_argument to sqrt\n" | _ -> ())
他の例外全部握りつぶしているがいいのか・・・？
OCaml Effects Tutorialの第一演習「Exceptionの再実装」をやってみる１
前回に続いてOCaml Effects Tutorialをやっていく。
問題
Exercise 1: Implement exceptions from effects ★☆☆☆☆
As mentioned before, effects generalise exceptions. Exceptions handlers are effect handlers that ignore the continuation. Your task is to implement exceptions in terms of effects. The source file is sources/exceptions.ml.
sources/exceptions.mlは以下の通り：
let raise (e : exn) : 'a = failwith "not implemented" (* Todo *) let try_with (f : unit -> 'a) (h : exn -> 'a) : 'a = failwith "not implemented" (* Todo *) exception Invalid_argument (** [sqrt f] returns the square root of [f]. @raise Invalid_argument if f < 0. *) let sqrt f = if f < 0.0 then raise Invalid_argument else sqrt f let _ = try_with (fun () -> let r = sqrt 42.42 in Printf.printf "%f\n%!" r; let r = sqrt (-1.0) in Printf.printf "%f\n" r) (fun Invalid_argument -> Printf.printf "Invalid_argument to sqrt\n") (* Prints: 6.513064 Invalid_argument to sqrt *)
raise (e : exn) : 'aとtry_with (f : unit -> 'a) (h : exn -> 'a) : 'aを実装せよ、ということだ。
sqrtに0未満のfloatが渡されたら投げる例外を処理できるかをテスト部分で確認している。
気になる点としては「実装する部分」から外れる(fun Invalid_argument -> Printf.printf "Invalid_argument to sqrt\n")がInvalid_argument以外の例外をハンドルできていない点で、これではwarningが出てしまうと思うがここはいじらないでおいていいんだろうか。
参考にする例
まずはtutorialのここまでで出てきた唯一の例を見てみる：
open Effect open Effect.Deep type _ Effect.t += Conversion_failure : string -> int Effect.t let int_of_string l = try int_of_string l with | Failure _ -> perform (Conversion_failure l) let rec sum_up acc = let l = input_line stdin in acc := !acc + int_of_string l; sum_up acc let _ = Printf.printf "Starting up. Please input:\n%!"; let r = ref 0 in match_with sum_up r { effc = (fun (type c) (eff: c Effect.t) -> match eff with | Conversion_failure s -> Some (fun (k: (c,_) continuation) -> Printf.fprintf stderr "Conversion failure \"%s\"\n%!" s; continue k 0) | _ -> None ); exnc = (function | End_of_file -> Printf.printf "Sum is %d\n" !r | e -> raise e ); (* Shouldn't reach here, means sum_up returned a value *) retc = fun _ -> failwith "Impossible, sum_up shouldn't return" }
上記のコードからパクる参考にするべきは以下の四箇所だろう：
open Effect open Effect.Deep type _ Effect.t += Conversion_failure : string -> int Effect.t ... | Failure _ -> perform (Conversion_failure l) ... match_with sum_up r { ... }
解答１
というわけで演習問題をやっていく。
まずはモジュールをOpenしてEffect.tに例外処理のeffectを追加する：
open Effect open Effect.Deep type _ Effect.t += Raise_exception : exn -> _ Effect.t
exception Invalid_argumentという本物のOCaml Exceptionを使うのが決まっているのでRaise_exceptionはexn型を引数に取るコンストラクタとなっている。Raise_exceptionをperformした場合、その箇所に何らかの値を戻して続行することはない（限定継続は破棄される）のでexn -> _ Effect.tとしてある（_の部分に入れる明確な型がない）。
次に実装する必要のある箇所の一つであるraise関数：
let raise (e : exn) : 'a = perform (Raise_exception e)
Raise_exceptionというeffectをperformするだけ。
最後にtry_with関数：
let try_with (f : unit -> 'a) (h : exn -> 'a) : 'a = failwith "not implemented"
try_withは「fというthunk」と「hという例外処理」の２関数を引数にとる。どちらの関数も返り値は同一な'a型で、try_with自体も返り値が'a型になる。
Effect的に考えるとfの中でRaise_exceptionなeffectが生じた場合にうまく処理するハンドラをtry_withの中に書く形になる：
let try_with (f : unit -> 'a) (h : exn -> 'a) : 'a = let handler = { effc=...; exnc=...; retc=...} in match_with f () handler
今回はexncには「f ()の中で本当に例外が投げられたらそのまま上に投げる」、retcには「f ()が普通に処理が終わって結果を返した場合はそのままその結果を返す」という処理を入れる：
let try_with (f : unit -> 'a) (h : exn -> 'a) : 'a = let handler = { effc=...; exnc=(fun e -> raise e); retc=(fun x -> x)} in match_with f () handler
（ただしraiseはこの場合シャドーされたやつになるが・・・ というかOCamlでのraiseって予約語じゃなくてシャドーできるものなんだ・・・）
なのでeffcの部分の実装：
effc = (fun (type c) (eff : c Effect.t) -> match eff with | Raise_exception e -> Some (fun (k : (c, _) continuation) -> h e) | _ -> None)
愚直にBasicsの例をなぞってみた。まず生じるeffectを表すeffとその限定継続k両方の型の一部に同一の型cが出てくる、という制約を表すために明示的に(type c)とlocally abstract typeを導入。effの型はc Effect.t、kの型は(c, _) continuationとなる。kの型の第二パラメータは限定継続がcontinueされると返ってくる型で、Exceptionの場合はcontinueすることはないので_にしておく。
effにパターンマッチしてRaise_exceptionならSome (fun (k : (c, _) continuation) -> h e)でこのハンドラで処理できることを示す（そして他のeffectはハンドルできない、ということを| _ -> Noneで表す）。
fun (k : (c, _) continuation) -> h eでは限定継続を引数にとるが使わず、その代わりRaise_exceptionに包まれていたexn型の値eをtry_withの引数として渡された「例外処理用の関数」hに適用している。
というわけで解答として実装した部分は以下の通り：
open Effect open Effect.Deep type _ Effect.t += Raise_exception : exn -> _ Effect.t let raise (e : exn) : 'a = perform (Raise_exception e) let try_with (f : unit -> 'a) (h : exn -> 'a) : 'a = let handler = { effc = (fun (type c) (eff : c Effect.t) -> match eff with | Raise_exception e -> Some (fun (k : (c,_) continuation) -> h e) | _ -> None); exnc = (fun e -> raise e); retc = (fun e -> e) } in match_with f () handler
テスト
実行してみる：
$ ocaml exceptions.ml
File "./exceptions.ml", line 33, characters 2-70:
33 | (fun Invalid_argument -> Printf.printf "Invalid_argument to sqrt\n")
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
*extension*
Matching over values of extensible variant types (the *extension* above)
must include a wild card pattern in order to be exhaustive.
6.513064
Invalid_argument to sqrt
懸念どおりfun Invalid_argument -> ...の部分でwarningが出る、がとりあえず期待された出力にはなる。
次回
この解答にはいくつか修正したい点がある。長くなったので次回に持ち越し。
OCaml 5.0のEffect Handlerのチュートリアルをやりはじめた
12月16日にOCaml 5.0が正式にリリースされた。
目玉機能としてはMulticoreサポートで、以前はPythonなどと同じくGlobal Interpreter Lockがあって複数スレッドでCPUバウンドな計算が同時に実行できなかったのを、ガベージコレクタをはじめとしたランタイムの大幅な更新により並行計算が可能となった。
それに関連してEffect Handlerという機能が入った。これは並行処理にも使えるが応用範囲は非常に幅広い機能で、まだ構文や型システムが決まりきっていないので実験的にライブラリとして使えるようになっている。モナドなどと似た、さまざまな副作用や制御フローを統一的に扱える機能で、正式採用されればOCamlプログラムの書き方が大きく変わる可能性もあり、私も含めた一部界隈ではMulticore以上に注目されている印象。
その新機能のチュートリアルがあるのでやりはじめた：
このチュートリアルはOCamlのEffect Handlerの実装がまだ実験段階だった（masterブランチにマージされるかも怪しいくらいの）時期からあったものだが、最終的にマージされた実装に合わせて今年修正されたようで、OCaml 5.0で追えるようだ。
ちなみに以下のPRで元々考えられていた専用構文から現在のライブラリ・関数を使ったEffect Handler構文に変更されたようなので、今後Effectsが専用構文付きで入るとしたらどのような構文になるかもしれないかを知る上では面白いかもしれない：
このチュートリアルの流れとしては
- 投げられたエラーを処理した上で、エラーが生じた点から続行する
- 可変なステート
- ジェネレータ
- 無限ストリーム
- コルーチン
- Async/Await
- ネットワークなどの非同期IO
といった機能をEffect Handlerで実装・解説するものとなっていて、かなり勉強になる。これから数回にわけてチュートリアルの内容や演習問題について書いていきたい。
とりあえず今回は第一の例である「投げられたエラーを処理した上で、エラーが生じた点から続行する」という例について見てみたい。以下の1.2 Basicsというセクションである：
ここのコードのeffect関連の部分を漁っていく。
まずEffectモジュールの扱い：
open Effect open Effect.Deep
いきなりEffectとEffect.Deepをopenしている。OCaml作法として個人的にはモジュール冒頭でのopenはあまり好ましくないように思うのだが・・・ チュートリアルだからショートカットとしてこのようにしているのだろうか？チュートリアルとしても、この二つのどちらから特定の名前が入ってきているのかわからなくなってマイナスに感じる。
とにかく今回はEffect.Deepを使っている。別にEffect.Shallowというものもあり、両者の違いはチュートリアルの先の方で説明されているので詳しくはまた今度の記事に書く。
次に新しいEffectの定義：
type _ Effect.t += Conversion_failure : string -> int Effect.t
この1行でOCamlの公式レファレンスでいうところのLanguage Extension（言ってしまえば上級者機能）が二つ使われている。extensible variant typeとgeneralized algebraic data typesである。
type ... += ...となっているのがextensible variant typeの構文で、既存のバリアント型に新しいコンストラクタを追加する、という意味になる。最近のOCamlではExceptionもこの機構を使っていて、ユーザ定義した例外もexn型のバリアントの一つとして追加できるようになっている。Exceptionを魔拡張したものという観点からすると、Effectもその機構を利用しているのは自然な流れかもしれない。
type _ t = T : a -> b tという構文がGADTだ。この言語機構については以前記事を書いた：
Conversion_failure : string -> int Effect.tとなっているのでConversion_failure "some text that fails to convert"という値はint Effect.t型を持つ。
その定義されたEffectの使いどころとしては：
let int_of_string l = try int_of_string l with | Failure _ -> perform (Conversion_failure l)
と前述の通りint Effect.t型となるConversion_failure lをperform関数に渡している。ちなみにperformはEffectsモジュール自体に含まれる唯一の関数で、これ以外のEffect関連関数などはすべてEffects.DeepかEffects.Shallowのいずれかに属している。
Conversion_failure lがint Effect.t型であるので、perform (Conversion_failure l)はint型となる。つまりEffectを実行した結果として何らかのintが帰ってくるということだ。一般的にa Effect.tをperformするとa型の値が返ってくる。
しかしこの例でint_of_stringがシャドーされてるのはどうなんだろう・・・。これもわかりにくい気がするが・・・。
とにかくこの例で定義されるint_of_stringから生じるConversion_failureというEffectをどのように扱うかを決めるEffect Handlerの定義：
let _ = ... match_with sum_up r { effc = (fun (type c) (eff: c Effect.t) -> match eff with | Conversion_failure s -> Some (fun (k: (c,_) continuation) -> Printf.fprintf stderr "Conversion failure \"%s\"\n%!" s; continue k 0) | _ -> None ); exnc = ...; retc = ... }
sum_upというのがint_of_stringを内部で使っている関数で、その関数に渡したい引数がrだ。
Effect.Deepで定義されているmatch_withは実行したい関数とそれに渡す引数、そしてhandler型の三つを引数としてとる。
handlerはsum_up rの実行中に
- effectを実行した場合の処理effc
- 例外を投げた場合のexnc
- 普通に関数適用が終了し値が返ってきた場合のretc
の三種類の関数からなるレコードである。
effcの定義に注目してみる：
fun (type c) (eff: c Effect.t) -> match eff with | Conversion_failure s -> Some (fun (k: (c,_) continuation) -> Printf.fprintf stderr "Conversion failure \"%s\"\n%!" s; continue k 0) | _ -> None
まずfun (type c) ... -> ...というのはまたしてもOCaml Language ExtensionであるLocally Abstract Typeだ。このfunの引数であるeffと、この関数内で出てくる限定継続kの間に共有される型cが出てくる、という制約をつけるために使われている。
具体的にはeffの型はc Effect.tなので前述の通りこのEffectが実行されるとc型が返ってくることを期待されている。そして継続kの型は(c,_) continuationである。(a,b) continuationはa型をとりb型を返す限定継続なので、(c,_) continuationは「何を返すかはわからないけどとにかくc型を受け取る限定継続」となる。
最終的にcontinue k 0している（continueはEffect.Deepで定義されている関数）のでperform (Conversion_failure l)の結果は必ず0となる。
というわけでしっかり追っていくとなんとかBasicな例は理解できた。しかしExtensible Variant Types、GADT、Locally Abstract Typeを明示的に使い、そして限定継続を表す('a, 'b) continuation型を明示的に型注釈する必要があるなど、OCamlの上級者向け機能が剥き出しでバンバン出てきて決して気軽に読み書きできるようなものではない。
Effect Handlerが普及していくにはやはり当初の計画通り専用構文で隠蔽していく必要があるのではないだろうか、というのが現在の印象である。
上記のOCaml Discussでの発表の通りEffect関連の型システムの詳細が決まった時点で専用構文の導入を検討するということなので、現状では好事家が試験的に使ってみる段階ということなのだろう。
