前回の記事に書いたとおり、今回はこのExtensible Interpreterの枠組みを使うとExpression Problemを解決できるということを見ていく。

Expression Problem

Expression Problemについては以前この記事で書いた：

zehnpaard.hatenablog.com

かいつまんで説明すると「オブジェクトだと新しいデータを追加するのは既存のコードを変更せずに（新しいクラスを追加するだけで）できるが、新しい処理を追加するのは（すべてのクラスにメソッドを実装する形で）既存のコードを改修する必要がある」「代数的データ型だと逆に処理を追加するのは簡単、新しいデータを（バリアントとして既存の型に）追加すると今まで書いた関数すべても変更が必要になる」というトレードオフの話。

Effect handler（とExtensible Variant Type）を使ったExtensible Interpreterの実装では、このExpression Problemが解決され、元のコードを触らずにデータも処理も追加できる。それを示すため、この記事では：

既存のevalコードを変更することなく項を文字列化するprint関数を追加
既存のevalとprintのコードを変更することなくif構文を追加し新しいeval+printを拡張として定義

の二つを行う。

処理の追加：print

前回のComposable Interpreterのコードに、evalの実装をほぼなぞるような形でprint関数を追加できる。

まずprint用のエフェクト：

type _ Effect.t +=
| PExtension : 'a expr -> string Effect.t
| Print : 'a expr -> string Effect.t

let print_effect e = Effect.perform (Print e)

eval用のExtensionとEvaluateに対応している。既存のExtensionエフェクトは'a expr -> 'a Effect.t型なのでハンドラを変えるだけではダメで、別途PExtensionのような別の'a expr -> string Effect.t型を用意する必要がある。

Printエフェクトとそれを発生させるprint_effect関数はevalでいうところのEvaluateとeval_effectに対応する。「ハンドラをすべてかけて文字列化する」というエフェクトだ。

PExtensionエフェクトのハンドラ：

let print_handler1 =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | PExtension (Int n) -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k (string_of_int n))
      | PExtension (Add(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          D.continue k (Printf.sprintf "(+ %s %s)" n1 n2))
      | PExtension (Sub(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          D.continue k (Printf.sprintf "(- %s %s)" n1 n2))
      | PExtension (Mul(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          D.continue k (Printf.sprintf "(* %s %s)" n1 n2))
      | PExtension (Div(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          D.continue k (Printf.sprintf "(/ %s %s)" n1 n2))
      | PExtension (Bool b1) -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k (string_of_bool b1))
      | PExtension (Eq(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          D.continue k (Printf.sprintf "(= %s %s)" n1 n2))
      | PExtension (Gt(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          D.continue k (Printf.sprintf "(> %s %s)" n1 n2))
      | _ -> None
  }

現在定義されているすべての構文を一つのハンドラで処理している。もちろんevalのように分割してもいい。文字列化の具体構文はS式にしてある。

インタプリタを組み上げる：

let print_base e = Effect.perform (PExtension e)
let print1 e = D.try_with print_base e print_handler1

let print e =
  let rec handler : 'a. 'a D.effect_handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Print e -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k (D.try_with print1 e handler))
      | _ -> None
  } in
  D.try_with print_effect e handler

evalとまったく同じで、PExtensionエフェクトを発生させるだけのprint_baseにPExtensionハンドラをかけて、その後Printハンドラも追加することでprint_effect関数が「すべてのハンドラをかけ直して項を文字列化」という処理になるようにする。

使ってみる：

let _ =
  let e = Gt(Mul(Int 2, Int 3), Add(Int 2, Int 3)) in
  let print_handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | PExtension _ -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k "???")
      | _ -> None
  } in
  let s = D.try_with print e print_handler in
  print_endline s

Gt(Mul(Int 2, Int 3), Add(Int 2, Int 3))が(> (* 2 3) (+ 2 3))と出力される。

evalの時はハンドラの存在しない構文に関してはfailwithでエラーにしていたが、文字列化では試しに???という文字列を返すようにしてみた。もしprint_handler1からPExtension (Int n)のケースを削除するとGt(Mul(Int 2, Int 3), Add(Int 2, Int 3))は(> (* ??? ???) (+ ??? ???))と出力される。

というわけで「既存の実装を変えることなく関数を追加」はできた。代数的データ型だから当たり前とも言えるが・・・。これがクラスベースの実装だったら既存のクラス一つ一つにprintメソッドを追加していくことになるだろう。

データの追加：if構文

では代数的データ型の「問題」とされる、「既存の実装を変えることなくデータの種類を追加」のケースを見ていく。

具体的にいうとif構文を追加する：

type 'a expr +=
  | If : bool expr * 'a expr * 'a expr -> 'a expr

ここはextensible variant type様様で、もし普通のバリアント型だったらその時点で「既存の型定義に変更を加える」という形にならざるを得なかった。この型の拡張はたとえば別々にコンパイルされるモジュールでも可能なことに注意。

eval関数の拡張：

let handler_if =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension (If(e1, e2, e3)) -> Some (fun (k: (b,_) D.continuation) ->
          let b = eval_effect e1 in
          let x = eval_effect (if b then e2 else e3) in
          D.continue k x)
      | _ -> None
  }

let eval4 e = D.try_with eval e handler_if

let eval e =
  let rec handler : 'a. 'a D.effect_handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Evaluate e -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k (D.try_with eval4 e handler))
      | _ -> None
  } in
  D.try_with eval_effect e handler

Composableにしたことが拡張性を損なっていないことがわかる。すでに定義したeval関数をベースにIf構文のExtensionハンドラとそのハンドラで生じるEvaluateエフェクトのハンドラをかける新しいeval関数を定義している。

printもまったく同じ：

let print_handler_if =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | PExtension (If(e1, e2, e3)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          let n3 = print_effect e3 in
          D.continue k (Printf.sprintf "(if %s %s %s)" n1 n2 n3))
      | _ -> None
  }

let print2 e = D.try_with print e print_handler_if

let print e =
  let rec handler : 'a. 'a D.effect_handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Print e -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k (D.try_with print2 e handler))
      | _ -> None
  } in
  D.try_with print_effect e handler

evalの実装をなぞるだけ。

こんな感じで使うと：

let _ =
  let e = If(Gt(Mul(Int 2, Int 3), Add(Int 2, Int 3)),Int 0, Int 1) in
  let handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension _ -> failwith "Unknown syntax"
      | _ -> None
  } in
  let n = D.try_with eval e handler in
  print_endline @@ string_of_int n;
  let print_handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | PExtension _ -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k "???")
      | _ -> None
  } in
  let s = D.try_with print e print_handler in
  print_endline s

$ ocaml interpreter3.ml
0
(if (> (* 2 3) (+ 2 3)) 0 1)

うまく使えているのがわかる。

雑考

Expression Problemに対する一つの解となっているのは確かだと思う。

しかしそのための道具立てがかなり重い感触ではある。行数からも、そして複雑な言語機能が剥き出しでコード読みにかかるオーバーヘッドからも、「ここまでするか？」という気持ちになる。専用構文などで軽くなったらマシになるだろうか？あるいはこのコードのようにハンドラをレコード（つまりデータ）として自由に扱うのが難しくなる可能性もある。今後effect handlerという言語機能が使われ出して、どのようなhandler compositionのパターンが出てくるのか、そしてそのパターンをどう構文でサポートしていくのか、大変興味深く目が離せない。

今回のExpression Problemの解決法にはEffect Handlerが必須で、Extensible Variant Typeだけでは足りない。後者だけだとバリアント型は既存の定義を触らずに拡張できるのだが、既存のeval関数に手を加えないとその追加されたバリアントに対応できない。

ちなみにExpression Problemとは直接関係ないが、Composable Interpreterを実装する別解としては多相バリアントを使ってやる方法もある。でこれきさん（@dico_leque）が以前書かれていた：

qiita.com

こちらはComposable but not Extensibleになるだろうか。新しいバリアントに対応するためには、既存のevalを使うのではなくパーツを集め直して新しいeval関数を定義することになる。

しかしEffect Handlerを使うとopen recursionも簡単（？）に実装できるようになるのか・・・？この点に関してはもうちょっと考えてみたい。

今回のコード

gist.github.com

Arantium Maestum

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

Effect Handler、Extensible Interpreter、Expression Problem

Expression Problem

処理の追加：print

データの追加：if構文

雑考

今回のコード