Reading3imppdf

3imp.pdfの4章を読んだときのメモです。これから読む人の参考になれば幸い。

3imp.pdf( Three implementation models for scheme )とは

ChezSchemeの作者 Kent Dyvbigによる、Scheme処理系の実装方法について 書かれた資料。

• http://b.hatena.ne.jp/entry/http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

注意

• let式がないので、ローカル変数は仮引数オンリーです。
• 「末尾呼び出しの最適化」とすべきところを「末尾再帰の最適化」と書いている場合があります^^;

目次

4.1 ブロック構造言語のスタックによる実装

4.1.1 Call Frame

• 関数適用のたびに作られる
  • 引数
  • ポインタ、レジスタを保存(おわったらもとにもどす)
  • local temp
  • 動的リンク
  • 静的リンク

ここで作る処理系のフレームは：

1. サスペンドされた呼び出しのフレームへのポインタ (=動的リンク) ??
2. 引数
3. リターンアドレス(残りの計算)
4. 呼ばれた関数の次の外側のスコープのフレームへのポインタ (=静的リンク)

レイアウト：

• 静的リンク (最後にpushされる＝topに近い)
• 引数1
• ...
• 引数n
• 次の式
• 動的リンク (最初にpushされる)

順番はわりとどうでもいいんだけど、末尾再帰の最適化のことを考えると静的リンク・引数が上にあるほうが良い。

4.1.2 動的リンクと静的リンク

• 動的リンク = caller's frame (戻り先フレーム)
  • 常に必要なわけではないけど、デバッグなどに役立つので置く
  • next frame in the control stack
• 静的リンク = ひとつ外側の変数束縛をもつフレーム
  • クロージャ、末尾再帰の最適化、継続
  • pointer to the next rib of an environment

両者は同じこともあるし、違うこともある

書き換え耐性

• 静的リンク in closure
• 動的リンク in continuation

4.1.3 Functional

• Functional(引数となる関数)は、静的リンクを保存しないといけない(クロージャ同様)
  • 別のリンクチェイン上から呼び出されることもあるから
• 作り方はheap-baseにおけるクロージャと同じだが、eはヒープ上の環境ではなくスタック上のフレームを指すポインタ

• 作られたスコープ外で呼び出されることはない
  • スタック上に置けば十分

4.1.4. スタック操作

スタックベースの特徴

• コールフレームと変数束縛がスタック上に置かれる
• 実装はそんなに変わらんよ

stack

スタック。長さ1000くらいのベクタ

(define stack (make-vector 1000))

push x s

スタックに値を置く(sはスタックトップを指すインデックス)

index s i

スタックのi番目を見る

index-set! s i v

スタックのi番目に値を置く

4.1.5 コンパイル

3.5章との違い：

• フレームサイズ＝arity (引数がフレーム内に置かれるから)
  • return命令はこの数を知ってる必要がある(return n)
  • n + (dynamic link) + (next exp)
• 末尾再帰は(まだ)サポートしないので、関数適用でのtail?関数は使われていない
• 継続は(まだ)なし

• compile-lookup, extendは3.5章のとおなじ(適切な回数だけリンクを辿るのは同じだから)
  • ただしextendはコンパイル時だけ使う(値はribではなくスタックに置かれるから)

4.1.6 評価

• ほとんど3.5といっしょ
  • (a)=アキュムレータ、(x)=next exp
• (e)は静的リンク(環境)を指すが、外側のフレームへのポインタになっている
• (s)はスタックトップ
• (r)はなくなった(引数はスタックに置くから)

変化した命令：

• refer, assign : envではなく静的リンクをたどる
• closure : closureではなくfunctionalを作る ?
• conti/nuate : なし
• frame x ret : x=動的リンク(現在のフレーム)、ret=次の式
• argument x: ribではなくスタックに引数を積む
• apply : ribではなくスタックに静的リンクを作る
• return n : n=取り除く引数の数 (その他、動的リンクと次の式も取り除く)

新しい関数：

• find-link n e: フレームポインタeから始まる静的リンクをたどったn番目
  • eはスタック上のフレームの位置を指す

4.2 動的リンクをスタックに

concession?

• ヒープベースよりだいぶ効率良くなる(メモリ確保、メモリ参照、命令数的な意味で)

まず

• 動的リンク(control stack)をスタックに
  • 静的リンクはヒープに入ったまま
• 継続は動的リンクを保存・復元しないといけない

4.2.1 スナップショットによる継続

• スタックのコピーを持てばいいよね

therein?

• リターンアドレス、環境へのポインタはヒープベースとおなじ
• スタック自身には変更は加わらない(スタックトップに積んだり取ったりするだけなので、その下は変わらない)
  • なので変更は気にしなくて良い。

動くけど、コスト高

• スタックはでかくなるよね
• まぁ継続とかそんなに使わんから勘弁してくれ(関数呼び出しが効率良くなる方が全体では得)

outweigh?

• よく使うものがコスト低になるようにしよう

4.2.2 評価

• コンパイラは変更なし
• 変更された命令：sを使うもの、conti, nuate, frame, return
  • frame, return: cons, car, cdrのかわりにpush, index, -を使うように
  • conti: 継続をつくるのにsave-stackを使うように
    • save-stack s: スタックの0からsまでをコピーしたベクタを返す
  • nuate: restore-stackを使うように
    • restore-stack v: ベクタvをスタックの0番目からコピーする(ベクタの長さを返す)

4.3 静的リンクをスタックに

• 動的リンクよりちょっと難しい
• まず、first-classな関数・代入・末尾再帰の最適化なしで考えてみよう

4.3.1 変数の値をフレームに入れる

• 静的リンクをスタックに→引数をフレームに入れる
  • 4.1と4.2を合体すればいい
  • が、4.1は一級関数・代入を考えてない
    • スタック上の静的リンクを保存しないといけないから
    • もちろんクロージャ作るたびにスタックをコピーすればできるけど、重すぎるｗ
    • 解決策は4.4で
  • 末尾最適化も考えてない
    • 最適化で呼び出し元のフレームをスタックから削除すると、呼ばれた関数内で呼び出しもとの変数を使ってたときに困る
    • 解決策は4.6で
  • 継続を考えると、代入も難しいよね
    • スタック上の変数束縛を再代入する→継続オブジェクトが保存してる変数と食い違う(multiple-update problem)
    • 継続は(コンパイラから見て)いつ生成・実行されるか(されないか)わからん
    • ということは、実行時にいくらかのコスト(代入にかかる時間、メモリ量)を払う必要がありそう
    • 解決策は4.5で

4.3.2 コンパイルと評価

• どちらも、4.1と4.2を足したかんじ
  • 引数はスタックに
  • 継続あり、一級関数・代入・末尾最適化なし

おなじところ

• スタックの構造
• 定数とかif式とか、単純なもの

4.1から：

• 引数・静的リンクをスタックに

4.2から：

• 継続の生成・実行

変更された関数：

• continuation s: return命令の変更に対応(スタックから取り除く数＝0)
• contiのつくるフレームは引数も静的リンクも含まないから

4.4 display closure

• 一級関数は特別な情報を必要とする(継続もそうだったね)
  • 継続の場合：継続開始点からの動的リンク全部＋必要そうな静的リンク
  • クロージャの場合：静的リンクのみ
  • なので、スタックごとコピーすると無駄が多すぎる
• 静的リンクの一部だけ(関数が必要とする値だけ)を取り出そう
  • この関数オブジェクトを "display closure" という。
  • display closureの生成・メンテナンスは、他の伝統的なブロック言語における"display"の実装に似ている

4.4.1 displayとは

• スコープのネストがある言語では、深いところの自由変数にアクセスするのに静的リンクを全部たどるのは遅い
  • ネストの1レベルごとに必要なメモリが増えるから
• displayはこれを解決するもの
  • displayは"display pointer"の配列(静的リンク上の各フレームを指す)
    • display pointerはたいていレジスタか高速なメモリに置かれるので、ネストの最大数が制限されてることが多い
  • ネストの最大数はコンパイル時のプログラム解析で分かる
  • displayを使えば、どの自由変数も1回のメモリ参照で値を得られる

• displayがあれば静的リンクはもういらない
  • 同じ情報がdisplay pointerの列で表されている
  • コストはそう変わらん

• 一級関数があるとdisplayはちょっと難しい
  • 普通は、現在のdisplayにdisplay pointerをつけ足していく
  • でもクロージャは、全く別のdisplay pointerの列から作られてるかもしれない
  • つまりクロージャの実行には、クロージャの属するdisplayの情報を必要とする

4.4.2 display closureを作ろう

• display＝静的リンク内の各フレームへのポインタの配列
  • なんだけど、display＝あるフレーム中の値へのポインタの配列　だったとしたら？
    • 要素数は増えるかもしれないし、減るかもしれない (各フレーム中について、必要な変数の値は0個〜複数)
    • が、現実には、外側の自由変数をいくつも使うってケースはレアなので、大抵減る

この改造のメリット：

• 普通のdisplay→ポインタを辿って、フレーム内の値を探す
• 改造後→ポインタを辿ったらそれが値だった

• もう一歩進めて、display＝実際の値の配列　という風にしたとしたら？
  • ポインタを辿る必要すらない
  • 結局、必要なのは値だけ (値は保存しないといけないよ：クロージャはそれを作った関数より長生きするかもしれないから)

display closureによる一級関数の実装

• functionalの代わりにdisplay closureを作り、メンテする
• display closureはコード本体に加え、自由変数の値のコピーを持つ。これが静的リンクの代わりになる

例1：((lambda (x) (lambda (f) (f x))) 'a)

• このとき、内側のlambdaに対応するdisplay closureは
  • [(λf.f x に対応するコード), 'a]
  • このxは配列の2番目に置いてある'aを参照する

例2：((lambda (x y) (lambda (f) (f x y))) 'a 'b)

• 内側のlambdaに対応するdisplay closureは
  • [(λf.f x yに対応するコード), 'a, 'b]
  • xは'aを、'yは'bを参照する

display closureの作り方

1. コンパイル時に、自由変数の一覧を計算する
2. 自由変数の値を取得し、クロージャ内に格納する

4.4.3 自由変数を見つける

• 自由変数とは、参照されるのに束縛されてない変数のこと
• 1つの方法は、束縛された変数を覚えながら式を再帰的にたどっていく方法

新しい関数：

• find-free x b: 式xの中の自由変数を見つける(bは既に束縛されている変数の一覧)
  • 式の種類によって分岐する(quote, lambda, if, 定数, 変数...)

• 変数のとき
  • その変数がbに含まれていれば、それは束縛変数 → '()を返す
  • 含まれてなければ、それは自由変数 → '(x) を返す
• それ以外のとき
  • 式の中の自由変数＝サブ式の中の自由変数の合計
  • 例：lambda のとき：
    • lambdaの本体(body)の中を探す
    • このとき、lambdaの引数部分は束縛変数として扱う

新しい関数：

• set-member?, set-union: 集合の演算 (pdfではリストを集合がわりに扱っている)

4.4.4 コンパイル

• 各lambda式について自由変数を探し、display closureに格納しなければならない
• また、2種類の変数を参照できなければならない
  • 現在のフレームに入っているもの(ローカル変数)と、現在の関数のdisplay closureに入っているもの(自由変数)

変更点：

• 最も大きいのは、lambda式の扱い
  • find-free関数で自由変数を集め、collect-free関数でその値を取ってきてdisplay closureに入れる
  • collect-freeは argument命令の列を生成する(これを実行すると、自由変数の値が一つずつスタックに積まれていく)

• compile-refer: 変数参照のときとcollect-freeの中から呼ばれる
  • 変数参照は2箇所探さないといけない(スタック中のcall frameか、現在の関数のdisplay closure内)
  • 内部でcompile-lookupを使っている
    • compile-lookupは関数を2つ取るようになった(compile-lookup x e f1 f2)
    • 一つは自由変数だったときに呼ぶ関数、もう一つはローカル変数だったときに呼ぶ関数
    • eはコンパイル時の環境(ローカル変数のリストと自由変数のリストのペア)

俺メモ

• find-free →collect-free

1. find-freeがSetを生成する(順序はset_unionに依存)

4.4.5 評価

新しい命令：

• refer-local, refer-free (referの代わり)

変化した命令：

• close, frame, return

新しいレジスタ：

• c (closure) : クロージャ外の自由変数を参照するときに使う
• f (frame) : eから改名 (環境は現在のフレームと現在のクロージャに分けて保存されるようになったので)

新しい/変化した命令まとめ

• refer-local n x: 現在のフレーム(fレジスタ)のn番目の値(引数)をaレジスタにロード ←let式がないので、ローカル変数＝関数の引数　であることに注意
• refer-free n x: 現在のクロージャ(cレジスタ)のn番目の値(自由変数)をaレジスタにロード
• close n body x: bodyとスタックの上からn個の値(=自由変数の値)を組み合わせてクロージャを作る。クロージャはこれらのベクタで表される。作ったクロージャをaレジスタに置く
• frame ret x: fレジスタだけでなくcレジスタも保存するように(c, f, retの順にスタックに積む)
• return n: fレジスタだけでなくcレジスタも復元するように(スタックのn番目から順にx, f, cを復元する)

新しいヘルパー関数(実行時の)：

• closure body n s: クロージャ(ベクタ)を作る関数
  • ベクタの0番目はbody
  • ベクタの1番目から引数(全部でn個)が入る
  • 引数の値はスタックのs番目から積まれている
• closure-body c: クロージャc内のbodyを取得する (単にベクタの0番目を参照するだけ)
• index-closure c n: クロージャc内のn番目の引数を取得する (ベクタのn+1番目を参照するだけ)

新しいevaluate:

• a:空リスト、x:コンパイルされた式、f(現在のフレームへのポインタ):0、c:空リスト(正しいプログラムは自由変数を含まないはずなので、この空リストの中身は参照されないはず)、s:0

俺メモ：

• close -> refer-freeなので、closeの前が問題

4.5 代入をサポートしよう

• 同じ変数が2箇所以上に存在する問題
  • 4.2で、継続を作るたびにスタックを丸ごとコピーするようにした。
  • 4.3で、変数束縛をスタックに置くことにした。
  • ということは、継続を作ると同じ変数への束縛が2箇所(以上)に存在することに
  • 4.4で、自由変数の値をクロージャに保存するようにした
  • ということは、クロージャを作ると自由変数への束縛が2箇所(以上)に存在することに

• 変数に値が代入されたら、全部のコピーを更新しないといけない
  • コンパイル時に、ある変数がどのクロージャや継続オブジェクトに含まれるかを調べることはできない
    • 実行時に値の変更をチェックして束縛をアップデートするしかない
    • 変数間のリンクも必要
    • これじゃあ、「メモリ量を減らし変数アクセスを高速化する」っていう目的に反しそう
• 一方、全ての変数に環境を使うのは無駄が多い(schemeのプログラムは代入をあまり使わないので)
  • 解決策：boxを使う
    • boxはヒープ上に置かれる値がひとつだけ入ったオブジェクトで、代入された変数ごとに1つずつ用意される
    • フレーム内に変数の値を直接置くのではなく、boxへのポインタを経由して参照するようにする
    • 継続オブジェクトやクロージャを作るときは、boxへのポインタを複製する
  • こうして、可能な最小限の努力でフレーム・スタックのコピー・display closureの間で変数束縛を共有することが可能になったのであった。
• 幸運にもレキシカルスコープのおかげで、コンパイル時にどの変数が代入され得るかがわかる。
  • 各変数のスコープ内のset!式を調べれば良い
  • もしこれができなければ全ての変数にboxを用意しないといけないわけよ。
• ヒープベースのときは、呼び出し元の関数が引数の入ったribを作っていた。
  • が、呼び出し元の関数は、呼び出す関数がどの引数にset!を行うか知ることができないので、呼び出し元関数がboxを用意するわけにはいかない(呼び出された関数が自分で用意する)
  • というわけで、関数呼び出しの時は：
    • まずフレームヘッダのあとに引数をpushする
    • 呼び出された関数に制御が移ったら、本体の実行前にboxのアロケートを行う
• 代入されない(unboxed)変数については今までのまま
  • 代入される(boxed)変数は、参照の経路が1段だけ長くなる
• クロージャを作るときに自由変数を探すプロセスは(boxedな変数についても)変わらない
  • クロージャはboxではなく値を必要とするから //って、それが代入されたら…????

こっから余談？？

• boxを使うのは、参照渡し(call-by-reference)に似てる
  • 同じところ：どちらもポインタ経由で値を得るし、どちらも代入を共有するのが目的
  • 違うところ：参照渡しでは値はヒープでなくスタックに置かれることが多いし、参照自体を作るのは呼び出しもとの関数である。
• CardelliのML処理系では、一級関数の実装にdisplay closureと本質的に同じオブジェクトを使っている
  • が、代入はサポートしていない(MLに代入はない)
  • 代わりに参照型があり、これはboxの構造と同じ
  • 実際、代入をプリプロセッサでbox/unboxに置き換えることもできる(OrbitというT言語のコンパイラとか)。
• これはbox・継続・クロージャに関する改善になり得るが、schemeには適さない
  • boxを作らなくていいのは、以下のようなプログラムのとき
    • 代入された変数があるときに継続が生成されない
    • 変数を参照・代入するようなクロージャを作らない(?)
  • 1個目の条件が成り立つかコンパイル時に判断するのは難しい
    • スコープ外の関数を呼び出す全てのところで、継続が作られる可能性がある
  • 2個目の条件は簡単
    • クロージャ内の自由変数のリストを調べればいい
  • なので、Common Lispとか一級関数・代入はあるけど継続がない言語ならこの最適化が可能
    • boxを作る条件に「代入される」だけでなく、「自由変数になり得る」を加える

4.5.1 コンパイル

• box対応でのもっとも興味深い変更点は、lambda式中の代入される変数を探してboxを作るところ
  • 探し方は、自由変数を探した方法と同じ
  • find-sets x v: 変数群vのうち、代入されるものを見つける

• find-setsとfind-freeの違い
  • 1. find-setsは参照ではなく代入を探す
  • 2. find-setsはvに含まれてる変数を調べる。find-freeはvに含まれてない変数を調べる
  • ただしfind-freeの定義はちょっとだけ変わる(set!式も調べるように)

• lambda式中でどれが代入される変数かわかったら、それぞれについてboxを作る
  • make-boxes sets vars next: 代入される変数(sets)と引数リスト(vars)からboxingのコードを作る

• compile関数に引数sが増えた
  • どの自由変数が代入されるか
  • 変数の参照、代入、lambda式のコンパイル時にsを変更する

4.5.2 実行

新しい命令：

• indirect x: box(aレジスタに格納されている)経由で値を取り出す
  • indirect命令を用意せず、refer-local-indirectとrefer-free-indirectを用意する実装も考えられる。
  • これは多少速いが、モジュール性に欠ける
• box n x: スタックトップからn番目の値を取り出し、それの入ったboxを作り、boxへのポインタを元の場所に置く
• assign-local n x: refer-localに似ているが、値を参照するのではなく(box経由で)書き換える
• assign-free n x: assign-localに似ているが、スタックを見るのではなく現在のクロージャを見る

4.6 末尾呼び出し(の最適化)

<末尾呼び出しの時は単にフレームを作らないだけでなく、スタックに積んである元の関数の引数も消してやらないといけない。→shift命令>

• ヒープベースのときは、単にフレーム作るのを避けることで最適化していた
  • スタックベースもいっしょ
  • だけど、フレーム本体だけでなく変数束縛もスタックから取り除いてやらないといけない
  • これは言うほど簡単じゃない
  • というのは、それ以降参照される可能性がある変数は取っちゃいけないから

• 静的リンクがある言語では、現在のフレームの外の変数を参照できるので、いらないフレームの変数が長生きしてしまうことがある
  • ので、末尾呼び出しは場合によっては最適化できない
  • 一般的に言うと、呼び出された関数が呼び出し元関数のスコープにリターンする可能性のあるときに、呼び出し元関数のフレームをスタックから取り除くことはできない(??)
  • 引数に関数を渡すような処理だとこれが起こる(最初の呼び出しがスコープ外へだったとしても)

• しかし、C言語のような関数定義がネストしない言語では最適化が可能(末尾呼び出しが呼び出し元関数のスコープへ返ることはないので)
  • ブロックのネストを許しても、新しい変数が現在のフレーム内におさまるなら問題ない
  • さらに、ネストしたブロックが無引数関数の呼び出しと見なせるなら、そういう呼び出しは末尾呼び出しとは見なされない (??)

• display closureを利用した実装では、末尾呼び出しを実行したらもう関数の引数はスタックから取り除いてよい
  • それでも、一般的には、末尾呼び出しされる関数の引数を評価してスタックに積むまでは変数束縛をスタックから取り除くことはできない
  • 結果として、開放されるフレームは引数より下にないといけない(?)

4.6.1 引数のシフト

• フレームヘッダ(frame命令がプッシュするもの)は
  • (a) 呼び出し元のdisplay closure (＝コード＋参照する値)
  • (b) 呼び出し元のフレームポインタ (＝フレームのスタック上での位置)
  • (c) 呼び出しが終わったあとに実行する残りの処理
  • から成る。
  • これらの情報は呼び出される関数に依存しない。
  • 末尾呼び出しを呼び出しではなく「ジャンプ」だと考えると、呼び出された関数が新しい関数を末尾呼び出し(=ジャンプ)する際にこれらの情報を変更する必要はない。
  • 結局、末尾呼び出しはフレームを新たに作らず、スタック上のフレームをそのまま残す。

• けれども、(上で見たように)末尾呼び出しが実行される直前には呼び出しもとの関数の引数がスタックに残ったままなので、呼ぶべき関数はその下にある。
  • 例えば以下のようなコードがあったとき：

(let1 g (lambda (x) x)
  (let1 f (lambda (x y) (g y))
    (h (f 'a 'b))))

• • この式は関数f, gを作る。fは最後にgを呼んでその返り値を返すので、これは末尾呼び出しである。
  • fを呼んだ結果はhの呼び出しの引数になっている(hはどこか外側で定義されている関数)。
  • fの呼び出しは末尾呼び出しではない(fの実行結果をそのまま返すわけではないから)
  • fが呼ばれたとき、スタックの上の方は以下のようになっている

 'a
 'b
 [fを実行したあとの式]
 fの呼び出し元のフレームへのポインタ
 fの呼び出し元のdisplay closure

• • fの中でgを呼び出す直前には：

 'b (gの引数)
 'a (fの引数)
 'b (fの引数)
 [fを実行したあとの式]
 fの呼び出し元のフレームへのポインタ
 fの呼び出し元のdisplay closure

• • しかし、gが呼ばれたときにはfの引数はもう要らないはず。

 'b (gの引数)
 [fを実行したあとの式]
 fの呼び出し元のフレームへのポインタ
 fの呼び出し元のdisplay closure

• • • 最も簡単な実現方法は、末尾呼び出し元の関数の引数の数だけスタックをシフトすること
    • このため、引数は上に積んだほうが良い(gの引数とfの引数が離れていたら、シフト操作はもっと複雑になる)
  • このスタックレイアウトでは、引数をシフトするときにフレーム情報を保存しないといけなかったり、シフトを複数回行わないといけない可能性がある(末尾再帰のように、呼び出し元と呼び出し先で引数の数が同じでない限り)

4.6.2 コンパイル

• 変更はcall/ccと関数呼び出しのみ
  • 末尾呼び出しを最適化するには、
    • 末尾呼び出しのときはフレームを作ってはならない
    • 末尾呼び出しのときはshift命令を入れて、新しい引数を古い引数で上書きする

4.6.3 評価

新しい命令：

• shift n m x: スタックトップからn個の要素を、m個だけ下にずらす

新しい関数：

• shift-args n m s: スタックトップからn個の要素を、m個だけ下にずらし、新しいスタックポインタを返す

4.7 できそうな改善

• 4.6の最終バージョンは(著者が作った)Chez Schemeの構造と本質的には同じである。
• が、真面目に実装するならもっと機能を増やしたり効率化しないといけない
• これらのいくつかを紹介する。
  • 他には4.5の"segmented stack"の話とか、4.7(6?)のboxを避ける話とか

4.7.1 グローバル変数とプリミティブ関数

• まともなScheme処理系はリスト操作とか、数値演算とか、その他のプリミティブ関数を用意している
• これらはプログラムのどこからでも参照可能なので、グローバル変数として管理するのが便利だろう
• グローバル変数はユーザ定義関数を使えるようにするのにも役立つ
• ユーザ定義関数は、
  • 互いに、任意の順序で呼び出しあって良い
  • 再定義してもよい(バグのあるプログラムにパッチを当てるとかのため)

• ナイーブな実装：
  • 他の変数と同じようにグローバルな束縛を用意し、これらを参照する全ての関数のdisplay closureに自由変数として突っ込む。
  • この実装だと、全てのグローバル束縛はbox化されていないといけない(いつ再代入されるかわからないため)。
  • これは単純だがメモリ効率が悪い(display closureがでかくなる)。

• よりよい実装：
  • プログラマが入力したコード中でグローバル束縛を参照している部分を、全てその束縛へのboxに置き換える。
  • ※グローバル変数はいつ書き換えられるかわからないので、全てboxを経由しなければならない

4.7.2 関数を直接実行する

• 「クロージャを作ってそれを呼び出す」のはちょっと手間である。(let式とか)最適化したい。
• 直接実行する関数の変数は、C言語におけるブロックローカル変数にあたる
• クロージャとフレームを作る代わりに、これらの変数をスタック上のフレーム内に置いてしまうことができる。
  • フレーム内のスペースを切り詰める(?)か、フレームを必要に応じて拡張する
• C言語：スタックフレームを作るのが省ける
• Scheme：直接実行される関数の自由変数を集めるのと、クロージャを作るのを省ける

4.7.3 末尾再帰の最適化

• Schemeではループを実装するのに再帰が使われる(他に繰り返しの構文はない)。
  • このとき、再帰呼び出しが末尾位置にしか来ないことが良くある。
  • 解析によってこのことが分かったとき、再帰に使われる関数名が再代入されないならば、再帰呼び出しはただのジャンプに変換できる。
    • これによって、再帰関数をdisplay closureから参照する手間が省ける。
    • あと引数個数のチェックとかを飛ばせる。

• さらに、関数が直接呼び出されるとき(named letとか)、クロージャを作るのも省略できる(4.7.2と似たような感じで)。
  • これによって、Cなど伝統的な言語で使われるループ関係の最適化を適用できるようになる。

4.7.4 クロージャをヒープに作らない

• ある条件が成り立てば、クロージャをヒープでなくスタックに作ったり、そもそもクロージャを作るのを省いたりできる。
  • 条件：クロージャが、それを作った関数より長生きしないとき。
  • 例：以下のfは、クロージャを作る必要がない

(let ((f (lambda (x) (+ x x))))
  (f 3))

• 逆に、ヒープに作らないといけないとき：
  • クロージャが別の関数に渡されるとき (その中で保存されるかもしれない)
  • クロージャが関数の戻り値であるとき

4.7.5 継続をジャンプに

• 継続はよく帯域脱出(nonlocal exit)に使われる。
  • 例：ファイル中の各数値を足し合わせる関数(数値以外を見つけたら'errorを返す)

 (define (sum-input file)
   (call/cc 
     (lamdba (quit)
       ...
       (if error?
         (quit 'error)
         loop))))

• • (call/ccを使わずにもっと簡単に書けるけど、例なので許して)
  • ここでquitは単にループの終わりを指すラベルであり、ループ中でquitを呼ぶことは単なるラベルへのgotoといっしょ
  • 洗練されたコンパイラなら、これを(重たいスタックコピーでなく)適切なラベルとジャンプに変換できる。