というわけでCont.tとVal.tを相互再帰的にするために、新しくValcontモジュールを作成して両者をここで定義する。さらにValcont内で別々のValとContモジュールを定義して、Val.ml内ではinclude Valcont.Val、Kont.mlではinclude Valcont.Contとしている。これで他のモジュールからは今までどおりValとContが使える。

本当はValcontモジュールがValとContモジュール以外からは隠蔽したくなるのだが、調べてみたところ難しいようだ。

今になって思えばこの変更はCont.tの文字列化にあまり影響しないので、この段階でやる必要はなかった・・・

継続を`list list`に

限定継続を実装する下準備その２。

限定継続を扱えるようにする言語機能のshift/resetでは、reset式の中に入った部分式は継続がreset外とは区切られていて、その中でshiftが呼ばれるとその区切りのところまでの継続が捕捉されて値に変換される。

これまで継続はフラットな一つのリストとして実装してきた。ここに例えばCont.Resetを導入して「現在の限定継続は直近のCont.Resetまで」と定義してもいいのだが、別解として

継続はCont.cont list list型
resetに入ったら継続に空リストを追加
他の式の継続はこの先頭のリストに追加していく
shiftはこの先頭をリストをとってくるだけ

という実装を思いついたので試してみたい。

これはCont.tの内部実装を大きく変えるところなので、Cont.to_stringを実装する前にやっておきたかった。

Cont.t型の変更：

type t = cont list      

let final = []

だったものが

type t = cont list list

let final = [[]]

こうなる。単なるリストに比べて追加がめんどくさくなるので専用のCont.add関数を用意：

let add c = function
| cont'::cont'' -> (c::cont')::cont''
| [] -> [[c]]

こういった変更に合わせてExecuteモジュールも変えていく。

let eval env cont = function
...
| Exp.Call(e, es) -> Eval(env, Cont.Call(es, []) :: cont, e)

が

let eval env cont = function
...
| Exp.Call(e, es) ->
  let cont' = Cont.add (Cont.Call(es, [])) cont in

になったり

let apply_cont env cont v = match cont with
...
| Cont.Call(e::es, vs) :: cont' -> Eval(env, Cont.Call(es, v::vs) :: cont', e)

が

let apply_cont env cont v = match cont with
...
| (Cont.Call(e::es, vs) :: cont')::cont'' ->
    let cont''' = Cont.add (Cont.Call(es, v::vs)) (cont'::cont'') in
    Eval(env, cont''', e)

になったりする。リストがネストしたぶん少し冗長になっている。

さらに

let apply_cont env cont v = match cont with
...
| []::cont'' -> ApplyCont(env, cont'', v)

というケースが追加されている。これは「resetの中の式を評価し終わったので、その限定継続から抜ける」ことを表している。

ただしまだshift/resetが実装されていないので、継続に二つ以上のリストが含まれることはないのだが・・・

継続と変数環境を文字列化できるようにする

ステップ実行で評価途中のインタプリタの状態を表示するには、式や値だけではなく継続と変数環境も出力する必要がある。なのでCont.to_stringやEnv.to_stringを追加する。

地味なのでコードは割愛。

ステップ実行インタプリタ

これでステップ実行時に必要な情報を文字列化できるようになった。

あとはExecuteモジュールにtrampolineにちょっと手を加えたtrampoline'を作る。具体的にはevalやapply_contが返すExecute.res型を出力して一時停止するdisplay関数を定義して：

let display = function
| Done v ->
  print_endline "Done";
  print_endline (Val.to_string v);
  ignore @@ read_line ()
| Eval(env, cont, e) ->
  print_endline @@ "Evaluating expression " ^ Exp.to_string e;
  print_endline @@ "Cont Head:\t" ^ Cont.to_string_hd cont;
  print_endline  @@ "Cont Full:\t" ^ Cont.to_string cont;
  print_endline  @@ "Environment:\t" ^ Env.to_string env;
  ignore @@ read_line ()
| ApplyCont(env, cont, v) ->
  print_endline  @@ "Applying continuation on value " ^ Val.to_string v;
  print_endline @@ "Cont Head:\t" ^ Cont.to_string_hd cont;
  print_endline  @@ "Cont Full:\t" ^ Cont.to_string cont;
  print_endline  @@ "Environment:\t" ^ Env.to_string env;
  ignore @@ read_line ()

trampoline'で次のステップに移る前にdisplayを呼び出す：

let rec trampoline' res = match res with
| Done v -> display res; v
| Eval(env, cont, e) -> display res; trampoline' @@ eval env cont e
| ApplyCont(env, cont, v) -> display res; trampoline' @@ apply_cont env cont v

trampoline'を使ったrun'やeval_string'も定義して、最後にstepwise.mlを作成：

open Kontlang

let rec read_eval_print exp_string =
  let s = read_line () in
  if s = "" then Execute.eval_string' exp_string |> print_endline
  else read_eval_print (Printf.sprintf "%s\n%s" exp_string s)

let () = (print_string ">>> "; read_eval_print "")

これで実装完了。

使い方

dune exec ./stepwise.exe

で実行できる。（duneはOCamlのビルドツールで、上記のコマンドはduneにstepwise.exeをコンパイルして実行するよう指示している）

実行して(let [x 3] (+ (* 1 2) x))を評価させてみる：

kontlang$ dune exec ./stepwise.exe
>>> (let [x 3] (+ (* 1 2) x))

Evaluating expression (let [(x 3)] (+ (* 1 2) x))
Cont Head:
Cont Full:
Environment:

Evaluating expression 3
Cont Head:  LET x [] [] (+ (* 1 2) x)
Cont Full:  LET
Environment:

Applying continuation on value 3
Cont Head:  LET x [] [] (+ (* 1 2) x)
Cont Full:  LET
Environment:

Evaluating expression (+ (* 1 2) x)
Cont Head:  ENV
Cont Full:  ENV
Environment:    [{x 3}]

Evaluating expression +
Cont Head:  CALL [(* 1 2) x] []
Cont Full:  CALL ENV
Environment:    [{x 3}]

Applying continuation on value Op(+)
Cont Head:  CALL [(* 1 2) x] []
Cont Full:  CALL ENV
Environment:    [{x 3}]

Evaluating expression (* 1 2)
Cont Head:  CALL [x] [Op(+)]
Cont Full:  CALL ENV
Environment:    [{x 3}]

Evaluating expression *
Cont Head:  CALL [1 2] []
Cont Full:  CALL CALL ENV
Environment:    [{x 3}]

Applying continuation on value Op(*)
Cont Head:  CALL [1 2] []
Cont Full:  CALL CALL ENV
Environment:    [{x 3}]

Evaluating expression 1
Cont Head:  CALL [2] [Op(*)]
Cont Full:  CALL CALL ENV
Environment:    [{x 3}]

Applying continuation on value 1
Cont Head:  CALL [2] [Op(*)]
Cont Full:  CALL CALL ENV
Environment:    [{x 3}]

Evaluating expression 2
Cont Head:  CALL [] [1 Op(*)]
Cont Full:  CALL CALL ENV
Environment:    [{x 3}]

Applying continuation on value 2
Cont Head:  CALL [] [1 Op(*)]
Cont Full:  CALL CALL ENV
Environment:    [{x 3}]

Applying continuation on value 2
Cont Head:  CALL [x] [Op(+)]
Cont Full:  CALL ENV
Environment:    [{x 3}]

Evaluating expression x
Cont Head:  CALL [] [2 Op(+)]
Cont Full:  CALL ENV
Environment:    [{x 3}]

Applying continuation on value 3
Cont Head:  CALL [] [2 Op(+)]
Cont Full:  CALL ENV
Environment:    [{x 3}]

Applying continuation on value 5
Cont Head:  ENV
Cont Full:  ENV
Environment:    [{x 3}]

Applying continuation on value 5
Cont Head:
Cont Full:
Environment:

Applying continuation on value 5
Cont Head:
Cont Full:
Environment:

Done
5

5

「Cont Full」では継続すべてを（個々の部分は簡略した形で）表示し、「Cont Head」ではその一番先頭（左側）の詳細を表示している。

パッと見で直感的とは言えないが、慣れてくるとインタプリタの状態がかなりわかるようになる。例えば

Evaluating expression 1
Cont Head:  CALL [2] [Op(*)]
Cont Full:  CALL CALL ENV
Environment:    [{x 3}]

であれば

次のステップは1という式を評価すること
現在関数呼び出し二つの内側にいる
直近の関数呼び出しでは、すでに関数に当たる部分が評価されていてその値は*である
まだ未評価の引数があってその式は2である（整数式も整数値も同じように表示されてしまうのがややこしい・・・）
現在の変数環境にはxという変数に3という値が束縛されている

ということを表している。

限定継続のような複雑な機能を実装・デバッグする上でこういう情報は非常に役に立つ。

次回

次回はこのステップ実行インタプリタを使って末尾再帰の挙動をチェック、末尾呼び出し最適化を実装する。

2020-05-31

めざそう言語処理系の沼　〜shift/resetへの旅〜　その１３マクロ

OCaml めざそう言語処理系の沼言語処理系

簡単なマクロ機構を実装していく。

背景

shift/resetが実装されたらやってみたいことの一つが@dico_lequeさんの発表「モナドをつくろう」をいろいろ試してみること。

モナドをつくろう from dico_leque

www.slideshare.net

スライド１９に出てくるreifyがマクロなので、それを再現できるようにしたい。

(define-syntax reify
  (syntax-rules ()
    ((_ expr)
     (reset (let ((v expr))
              (some v)))))

Schemeのマクロは強力でいろんな機構があるが、このマクロ自体は比較的簡単。

(reify expr)

を

(reset (let ((v expr))
         (some v))

に置換する、というもの。何故これがマクロなのかというと、ただの関数だと関数適用の前に引数が評価されるので、exprの中でshiftがあった場合reify内で使われているresetに捕捉されない問題が生じるため。

このreifyが再現できる最低限のマクロ機構と考えると

マクロ本体の中に出てくる仮引数と一致する変数を、実引数に当たる式と置換する
引数の式はマクロ適用時は評価せず、式のままマクロ本体に代入される
マクロはクロージャを持たず、マクロ定義時ではなく呼び出し時の変数環境を使って変数解決するダイナミックスコープ

という形で実装してみる。

ちなみに何故マクロだけダイナミックスコープにしているかというと、レキシカルスコープにするとマクロの引数となる式がマクロ定義時の変数環境で評価されることになってしまうからで、それを避けるような機能を実装するのも可能だが関数のレキシカルスコープに比べてかなり大変になる、というのが理由。

（ちなみに後々reifyを書いてみるときは、someは(fn [x] (cons "Some" x))で代用するつもり。代数的データ型がないので・・・）

使い方

fnと同じように、macroというキーワードで無名マクロを作成できるようにする。そのまま使うも変数に束縛して使うも自由：

  ((macro [x y] (do [y x]))
     (println "hello")
     (println "goodbye")))

(let [m (macro [x y] (do [y x]))]
  (m (println "hello")
     (println "goodbye")))

普通の引数と違ってマクロ適用の時点では引数が評価されないので、上記の例は二つとも"hello"の前に"goodbye"が出力される。

コード解説

前回とのコード差分：

Comparing v0.12...v0.13 · zehnpaard/kontlang · GitHub

Exp.tにMacroコンストラクタを追加（比較のためにFnも載せている）：

type t =
| Fn of string list * t
| Macro of string list * t

Val.tにも同様:

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

Exp.MacroとVal.Macroがまったく同一なのがわかるかと思う。仮引数のリストと本体の式だけ。Fnの場合、Val.FnはExp.Fnの内容に加えてクロージャに当たる(string * t) list refが追加されているが、Macroの場合はダイナミックスコープにしてあるのでクロージャはなし。

次にマクロの根本である「部分式の置換」を行う関数substituteを持つ新しいMacroモジュールを定義：

let substitute e ss es =
  let env = List.combine ss es in
  let rec f = function
  | Exp.Int _ as x -> x
  | Exp.Str _ as x -> x
  | Exp.Macro(ss, e) -> Exp.Macro(ss, f e)
  | Exp.Var s as e -> (match List.assoc_opt s env with
    | Some e' -> e'
    | None -> e)
  | Exp.Call(e, es) -> Exp.Call(f e, List.map f es)
  | Exp.If(e1, e2, e3) -> Exp.If(f e1, f e2, f e3)
  | Exp.Cond(ees) ->
      Exp.Cond(List.map (fun (e1, e2) -> (f e1, f e2)) ees)
  | Exp.Let(ves, e2) ->
      Exp.Let(List.map (fun (v, e) -> (v, f e)) ves, f e2)
  | Exp.Lets(ves, e2) ->
      Exp.Lets(List.map (fun (v, e) -> (v, f e)) ves, f e2)
  | Exp.Fn(params, body) -> Exp.Fn(params, f body)
  | Exp.LetFn(fns, e) ->
      Exp.LetFn(List.map (fun (v, ps, e) -> (v, ps, f e)) fns, f e)
  | Exp.LetRec(fns, e) ->
      Exp.LetRec(List.map (fun (v, ps, e) -> (v, ps, f e)) fns, f e)
  | Exp.Do es -> Exp.Do (List.map f es)
in
f e

substitute関数内で（変数*式）リストのenvとそれを使って再帰的に部分式を置換していくf関数が定義されている。

マクロ変数環境であるenvはExecute.evalで使われているEnv.tとは型からして違うことに注意（Env.tは(string * Val.t) list list）。

fの実引数が変数Exp.Varだった場合、マクロ変数環境を調べて式が束縛されていれば完全に置換、そうでないなら変数のまま残す。

fの実引数がそれ以外の式だった場合、その式の部分式にfを再帰的に適用する。

これらを使う形でExecuteモジュールを変更する。まずはExecute.eval：

let eval env cont = function
...
  | Exp.Macro(ss, e) -> ApplyCont(env, cont, Val.Macro(ss, e))

Exp.Macro式はそのままVal.Macro値に変換してから残りの継続に渡す。

Execute.apply_cont：

let apply_cont env cont v = match cont with
...
| Cont.Call(e::es as es', []) :: cont' -> (match v with
  | Val.Macro (ss, me) ->
      let paramcount = List.length ss in
      let argcount = List.length es' in
      if paramcount = argcount then
        Eval(env, cont', Macro.substitute me ss es')
      else failwith @@ Printf.sprintf "Macro called with incorrect number of args: expected %d received %d" paramcount argcount
  | _ -> Eval(env, Cont.Call(es, [v]) :: cont', e))

マクロの実行も関数と同じくCont.Call継続を使う。ただし、「引数の式が一つも評価されていない状態のCont.Call」ケースを場合分けに追加していて、ここでオペレータ部分がVal.Macroならマクロ呼び出し。別の値なら今までどおり引数の評価に移行する。

マクロ呼び出しでは：

仮引数と実引数の数が一致することを確認
それらとMacro.substituteを使ってマクロ本体の式を置換
その置換された式をCont.Callを外した残りの継続で評価

という流れとなる。

これでマクロも実装できた。

次回

次回は評価ステップごとにインタプリタの状態が見えるようにする。

2020-05-31

めざそう言語処理系の沼　〜shift/resetへの旅〜　その１２文字列、入出力とDo

OCaml めざそう言語処理系の沼言語処理系

今まで作ってきた言語には副作用がなかったが、やはり入出力くらいはほしいよね、というわけで

式と値に文字列を追加
標準入出力からの読み取り・書き込みのための組み込み関数
副作用のある処理を順次実行して、最後の式の値をとるDo式

を言語に追加する。

前回からの差分：

Comparing v0.11...v0.12 · zehnpaard/kontlang · GitHub

式と値に文字列を追加

式のExp.tに追加：

type t =
...
| Str of string

値のVal.tにも追加：

type t =
...
| Str of string

式を評価して値にするExecute.eval：

let eval env cont = function
...
| Exp.Str s -> ApplyCont(env, cont, Val.Str s)

これだけ。

標準入出力

組み込み関数にいくつか追加していく。

まず複数の文字列を結合するconcat:

let concat_op ss =
  let f = function
  | Val.Str s -> s
  | _ -> failwith "Non-string passed to concat"
  in
  Val.Str (String.concat "" @@ List.map f ss)

文字列を標準出力するprintと出力の最後に改行を入れるprintln：

let print_op = function
  | [Val.Str s] -> print_string s; Val.Nil
  | _ -> failwith "Non-string passed to print"

let println_op = function
  | [Val.Str s] -> print_endline s; Val.Nil
  | _ -> failwith "Non-string passed to println"

これらは文字列を引数にとり、Val.Nilを返す。

標準入力から文字列を取ってくるread：

let read_op = function
  | [] -> Val.Str (read_line ())
  | _ -> failwith "Args passed to read"

これらはすべてOCamlの関数をラップしているだけなので楽。

あとは変数環境に入るようbuiltinsに名前と一緒に入れるだけ：

let builtins =
[
...
; "concat", Val.Op("concat", concat_op)
; "print", Val.Op("print", print_op)
; "println", Val.Op("println", println_op)
; "read", Val.Op("read", read_op)
]

`Do`式

副作用のある処理を記述できるようになったので、そういった処理を順次行うための構文がほしくなる。

というわけでこんなDo式を導入する：

(do [(println "hello")
     (print "please enter your name: ")
     ( read)])

最後の式の値がDo式全体の値となるので、上記のコードの場合、readで受け取った入力の文字列が結果となる。

Exp.tに追加：

type t =
...
| Do of t list

Contにも追加：

type cont =
...
| Do of Exp.t list

Exp.DoもCont.DoもExp.t listを持っている。

ただしこのデータの持つ意味が少し違って、Exp.DoのExp.t listはDo式の持つすべての部分式なのに対してCont.Doの場合は「まだ未評価の式」を保持する形となる。

Execute.eval：

let eval env cont = function
...
  | Exp.Do(e::es) -> Eval(env, Cont.Do es::cont, e)
  | Exp.Do([]) -> failwith "Evaluating empty do"

Exp.Doを評価するのには、Exp.t listのtailを持つCont.Doを継続に追加して、Exp.t listのheadを評価する。

Execute.apply_cont：

let apply_cont env cont v = match cont with
...
| Cont.Do(e::es)::cont' -> Eval(env, Cont.Do es::cont', e)
| Cont.Do([])::cont' -> ApplyCont(env, cont', v)

値をCont.Doが先頭にくる継続に適用するのに、Cont.Doの持つExp.t listが空リストかどうかで場合分けする。

空リストではない場合、apply_contの引数である値は無視して、Exp.t listのtailを持つCont.Doを継続に追加して、Exp.t listのheadを評価する。

空リストの場合、apply_contの引数である値をそのまま残りの継続に適用する。

これでDoも実装完了。

次回

次回は簡単なマクロ機能を実装する。

2020-05-30

めざそう言語処理系の沼　〜shift/resetへの旅〜　その１１ Cond＆リファクタリング

OCaml めざそう言語処理系の沼言語処理系

今回の変更は三点：

condによる条件分岐
Val.FnとVal.RecFnを統一
式の中の自由変数を検出するget_freeをリファクタ

前回とのコード差分：

Comparing v0.10...v0.11 · zehnpaard/kontlang · GitHub

`cond`による条件分岐

すでにifによる条件分岐は実装してあるが

if ... then ... 
else if ... then ... 
else ...

上記のような複数の条件を順次調べて分岐するようなロジックは

(if ...
  ...
  (if ...
    ...
    ...))

のような形になり、ネストがどんどん深くなっていってしまう。このように書けるようにしたい：

(cond
  [... ...]
  [... ...]
  [true ...])

（trueはelseと同じ意味になる）

まずExpモジュールにExp.Contを追加：

type t =
...
| Cond of (t * t) list

条件式と、その条件が真だった場合の結果となる式のタプルのリスト。

ある条件式を評価している間、「現在Condの一部を評価している」というコンテキストを保持する必要があるのでCont.tにもコンストラクタを追加：

type cont =
...
| Cond of Exp.t * (Exp.t * Exp.t) list

現在評価している条件式が真だった場合の結果となる式と、残りの条件式・結果式のタプルのリスト。以前評価した結果やそれに対応する式は必要ない（条件が一つ真だった時点でCont.Condは外した上で対応する結果式を評価するので）。

あとはExecuteモジュールでVal.CondやCont.Condのケースを追加：

let eval env cont = function
...
| Exp.Cond((e1,e2)::ees) -> Eval(env, Cont.Cond(e2, ees)::cont, e1)
| Exp.Cond _ -> failwith "Evaluating cond with no matching condition"

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

evalではVal.Condのデータの先頭からタプルを取り、継続にCont.Condを追加してからタプルの条件式の部分を評価。

apply_contでは、条件式の評価結果が真なら結果式を、そうでないなら残った（条件式*結果式）タプルのリストで新しくExp.Condを作成してそれを評価する。

もし何も該当する条件がなかった場合は実行時エラーになる。nilを返すようにしてもよかったのだが、この言語は他のところでも少し厳しめの実装になっているのでそっちに寄せた。

`Val.Fn`と`Val.RecFn`を統一

以前、再帰関数を定義できるようにした時にVal.t型に新しくRecFnコンストラクタを追加した。関数を作成した後に、クロージャにその関数（あるいは相互再帰関係にある他の関数）を追加できるように、クロージャを表す型を(string * Val.t) listから(string * Val.t) list refに変更したいためだ。

しかしこのRecFnの定義は普通のFnでも使いまわせる。そうするとVal.tに対するパターンマッチの場合分けを少し減らし、大部分同じで微妙に違うFnとRecFnに対する処理を統一できる。

最終的にはVal.Fnの定義はこうなる：

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

あとはExecuteモジュールでの場合分けで、今まであったVal.Fnの部分を削除してVal.RecFnというコンストラクタをVal.Fnに書き換えるだけ。（細かいので割愛）

`get_free`をリファクタ

ある式のなかに出てくる自由変数を検出するget_freeにいくつか不満があったので変更した。

修正点は以下のとおり：

戻り値である自由変数のリストをconcatしないようにする
変数環境Env.t型の引数を取らないようにする
get_free関数をExecuteからExpに移す

１の「戻り値である自由変数のリストをconcatしないようにする」に関しては、get_freeが再帰的に部分式に適用された結果を愚直にconcatで繋げていて効率が非常に悪い（そのconcat部分だけでO(n log n)）。それを避けるために「出てきた自由変数を追加するためのリスト」を引数に加える。部分式が複数ある場合、fold_leftなどを使ってこのリストを使い回す。これでそのO(n log n)部分をO(n)に下げられる。

２の「変数環境Env.t型の引数を取らないようにする」については、今まで式の中で出てきた変数が束縛されているかどうかを調べるのに、evalで使っているのと同じ変数環境の型Env.tを使っていた。なので例えば(let [x 5] (+ x x))という式の自由変数を調べる時に、(+ x x)のxが束縛されていることを表すために変数環境に("x", Val.Nil)のような変数とダミー値のタプルを入れていた。ダミー値が無駄だし、get_env関数が不必要にEnvモジュールに依存してしまう、ということで「現在束縛されている変数の集合」をExp.t型のenv引数ではなくただの文字列のリストであるbound引数で表すことにした。

３「get_free関数をExecuteからExpに移す」については、２でEnvへの依存がなくなったのでget_freeの残る依存性はExpに対するものだけ。さらに「式の自由変数を検出する」という関数の目的からも、Expモジュールに入っているのが一番自然なのでそのように変更。

最終的にExp.get_freeはこのようになった：

let rec get_free bound free = function
| Int _ -> free
| Var s -> if (List.mem s bound) then free else s::free
| Call(e, es) -> List.fold_left (get_free bound) free @@ e::es
| If(e1, e2, e3) -> List.fold_left (get_free bound) free [e1; e2; e3]
| Cond(ees) ->
    let f free (e1, e2) = get_free bound (get_free bound free e1) e2 in
    List.fold_left f free ees
| Let(ves, e2) ->
    let vs, es = List.split ves in
    let free' = List.fold_left (get_free bound) free es in
    get_free (vs @ bound) free' e2
| Lets((s, e1)::ves, e2) ->
    let free' = get_free bound free e1 in
    get_free (s::bound) free' @@ Lets(ves, e2)
| Lets ([], e2) -> get_free bound free e2
| Fn(params, body) -> get_free (params @ bound) free body
| LetFn(fns, e) ->
    let fnames, paramss, bodys = Utils.split3 fns in
    let f free params body = get_free (params @ bound) free body in
    let free' = List.fold_left2 f free paramss bodys in
    get_free (fnames @ bound) free' e
| LetRec(fns, e) ->
    let fnames, paramss, bodys = Utils.split3 fns in
    let f free params body = get_free (fnames @ params @ bound) free body in
    let free' = List.fold_left2 f free paramss bodys in
    get_free (fnames @ bound) free' e

Executeモジュールでの使い方は：

| Exp.Fn(params, body) as e ->
    let free = Utils.dedupe @@ Exp.get_free [] [] e in (* ここ *)
    let fvalsr = ref @@ List.map (fun v -> v, Env.find v env) free in
    ApplyCont(env, cont, Val.Fn("anon", params, fvalsr, body))

新しいget_freeの戻り値でも自由変数の重複はありえるのでUtils.dedupeを使う必要がある。まあdedupeもO(n)だしまあいいか、というところ。

次回

次回は文字列と入出力、そして複数の式を評価して最後の式の値をとるDo構文を追加する。

2020-05-26

めざそう言語処理系の沼　〜shift/resetへの旅〜　その１０ Consとリスト

OCaml めざそう言語処理系の沼言語処理系

今回は言語で簡単なデータ構造を扱えるようにする。具体的にはイミュータブルなconsセル（とnil値）を導入して、linked listを作れるようにする。

ついでにLisperならお馴染みのcar、cdrやリストを便利に作れる・使えるlist、applyなども定義する。

こんな感じで使える：

(let [x (cons 1 2)]
  (+ (car x) (cdr x)))

(apply + (list 1 2 3 4 5))

前回との差分：

Comparing v0.9...v0.10 · zehnpaard/kontlang · GitHub

テスト以外で変更したのはValとBuiltinsだけ。パーサも評価器も変更なし。

まずValモジュールにConsと`Nilを追加：

type t =
| Nil
...
| Cons of t * t

Val.Consは要素２のタプル。Val.Nilは今後副作用ありの計算の結果に使ったりもする予定だが、ここではリストの終端を表すようにしている。

つまり

(cons 1 (cons 2 (cons 3 nil)))

が[1 2 3]というリストとしてみなされる。

ちなみに

(cons 1 (cons 2 (cons 3 4)))

と終端がnilでない場合、dotted listといって[1 2 3 . 4]のように表記される。

ある値が（nilで終わっている）リストか確認する関数is_list：

let rec is_list = function
| Nil -> true
| Cons(_, x) -> is_list x
| _ -> false

や、list、dotted_listをOCamlのリストやリストとVal.tのタプルに変換するヘルパー関数：

let rec cons_to_list = function
| Nil -> []
| Cons(x, xs) -> x::(cons_to_list xs)
| _ -> failwith "Converting non-cons-list into arg list"

let rec cons_to_dotted_list acc = function
| Nil -> failwith "Dotted list cannot end with nil"
| Cons(x, xs) -> cons_to_dotted_list (x::acc) xs
| v -> (List.rev acc, v)

なども追加してある。

Builtinsモジュールに追加された組込関数など：

let builtins =
[
...
; "nil", Val.Nil
; "cons", Val.Op("cons", cons_op)
; "car", Val.Op("car", car_op)
; "cdr", Val.Op("cdr", cdr_op)
; "list", Val.Op("list", list_op)
; "apply", Val.Op("apply", apply_op)
; "nil?", Val.Op("nil?", nilp_op)
; "cons?", Val.Op("cons?", consp_op)
]

nilやconsも予約語ではなく、ただの変数。

cons、car、cdrの定義：

let cons_op = function
  | [x; y] -> Val.Cons(x, y)
  | xs -> failwith @@ Printf.sprintf "Cons applied to %d args" (List.length xs)

let car_op = function
  | [Val.Cons(x, _)] -> x
  | _ -> failwith "Non-cons passed to car"

let cdr_op = function
  | [Val.Cons(_, y)] -> y
  | _ -> failwith "Non-cons passed to cdr"

パターンマッチで、consの場合引数が２つでない場合、carやcdrの場合引数が１つのVal.Consでない場合はエラーとなる。

listとapplyの定義：

let rec list_op = function
  | [] -> Val.Nil
  | x::xs' -> Val.Cons(x, list_op xs')

let apply_op = function
  | [Val.Op(_, op); Val.Cons _ as cons] -> op @@ Val.cons_to_list cons
  | _ -> failwith "Incorrect args passed to apply"

listは引数のリストを再帰的に(cons x (cons y (... nil) ...))の形に変換する。

applyは第一引数の関数を第二引数のリストに適用する、のだがその時「ソース言語のリスト」を「OCamlのリスト」に変換している。なので

(apply + (list 1 2 3 4))

(+ 1 2 3 4)

が同じ結果となる。

あとはnilやconsかどうかを調べる述語：

let nilp_op = function
  | [Val.Nil] -> Val.Bool true
  | [_] -> Val.Bool false
  | _ -> failwith "nil? called with invalid number of args"

let consp_op = function
  | [Val.Cons _] -> Val.Bool true
  | [_] -> Val.Bool false
  | _ -> failwith "cons? called with invalid number of args"

引数が１つ出なければエラー。１つの場合、cons?は引数がVal.Consなら真、それ以外は偽。nil?は引数がVal.Nilなら真、それ以外は偽。

以上で実装完了。

これでmapやfilterが書ける！と思ったのだが、ifだけだと少し書きにくいのでcondを追加して場合分けで分岐できるようにしたい。

というわけで次回はcondの話。

2020-05-26

めざそう言語処理系の沼　〜shift/resetへの旅〜　その９微調整

OCaml めざそう言語処理系の沼言語処理系

今回は細かいところを調整しただけ。

前回との差分：

Comparing v0.8...v0.9 · zehnpaard/kontlang · GitHub

調整ポイントは：

レキシカル・スコープで関数作成時にクロージャに束縛する自由変数の重複を排除
Exp.Letsを評価する時、変数に束縛されるべき式をすべて評価し終わった後に継続にCont.Envを追加していたのを、実引数評価の前に追加するよう変更
Cont.Letで変数に束縛されるべき式をすべて評価し終わった後、それらをList.revしていたのをやめた

地味かつ現行の機能にはなんの変化もないリファクタリング。

クロージャに束縛する自由変数の重複を排除

関数作成時に自由変数を全部検出するのだが、今までの実装だと例えば

(fn [y]
  (+ x y (+ x x) z))

などといった式の場合、自由変数が[+ x + x x z]のような重複のあるリストになってしまって非効率。重複は排除したい。

Utilsモジュールにdedupe関数を追加：

let dedupe xs =
  let hsh = Hashtbl.create 1024 in
  let rec f acc = function
  | [] -> acc
  | x::xs' ->
    if Hashtbl.mem hsh x then f acc xs'
    else (Hashtbl.add hsh x 0; f (x::acc) xs')
  in
  f [] xs

ミュータブルなデータ構造であるHashtblを使っているが、この関数の外には漏れないので問題なし。ほぼSetとして使っているが、イミュータブルなSetに比べてHashtblはいろいろと性能がいい。OCaml公式サイトのチュートリアルにも

Sets and maps are very useful in compilation and meta-programming, but in other situations hash tables are often more appropriate

と書かれている。今回はSetのような永続性はいらないのでHashtblを使う。

こうやって定義したUtils.dedupeを、Execute.evalでget_freeが使われているところに加える：

let eval env cont = function
...
| Exp.Fn(params, body) as e ->
    let free = Utils.dedupe @@ 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.Lets`評価時に`Cont.Env`を追加するタイミング

前回までのコードだとExp.Letsを評価する時に：

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

evalのタイミングで[]::envと空リストを変数環境に追加しているが：

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)

「let*式から出たらそのリストを外す必要がある」と継続にCont.Envを追加するのはapply_cont関数内で、Cont.Letsの未評価の式がなくなった時点だ。現在エラー以外でevalからapply_contの流れが止まることはないので問題が表面化しないのだが

変数環境に空リストを追加するのと継続にCont.Envを追加するのとは対応しているのに、こんなに離れてしまっているのは気持ち悪い
限定継続が追加されるとevalとapply_contの流れが中断される恐れがある

という二点を踏まえて修正しておく。

let eval env cont = function
...
| Exp.Lets((s, e1)::ves, e2) -> Eval([]::env, Cont.Lets(s, ves, e2)::Cont.Env::cont, e1)

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

Cont.Envが追加される場所がevalに移すだけで修正完了。

`Cont.Let`で`List.rev`するのをやめる

これはどういうことかというと

(let [(x 10)
      (x 5)]
  (* x 2))

のような式がある場合、下にある変数束縛の方が優先されるべき（なので結果は10）。

変数環境に追加するリストは[(x 10) (x 5)]ではなく[(x 5) (x 10)]である必要がある。

元の：

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

だとList.revが余計。実際には先頭から評価してリストに加えていったものを、そのまま変数環境に加えるのが正しい順序になる。

それを踏まえてこう変える：

| Cont.Let(s, [], vvs, e2) :: cont' ->
    let env' = Env.extend_list ((s, v)::vvs) env in
    Eval(env', Cont.Env::cont', e2)

List.revを消しただけ。これで環境内で変数の出てくる順序が正しくなる。

それ以外

それ以外はコンストラクタの間のスペースを消したり、パーサの部分表記を統一したり、といったこまごました変更。やはり機能には影響なし。

次回は言語にcons、car、cdrを追加してLispらしいリストを作れるようにする。

2020-05-25

めざそう言語処理系の沼　〜shift/resetへの旅〜　その８再帰

OCaml めざそう言語処理系の沼言語処理系

普通の関数が実装できたので、今度は再帰関数を定義できるようにする。

具体的にはこのような構文：

(letrec
  [factorial [n]
     (if (= 1 n)
         1
         (* n (factorial (- n 1))))]
  (factorial 6))

あるいは：

(letrec
  [(odd? [x]
      (if (= 0 x)
          false
          (even? (- x 1))))
    (even? [x]
       (if (= 0 x)
           true
           (odd? (- x 1))))]
  (odd? 101))

といった形で相互再帰もできるようになる。

前回との差分：

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

まずExp.tにLetRecを追加：

type t =
...
| LetRec of (string * string list * t) list * t

「再帰関数名」「仮引数」「関数の本体」のリスト
letの本体である式

の二つの部分で構成されている。ちなみにLetFnの定義は

| LetFn of (string * string list * t) list * t

なのでLetRecとLetFnは式の保持する情報はまったく同じものとなる。

次にValモジュールに再帰関数の値を追加：

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

各要素の意味は

関数名
仮引数
クロージャ
関数本体の式

となる。これもFnと比較してみると：

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

ほぼ同じだが、クロージャの部分がRecFnではrefになっているのが違い。再帰関数のクロージャには「自由変数と対応する値」だけではなく「letrecで定義された関数名とそれに対応する値」も追加されるのだがその「対応する値」にこのRecFn値も含まれる。そういうループ構造を実装するために、関数を作成後に変更できるミュータブルなrefを使っている。（他のやり方もある。Essentials of Programming Languagesの第3章を参照）

新しい式を追加したのでExecute.get_freeも変更：

let rec get_free env = function
...
| Exp.LetRec(fns, e) ->
    let fnames, paramss, bodys = Utils.split3 fns in
    let f params body = get_free (Env.add_vars env (fnames @ 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

再帰関数の要素のリストから「関数名」のリスト、「仮引数」のリスト、「関数本体」のリストを作成
「関数一つの自由変数を出す」関数を定義
定義されている再帰関数すべての自由変数を上記2行の結果を使って検出
LetRec本体の式の自由変数を検出し、上記の「再帰関数の自由変数」のリストとconcat

となっている。

「『関数一つの自由変数を出す』関数を定義」の

    let f params body = get_free (Env.add_vars env (fnames @ params)) body in

で定義されたすべての再帰関数名fnamesも変数環境に追加し、再帰関数の自由変数から除外しているのもポイント。

Execute.eval：

let eval env cont = function
...
| Exp.LetRec(fns, e) ->
    let fnames, _, _ = Utils.split3 fns in
    let f fnames (fname, params, body) =
      let free = get_free (Env.add_vars Env.empty (fnames @ params)) body in
      let fvals = List.map (fun v -> v, Env.find v env) free in
      let fvalsr = ref fvals in
      let fn = Val.RecFn(fname, params, fvalsr, body) in
      ((fname, fn), fvalsr)
    in
    let fname_fns, fvalsrs = List.split @@ List.map (f fnames) fns in
    List.iter (fun fvalsr -> (fvalsr := (fname_fns @ !fvalsr))) fvalsrs;
    Eval(Env.extend_list fname_fns env, Cont.Env::cont, e)

おおさっぱな流れを解説すると：

再帰関数の要素のリストから再帰関数を作成
作成されたすべて再帰関数のクロージャに「作成されたすべての再帰関数の名前と値」を追加
変数環境に作成されたすべて再帰関数を追加して、letrec本体の式を評価

となっている。

「再帰関数の要素のリストから再帰関数を作成」するために定義されているf関数が過半数の行を占めている。（おっと、このf関数がfnamesを引数にとる意味がないな・・・）

ポイントとしては、再帰関数の名前と値のタプルだけでなく、その関数のクロージャも同時に返しているところ。すべての再帰関数の値をクロージャに追加しなければいけないので、「一つの再帰関数を作る」f関数内ではクロージャの更新はできない。

最後にExecute.apply_cont：

let apply_cont env cont v = match cont with
...
| Cont.Call([], vs) :: cont' -> (match List.rev (v::vs) with
...
  | Val.RecFn(s, ss, fvalsr, e) :: vs' ->
    let paramcount = List.length ss in
    let argcount = List.length vs' in
    if paramcount = argcount then
      let env' = Env.extend_list (!fvalsr @ (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を追加してからletrec本体の式を評価する。（引数の要素数が一致しない場合はエラー）。

くどいようだがVal.Fnのケースと比較してみる：

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

目を凝らさないとなかなかわからないと思うが、

let env' = Env.extend_list (!fvalsr @ (List.combine ss vs')) env in (* RecFn *)
let env' = Env.extend_list (fvals @ (List.combine ss vs')) env in (* Fn *)

この違いである。Fnだとそのままリストである「自由変数と対応する値」のfvalを直接concatしているのが、RecFnだとref型なので!fvalsrとしている。

今気づいたのだが、FnもRecFn側に寄せてクロージャをrefで持つようにすれば値の種類をわける必要もなく、この場合分けもいらなくなるな・・・（Exp.LetRecはいるがVal.RecFnはいらない）　どこかのタイミングで修正してみよう。

というわけで再帰も実装完了。「クロージャをミュータブルにする」という方針が決まっていれば比較的簡単に既存の非再帰関数のコードを修正できる。

次回はいくつかマイナー修正を加える。

Arantium Maestum

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

めざそう言語処理系の沼　〜shift/resetへの旅〜　その１４ステップ実行インタプリタ

値と継続の定義を共通のモジュールに移す

継続を`list list`に

継続と変数環境を文字列化できるようにする

ステップ実行インタプリタ

使い方

次回

めざそう言語処理系の沼　〜shift/resetへの旅〜　その１３マクロ

背景

使い方

コード解説

次回

めざそう言語処理系の沼　〜shift/resetへの旅〜　その１２文字列、入出力とDo

式と値に文字列を追加

標準入出力

`Do`式

次回

めざそう言語処理系の沼　〜shift/resetへの旅〜　その１１ Cond＆リファクタリング

`cond`による条件分岐

`Val.Fn`と`Val.RecFn`を統一

`get_free`をリファクタ

次回

めざそう言語処理系の沼　〜shift/resetへの旅〜　その１０ Consとリスト

めざそう言語処理系の沼　〜shift/resetへの旅〜　その９微調整

クロージャに束縛する自由変数の重複を排除

`Exp.Lets`評価時に`Cont.Env`を追加するタイミング

`Cont.Let`で`List.rev`するのをやめる

それ以外

めざそう言語処理系の沼　〜shift/resetへの旅〜　その８再帰

値と継続の定義を共通のモジュールに移す

継続をlist listに

継続と変数環境を文字列化できるようにする

ステップ実行インタプリタ

使い方

次回

背景

使い方

コード解説

次回

式と値に文字列を追加

標準入出力

Do式

次回

condによる条件分岐

Val.FnとVal.RecFnを統一

get_freeをリファクタ

次回

クロージャに束縛する自由変数の重複を排除

Exp.Lets評価時にCont.Envを追加するタイミング

Cont.LetでList.revするのをやめる

それ以外

継続を`list list`に

`Do`式

`cond`による条件分岐

`Val.Fn`と`Val.RecFn`を統一

`get_free`をリファクタ

`Exp.Lets`評価時に`Cont.Env`を追加するタイミング

`Cont.Let`で`List.rev`するのをやめる