(let ((x 3) (y 4))
(lambda (a b c d e)
(let ((y (* a b x))
(z (+ c d x)))
(* x y z))))
で返された手続きの作用で, 式(* x y z)を評価する時, xの値を探している問題を考えよう. let式はlambda組合せの構文シュガーに過ぎないから, これは
((lambda (x y)
(lambda (a b c d e)
((lambda (y z) (* x y z))
(* a b x)
(+ c d x))))
3
4)
と等価である. lookup-variable-valueがxを探索する度に, 記号xは(第一のフレームで)yやzとeq?でないか, (第二のフレームで)
a, b, c, dやeとeq?でないか決めなければならない.
ここでわれわれのプログラムはdefineを使わない---変数は
lambdaだけで束縛される---と仮定しよう. われわれの言語は
静的有効範囲だから, 式の実行環境は式が現れるプログラムの文面の構造と対応する構造を持っている.45
従って翻訳系は上の式を解析する時, 手続きを作用させる度に(* x y z)の変数は現在のフレームから二フレーム外で見つかり, そのフレームの最初の変数であると知ることが出来る.
この事実を新しい変数探索演算lexical-address-lookupを考えて調べることが出来る. 引数として環境と二つの数: 何個のフレームを読み過すかを指定するフレーム数(frame number)と, そのフレームで何個の変数を読み過すかを指定する変位数(displacement number)からなる文面アドレス(lexical address)をとる. lexical-address-lookupは現在の環境から相対的な文面アドレスに格納した変数の値を出す. われわれの計算機にlexical-address-lookup演算を追加すると, 翻訳系にlookup-variable-valueではなく, この演算を使って変数を参照するコードを, 生成させることが出来る. 同様に翻訳したコードは, set-variable-value!の代りに lexical-address-set!を使うことが出来る.
こういうコードを生成するためには, 翻訳系は参照を翻訳しようとする変数の文面アドレスを決めることが出来なければならない. プログラム中の変数の文面アドレスは, それがコードのどこにあるかに依存する. 例えば次のプログラムで式⟨e1⟩のxのアドレスは(2,0)---二フレーム後方で, そのフレームの最初の変数---である. その点でy はアドレス(0,0), cはアドレス(1,2)である. 式⟨e2⟩ではxは(1,0), yは(1,1), そしてcは(0,2)である.
((lambda (x y)
(lambda (a b c d e)
((lambda (y z) ⟨e1⟩)
⟨e2⟩
(+ c d x))))
3
4)
翻訳系に文面アドレスを使ったコードを作り出させる一つの方法は, 翻訳時環境 (compile-time environment)というデータ構造を維持することである. これは, ある変数アクセス演算を実行する時に, どの変数が実行時環境のどのフレームのどの場所にあるかを覚えておくものである. 翻訳時環境は, それぞれが変数のリストを持つフレームのリストである. (もちろん, 翻訳時に値は計算しないので, 変数には値は束縛していない.) 翻訳時環境はcompileの追加の引数となり, 各コード生成器に渡される. compileへのトップレベルでの呼出しは, 空の翻訳時環境を使う. lambda本体を翻訳する時, 本体を形成する列が, 拡張した環境で翻訳出来るよう, compile-lambda-bodyは翻訳環境を, 手続きのパラメタを含むフレームで拡張する. 翻訳の各時点で, compile-variableとcompile-assignmentは適切な文面アドレスを生成するため, 翻訳時環境を使う.
問題5.39から5.43は文面探索を翻訳系に組み込むため, 文面アドレス戦略の概要を完成する方法を述べる. 問題5.44は翻訳時環境のもう一つの使い方を述べる.
問題 5.39
新しい探索演算を実装する手続きlexical-address-lookupを書け. それは二つの引数---文面アドレスと実行時環境---をとり, 指定した文面アドレスに格納した変数の値を返す. lexical-address-lookupは変数の値が*unassigned*の記号ならエラーとする.46
また, 指定した文面アドレスにある変数の値を変更する演算を実装する手続きlexical-address-set!を書け.
問題 5.40
翻訳系を修正し, 上述の翻訳時環境を維持するようにせよ. つまりcompileとそれぞれのコード生成器に翻訳時環境の引数を加え, compile-lambda-body
で翻訳時環境を拡張せよ.
問題 5.41
引数として変数と翻訳時環境をとり, その環境に対する変数の文面アドレスを返す手続きfind-variableを書け. 例えば上に示したプログラムの断片では, 式⟨e1⟩翻訳中の翻訳時環境は((y z) (a b c d e) (x y))である. find-
うに出さなければならない.
(find-variable 'c '((y z) (a b c d e) (x y))) (1 2) (find-variable 'x '((y z) (a b c d e) (x y))) (2 0) (find-variable 'w '((y z) (a b c d e) (x y))) not-found
(lambda (+ * a b x y) (+ (* a x) (* b y)))を考えよう. 引数+matrix, *matrixと四つの行列を持ってこれを呼び出したいが, オープンコード翻訳系は(+ (* a x) (* b y))の+や*を基本手続きの+や*としてオープンコードのままとする. オープンコード翻訳系を修正し, 基本手続きの名前を含む式の正しいコードを翻訳するため, 翻訳時環境を調べるようにせよ. (プログラムがこれらの名前をdefineしたりset!したりしないうちは, コードは正しく働く.)
45
内部定義を許すと, それを掃き出さない限り, これは正しくない. 問題5.43参照
46
これは, 内部定義を消去する
掃き出し技法を実装するなら, 変数探索の必要な修正である(問題5.43参照). 文面アドレスが働くためには, これらの定義の消去が必要である.
47
文面アドレスは大域環境の変数のアクセスには, これらの名前はいつでも対話的に定義, 再定義されるので使えない. 問題5.43のように内部定義が掃き出された場合には, 翻訳系が見る唯一の定義はトップレベルのものであり, それらは大域環境として働く. 定義の翻訳は定義した名前を翻訳時環境に入れるとは限らない.