global変数判定のバグ - Scheme VM を書く

scheme

コンパイル時の global 変数判定のバグを発見。
わりと深刻なのでまじめに考えないとまずい。

症状

(compile-lambda '(lambda () (print "Status: 200 OK")) '() '() '() '(HALT))
=> (REFER_GLOBAL print (ARGUMENT (CLOSE 1 (CONSTANT "Status: 200 OK" (ARGUMENT (REFER_FREE 0 (SHIFT 1 0 (APPLY 1))))) 0 #f (HALT))))

lambda 内の print 参照が free variable 扱いになり display closure を作ろうとしている。
lambda の外では print は global 扱いなので REFER_GLOBAL して push して free 扱いにするというなぞの挙動に。

何が問題か？

print が free variable と判定されているのが問題。
具体的には find-free で print が free と判定されるのが良くない。

     [(symbol? sexp)
      (cond ((set-member? sexp b) '())
            ((set-member? sexp f) (list sexp))
            ((set-member? sexp global-variables) '())
            (else (list sexp)))]

どれにもあてはまらないときは free variable ではなく global variable と判定するのが良い。
free variable をいかに正しく判定するかという問題に帰着。

おおざっぱな方針

free variable になるのは、親（またはその親）の lambda で引数として渡っているものである。
親からきちんとこれらの引数を引き継いで find-free すれば良いはず。

つまり一番外側の lambda から

(lambda ()
  (lambda (a b)
     (lambda (c d)
          ;; (a b) が free 候補
        (lambda (e f)
          ;; (a b c d) が free 候補
          ...))))

という感じ。

find-free の引数を思い出す

どの引数も lambda 式の body のコンパイル時に使われる。

e

(vars . free vars) の形式でその lambda 式の中で、引数として扱うもの、見つかった free variable のペア。

f

vars と以前の f の union。
これが free variable と判定されるべき候補。

s

その lambda 内で代入される可能性があるもの。

作業

  • e, f, s 見直し => OK
  • fが正しく使われているか？
    • find-free の symbol 判定がまちがっている？
    • 間違ってた

残作業

  • stack-vm22.scm 整理
    • print 削除
    • テストをまとめる
    • compile.scm に反映
  • stack-vm23
    • global 変数の引きまわしいらない疑惑

完了

2.5時間。
テスト書いてなかったら enbug するところだったな。