define の実装 - Scheme VM を書く

scheme

方針は決まったので実装。
あらかじめやることを列挙しよう。

  • 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 に渡せば良い。やってみよう。
    • →できた