free variables のマーキングのタイミングについて - Scheme VM を書く

現在の3passにおいて、いかなるタイミングで free variables をマーキングすべきかを考えます。

display に必要なもの3つ

まず display に必要なものは3つ。

変数参照解決
- REFER_FREE N
- 各 let/lambda に対して free variables の列挙が完了している必要あり
外側の環境から値を引き継ぐ
- 外側の環境で変数を参照して display frame 作成時に値を渡す
- 外側の環境が正しく判明している必要あり
代入発見
- free variable 全てにおいて set! されるかどうかを調べる
- set! される場合は box 生成コードを出力する必要あり

最適化で起こりうること

let が消える
lambda が消える
call が lambda の body になる
変数が参照されなくなる

考えたいこと

free variable をどのタイミングで見つけるべきか。
pass1(S式->IForm) 、pass2（最適化）、pass3（コード生成）のいずれか。
pass2 のときはほぼありえないので pass1 or pass3 ということになりそう。

例から考える

以下のような最適化で激変しそうなコードを考えます。

(let1 x global-var
  (let1 func (lambda (y) (+ x y))  ;; x が free variable
     (let1 a 0
        (let1 b 1  ;; a が free variable
           (func a)))))

2つほど free variable があるのに注意してください。
最適化すると何だかんだで以下のようになると思います。

(let x global-var
  (let y 0 ;; x が free variable
    (+ x y)))

最適化の前に free variable をマーキングしても全部消えてしまいましたね。

もし仮に最適化が甘くて let が消えずに残っていたとしましょう。

(let x global-var
  (let1 b 1 ;; a が free variable
    (let y 0  ;; x が free variable
      (+ x y))))

今度は a が free variable であるという情報が残ってしまいました。更に x が free variable であるのは間違いないのですが外側の環境が上の場合と違いますね。
どうやら最適化のあとに free variable を見つけた方が良さそうです。

結論

pass2（最適化）で環境が激変してしまう可能性が高いので、free variables のマーキングは pass3 で行ったほうが良い。