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

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

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

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はPythonやJavaScriptでyieldキーワードで定義されるような、あるコンテナの要素を一つずつ取り出せるモノ（データであれオブジェクトであれ関数であれ）。この演習では以下の型の関数として実装する：

type 'elt generator = unit -> 'elt option

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

let generate (type elt) (i : (elt, 'container) iterator) (c : 'container) : elt 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 =
    | 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などなら大した問題はないが、例えば副作用のあるもの（ネットワーク越しにデータを取りにいってるとか）や計算量が大きいものなどの場合はこうしたルックアヘッドな処理は避けたい。

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

Arantium Maestum

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

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

container, iterator, generator

解答１

問題点