Arantium Maestum

プログラミング、囲碁、読書の話題

OCaml 5.0のEffect HandlersでExtensible Interpreter 続

前回「任意のハンドラを組み合わせてインタプリタを作るといったComposabilityも持たせることができる」と書いた。今回はそのComposable Interpreter実装への準備段階として、前回のコードをリファクタしてeval関数とeffect handlerをある程度分離した形にする。

大まかに言って変更箇所は二点:

  • インタプリタ拡張のeval2、eval3の中で定義されているhandlerをeval関数の外に出す
  • Int, Add, SubなどもExtensionエフェクトを使ったインタプリタ拡張として表現する

eval関数からhandlerを出す

前回のコードをみると、eval2などの拡張インタプリタ関数とそれに使われるeffect handlerは密結合になっている:

let rec eval2 : 'a. 'a expr -> 'a = fun e ->
  let handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension (Mul(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = eval2 e1 in
          let n2 = eval2 e2 in
          D.continue k (n1 * n2))
      | Extension (Div(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = eval2 e1 in
          let n2 = eval2 e2 in
          D.continue k (n1 / n2))
      | _ -> None
  } in
  D.try_with eval1 e handler

eval2の中でhandlerが定義されているだけではなく、eval2自体が再帰的にhandlerの中で使われている。例えば以下の箇所:

      | Extension (Mul(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = eval2 e1 in
          let n2 = eval2 e2 in
          D.continue k (n1 * n2))

これは部分項の評価のためにeval2を再帰的に呼び出している。eval2の終わりでhandlerが使われているため、この再帰をなんとかしないとeval2とhandlerをうまく分離できない。

しかしよくみるとeval2 eの代わりにD.try_with eval1 e handlerでもいいことがわかる。これだとhandler自身は再帰的だが、eval2への依存はなくなる:

      | Extension (Mul(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = D.try_with eval1 e1 handler in
          let n2 = D.try_with eval1 e2 handler in
          D.continue k (n1 * n2))

handlerが再帰的になったが、handlerは実は多相だ。再帰関数については多相型に型推論されないので、明示的な多相型注釈が必要になる:

let rec handler : 'a. 'a D.effect_handler = ...

この時点でhandlerはeval2の内容に何ら依存していないのでeval2の定義の前に出すことができる。ついでに名前もeval2に合わせてhandler2にして、eval2の型注釈が不必要になったので省略すると、拡張インタプリタのコードは以下のようになる:

let rec handler2 : 'a. 'a D.effect_handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension (Mul(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = D.try_with eval1 e1 handler2 in
          let n2 = D.try_with eval1 e2 handler2 in
          D.continue k (n1 * n2))
      | Extension (Div(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = D.try_with eval1 e1 handler2 in
          let n2 = D.try_with eval1 e2 handler2 in
          D.continue k (n1 / n2))
      | _ -> None
  }

let eval2 e = D.try_with eval1 e handler2

eval3でもまったく同じリファクタを行う。

このコードだとまだhandler部分に「拡張前のインタプリタ関数」が出てきて、handlerを自在に組み合わせることはできない。しかし現在少なくとも「インタプリタ関数の作成」と「handlerの定義」を分離できたので一歩前進といえる。

Int, Add, Subなども拡張インタプリタ

前回のコードだと一番基本のインタプリタは既にInt、Add、Subの評価ができるようになっており、それ以外の構文の時にExtensionエフェクトを発生させるようになっていた:

let rec eval1 : type a. a expr -> a = function
| Int n1 -> n1
| Add(e1,e2) ->
  let n1 = eval1 e1 in
  let n2 = eval1 e2 in
  n1 + n2
| Sub(e1,e2) ->
  let n1 = eval1 e1 in
  let n2 = eval1 e2 in
  n1 - n2
| e -> Effect.perform (Extension e)

しかしInt, Add, Subが特別である必要はなく、むしろこれらもインタプリタ拡張として扱う方が統一性があっていいように思う。次の記事でみるComposableなインタプリタの場合、インタプリタがInt, Add, Subを扱えるかどうかも自由に決定できるようにしたい。

というわけでベースのインタプリタはあくまでExtensionエフェクトを発生させるだけにする:

let eval_base e = Effect.perform (Extension e)

そしてInt, Add, SubはMul, Divなどと同じようなハンドラベースの拡張インタプリタとして定義:

let rec handler1 : 'a. 'a D.effect_handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension (Int n) -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k n)
      | Extension (Add(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = D.try_with eval_base e1 handler1 in
          let n2 = D.try_with eval_base e2 handler1 in
          D.continue k (n1 + n2))
      | Extension (Sub(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = D.try_with eval_base e1 handler1 in
          let n2 = D.try_with eval_base e2 handler1 in
          D.continue k (n1 - n2))
      | _ -> None
  }

let eval1 e = D.try_with eval_base e handler1

次回

次こそはeval関数とhandlerを疎結合にしてhandlerを自由に組み合わせてインタプリタを作成できるようにする。疎結合化のためのツールはまたしてもエフェクトだ。

今回のコード

gist.github.com

OCaml 5.0のEffect HandlersでExtensible Interpreter

ツイッターOCamlのEffect Handlerの話題を漁っていたらこのようなツイートを見つけた:

Extensible Interpreterというのは「既にプログラムを実行できる既存の実装コードを変えることなく新しい構文を追加できる」というインタプリタのこと。OOPのOpen/Closed Principle("Programs should be open for extension, closed for modification")を体現したようなインタプリタだ。

コードはこちら:

Extensible Interpreter with Algebraic Effects · GitHub

このツイートとコードは2020年のもので、OCaml 5.0のeffect handler仕様が固まる前で、effect専用構文が使われている(ちなみにOCaml Effects Tutorialも出た当初は専用構文を使っていた)。

大変勉強になるのでこのコードをまずOCaml 5.0のeffect handlerで書き直して、その後拡張したいと考えている。とくにExtensibleなだけではなくComposableにしてみたい。(@takahisa_wt さん、ご快諾いただきありがとうございます!)

というわけでほぼ同じ実装をOCaml 5.0用に書き直したものがこちら。今回の記事ではこの実装の詳細を見ていく。

セットアップ

まずはモジュール名束縛:

module D = Effect.Deep

今回はEffect.Deepを使うのでDに束縛している。

項の型'a exprの定義:

type 'a expr = ..

'a exprは「項を評価した結果の型」'aにパラメトリックなGADTでかつextensible variant typeだ。

エフェクトを追加:

type _ Effect.t += Extension : 'a expr -> 'a Effect.t

「拡張された構文の項」を評価するためのエフェクトExtensionをEffect.tに追加している。このエフェクトはハンドラに'a expr型の値(評価したい項)を渡し、評価結果である'a型の値を限定継続に返す。

ベースのインタプリタ

次にインタプリタ本体の実装を見ていく。

まず基本的な構文:

type 'a expr +=
| Int : int -> int expr
| Add : int expr * int expr -> int expr
| Sub : int expr * int expr -> int expr

拡張前のインタプリタは整数リテラルとその加算・減算のみを扱う。extensible variant typeの'a exprに追加されているバリアントはGADT記法になっていて、Int nAdd(n, m)Sub(n, m)はすべてint exprとなる(ただしnやmもint expr)。

その構文を扱うインタプリタeval1:

let rec eval1 : type a. a expr -> a = function
| Int n1 -> n1
| Add(e1,e2) ->
  let n1 = eval1 e1 in
  let n2 = eval1 e2 in
  n1 + n2
| Sub(e1,e2) ->
  let n1 = eval1 e1 in
  let n2 = eval1 e2 in
  n1 - n2
| e -> Effect.perform (Extension e)

このベースとなるインタプリタにおいては、Int、Add、Subは普通のtree-walking interpreterのように評価される。Intはそのもののintとして評価され、AddやSubの場合は部分項二つが順次評価され、結果の整数が足され・差し引かれて結果として返る。

それ以外の構文に遭遇した場合は| e -> Effect.perform (Extension e)でExtensionエフェクトを生じさせている。外部のハンドラに処理を完全に移譲しているわけだ。面白いポイントとしてはハンドラの詳細(存在さえも)をeval1はまったく知らないという点だ。依存性の注入などよりもさらに極端な「関心の分離」といえる。その外部のハンドラが(存在すると仮定して)正しくその構文を評価してその結果を限定継続に渡すとその結果がeval1の返り値となる(Effect.perform (Extension e)が末尾ポジションなため)。

インタプリタ拡張1

整数を扱う構文二つを追加:

type 'a expr +=
| Mul : int expr * int expr -> int expr
| Div : int expr * int expr -> int expr

そしてeval1を使った拡張インタプリタeval2の定義:

let rec eval2 : 'a. 'a expr -> 'a = fun e ->
  let handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension (Mul(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = eval2 e1 in
          let n2 = eval2 e2 in
          D.continue k (n1 * n2))
      | Extension (Div(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = eval2 e1 in
          let n2 = eval2 e2 in
          D.continue k (n1 / n2))
      | _ -> None
  } in
  D.try_with eval1 e handler

eval2はeval1と違ってlocally abstract typeな型注釈は必要ないのでlet rec eval2 : type a. a expr -> aではなくlet rec eval2 : 'a. 'a expr -> 'aとなっている。これはGADTに必要なlocally abstract typeによる抽象性がhandler部分の型注釈で担保されているからだろう(多分)。

handlerでは新たに定義された構文の処理をExtensionエフェクトに対するパターンマッチとして書いている。Mul(n, m)Div(n, m)の部分項であるnやmの評価のためにeval2を再帰的に使っていることに注意。

最後に、D.try_with eval1 e handlerと、try_withを使って「拡張構文のためのハンドラhandler」の影響下で「拡張前のインタプリタeval1」に「拡張構文で書かれた項e」を渡している。

インタプリタ拡張2

次は真偽型も追加:

type 'a expr +=
| Bool : bool -> bool expr
| Eq : int expr * int expr -> bool expr
| Gt : int expr * int expr -> bool expr

拡張インタプリタeval3:

let rec eval3 : 'a. 'a expr -> 'a = fun e ->
  let handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension (Bool b1) -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k b1)
      | Extension (Eq(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = eval3 e1 in
          let n2 = eval3 e2 in
          D.continue k (n1 = n2))
      | Extension (Gt(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = eval3 e1 in
          let n2 = eval3 e2 in
          D.continue k (n1 > n2))
      | _ -> None
  } in
  D.try_with eval2 e handler

ほぼeval2と同じ。最後のD.try_with eval2 e handlerでうっかりD.try_with eval1 e handlerなどとするとMulとDivに対応していないインタプリタになってしまうので注意。

GADTを使っているので「今まで整数型しか返していなかったのが真偽型も返せるようにする」といった拡張が可能になっている。ハンドラもそういう多相をサポートしているのも面白いところだ。

使ってみる

let _ =
  let e = Gt(Mul(Int 2, Int 3), Add(Int 2, Int 3)) in
  let handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension _ -> failwith "Unknown syntax"
      | _ -> None
  } in
  let b = D.try_with eval3 e handler in
  print_endline @@ string_of_bool b

2*3 > 2+3という項e、未定義の構文エフェクトをすべて捕捉してエラーにするハンドラhandlerを定義、eval3で評価した結果を文字列化して出力している。

この「未定義の構文エフェクトを捕捉してエラーに」というのは@takahisa_wt さんの元のコードにあったものの直訳。実際にはOCaml 5.0だと完全なEffect Systemが載っておらず、この部分は無しでも型エラーにならないので省略可。(実際に使う分には型エラーになってくれた方がよっぽど嬉しいが・・・)

このコードを実行するとtrueと出力される。結果は簡単だが、どういう流れでこの結果が算出されるのかを考えるとかなりややこしい。大まかなステップを列挙してみようと思ったがはじめてみるとあまりにも長く複雑だったのでやめた。

既にあまり短くない要約としては:

  • 全体の項を評価するためにすべてのeval関数のtry_withを経由して、複数の層のハンドラをかけた上でeval1が呼び出される
  • eval1がそのまま評価できない項はExtensionエフェクトを発生させ、ハンドラの層を抜けていきながら正しく評価できるハンドラのところで止まって処理される
  • ハンドラが部分項の評価の結果を得るために、抜けてきたハンドラを再度かけた上でeval1する(項の評価は常にすべてのハンドラの影響下でのeval1関数で行われる)(ハンドラは自身より下の層のハンドラをかけ直す責務も負うので自分が定義されたevalを再帰的に呼び出す)
  • ハンドラが必要な部分項の結果を得ると、それらを適切に組み合わせて(例えば掛け合わせて)その結果を限定継続に渡す。それがExtensionエフェクトの発生元であるeval1の結果になる

上記の流れの2〜4が必要なだけ(部分項が出てくるたび)再帰的に繰り返されて最終的な結果が算出される。

次回

このコードはハンドラ自体に「現在のインタプリタ」が再帰的に使われており、そしてその現在のインタプリタには明示的に「拡張前のインタプリタ」がlet rec eval3 = ... D.try_with eval2 e handlerといった形でハードコードされている。

Extensibilityを実現するのにはこれで過不足ないのだが、これだと構文同士には依存関係がないのに構文を定義しているコードには依存グラフができている。

やりようによってはこういった依存性を排除できる。ハンドラはあくまで「追加される構文」についてのみの記述となり、任意のハンドラを組み合わせてインタプリタを作るといったComposabilityも持たせることができる。次回はその実装を見ていく。

今回のコード

gist.github.com

OCaml Effects Tutorialの演習「Generators from iterators」をやってみる3

前回の終わりに書いた通り、Effect.Shallowを使って「generatorが作成されてまだ要素を返していない」状態を特殊ケース化せずに処理できるようにする。

今回のコード

type ('elt, 'container) iterator = ('elt -> unit) -> 'container -> unit

type 'elt generator = unit -> 'elt option

let generate (type elt) (i : (elt, 'container) iterator) (c : 'container) : elt generator =
  let module S = Effect.Shallow in
  let open struct
    type _ Effect.t += Yield : elt -> unit Effect.t
    type status =
    | Paused of (unit, unit) S.continuation
    | Done
  end in
  let yield x = Effect.perform (Yield x) in
  let status = ref @@ Paused (S.fiber (fun () -> i yield c)) in
  let handler = {
    S.retc = (fun () -> status := Done; None);
    S.exnc = (fun e -> raise e);
    S.effc = (fun (type b) (eff : b Effect.t) ->
      match eff with
      | Yield x ->
        let handle_eff (k: (b,unit) S.continuation) =
          status := Paused k;
          Some x
        in
        Some handle_eff
      | _ -> None)
  } in
  fun () -> match !status with
  | Paused k -> S.continue_with k () handler
  | Done -> None

ポイントは四つ。

Effect.DeepではなくShallowを使っている:

  let module S = Effect.Shallow in

status型からStartingバリアントが再度消えている:

    type status =
    | Paused of (unit, unit) S.continuation
    | Done

ついでに限定継続の型も(unit, elt option) D.continuationから(unit, unit) S.continuationに変わっている。Effect.Shallowを使う影響で、限定継続がハンドラを含まなくなっているので、最終的に限定継続から返ってくる値の型はunitになる。Deepの場合は限定継続の中でハンドラが()を受け取りNoneを返していたのでelt option型となっていた。

Startingバリアントが消えたことに伴い最後のパターンマッチ関数でもStartingのケースが消えている:

  fun () -> match !status with
  | Paused k -> S.continue_with k () handler
  | Done -> None

(ついでにDeepではなくShallowを使っている影響でD.continue k ()S.continue_with k () handlerに変わっている)

最後にstatus値の初期化がStartedではなくPausedで始まること:

  let status = ref @@ Paused (S.fiber (fun () -> i yield c)) in

この最後のポイントが肝心。

Effect.Deepではあるハンドラの影響下でエフェクトの生じる処理を開始するmatch_withと、その処理のなかで生じたエフェクトから返ってきた限定継続を再度実行するcontinueがわかれている。そのためgeneratorから最初の要素を取り出す時はmatch_with、それ以降はcontinueを呼ぶ必要がある。

Effect.Shallowは単にcontinue_withのみがあり、初めてcontinue_withを呼ぶときのために「ただの関数を限定継続として扱えるようにする」fiber関数を提供しているので、初期値に独特のバリアントを用意する必要もなくただgeneratorが停止しているかどうかだけを気にしていればよく、ケースわけも減ってスッキリした記述となる。

次回

Effect.DeepでもStartingバリアントなしにできなくはないのだが、そのための記述量がEffect.Shallowに比べて非常に多いのであまりスッキリはしない。次はそのDeepを使った書き方の話(次といいつつすぐ書くかはわからないが、とりあえずこの話題に関しての続きという意味で・・・)。

OCaml Effects Tutorialの演習「Generators from iterators」をやってみる2

前回に続いてOCaml Effects TutorialのGenerators from Iteratorsをやっていく。

前回のコード

前回のコードを再掲する:

type ('elt, 'container) iterator = ('elt -> unit) -> 'container -> unit

type 'elt generator = unit -> 'elt option

let generate (type elt) (i : (elt, 'container) iterator) (c : 'container) : elt generator =
  let module D = Effect.Deep in
  let open struct
    type _ Effect.t += Yield : elt -> unit Effect.t
    type status =
    | Paused of elt * (unit, status) D.continuation
    | Done
  end in
  let yield x = Effect.perform (Yield x) in
  let handler = {
    D.retc = (fun () -> Done);
    D.exnc = (fun e -> raise e);
    D.effc = (fun (type b) (eff : b Effect.t) ->
      match eff with
      | Yield x -> Some (fun (k: (b,status) D.continuation) -> Paused (x, k))
      | _ -> None)
  } in
  let status = ref (D.match_with (i yield) c handler) in
  fun () -> match !status with
  | Paused (v, k) -> status := (D.continue k ()); Some v
  | Done -> None

前回書いた通り、このコードの問題は「n番目の要素をgeneratorから取り出した時点で既に内部状態でn+1番目の要素をiteratorから取り出している」というルックアヘッドに頼っている点。なるべくiteratorとgeneratorの進み具合を一致させたい。

修正したコード

というわけで修正したコードの全容:

type ('elt, 'container) iterator = ('elt -> unit) -> 'container -> unit

type 'elt generator = unit -> 'elt option

let generate (type elt) (i : (elt, 'container) iterator) (c : 'container) : elt generator =
  let module D = Effect.Deep in
  let open struct
    type _ Effect.t += Yield : elt -> unit Effect.t
    type status =
    | Starting
    | Paused of (unit, elt option) D.continuation
    | Done
  end in
  let yield x = Effect.perform (Yield x) in
  let status = ref Starting in
  let handler = {
    D.retc = (fun () -> status := Done; None);
    D.exnc = (fun e -> raise e);
    D.effc = (fun (type b) (eff : b Effect.t) ->
      match eff with
      | Yield x ->
        let handle_eff (k: (b,elt option) D.continuation) =
          status := Paused k;
          Some x
        in
        Some handle_eff
      | _ -> None)
  } in
  fun () -> match !status with
  | Starting -> D.match_with (i yield) c handler
  | Paused k -> D.continue k ()
  | Done -> None

変更箇所は以下の通り:

  • status型にStartingバリアントを追加
  • status型のPausedバリアントの保持する値をelt * (unit, status) D.continuationから(unit, elt option) D.continuationに変更
  • let status = ...let handler = ...の前に定義
  • let status = ref (D.match_with (i yield) c handler)からlet status = ref Starting
  • handlerがstatus型の値を返すのではなくstatus値に代入した上でelt option型の値を返す
  • 最後のfun () -> ...| Starting -> D.match_with (i yield) c handlerというケースを追加
  • fun () -> ...のPausedケースを| Paused (v, k) -> status := (D.continue k ()); Some vから| Paused k -> D.continue k ()に変更

一つ一つを見ていく。

status型

generatorの状況を表現するためのstatus型に「まだgeneratorから値を取り出していない」状況を表すStartingバリアントを追加する:

    type status =
    | Starting
    | Paused of (unit, elt option) D.continuation
    | Done

また前回のコードではPaused of elt * (unit, status) D.continuationで「次にgeneratorとして返す値」を「次に実行する限定継続」と一緒に保持していたのだが、そのような「次に渡す値」を算出しないようにするのでPaused of (unit, elt option) D.continuationと保持する値が限定継続だけになる。また限定継続の型自体も(値も保持した)statusを返すのではなく値そのもののオプションelt option型を返すようにする。

let status = ...

ハンドラの定義が前回では:

  let handler = { ... } in
  let status = ref (D.match_with (i yield) c handler) in

だったのが今回は:

  let status = ref Starting in
  let handler = { ... } in

このようになっている。

以前はstatusの初期値を計算するのにhandlerを使って一回iteratorから値と限定継続を取り出していたのが、今回は単にStartingで初期化している。そのかわりhandlerの中でstatus値に対して破壊的代入を行なっている。なので定義順を入れ替える必要があった。

let handler = ...

ハンドラはretcとeffcの両方が変わっている。

前回:

  let handler = {
    D.retc = (fun () -> Done);
    D.exnc = (fun e -> raise e);
    D.effc = (fun (type b) (eff : b Effect.t) ->
      match eff with
      | Yield x -> Some (fun (k: (b,status) D.continuation) -> Paused (x, k))
      | _ -> None)
  }

今回:

  let handler = {
    D.retc = (fun () -> status := Done; None);
    D.exnc = (fun e -> raise e);
    D.effc = (fun (type b) (eff : b Effect.t) ->
      match eff with
      | Yield x ->
        let handle_eff (k: (b,elt option) D.continuation) =
          status := Paused k;
          Some x
        in
        Some handle_eff
      | _ -> None)
  }

retc

    D.retc = (fun () -> Done);

    D.retc = (fun () -> status := Done; None);

になっている。つまり以前はstatus型のDoneバリアントを返していたのに対して、今回のコードではstatus値にDoneを代入した上でNoneを返している。(Noneはelt option型だ)

effc

    D.effc = (fun (type b) (eff : b Effect.t) ->
      match eff with
      | Yield x -> Some (fun (k: (b,status) D.continuation) -> Paused (x, k))
      | _ -> None)

    D.effc = (fun (type b) (eff : b Effect.t) ->
      match eff with
      | Yield x ->
        let handle_eff (k: (b,elt option) D.continuation) =
          status := Paused k;
          Some x
        in
        Some handle_eff
      | _ -> None)

になっている。

限定継続の型注釈がk: (b,status) D.continuationk: (b,elt option) D.continuationになり、限定継続が返す値の型がstatusからelt optionになったのを反映している。

そしてYield xエフェクトに対する処理自体が単にPaused(k, x)を返していたのが、status値にPaused kを破壊的に代入してからSome xを返すようになった。

以前はstatus値の更新をハンドラの外でやっていたのだが、今回はハンドラ内で実行している。ハンドラの外にPaused k(あるいはDone)も持ち出す場合、ハンドラからの返り値の型を新たに定義しなくてはいけなかったり、その結果に対して再度パターンマッチする必要が生じたりと記述がもたつくので、ほとんどの処理をハンドラ内で完結するようにしてある。

fun () -> match !status with ...

前回:

  fun () -> match !status with
  | Paused (v, k) -> status := (D.continue k ()); Some v
  | Done -> None

今回:

  fun () -> match !status with
  | Starting -> D.match_with (i yield) c handler
  | Paused k -> D.continue k ()
  | Done -> None

まず| Paused (v, k) -> status := (D.continue k ()); Some v| Paused k -> D.continue k ()になっている。ポイントは:

  • Pausedが限定継続のみを保持するようになった
  • status値の更新はハンドラ内で行われるようになった
  • D.continue k ()がそのままSome vのようなelt option型の値を返すようになった

という三点。今回の実装だと現在Pausedに保持されている限定継続をcontinueして返ってきた結果をそのまま返すようになっていて、前回の「一つ先の要素に対するルックアヘッドが行われてしまう」という問題が解決している。

さらにstatus型に追加された新バリアントであるStartingに対して| Starting -> D.match_with (i yield) c handlerとパターンマッチを行なっている。generate関数の引数であるiteratorのi、containerのc(この1文字変数名、演習問題だからそのままにしているけど嫌な気分になるな・・・)、Yieldエフェクトを発生させるyield関数、そして定義したhandlerがここで組み合わさる。

iterator関数のiがcontainerであるcに対してiterateし、cの各要素に対してyieldでYieldエフェクトを発生させ、そのエフェクトをhandlerで受け取って「iterationをそこで一旦停止させ限定継続を保存した上で要素を返す」という挙動を実現している。D.match_with (i yield) c handlerはやはり使われているハンドラ内部でstatus値を更新し、結果としてelt option型の値を返す。

次回

このコードで問題ないのだが、Effect.Shallowを使うと普通の関数を限定継続化できるのでStartingというバリアントに表される特殊ケースが必要なくなる。次回はその実装を見ていく。

OCaml Effects Tutorialの演習「Generators from iterators」をやってみる1

OCaml Effects Tutorialの演習問題として、任意のcontainerとそれに対するiteratorからgeneratorを作成する関数を実装してみる。

github.com

エフェクトハンドラが受け取る限定継続を直ちに使用あるいは破棄してきた今までの例と違って、「限定継続を一旦保存しておいて後で使う」というエフェクトの実装をする必要がある。

問題の未実装コードはここ:

github.com

container, iterator, generator

まず問題の解説として、何を指してcontainer, iterator, generatorと呼んでいるのかを説明する。

containerは何らかの要素(要素の型'eltに対してパラメトリック多相)を0個以上保持している(ただしメモリ上でとは限らない)データ型。簡単なものとしてはlistやtreeが挙げられるが、もしかするともっと複雑な、あるいはネットワークなどの副作用も含んだものかもしれない。

iterator'elt -> unitな関数と'elt型の要素を持つcontainerを引数にとり、containerに含まれるすべての要素に関数を適用する高階関数。List.iterを例に考えるとわかりやすい。

iteratorの型は

type ('elt,'container) iterator = ('elt -> unit) -> 'container -> unit

OCamlは型コンストラクタに対して多相になれないので'elt 'container'ではなく'containerに対して多相になっている)

generatorはPythonJavaScriptでyieldキーワードで定義されるような、あるコンテナの要素を一つずつ取り出せるモノ(データであれオブジェクトであれ関数であれ)。この演習では以下の型の関数として実装する:

type 'elt generator = unit -> 'elt option

任意のiteratorに対してgeneratorを作成する、以下のgenerate関数を実装するのが今回の演習問題:

let generate (type elt) (i : (elt, 'container) iterator) (c : 'container) : elt generator = ...

解答1

まず第一感で実装した解答について書く。これは演習問題直前の例題のコードを下書きに使ったもので、実際これでテストケースはすべて通る:

type ('elt, 'container) iterator = ('elt -> unit) -> 'container -> unit

type 'elt generator = unit -> 'elt option

let generate (type elt) (i : (elt, 'container) iterator) (c : 'container) : elt generator =
  let module D = Effect.Deep in
  let open struct
    type _ Effect.t += Yield : elt -> unit Effect.t
    type status =
    | Paused of elt * (unit, status) D.continuation
    | Done
  end in
  let yield x = Effect.perform (Yield x) in
  let handler = {
    D.retc = (fun () -> Done);
    D.exnc = (fun e -> raise e);
    D.effc = (fun (type b) (eff : b Effect.t) ->
      match eff with
      | Yield x -> Some (fun (k: (b,status) D.continuation) -> Paused (x, k))
      | _ -> None)
  } in
  let status = ref (D.match_with (i yield) c handler) in
  fun () -> match !status with
  | Paused (v, k) -> status := (D.continue k ()); Some v
  | Done -> None

解答部分はすべてgenerate関数の内部だ。

順を追って解説する。

まずモジュール指定:

  let module D = Effect.Deep in

今回はハンドラを動的に変えたりする必要はないのでEffect.Deepを(省略名Dで)使う。

関数ローカルなモジュール定義:

  let open struct
    type _ Effect.t += Yield : elt -> unit Effect.t
    type status =
    | Paused of elt * (unit, status) D.continuation
    | Done
  end in

Yieldエフェクトとgeneratorの現状を表すstatus型をgenerate関数にローカルな型として定義するため、無名モジュールを作成して即openしている。

Yieldはelt型の値を一つ保持するバリアント型。elt -> unit Effect.tなのでYield箇所で作成される限定継続は()を渡されることを期待している。

status型は「まだ要素が残っている状態」のPausedか「すでにすべての要素を返している状態」のDone。Pausedは最後にYieldで返された値とその限定継続が保持されている。

yield関数の定義:

  let yield x = Effect.perform (Yield x) in

単にYieldエフェクトをwrapしているだけ。

ハンドラ:

  let handler = {
    D.retc = (fun () -> Done);
    D.exnc = (fun e -> raise e);
    D.effc = (fun (type b) (eff : b Effect.t) ->
      match eff with
      | Yield x -> Some (fun (k: (b,status) D.continuation) -> Paused (x, k))
      | _ -> None)
  } in

retcはiteratorが正常に終わり結果としてunitを返してきた時点でstatus型の値Doneを返す。

exncは例外をそのまま上に投げる。

effcはYieldエフェクトのみハンドルしている。Yieldで値xと限定継続kを渡されるのでstatus型の値Paused(x, k)を返す。前述のとおり、今まではeffect handlerそのものやその中で呼び出される関数で即座に限定継続kに対してcontinueしたり破棄したりしていたのが、今回はkをデータ型に入れて返している。今後任意の時にこの限定継続をcontinueすることで停止した処理を続行させることができ、このように制御フローを扱えることがエフェクトの強力さの源になっている。

generatorの現在の状態を表すミュータブルなデータ:

  let status = ref (D.match_with (i yield) c handler) in

status ref型の値に変数statusを束縛している。ややこしい気もするがこういう型と式で同じ変数名を使い回すのってOCamlだとよくやるよね?status ref型の値を得るためにD.match_withでeffectfulな計算を実行している。

match_withはeffectfulな処理を行う関数、その関数に渡す値、ハンドラの三つを引数として受け取る。i yieldで引数として渡されたiteratorのiにgenerate内で定義したyield関数を部分適用していて、その結果の関数がこの場合の「effectfulな処理を行う関数」だ。

最後にgeneratorそのものとなる無名関数:

  fun () -> match !status with
  | Paused (v, k) -> status := (D.continue k ()); Some v
  | Done -> None

unit型の引数をとり、generatorの状態であるミュータブルなstatusを参照・パターンマッチする。

もしstatusがPausedなら保持されている限定継続を実行し結果をstatusに束縛した上で、元から保持されていた値vをoptionに包んでSome vとして返す。

もしstatusがDoneならNoneを返す。

以上がgenerate関数で、前述の通りこれでtutorialに載っているすべてのテストは通る。

問題点

ただし問題点は存在していて、それはgeneratorからn番目の要素を取り出す時に、generator内部ではn+1番目の要素をすでにiteratorから取り出しているような実装になっていること。iteratorがList.iterなどなら大した問題はないが、例えば副作用のあるもの(ネットワーク越しにデータを取りにいってるとか)や計算量が大きいものなどの場合はこうしたルックアヘッドな処理は避けたい。

次回はそれを踏まえた修正の話。

Effect.Deepで書かれたResumable ExceptionをEffect.Shallowで書き直す

OCaml 5.0のeffect handler機能はStandard Libraryに入っているEffectというモジュールを通して扱う。

このEffectというモジュールにはEffect.DeepとEffect.Shallowという二つのサブモジュールがあり、ほとんどの機能はこれらサブモジュールに入っている。

この二つのサブモジュールは一見似たような機能を提供しており、どちらにも('a, 'b) continuation('a, 'b) handlerといった型、get_backtracediscontinue_with_backtraceといった関数(後者は同じ名前なのにシグニチャが違うが・・・)、そしてEffect.Deep.continueEffect.Shallow.continue_withなどの対応する関数などが多く存在している。

この二つのモジュールの違いについてOCaml Effect Tutorialは以下のように説明している:

When a deep handler returns a continuation, the continuation also includes the handler. This means that, when the continuation is resumed, the effect handler is automatically re-installed, and will handle the effect(s) that the computation may perform in the future.

Shallow handlers on the other hand, allow us to change the handlers every time an effect is performed.

Deepの方の限定継続は自動的に元のハンドラに包まれていて新しいハンドラをつけることはできない(しかしその分ハンドラを明示することを省略できる)のに対して、Shallowでは限定継続を呼び出す時に明示的にハンドラをつけなければいけない分呼び出しごとにハンドラを更新することもできる。

両者の違いを理解するために、Effect.Deepで書かれたResumable Exceptionの例をEffect.Shallowで書き直してみる。

Effect.Deepのコード

このResumable Exceptionコードは「文字列を整数に変換するが、変換できない場合はConversion_failureというエフェクトを発生させる」というオレオレint_of_stringと、それを利用した「Conversion_failureが発生したらエラーを出力した上で整数0として扱って処理を続行する」というロジックを実装している。

まず少し自分好みにリファクタしておく:

type _ Effect.t += Conversion_failure : string -> int Effect.t

let int_of_string l =
  try int_of_string l with
  | Failure _ -> Effect.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 _ =
  let module D = Effect.Deep in
  Printf.printf "Starting up. Please input:\n%!";
  let r = ref 0 in
  let handler =
  { D.effc = (fun (type c) (eff: c Effect.t) ->
      match eff with
      | Conversion_failure s -> Some (fun (k: (c,_) D.continuation) ->
          Printf.fprintf stderr "Conversion failure \"%s\"\n%!" s;
          D.continue k 0)
      | _ -> None
    );
    D.exnc = (function
      | End_of_file -> Printf.printf "Sum is %d\n" !r
      | e -> raise e
    );
    D.retc = fun _ -> failwith "Impossible, sum_up shouldn't return"
  } in
  D.match_with sum_up r handler

主な変更点は二点:

  • open Effectなどを避けてモジュール名を明示するようにした
  • 複雑なレコードを関数適用している箇所で定義するのではなく、変数handlerとして定義した上でmatch_with関数に渡すようにした

Effect.Shallowのコード

上記のEffect.Deepを使ったコードをEffect.Shallowを使うように変更する:

type _ Effect.t += Conversion_failure : string -> int Effect.t

let int_of_string l =
  try int_of_string l with
  | Failure _ -> Effect.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 _ =
  let module S = Effect.Shallow in
  Printf.printf "Starting up. Please input:\n%!";
  let r = ref 0 in
  let rec handler =
  { S.effc = (fun (type c) (eff: c Effect.t) ->
      match eff with
      | Conversion_failure s -> Some (fun (k: (c,_) S.continuation) ->
              Printf.fprintf stderr "Conversion failure \"%s\"\n%!" s;
              S.continue_with k 0 handler)
      | _ -> None
    );
    S.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 *)
    S.retc = fun _ -> failwith "Impossible, sum_up shouldn't return"
  } in
  S.continue_with (S.fiber sum_up) r handler

変更点はすべてlet _ = ...の中だ。

列挙すると:

  • let module D = Effect.Deep inの代わりにlet module S = Effect.Shallow in
  • {D.effc=...; D.exnc=...; D.retc=...}{S.effc=...; S.exnc=...; S.retc=...}
  • fun (k: (c,_) D.continuation) -> ...fun (k: (c,_) S.continuation) -> ...
  • let handler =let rec handler =
  • D.continue k 0S.continue_with k 0 handler
  • 最後のD.match_with sum_up r handlerS.continue_with (S.fiber sum_up) r handler

最初の3つは自明だろう。Deepの代わりにShallowを使うので、名前を入れ替える必要がある(余談だがここはもしopen Effect.Deepとしていたらそこだけ変えればよかった、がしかしどの型・関数の提供元が変わったのかが明示的にわかる方がメリットがあると思う)

let handler =let rec handler =になるというのは、その次のD.continue k 0S.continue_with k 0 handlerになる変更に対応するためだ。つまりhandlerの中で限定継続に対してcontinueしているわけだが、Deepだとその場合特定のhandlerを指定しなくても現在のものがそのまま使われるのに対してShallowだと明示的に指定する必要が出てくる。なのでhandlerの中でShallow.continue_withにhandlerを再帰的に渡すという処理が出てくる。OCamlでは少し珍しい非関数な再帰だ。

最後のD.match_with sum_up r handlerS.continue_with (S.fiber sum_up) r handlerになるというところには二つの変更点がある。まずD.match_withS.continue_withになっている点、そしてsum_up(S.fiber sum_up)になっている点だ。

D.match_withS.continue_withになることに関しては、Deepがmatch_withtry_withcontinueを提供しているのに対してShallowはこれらに対応するものはcontinue_withしか提供していない。Shallowのeffectfulな処理を実行する場合、必ず処理を限定継続の形にしてハンドラと共にcontinue_withに渡すことになる。

sum_up(S.fiber sum_up)に変わっているというのはまさに「effectfulな処理を関数から限定継続に変換する」というShallow特有のロジックの発露だ。

雑感

個人的にはDeepにも限定継続を作り出せるfiber関数が(関数だけではなくハンドラも渡すような形で)存在してもいいのでは?と思わなくもない。そうすればmatch_withはcontinueに統合できるように思う。またShallowにもtry_withのように「ハンドラにeffcだけ書いてexncとretcを省略する」ような記法があってもいいはず。ここら辺のAPIの整備は今後進んでいくのかもしれない。

そもそもDeepって必要だろうか?DeepでできることはまずShallowでもできるはず(同じハンドラを使うよう指定するだけ)。逆はその限りではなく、Shallowでできるような「限定継続の呼び出しのたびにハンドラを変更する」といった処理は(少なくとも副作用などを使わない限り)Deepではできない。内部実装が違う可能性はあるが、上部だけをみるとDeepはShallowに対するちょっとした糖衣構文のように見える。

OCamlのlocally abstract typeに関するメモ2 (構文)

Locally abstract typeについてメモを続けていく。今回は構文について。

locally abstract typeに関する構文は4つある。そのうち3つは糖衣構文と言っていい。

基本構文

まず一番基本の構文

fun (type a) -> e

ぱっと見では関数式のように見えるが、上記の構文ではfun (type a) -> ...の部分はあくまでlocally abstract typesを導入しているだけでeには関数だけではなく任意の式が入る(型検査が通るかは別問題だが・・・)。そしてfun (type a) -> eを評価するとeは即座に評価される。

この「ぱっと見では関数式に見えるけど違う」というのは公式リファレンスでもかなり初めの方で:

Note that contrary to what the syntax could suggest, the expression fun ( type typeconstr-name ) -> expr itself does not suspend the evaluation of expr as a regular abstraction would. The syntax has been chosen to fit nicely in the context of function declarations, where it is generally used.

と言い訳的な説明が入る。"where it is generally used"とある通り関数以外でのうまい使用例は知らないが、構文上は関数に限定されていない。

ちなみにこの構文は言語開発者の間でもなんとなく微妙だと思われているようで、Gabriel Schererがredditのスレで「ほとんど使われないような機能だろうから構文がちょっと微妙でもいいだろうと考えていたら、時が経つにつれてみんな使うようになってしまった」と書いていた:

Finally: at the time where this feature was introduced, it was understood to be useful only in combination with advanced/arcane constructs that most OCaml programmers would rarely, if ever, encounter. So the fact of being slightly convoluted was not such a big issue. As time goes on, features thought of as "advanced" get internalized by more and more people and end up in more codebases.

関数用の糖衣構文2つ

実際に使うとなるとeは関数式であることが多い。そうするとfun (type a) -> fun (x : t) -> e(ただしtやeにaが出てくる)となってかなり冗長だ。

それを避けるための糖衣構文が二つ用意されている。

まず第一:

fun (type a) (x : t) -> e

fun (type a) -> fun (x : t) -> eの最初の二つのfunを合わせて一つにしている。

第二の糖衣構文はlet f = fun x -> elet f x -> eと書けるのと同じ理屈:

let f (type a) (x : t) = e

明示的な多相型注釈との組み合わせ

最後の糖衣構文は、locally abstract typeを導入するだけではなく関数に明示的な多相型注釈をつける場合。

糖衣構文なしだと

let f : 'a. t = fun (type a) (x : u) -> e

といった形になるのが

let f : type a. t' = fun (x : u) -> e

と表現できる(t'はtの中の'aをaに置換したもの)。

OCamlで関数に明示的な多相型注釈をつける必要があるのは大抵(常に?)多相な再帰関数なので、この糖衣構文は「多相な再帰関数にlocally abstract typesを導入する必要がある」ケース、例えばGADTに対する再帰などで活躍する。

次回

次はどのような状況でlocally abstract typesが必要になってくるのかを見ていく。