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