めざそう言語処理系の沼　〜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*の中に入る前の状態に戻せる。

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

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

Arantium Maestum

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

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