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

Algebraic Effects (Multicore OCaml)を使ってExtensible Interpreterを実装する例:https://t.co/b1Tu4pys6d

ポイントはeffect handlerにcontinuationが渡ってくる (=復帰ができる)点で、これがExtensible Interpreterと非常に相性が良い。他の実装法に比べても簡潔で綺麗な印象 (主観)
— takahisa (@takahisa_wt) July 24, 2020

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 n、Add(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)が末尾ポジションなため）。

インタプリタ拡張１

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

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」を渡している。

インタプリタ拡張２

次は真偽型も追加：

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の結果になる

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

次回

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

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

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

今回のコード

gist.github.com

Arantium Maestum

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

OCaml 5.0のEffect HandlersでExtensible Interpreter