めざそう言語処理系の沼 〜shift/resetへの旅 〜 その７ 関数（レキシカル・スコープ）

前回実装したダイナミック・スコープの関数は、実装は楽だが使うにはけっこうピーキーである。より一般的なレキシカル・スコープに直すとする。

関数の定義を評価して「関数の値」を作成する時に、関数内に出てくる自由変数を検出して、定義時の変数環境でそれらに対応する値を取って、「関数の値」に保持させる。

関数呼び出し時にはこれら「自由変数と対応する値」のリストと仮引数・実引数のリストだけを変数環境に入れてから関数の本体の式を評価する。

「式の中の自由変数を取ってくる」というのが最大のポイントで、これが出来ればあとは比較的簡単。

前回との差分：

Comparing v0.6...v0.7 · zehnpaard/kontlang · GitHub

まずValモジュールで関数の値の定義をいじる：

type t =
...
| Fn of string * string list * (string * t) list * Exp.t

前回に比べて(string * t) listが加わっている。これが「関数内の自由変数と、それに対応する値」のリストだ。

Utilsモジュールを新しく作成した。インタプリタ固有の型（Val.tやExp.tなど）とは関係ない関数などを入れていく。今回はUtils.split3を定義：

let split3 xyzs =
  let rec f xs ys zs = function
  | [] -> xs, ys, zs
  | (x,y,z)::xyzs -> f (x::xs) (y::ys) (z::zs) xyzs
  in
  f [] [] [] xyzs

OCamlのスタンダードライブラリのListモジュールに定義されているsplitの型が

(a, b) list -> (a list, b list)

なのだが、Utils.split3は

(a, b, c) list -> (a list, b list, c list)

という型で、要素３のタプルのリストをリスト三つのタプルに変換する。

次にEnvモジュールにヘルパー関数を三つ追加：

let rec contains var = function
| [] -> false
| []::env' -> contains var env'
| ((var', _)::env')::env'' ->
    if var = var' then true
    else contains var @@ env'::env''

let add_var env v = extend_current v (Val.Int 0) env
let add_vars env vs =
  let vvs = List.map (fun v -> (v, Val.Int 0)) vs in
  extend_list vvs env

containsは変数環境にある変数が含まれているかどうかを調べる。

add_varとadd_varsは変数環境にダミー変数を追加する。つまり「ある変数に何かしらの値が束縛されている（値の内容は問わない）」という状況を作るための関数である。

最後はやはりExecuteモジュール。ある式の自由変数を取ってくるget_free：

let rec get_free env = function
| Exp.Int _ -> []
| Exp.Var s -> if (Env.contains s env) then [] else [s]
| Exp.Call(e, es) -> (get_free env e) @ (List.concat @@ List.map (get_free env) es) 
| Exp.If(e1, e2, e3) -> (get_free env e1) @ (get_free env e2) @ (get_free env e3)
| Exp.Let(ves, e2) ->
    let vs, es = List.split ves in
    (get_free (Env.add_vars env vs) e2) @ (List.concat @@ List.map (get_free env) es)
| Exp.Lets((s, e1)::ves, e2) ->
    (get_free env e1) @ (get_free (Env.add_var env s) @@ Exp.Lets(ves, e2))
| Exp.Lets ([], e2) -> get_free env e2
| Exp.Fn(params, body) -> get_free (Env.add_vars env params) body
| Exp.LetFn(fns, e) ->
    let fnames, paramss, bodys = Utils.split3 fns in
    let f params body = get_free (Env.add_vars env params) body in
    let free_in_fns = List.concat @@ List.map2 f paramss bodys in
    (get_free (Env.add_vars env fnames) e) @ free_in_fns

再帰的に式から自由変数を取り出していき、List.concat（あるいはその演算子である@）で繋げていってる。EnvやUtilsで新しく定義された関数もここで使われている。

今見返してみるといくつか問題点が見つかる：

• 自由変数がダブる。同じ自由変数が複数出てくる度に自由変数リストにも追加されてしまう
• 自由変数かどうかを調べるためだけに変数環境（文字列と値のリストのリスト）を使っていてそのためにダミー値まで追加しているが、定義済み変数のリスト（文字列のリスト）だけで本来事足りる
• いちいちconcatしまくっていて非常に効率が悪い

まあ自由変数のリストがそう大きくなることはないと思うのでそこまで気にするところでもないが、とりあえず「自由変数がダブる」ところは後ほど修正する。

Executeモジュールのeval：

let eval env cont = function
...
| Exp.Fn(params, body) as e ->
    let free = get_free Env.empty e in
    let fvals = List.map (fun v -> v, Env.find v env) free in
    ApplyCont(env, cont, Val.Fn("anon", params, fvals, body))
| Exp.LetFn(fns, e) ->
    let f (fname, params, body) =
      let free = get_free (Env.add_vars Env.empty params) body in
      let fvals = List.map (fun v -> v, Env.find v env) free in
      (fname, Val.Fn(fname, params, fvals, body))
    in
    Eval(Env.extend_list (List.map f fns) env, Cont.Env::cont, e)

get_freeを使って自由変数を取ってきて、さらに現在の変数環境で対応する値を取り、その変数*値のリストを関数の値に保持する、という変更。前回のダイナミック・スコープがほとんどなんの処理もしていなかったのと打って変わってけっこう複雑になっている。

最後にapply_cont関数：

let apply_cont env cont v = match cont with
...
| Cont.Call([], vs) :: cont' -> (match List.rev (v::vs) with
  ...
  | Val.Fn(s, ss, fvals, e) :: vs' ->
    let paramcount = List.length ss in
    let argcount = List.length vs' in
    if paramcount = argcount then
      let env' = Env.extend_list (fvals @ (List.combine ss vs')) env in
      Eval(env', Cont.Env::cont', e)
    else failwith @@ Printf.sprintf "Function %s called with incorrect number of args: expected %d received %d" s paramcount argcount

ダイナミック・スコープでは仮引数と実引数を変数環境に追加してから関数本体の式を評価していたのだが、今回は仮引数・実引数に加えて自由変数と対応する値も変数環境に加えている。

レキシカル・スコープの場合、既存の変数環境に加えるのではなく、まっさらな変数環境に仮引数・実引数、自由変数と対応する値だけ加えて評価してもいいのだが、そうすると関数呼び出しの評価が終わって元の変数環境に戻したい時にめんどくさい（継続に変数環境を格納する必要がある）。今回実装したように既存の変数環境に追加してもシャドーイングで評価結果は同じな上、今までどおりCont.Envだけで元の環境に戻せる利点がある。

以上でレキシカル・スコープへの変換終了。

こんな式も：

(letfn [f [x] (* x x)]
  (let [* +] (f 5)))

期待どおりに結果が２５になり、関数定義時になかった変数束縛に関数呼び出しの結果が影響されなくなっている。

次回は再帰関数を追加する。

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その６ 関数（ダイナミック・スコープ）

分岐や変数束縛が出来るようになったので、次は関数定義を追加したい。

機能としては：

• fnで無名関数を作成
• letfnで関数を名前付きで作成（複数同時も可）
• 多引数に対応、引数の数が定義時と呼び出し時に合っていなかったらエラー
• 今回はダイナミック・スコープ

といったところ。

使用例としては：

((fn [x y]
   (+ (* x x)
      (* y y)))
 3
 4)

（結果は25）とか：

(letfn [f [x y] (+ (* x x) (* y y))]
  (f 3 4))

(letfn [(f [x] (* x x))
        (g [x] (+ x x))]
  (- (f 5) (g 10)))

（結果は２５と5）といったプログラムが書けるようになる。（letと同じく、定義されている関数が一つだけだったら[]の内側の()は省略できる）

今回のコード差分：

Comparing v0.5...v0.6 · zehnpaard/kontlang · GitHub

まず、Exp.tにfnとletfnの式を追加：

type t =
...
| Fn of string list * t
| LetFn of (string * string list * t) list * t

無名関数は

• 引数の文字列のリスト
• 呼び出し時、引数を変数束縛した後に評価される式

だけで成り立っている。

名前付き関数だとここに関数名を表す文字列が追加される。なのでLetFnは

• 名前付き関数を表す「『関数名の文字列』『引数の文字列のリスト』『呼び出し時に（中略）評価される式』」のリスト
• let本体の式

を持つ。

次にValモジュール：

type t =
...
| Fn of string * string list * Exp.t

無名関数、名前付き関数どちらも定義が評価されるとVal.Fnという値になる。

• 関数名の文字列
• 引数の文字列のリスト
• 呼び出し時に（中略）評価される式

と、関数の値は式とほとんど同じ構成になっている。この簡単な構成はダイナミック・スコープならではで、本体の式に出てくる自由変数を捕捉してクロージャにしたりする必要がないので非常に楽（その分言語がピーキーになるが・・・）。

最後はExecuteモジュール。eval：

let eval env cont = function
...
| Exp.Fn(params, body) -> ApplyCont(env, cont, Val.Fn("anon", params, body))
| Exp.LetFn(fns, e) ->
    let f (fname, params, body) = (fname, Val.Fn(fname, params, body)) in
    Eval(Env.extend_list (List.map f fns) env, Cont.Env::cont, e)

Exp.Fnの場合はそのままVal.Fnに変換（変数名は"anon"に統一）して、apply_contに渡している。

Exp.LetFnの場合はExp.Fnと同じようにVal.Fnに変換してから、Exp.Letと同じように変数束縛し、継続にCont.Envを追加して本体の式を評価している。

新しい継続がまったく出てこない。関数定義を評価する時に「式の一部分の式を評価してあれこれする」と流れが出てこないので特殊な継続が必要ないのである。

ただし、apply_contのCont.Callケースに手を入れる必要はある：

let apply_cont env cont v = match cont with
...
| Cont.Call([], vs) :: cont' -> (match List.rev (v::vs) with
  | Val.Op(_, fn) :: vs' -> ApplyCont(env, cont', (fn vs'))
  | Val.Fn(s, ss, e) :: vs' ->
    let paramcount = List.length ss in
    let argcount = List.length vs' in
    if paramcount = argcount then Eval(Env.extend_list (List.combine ss vs') env, Cont.Env::cont', e)
    else failwith @@ Printf.sprintf "Function %s called with incorrect number of args: expected %d received %d" s paramcount argcount
  | _ -> failwith "Calling non-callable in operator position")

今までは関数呼び出し時にオペレータポジションがVal.Opならよし、そうでない場合はエラーだったのだが、今回Val.Fnケースを追加（ついでにエラー時にCalling non-opだったメッセージをCalling non-callableにした）。

関数呼び出しのロジックはけっこう簡単で、定義時の引数の数と呼び出し時の引数の数（仮引数と実引数）が一致しない場合はエラー。一致した場合、仮引数と実引数を合わせて変数環境に追加し、Cont.Envを継続に追加した上で、関数の本体の式を評価する。

このように意外と簡単に関数が実装できた。ダイナミック・スコープなのも楽だった要因の一つである。

しかし、ダイナミック・スコープだと言語としては使いづらい。関数呼び出し時の変数環境によって関数の挙動が変わってしまう可能性があるからである。

例えば変な例だが：

(letfn [f [x] (* x x)]
  (let [* +] (f 5)))

だと、f定義時には*は普通なのに、呼び出し時にはシャドーされてしまって挙動が完全に変わっている（結果は１０になる）。例を簡単にするために*を使ったが、普通のユーザ定義された変数だったらこのようなシャドーイングが簡単に起き得るのは想像がつくと思う。うまくやれば面白い使い方もできそうだが、プログラムの挙動が予想できなくなる可能性の方がずっと高い。

ということで次回は関数をレキシカル・スコープに変更する。

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その５ 変数とlet

前回でようやくifで分岐ができるようになった。今回はletを使って変数を定義できるようにする。

こんな感じの式が評価できるようになる：

(let [x 5]
  (+ x 6))
(let [(x 5)
      (y 6)]
  (+ x y))

Clojureっぽく[]が構文に現れるようにしてみた。複数の変数を同時に定義できるようになっている。ただし、複数の変数を定義する場合は変数と式を()で囲む必要がある点はClojureとは違う（フォーマッタなしでプリント出力した時に読みやすくするため）

また、一つのletの中で定義された変数はお互いに参照できない。そのためのlet*も追加する：

(let* [(x 5)
       (y (+ x 1))]
  (+ x y))

この場合yの定義にxが使える。ただし、出てくる順番は大事で上の例だとxの定義にyは使えない。相互再帰はまだ無理。

というわけで今回のコード差分：

Comparing v0.4...v0.5 · zehnpaard/kontlang · GitHub

ExpモジュールにLet``Letsを追加：

type t =
...
| Let of (string * t) list * t
| Lets of (string * t) list * t

Contモジュールにも追加：

type cont =
...
| Let of string * (string * Exp.t) list * (string * Val.t) list * Exp.t
| Lets of string * (string * Exp.t) list * Exp.t
| Env

Cont.Letはletの変数に束縛される式を評価している間

• 評価中の式に対応する変数
• 残っている未評価の式と対応する変数」
• すでに評価済みの値と対応する変数名
• 最終的に評価する本体の式

を保持しておく。未評価の式がなくなったらCont.Letを外し、変数環境を更新して本体の式を評価する。

同じようにlet*に対応するCont.Letsには

• 評価中の式に対応する変数
• 残っている未評価の式と対応する変数
• 最終的に評価する式

が保持される。let*の場合、すでに評価済みの値はそのまま変数環境に格納するので継続で保持する必要がない。

さらに「let``let*式の評価が終わった時点で、環境に追加された変数を取り除く」Cont.Env継続も追加。これを忘れるとlet内で定義した変数が外部に漏れてしまう。

変数環境から直近で追加された変数の集まりを取り除くのを簡単にするため、Env.tの内部実装を変更する：

type t = (string * Val.t) list list

let empty = [[]]

let extend var val_ env = [(var, val_)]::env
let extend_current var val_ = function
| [] -> [[(var, val_)]]
| env::env' -> ((var, val_)::env)::env'
let extend_list vvs env = vvs :: env

let rec find var = function
| [] -> failwith @@ Printf.sprintf "Variable %s not found" var
| []::env' -> find var env'
| ((var', val')::env')::env'' ->
    if var = var' then val'
    else find var @@ env'::env''

let pop = function
| [] -> failwith "Popping empty environment"
| _::env' -> env'

今までは変数環境Env.tは(string * Val.t) listだったのが(string * Val.t) list listになっている。letやlet*で一度に追加される変数と値は一つのリストとしてEnv.tに追加され、式の評価が終わったらpopで一度に外される。

Executeモジュールのeval関数：

let eval env cont = function
...
| Exp.Let((s, e1)::ves, e2) -> Eval(env, Cont.Let(s, ves, [], e2) :: cont, e1)
| Exp.Let _ -> failwith "Evaluating empty Let"
| Exp.Lets((s, e1)::ves, e2) -> Eval([]::env, Cont.Lets(s, ves, e2) :: cont, e1)
| Exp.Lets _ -> failwith "Evaluating empty Let"

Exp.Letの評価は非常に単純で、変数束縛の部分のリストの先頭をとり、Cont.Let/Cont.Letsを継続に追加した上で、その先頭の式を評価する。変数束縛の部分が空だと実行時エラー。

Exp.Letsもほとんど同じだが、唯一の違いとして変数環境に空のリストを追加している。変数環境を最後に一度に変更するletと違って、let*では変数一つ一つを逐次環境に追加していくので、この空リストはそれらの受け皿になる。

apply_cont関数のCont.Let部分：

let apply_cont env cont v = match cont with
...
| Cont.Let(s, [], vvs, e2) :: cont' ->
    let env' = Env.extend_list (List.rev ((s, v)::vvs)) env in
    Eval(env', Cont.Env::cont', e2)
| Cont.Let(s, (s', e')::ves, vvs, e2) :: cont' ->
    Eval(env, Cont.Let(s', ves, (s, v)::vvs, e2) :: cont', e')

「未評価な式と変数」のリストが空かどうかで場合分けしてある。

「未評価な式と変数」のリストが空な場合は、変数に束縛するべき式がすべて評価し終わっているので、評価済みの値をリバースして環境にくっつける（今気づいたがリバースする必要ないな・・・）。その環境を使ってlet式の本体の式を評価する。その評価が終わったら変数環境を元に戻すようCont.Envを継続に追加しておく。

「未評価な式と変数」のリスト（variable+expressionsということでvesで表している）が空ではない場合、apply_contの引数の一つである「たった今評価が終わった値」とその変数（Cont.Letの第一要素）を評価済み値と変数のリスト（variable+valuesのvvs）に追加したCont.Letを継続に加えた上で、次の式を評価する。

apply_cont関数のCont.Lets部分：

let apply_cont env cont v = match cont with
...
| Cont.Lets(s, [], e2) :: cont' ->
    Eval(Env.extend_current s v env, Cont.Env::cont', e2)
| Cont.Lets(s, (s', e')::ves, e2) :: cont' ->
    Eval(Env.extend_current s v env, Cont.Lets(s', ves, e2) :: cont', e')

Cont.Letと同じように「未評価な式と変数」のリストが空かどうかで場合分けしてある。空だったらCont.Envを継続に追加してlet*本体の式を評価、空ではない場合は更新したCont.Letsを継続に追加して次の式の評価を続行。どちらのケースでも、evalの部分で環境に追加されたリストにEnv.extend_currentで変数と値を追加していく。

ちなみにCont.Envを追加するタイミングはapply_cont内じゃなくて最初のevalの時の方がいいかもしれない。今はどちらでも問題ないが、今後shift/resetを実装するなどしてlet*の途中で実行が中断された場合、変数環境に空リストが追加された時点で対になるCont.Envが継続に追加されていた方がいいはず。後々修正する。

最後にapply_cont関数のCont.Env部分：

let apply_cont env cont v = match cont with
...
| Cont.Env :: cont' -> ApplyCont (Env.pop env, cont', v)

変数環境の直近のリストを一つ外す。これで変数環境をletやlet*の中に入る前の状態に戻せる。

というわけで変数束縛が可能になった。

次は非再帰関数を言語に追加する。

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その4 真偽値

前回までは言語で扱える値は整数値と組み込み関数だけだった。比較とか分岐とかしたいよね、ということで今回は真偽値を追加して、ifで分岐できるようにする。

以下のようなコードが書けるようにする：

(if
  (and (>= 3 1 1)
       (< 0 3)
       false
       (<= 1 2 3 3 5))
  1
  2)

コード差分：

Comparing v0.3...v0.4 · zehnpaard/kontlang · GitHub

Valモジュール：

type t =
| Int of int
| Bool of bool
| Op of string * (t list -> t)

let to_string = function
| Int n -> string_of_int n
| Bool b -> string_of_bool b
| Op (s, _) -> Printf.sprintf "Op(%s)" s

Val.t型にBoolコンストラクタを追加した。

次はBuiltinsモジュールにいろいろ追加していく。

まずはtrue/false：

let builtins =
[ ...
; "true", Val.Bool true
; "false", Val.Bool false
...
]

trueやfalseをパーサに追加するのではなく、Val.Boolの値を持つ組み込み変数として定義している。

次は整数の比較：

let num_bool_op s op =
  let g = function
  | Val.Int n -> n
  | _ -> failwith @@ "Non-numeric value passed to numeric op " ^ s
  in
  let rec h op = function
  | [] | [_] -> Val.Bool true
  | x::y::ys -> if op x y then h op @@ y::ys else Val.Bool false
  in
  let f xs = match List.map g xs with
  | [] -> failwith @@ Printf.sprintf "NumBool op %s applied to empty list" s
  | [_] -> failwith @@ Printf.sprintf "NumBool op %s applied to one arg" s
  | ys -> h op ys
  in
  Val.Op (s, f)

let not_equal_op =
  let g = function
  | Val.Int n -> n
  | _ -> failwith "Non-numeric value passed to numeric op !="
  in
  let rec h = function
  | [] | [_] -> Val.Bool true
  | x::y::ys -> if x != y then h @@ y::ys else Val.Bool false
  in
  let f xs = match List.sort compare @@ List.map g xs with
  | [] -> failwith "NumBool op != applied to empty list"
  | [_] -> failwith "NumBool op != applied to one arg"
  | ys -> h ys
  in
  Val.Op ("!=", f)


let builtins =
[ ...
; "=", num_bool_op "=" (=)
; "!=", not_equal_op
; ">", num_bool_op ">" (>)
; ">=", num_bool_op ">=" (>=)
; "<", num_bool_op "<" (<)
; "<=", num_bool_op "<=" (<=)
...
]

整数のリストを引数に取って真偽値を返す組み込み関数を作るためのヘルパ関数num_bool_opを定義し、それを使って=, >, >=, <, <=を定義している。これらは引数の左端からペアごとに比較していけば全体の結果が出るため。

num_bool_opの内容としては：

• 引数がVal.Intであることを確認しつつOCamlの整数に変換するg関数（Val.Intでないものが含まれている場合はエラー）を定義
• 左端からペアごとにop比較演算子を適用していくh関数を定義
• まず引数であるリストにmap gしてから、要素数が２以上であることを確認してhを適用するf関数を定義
• fをラップしたVal.Opを返す

となっている。今見直すと、hの引数にopいらないな・・・

ポイントの一つとしては、引数がVal.Intじゃなかった場合エラーを返すところ。Lispや他の動的言語だとこういう場合は型変換が起きることもある（例えば偽は0、それ以外は1に変換されるなど）がもしかしたら後々この言語に静的型付けを追加したくなるかもしれないので制約を厳しめにしておく。

!=だけは特別で、専用のnot_equal_opを定義している。何故なら(!= 0 1 0)のような式もfalseになってほしいのでそのままでは「左端からペアごとに比較」が使えない。no_equal_op内では、効率が悪くなるがまずはソートしている。

最後にand、or、not：

let bool_bool_op s op =
  let g = function
  | Val.Bool b -> b
  | _ -> failwith @@ "Non-boolean value passed to bool op " ^ s
  in
  let f xs = Val.Bool (List.fold_left (fun x y -> op x @@ g y) true xs) in
  Val.Op (s, f)

let not_op = function
  | [Val.Bool b] -> Val.Bool (not b)
  | [_] -> failwith "Non-boolean value passed to bool uniop not_op"
  | _ -> failwith "Bool uniop not_op applied to more than one arg"

let builtins =
[ ...
; "and", bool_bool_op "and" (&&)
; "or", bool_bool_op "or" (||)
; "not", Val.Op("not_op", not_op)
]

andやorはVal.Boolのリストをとり、Val.Boolを一つ返す。（andの時にfalseが見つかった時点でその後の評価をやめるようなロジックを実装していないので非効率だが）notもVal.Boolのリストをとり、そのリストの要素数が１ならVal.Boolを、１以外ならエラーを返す。

これで真偽値（と真偽値を返す演算）が言語に追加できた。

今度はこれを有効活用するためにifを追加する。

Expモジュールにif式を追加：

type t =
...
| If of t * t * t

let rec to_string = function
...
| If (e1, e2, e3) ->
    let s1 = (to_string e1) in
    let s2 = (to_string e2) in
    let s3 = (to_string e3) in
    Printf.sprintf "(if %s %s %s)" s1 s2 s3

パーサも拡張：

...
%token IF
...

%start <Exp.t> f

%%

f : e = expr; EOF { e }

expr :
...
| LPAREN; IF; e1 = expr; e2 = expr; e3 = expr; RPAREN { Exp.If (e1, e2, e3) }

if式は「真偽を確かめる式」と「真だった場合に評価する式」と「偽だった場合に評価する式」の三つの式を保持する。

「真偽を確かめる式」を評価してから次の式を選んで評価するので、継続が必要になる。

Contモジュール：

type cont =
...
| If of Exp.t * Exp.t

このCont.If継続に「真だった場合に評価する式」と「偽だった場合に評価する式」を保存しておく。

最後にExecuteモジュール：

let eval env cont = function
...
| Exp.If(e1, e2, e3) -> Eval(env, Cont.If(e2, e3) :: cont, e1)

let apply_cont env cont v = match cont with
...
| Cont.If(e2, e3) :: cont' -> (match v with
  | Val.Bool b -> Eval(env, cont', if b then e2 else e3)
  | _ -> failwith "Non-boolean in condition position of If expression")

evalにExp.Ifのケースを追加、apply_contにCont.Ifのケースを追加している。apply_contの部分で最初に評価した式がVal.Boolではなかった場合、やはり厳しめにエラーにしている。

これで真偽値、比較、分岐が実装できた。

次回はletで変数を定義できるようにする。

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その3 トランポリン化

前回継続渡しスタイルで末尾再帰化したインタプリタにさらに手を加えてトランポリン化する話。

一般的に、トランポリン化は「末尾再帰のない言語でスタックオーバーフローを起こさずに深い再帰をシミュレートする」手法だと言える。再帰的な関数呼び出しを遅延的に捉えたthunkを返すようにし、whileループで返ってきた値がthunkなら実行し続け、thunkでないものが返ってきた時点で終了、という流れでスタックを消費せずに再帰的なプログラムが書ける。

しかしOCamlにはそもそも末尾再帰がある。スタックオーバーフローを起こしたくないからといってトランポリン化する必要はない。

なら何故トランポリン化するのかというと、evalとapply_contを使うたびに計算の途中経過を返すようにしておきたいからだ。

それもあって、今回もdefunctionalizationのお世話になる。具体的には相互再帰的関数呼び出しを無名関数として返すのではなく、代数的データ型で引数も含めて返すようにする。

前回とのコード差分：

Comparing v0.2...v0.3 · zehnpaard/kontlang · GitHub

変更したのはExecute.mlモジュールのみ。

まずはeval、apply_contが返すthunkを表すデータ型：

type t =
| Done of Val.t
| Eval of Env.t * Cont.t * Exp.t
| ApplyCont of Env.t * Cont.t * Val.t

次に呼び出す関数がない場合はDoneで値、ある場合はEval、ApplyContと必要な引数が返されるようにする。

eval関数：

let eval env cont = function
| Exp.Int n -> ApplyCont (env, cont, Val.Int n)
| Exp.Var s -> ApplyCont (env, cont, Env.find s env)
| Exp.Call (e, es) -> Eval (env, (Cont.Call (es, []) :: cont), e)

前回のようにapply_contやevalを相互再帰的に呼び出すかわりにExecute.t型を返す。

apply_contも似たような形に：

let apply_cont env cont v = match cont with
| [] -> Done v
| Cont.Call ([], vs) :: cont' -> (match List.rev (v::vs) with
  | Val.Op (_, fn) :: vs' -> ApplyCont (env, cont', (fn vs'))
  | _ -> failwith "Calling non-op in operator position")
| Cont.Call (e::es, vs) :: cont' -> Eval (env, (Cont.Call (es, v::vs) :: cont'), e)

継続が終端な場合はDoneを返す。

ループのためのtrampolineとそれを使ったrun関数：

let rec trampoline = function
| Done v -> v
| Eval (env, cont, e) -> trampoline @@ eval env cont e
| ApplyCont (env, cont, v) -> trampoline @@ apply_cont env cont v

let run e = trampoline (Eval (Builtins.load Env.empty, Cont.final, e))

trampolineの実装に末尾再帰を使っているが、そもそも末尾再帰のシミュレートが目的ではないので問題なし。また普通のトランポリン化だとeval、apply_contはthunkとして匿名関数を返し、trampolineではその匿名関数を呼び出すことが多いが、Done | Eval | ApplyContのコンストラクタを持つデータ型で表現している（前述のとおりdefunctionalizationという手法）。

今回は実装していないが、trampolineに手を加えると「実行ステップを一つずつ進めて、途中での継続や変数環境の状態を調べられる」インタプリタが書けたりする。今後インタプリタが複雑化してきたときにはデバッグ用にそんなモードを用意する予定。

例えばこんな変更が可能：

let inspect = function
| Done v -> ()
| Eval (env, cont, e) ->
    print_endline @@ Env.to_string env;
    print_endline @@ Cont.to_string cont;
    print_endline @@ Exp.to_string e;
    ignore @@ read_line ()
| ApplyCont (env, cont, v) ->
    print_endline @@ Env.to_string env;
    print_endline @@ Cont.to_string cont;
    print_endline @@ Val.to_string v;
    ignore @@ read_line ()

let rec trampoline_inspect = function
| Done v -> v
| Eval (env, cont, e) as x ->
    inspect x;
    trampoline_inspect @@ eval env cont e
| ApplyCont (env, cont, v) as x ->
    inspect x;
    trampoline_inspect @@ apply_cont env cont v

こうするとtrampoline_inspectが呼び出されるたびに現在のプログラムの状態が出力され、ユーザから何らかの入力を受けとってから次のステップを実行する。デバッグモードとしてなかなか有用（Env.to_stringやCont.to_stringを実装していないので現段階では動かないが・・・）

最後にeval_string：

let eval_string s =
  Lexing.from_string s
  |> Parser.f Lexer.f
  |> run
  |> Val.to_string

evalのかわりにrunを使うようになっただけ。これでインタプリタのトランポリン化が完了。

前回、今回と続いて、言語機能は加えずにインタプリタの実装を変更してきた。次回は真偽値、論理式、ifなどの機能を言語に追加する。

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その２ 継続渡しスタイル

前回に続いて、機能としては整数と四則演算だけのインタプリタの話。

今回は機能はそのままで、式を評価して値を返すeval関数を継続渡しスタイルに変換する。

そもそも継続渡しスタイルだと何が嬉しいのか。

インタプリタの実行手順を考えると、関数呼び出しを評価する時：

let rec eval env = function
...
| Exp.Call (e, es) -> (match eval env e with
  | Val.Op (_, fn) -> fn @@ List.map (eval env) es

オペレータやオペランドがeval env ...で評価された後に何を実行するか（次はオペランドを一つ評価するのか、あるいはすべてのオペランドが評価し終わってオペレータを適用する段階なのか）は、インタプリタのスタックを巻き戻してeval呼び出し元のコンテキストに戻ってみないとわからない。

ここで二つの問題が生じている。一つはコンテキストを保持するためにスタックが消費されていること。もう一つはコンテキストの情報が「ホスト言語のスタック」に保持されているせいでインタプリタが自在にコンテキストを扱えないこと。

最初の問題はスタックオーバーフローを起こす要因となる。この情報をデータ化してしまえば、スタックをどんどん追加しない末尾再帰の形に持っていける。

二番目の問題に関しては、この「コンテキストの情報」をインタプリタが扱えるようにしないと、「コンテキストの破棄」である例外や「複数コンテキストを交互に実行」という並行処理などの言語機能が実装しにくい。

継続を取り出してデータ化し、インタプリタ自体は必ず末尾再帰するように変更することで、このコンテキストをいろいろといじれるようになる。その最たる例が「言語機能として継続を扱えるようにする」ことで、ユーザ側で例外や並行処理を実装できるようになる。

OCamlでは関数は第１級の存在なので、継続も無名関数として表現してもいいのだが、限定継続として中身をいじったりしたいのと、計算の途中で継続を文字列として出力したりしたくなるので、代数的データ型として定義しておく。ちなみにこういう「高階関数を代数的データ型として表す」手法をdefunctionalizationというらしい。

前回とのコード差分：

Comparing v0.1...v0.2 · zehnpaard/kontlang · GitHub

ポイントとしては、まず継続をCont.mlでデータ型として定義：

type cont =
| Call of Exp.t list * Val.t list

type t = cont list

let final = []

現在の非常に簡単な言語だと継続が必要になるのは関数呼び出しの時だけ。「まだ評価していない式」のリストと「評価済みの値」のリストを持つCont.Callが唯一のコンストラクタであるCont.contが定義されている。

実際の継続を表すCont.t型はCont.cont list。空のリストが継続の終端で、式を評価して値が出た時点で継続が空リストならプログラムは終了。

この継続を踏まえてExecute.mlも変更：

let rec eval env cont = function
| Exp.Int n -> apply_cont env cont @@ Val.Int n
| Exp.Var s -> apply_cont env cont @@ Env.find s env
| Exp.Call (e, es) -> eval env (Cont.Call (es, []) :: cont) e
and apply_cont env cont v = match cont with
| [] -> v
| Cont.Call ([], vs) :: cont' -> (match List.rev (v::vs) with
  | Val.Op (_, fn) :: vs' -> apply_cont env cont' (fn vs')
  | _ -> failwith "Calling non-op in operator position")
| Cont.Call (e::es, vs) :: cont' -> eval env (Cont.Call (es, v::vs) :: cont') e

前回はevalだけだったが、今回はevalとapply_contの相互再帰になっている。

Exp.IntとExp.Varは式評価時に継続は追加されず、値をそのまま今までの継続に渡す形でapply_contが呼ばれる。Exp.Callの時だけ、まずオペランドのリストを持ったCont.Callが継続に追加された上でオペレータだけがevalを再帰呼び出しすることで評価される。

apply_contでは継続の終端である空リストかCont.Callが先頭にあるか、Cont.Callがある場合、未評価の式が残っているか、で場合分けしている：

• 終端である場合はそのまま値を（プログラム全体の結果として）返す
• 未評価の式が残っていないCont.Callの場合、まず評価済み値のリストをリバースさせ、そのリストの先頭がVal.Opであればそのまま関数適用、Val.Opでなければエラー
• Cont.Callで未評価の式が残っている場合、apply_contの引数である値を「評価済み値」のリストに追加（ここで元の式の順と逆になってしまうことに注意）した新しいCont.Callを作り、次の未評価の式をその継続でevalする

これでプログラムのコンテキストをデータ化できた。すべての再帰・相互再帰呼び出しが末尾再帰になっていて、evalに渡される式と変数環境と継続あるいはapply_contに渡される値と変数環境と継続でプログラム実行のコンテキストがすべて保持できている。

次回は相互再帰をトランポリン化して、実行途中のプログラムの状態がデータとしてevalやapply_contから返されるようにする。

めざそう言語処理系の沼 〜shift/resetへの旅 〜 その１ 四則演算

shift/resetという限定継続を扱うための機構を備えた言語のインタプリタをOCamlで段階的に作っていく。長めのシリーズになりそう。

今回は整数と関連する演算が評価できるインタプリタを作成するまで。EoPLの最初の言語であるLETの二歩くらい手前。

例えば：

(+ (* 1 2 3) 4 (- 5 6 7))
=> (+ 6 4 -8)
=>  2

コードは以下の通り：

GitHub - zehnpaard/kontlang at v0.1

構成：

.
├── README.md
├── dune
├── dune-project
├── main.ml
├── src
│   ├── builtins.ml
│   ├── dune
│   ├── env.ml
│   ├── execute.ml
│   ├── exp.ml
│   ├── lexer.mll
│   ├── parser.mly
│   └── val.ml
└── test
    ├── dune
    └── test_nums.ml

心臓部分と言えるのはexecute.mlの中のこの部分：

let eval_string s =
  Lexing.from_string s
  |> Parser.f Lexer.f
  |> eval (Builtins.load Env.empty)
  |> Val.to_string

流れとしては

• 文字列をLexing.lexbuf型に変換し
• ocamllex/menhirのパーサに渡し
• 返ってきた式（Exp.t型）をビルトイン変数だけ追加した変数環境を使って評価し
• その結果であるVal.t型の値を文字列に変換して返す

というものになる。他の記事でも使っているいつものインタプリタ構成である。ついでに言うとS式なのでlexerやparser部分の説明は今回は割愛。

インタプリタの機能が非常に限られているので式や値は非常に簡単なもの。

式を表すExpモジュール：

type t =
| Int of int
| Var of string
| Call of t * t list

let rec to_string = function
| Int n -> string_of_int n
| Var s -> s
| Call (e, []) -> Printf.sprintf "(%s)" @@ to_string e 
| Call (e, es) ->
    let fn = to_string e in
    let args = List.map to_string es |> String.concat " " in
    Printf.sprintf "(%s %s)" fn args

整数、変数、関数適用のみ。（ちなみに言語内でありえる変数・関数はビルトインのみで、変数を追加したり関数を定義したりはできない）

値を表すValモジュール：

type t =
| Int of int
| Op of string * (t list -> t)

let to_string = function
| Int n -> string_of_int n
| Op (s, _) -> Printf.sprintf "Op(%s)" s

整数と演算子しか存在しない。

変数環境は素直にリストを使うだけ、なEnvモジュール：

type t = (string * Val.t) list

let empty = []

let extend var val_ env = (var, val_)::env
let extend_list vvs env = vvs @ env

let rec find var = function
| [] -> failwith @@ Printf.sprintf "Variable %s not found" var
| (var', val')::env' ->
    if var = var' then val'
    else find var env'

いわゆるassociation listで、変数を評価するときにO(定義されている変数の総数)かかるので効率としてはかなり悪い。が、楽なのでとりあえず・・・

変数環境の初期状態として追加されるBuiltinsモジュール：

let num_num_op s op =
  let g = function
  | Val.Int n -> n
  | _ -> failwith @@ "Non-numeric value passed to numeric op " ^ s
  in
  let f xs = match List.map g xs with
  | [] -> failwith @@ Printf.sprintf "Numeric op %s applied to empty list" s
  | y::ys -> Val.Int (List.fold_left op y ys)
  in
  Val.Op (s, f)

let builtins =
[ "+", num_num_op "+" (+)
; "-", num_num_op "-" (-)
; "*", num_num_op "*" ( * )
; "/", num_num_op "/" (/)
]

let load env = Env.extend_list builtins env

「引数としてVal.Intのリストを受けとり、fold_leftで畳み込んでVal.Intを返すVal.Op」を定義するためのヘルパー関数num_num_opを使って四則演算を実装している。

Executeモジュール内で定義されている、Exp.tをVal.tに変換するためのeval関数：

let rec eval env = function
| Exp.Int n -> Val.Int n
| Exp.Var s -> Env.find s env
| Exp.Call (e, es) -> (match eval env e with
  | Val.Op (_, fn) -> fn @@ List.map (eval env) es
  | v ->
      let s = Val.to_string v in
      failwith @@ Printf.sprintf "Non-function %s in operator position" s)

• 整数を表す式はそのまま整数を表す値に
• 変数を表す式は変数環境でその変数に対応する値に
• 関数適用の式はまず関数部分を評価し、その後引数をすべて評価してから関数適用した結果の値に（関数部分が関数でなかった場合はエラー）

となる。継続渡しなども使わない、非常に簡単な再帰スタイルの式評価である。（関数適用の部分が末尾再帰になっていない）

次回は言語機能はこのままで、式評価を継続渡しスタイルに変換する。