define の実装方法に関する考察 - Scheme VM を書く

scheme

以下の2例に関して define の実装を考える。

;; パターン A
(define a 3)
((lambda () a))

;; パターン B
(define b (lambda () c))
(define c 4)
(b)

define はトップレベルでのみ有効とし2つ実装方法を考えてみる。

global 変数は global に管理する

ヒープベースの VM の欠点は各フレームの env をさかのぼって変数の lookup をすることのオーバーヘッドが大きい点。
この問題はスタックベースになり display closure の仕組みを導入したことで解決された。（コンパイル時に変数の参照位置が解決されている。）
global な変数だけは動的に通常の lookup を行って良いのではなかろうかというのがこの方法。

例えばパターン A における define は以下のようにコンパイルされる。 a はシンボル。

'(const 3 (define-global a (next)))

そして参照するコードは

'(refer-global a (next))

となり参照結果が accumulator にセットされる。

この場合、内部実装はグローバルなハッシュテーブルに対する put/get になる。
コンパイラは display closure を考えた場合の free variable、そして local variable 以外のシンボルを refer-global として扱えば良い。
パターン B でもこの方法で実現できる。

display closure を利用する

display closure は、そのクロージャから見て local でない変数を保持しているものなのだからこれを利用しようというアイデア。
前提は

の2点。

パターンAの場合
初期状態の display closure を

closure 組込み関数A 組込み関数B

とする。
define の登場で

closure 組込み関数A 組込み関数B aを保持(3)

となる。

次に a を参照する場面では (refer-free 2 (next)) とコンパイルされていれば参照は解決する。
ここで問題になるのは、あらかじめコンパイラが (refer-free 2 (next)) を生成できるか？につきる。
これは無理だよ。
repl や load で後からコードが動的に追加されるので厳しい。

結論

「global 変数は global に管理する」を採用する事としよう。