define の実装 - Scheme VM を書く
方針は決まったので実装。
あらかじめやることを列挙しよう。
- symbol から値を lookup する関数を書く。
- VM に上記関数を組込む。
- VM に define-global 命令を追加する
- (define-global id)
- accumulator に置かれているものを id に結び付かせる
- 以前 define されている id ならエラー
- VM に refer-global を追加する
- (refer-global id)
- id をキーに expr を取り出す
- accumulator に取り出した値をセットする
- 見つからなければエラー
- VM に assign-global を追加する
- (assign-global id expr)
- id をキーに expr を値としてセットする
- define されていない場合はエラー
- コンパイラが define-global/refer-global/assign-global を吐くようにする。
- define は define を見つければ簡単
- refer-global、set-global は面倒そうなのでそのとき考える
- →とても面倒だった。大変の作業はここに費した(以下のデバッグメモはその話)
デバッグメモ
(print (compile '((lambda (a) (lambda () a)) 10) '() '() '(halt)))
これの結果
正しい:(frame (halt) (constant 10 (argument (close 0 (refer-local 0 (argument (close 1 (refer-free 0 (return 0)) (return 1)))) (apply 1))))) 誤り: (frame (halt) (constant 10 (argument (close 0 (close 0 (refer-global a (return 0)) (return 1)) (apply 1)))))
なぜ「誤り」になるか。
- 内側の lambda のコンパイル時に refer-free 手続きが () を返すから。(a)が返るべき
- なぜ返らないか?
- (lambda () a) という式を見ただけでは global 変数か、free変数か分からない。
- global変数とは何か?、free変数とは何か?何を見れば区別できるか。
- global変数とは define によって定義された変数である
- free変数とは、local変数ではなく、global変数でもないもの
- local変数とは lambda の (vars) にあるもの
- 上記以外にまだ決まっていない変数もある
- (define a (lambda () b)) この b は unbound variable だが、今後 (define b 3) されて、global variable になるかもしれない。
- 何か分からないものは global 変数にしておいて refer-global とするのが良さそうだ。
- free 変数を特定する方法はないだろうか。
- (lambda (a) (lambda () a)) 以外に free 変数が出来るパターンがあるだろうか。lambda 内 lambda 以外にという意味。
- ないかな。
- compile に引数を増やして free-variables というのをつくったらどうだろうか。
- free-variable の候補を渡してやる。それを find-free に渡せば良い。やってみよう。
- →できた