実装したモナドやmap、fold_leftなどの関数をライブラリ化することで毎回定義し直さなくても済むようにしたい。

その準備段階としてモジュールを実装する。（ファイルから読み込む場合もモジュールとして扱いたいため）

具体的には

(module [...])という構文でモジュール（第１級オブジェクト）を定義
(define ... ...)でモジュール内での変数束縛
M.xなどでモジュールM内の変数xにアクセス

を追加して

(let [M (module [(define x 5) (define y 10)])]
  (+ M.x M.y))

のような書き方ができるようにする。

今回のコード差分：

Comparing v0.16...v0.17 · zehnpaard/kontlang · GitHub

`define`

モジュール定義の中でだけ使えるキーワードdefineを追加する。

まずExp：

type t =
...
| Define of string * t

let rec get_free bound free = function
...
| Define(_, e) -> get_free bound free e

モジュール内で束縛する変数名を表す文字列と、その変数に束縛する値へと評価される式を持つ。

define式の自由変数は保持している式の中の自由変数である。

define式は独自の値とはならず、式の評価も必ずmodule式の一部として評価される。

なのでExecute.evalで生のExp.Defineに当たると：

let eval env cont = function
...
| Exp.Define _ -> failwith "Define used outside of Module definition"

この通り実行時エラーを吐く。実際にはパーサにも制約をかけてあって、(module [...])の中以外でdefineを使うとパースエラーになるのでこの実行時エラーのケースには到達しない（はず）。

また、独自の値にならないのでValcontモジュールには登場しない。

`module`

無名モジュールを作成するmodule式を定義する。

まずExp：

type t =
...
| Module of t list

let rec get_free bound free = function
...
| Module [] -> free
| Module((Define(s,e))::es) -> get_free (s::bound) (get_free bound free e) (Module es)
| Module(e::es) -> get_free bound (get_free bound free e) (Module es)

モジュールは式のリストを保持する。defineだけではなく、副作用を起こすような任意の式もモジュール内で記述できるので保持する式にはなんの制限もない。

(module
  [(define x 10)
   (define y (+ x 5))]

のように、先にdefineで定義された変数を後々モジュール内で使えるようにするので自由変数を求める時にmoduleの保持する式を再帰的に探っていきdefineの場合は後続の式にとってのbound変数を更新している。

今見直すと再帰するたびにExp.Moduleを解体しては新しく作り直していてあまり効率がよくない。fold_leftで綺麗に書けそうなので今度書き直したい。

次にValcontモジュール：

type valt =
...
| Module of (string * valt) list
and contt =
...
| ModuleExp of Exp.t list * (string * valt) list
| ModuleDefine of string * Exp.t list * (string * valt) list

Module値はモジュール内で束縛されている「変数と値」のリストを保持する。

そして継続としては

モジュール式の中のdefine式を評価していることを表すModuleDefine
モジュール式の中のdefine以外の式を評価していることを表すModuleExp

を追加。

ModuleExpは未評価の式のリストと、これまで評価済みの「変数と値」のリストを持つ。

ModuleDefineはModuleExpのデータに加えて「現在評価中のdefineで束縛される変数の文字列」を持つ。

ではExecute.eval：

let eval env cont = function
...
| Exp.Define _ -> failwith "Define used outside of Module definition"

まずはExp.Defineのケース。これは特殊でdefineはモジュール定義内でのみ使われることになっていて、Exp.Moduleの評価やCont.ModuleDefine、Cont.ModuleExpの継続適用の一部として処理されることになる。パーサの仕様上それ以外の状況で出てくることはないはずだが、もし出現してevalされた場合は実行時エラー。

次にExecute.evalのExp.Moduleケース：

| Exp.Module(Exp.Define(s, e)::es) ->
  let env' = []::env in
  let cont' = Cont.add (Cont.ModuleDefine(s, es, [])) @@ Cont.add Cont.Env cont in
  Eval(env', cont', e)
| Exp.Module(e::es) ->
  let env' = []::env in
  let cont' = Cont.add (Cont.ModuleExp(es, [])) @@ Cont.add Cont.Env cont in
  Eval(env', cont', e)
| Exp.Module [] -> ApplyCont(env, cont, Val.Module [])

三つのケースが考えられる：

モジュール内の式の先頭がdefineだった場合
モジュール内の式の先頭がdefine以外だった場合
モジュール内で式定義がなかった場合（つまり(module [])）

後者はエラーでもいいと思ったのだが、空のモジュールを禁止する強い理由もないので許容。

モジュール内の式の先頭がdefineだった場合は、変数環境を新しく区切り（モジュール内でdefineを使って定義された変数がそれ以降のモジュール内定義で使用できるようにするため＆モジュール定義が終わったら変数環境から外せるようにするため）、Cont.Envを継続に追加。さらにCont.ModuleDefineに「先頭要素以外のモジュール内の式のリスト」と(define x e)のxに当たる変数名を保持させて継続に追加。この変数環境と継続で(define x e)のeの式を評価する。

モジュール内の式の先頭がdefine以外だった場合もほぼ同じだが、Cont.ModuleDefineの代わりにCont.ModuleExpを使う（変数名は保持しない）。そしてモジュール内の式の先頭要素すべてを評価する（(define x e)のように分解して一部を評価、といった手順は踏まない）。

次にExecute.apply_contのCont.ModuleDefineケース：

let apply_cont env cont v = match cont with
...
| (Cont.ModuleDefine(s, [], svs)::cont')::cont'' ->
    ApplyCont(env, cont'::cont'', Val.Module((s, v)::svs))

もし未評価の式が残っていなければ、たった今の評価結果である値とそれに対応する変数名を「評価済みの値と変数名のリスト」に追加して、それを保持するVal.Module値を作成、それを現在の継続に渡す。（Execute.evalのExp.Moduleケースを見れば最初に行われるのは「現在の変数環境を一つ外す」である）

Cont.ModuleDefineに未評価の式が残っていて、その先頭の要素がExp.Defineだったケース：

| (Cont.ModuleDefine(s, Exp.Define(s', e')::es, svs)::cont')::cont'' ->
    let env' = Env.extend_current s v env in
    let cont''' = Cont.add (Cont.ModuleDefine(s', es, (s,v)::svs)) (cont'::cont'')in
    Eval(env', cont''', e')

たった今の評価結果である値とそれに対応する変数名を「評価済みの値と変数名のリスト」に追加すると同時に変数環境にも追加。先頭の要素がExp.Defineなので、次の継続もCont.ModuleDefineとなる。その新しいCont.ModuleDefineを継続に追加してから新しい変数環境と継続でExp.Defineの保持する式を評価する。

Cont.ModuleDefineに未評価の式が残っていて、その先頭の要素がExp.Define以外だったケース：

| (Cont.ModuleDefine(s, e::es, svs)::cont')::cont'' ->
    let env' = Env.extend_current s v env in
    let cont''' = Cont.add (Cont.ModuleExp(es, (s,v)::svs)) (cont'::cont'')in
    Eval(env', cont''', e)

たった今の評価結果である値とそれに対応する変数名を「評価済みの値と変数名のリスト」に追加すると同時に変数環境にも追加（これは直前のケースとまったく同じ）。次の継続はCont.ModuleExpとなる。未評価の式の先頭要素を新しい変数環境と継続で評価する。

Execute.apply_contでCont.ModuleExpのケース：

| (Cont.ModuleExp([], svs)::cont')::cont'' ->
    ApplyCont(env, cont'::cont'', Val.Module svs)
| (Cont.ModuleExp(Exp.Define(s', e')::es, svs)::cont')::cont'' ->
    let cont''' = Cont.add (Cont.ModuleDefine(s', es, svs)) (cont'::cont'')in
    Eval(env, cont''', e')
| (Cont.ModuleExp(e::es, svs)::cont')::cont'' ->
    let cont''' = Cont.add (Cont.ModuleExp(es, svs)) (cont'::cont'')in
    Eval(env, cont''', e)

ModuleDefineから少々修正しただけなので詳細は割愛。

ここまでで(module [(define x 5) (define y 10) (define f (fn [a b] (+ a b)))])のようなモジュールが作成できるようになった。

モジュール変数にアクセス

モジュールを作ったはいいが、中の変数にアクセスする方法が必要。

というわけでM.xやM.N.yのようにドット記法でモジュールの中身にアクセスできるようにする。M.N.yは「Mモジュール内の変数Nに束縛されているモジュールのy変数にアクセス」という意味になる。

まずはExpモジュールで式を定義：

type t =
...
| MVar of string list

let rec get_free bound free = function
...
| MVar [] -> free
| MVar(s::_) -> if (List.mem s bound) then free else s::free

MVarはモジュール変数の意。M.N.yだとMVar ["M"; "N"; "y"]と表現されることになる。

自由変数検出に関しては、先頭の要素のみ検出される。つまりM.N.yというモジュール変数が出てきた場合、Mはもしかすると自由変数かもしれないが、Nとyは自由変数にはなり得ない。

珍しくlexerのコードも載せてみる：

let char = ['a'-'z' 'A'-'Z' '+' '-' '*' '/' '<' '>' '=' '!' '?' '_']
let number = ('0'|['1'-'9'] digit*)
let variable = char (char|digit)*
let mvariable = variable '.' variable ('.' variable)*

rule f = parse
...
  | mvariable as s { Parser.MVAR (String.split_on_char '.' s) }

mvariableという正規表現っぽいパターンにマッチした文字列をString.split_on_chat '.'で分割したリストをMVARとしてパーサに渡している。

Execute.eval：

let eval env cont = function
...
| Exp.MVar([]) -> failwith "Evaluating invalid/empty module var"
| Exp.MVar(s::ss) ->
  let m = Env.find s env in
  let f m s = match m with
  | Val.Module svs -> (match List.assoc_opt s svs with
    | Some n -> n
    | None -> failwith @@ Printf.sprintf "Member %s of module does not exist" s)
  | _ -> failwith @@ "Accessing member of non-module"
  in
  let v = List.fold_left f m ss in
  ApplyCont(env, cont, v)

Exp.MVarが空リストということはパーサ上あり得ないが、パターンマッチの網羅性のために実行時エラーになるケースを追加しておく。

Exp.MVarの変数名リストに要素が含まれている場合はまず先頭要素の変数を現在の変数環境の中から探して、その値を起点にfold_leftで残りの変数名リストを解決していく。変数が見つからない場合と最後の変数名以外がモジュールでない値であった場合には実行時エラーとなる。

これでモジュールの基本機能である「作成」と「アクセス」は完了。

再掲になるが：

(let [M (module [(define x 5) (define y 10)])]
  (+ M.x M.y))

のような書き方ができて、結果は15になる。

次回

次は外部ファイルからモジュールを読み込めるようにする。

Arantium Maestum

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

めざそう言語処理系の沼　〜shift/resetへの旅〜　その２２モジュール

`define`

`module`

モジュール変数にアクセス

次回