3impメモ

3imp http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

3章　ヒープベースモデル

• rib: 関数への実引数を保持
• 関数呼び出し：frame作成 -> argument …で実引数をribに積んでいく -> applyでクロージャを実行 -> returnで戻る

4章　スタックベースモデル

• 4.1 標準的なブロック構造言語の、スタックベースモデルの実装（関数は第一級じゃない、継続はサポートしない、末尾呼び出しなし）
• 4.2 ヒープベースモデルをベースに、ダイナミックチェーンだけスタックに乗せる
• 4.3 スタティックチェーンもスタックに乗せるが、関数は第一級じゃなくなり、末尾呼び出しもなくす、代入もサポートしない、継続はサポート
• 4.4 クロージャのサポート
• 関数への実引数はスタックに、内部に登場する自由変数はクロージャオブジェクト中にコピーとして値が直接配列に保持される。

3.1 モチベーションと問題

• 典型的なレキシカルスコープの言語（Algol 60, C, Pascalなど）はコールフレームを実際のスタック上に記録している
• コールフレームはリターンアドレス、変数バインディング、前のフレームへのリンク、あと時々追加情報を持つ
• Schemeだと１級クロージャや継続があるので、この構造は充分でない。変数バインディングはスタックでは保持できない。ヒープに確保した環境に実引数を保持し、この環境へのポインタをスタックに置く
• ヒープの確保・解放や環境へのアクセスに時間がかかる

3.2 データ構造

• ヒープベースのシステムは、５つのデータ構造でコア言語をサポートする：環境、コールフレーム、制御スタック、クロージャ、継続
• 環境：変数のリストと値のリスト（3.4で値のリストだけに改善する）
• フレームと制御スタック：フレームは別の計算を行うときに、中断する計算の状態を記録する。これはある関数が他の関数を呼び出すときに作られる。フレームはリターンアドレス、環境やそれと同等な変数バインディング、前のフレームへのポインタ、そして他に続きの計算に必要な状態を保持しなければならない。
• クロージャと継続：略

3.3 実装戦略

• ５つのレジスタ
  • a: アキュムレータ
  • x: 次の式
  • e: 現在の環境
  • r: 現在の値rib
  • s: 現在のスタック

3.4 ヒープベースモデルの実装

3.4.1 アセンブリコード

• (halt): 停止
• (refer var x): 変数varの値を現在の環境から探してアキュムレータに置き、xを次の式にする
• (constant obj x): objをアキュムレータに置き、xを次の式にする
• (close vars body x): body, varsと現在の環境からクロージャを作る
• (test then else): アキュムレータを調べ、真ならthenを次の式に、そうでなければelseにする
• (assign var x): 現在の環境の変数varをアキュムレータの値に変更し、xを次の式にする
• (conti x): 現在のスタックから継続を作り、それをアキュムレータに置き、xを次の式にする
• (nuate s var): sを現在のスタックとして復元し、アキュムレータを現在の環境のvarの値にし、(return)を次の式にする（以下で説明）
• (frame x ret): 現在の環境、rib、そしてretを次の式としてフレームを作成し、このフレームを現在のスタックに足し、現在のribを空にし、xを次の式にする
• (argument x): アキュムレータの値を現在のribに追加し、xを次の式にする
• (apply): アキュムレータに入っているクロージャを現在のribにある値のリストに適用する。正確には、この命令はクロージャの変数リストと現在のribでクロージャの環境を拡張し、その新しい環境を現在の環境にセットし、現在のribを空リストにし、クロージャの本体を次の式にする
• (return): スタックから最初のフレームを取り除き、現在の環境、現在のrib、次の式、そして現在のスタックをリセットする

3.4.2 変換

3.4.3 評価

3.5 変数アクセスの改善

• Schemeは静的スコープなので、変数が実行時の環境のどこに登場するかが、ソースから正確にわかる

4章　スタックベースモデル

• ヒープベースモデルの実行の大半は変数参照と関数呼び出しにかかっていて、クロージャの生成や継続の生成と呼び出しはそれほどかかっていない。これはプログラミングスタイルに悪影響を及ぼしてしまう。

4.1 ブロック構造言語のスタックベース実装

• 標準的なブロック構造言語（第一級クロージャを持たない）の実装を説明する。関数は引数として渡せるが、第一級ではなくスコープ外からの呼び出しは保証しない。

4.1.1 コールフレーム

• コールフレームは関数が引数に適用されるときごとに作られる。この節で説明するスタックモデルのコールフレームは、1.中断された呼び出しのコールフレームが保持しているフレームポインタ（ダイナミックリンク）、2.リターンアドレス（呼び出し後の次の式）、3.呼び出された関数への引数、4.呼び出された関数の次の外側のスコープのコールフレームが保持しているフレームポインタ（スタティックリンク）

4.1.2 ダイナミックリンクとスタティックリンク

• ダイナミックリンクは常に呼び出し元のフレームを指す。これは関数から戻るときに次のフレームがスタックのどこにあるかを決定するために使われる。ダイナミックリンクはときには必要でない、なぜなら次のフレームは常にスタック上の現在のフレームのすぐ下に配置されていて、コンパイラがそれぞれのフレームサイズを知っていると仮定すれば。
• 他方スタティックリンクは常に呼び出された関数を包む関数のフレームを指す、そのフレームは呼び出された関数から見える変数バインディングを保持する。言語がクロージャや末尾呼び出しや継続をサポートしないという仮定は重要で、それによりこのフレームがスタック上にあることを保証する。
• ヒープベースでもスタティックとダイナミックチェーンは存在するが、それぞれは独立している。

4.1.3 関数 (functional)

• あれこれ
• 関数はそれを生成したところの外側では生存しない（それゆえ、それを生成したスコープが抜けた後には使われない）ので、list操作によるヒープ確保は必要ない。スタック上のコールフレームに関数を作るほうが適切かもしれない。しかしコールフレームを簡潔に保つため、その改善はここでは採用しない。

4.1.4 スタック操作

• スタックベースモデルとヒープベースモデルの実装の主要な違いは、自然に、コールフレームと変数バインディングがヒープに確保されたリンク構造の代わりに実際のスタック上にあることだ。この違いは思ったほど実装に影響しない。
• push, index, index-set!

4.1.5 変換

• 3.5節のコンパイラから3つのマイナーな変更
• １：関数への引数が直接コールフレーム上に配置され、コールフレームのサイズは引数の数によって変わる。バーチャルマシンのreturn命令はコールフレームを取り除く責任があるので、この情報を持つ必要がある。return命令に引数nを追加し、それがスタックからいくつ取り除くかを示す。スタティックリンクもスタック上に保持されるが、それもカウントに含めておくので明示的には取り除かれない（nが引数の数+1になっている）。
• ２：末尾呼び出しはサポートされないので、関数適用時のコードのtail?が削除された
• ３：継続は完全に削除

4.1.6 評価

• バーチャルマシンは3.5節と似たような構造で、ほとんど同じ命令をサポートする。アキュムレータaと次の式xレジスタはまったく同じ用途で、環境eとスタックsは異なる使い方。eレジスタは環境のようなものを保持するが、これはスタックポインタで次の外側のスコープのコールフレームを指す。sレジスタは現在のスタックのトップを指す。現在のribを保持していたrレジスタは削除された。引数はヒープに確保されたrib上ではなく直接スタック上に置かれるようになったため。
• find-linkヘルパー関数は3.5節のヒープベースモデルのlookup関数の外側のループと似ている。2つの引数を受け取り、eから始まるスタティックフレームのn番目のフレームを返す。

4.2 スタック確保のダイナミックチェーン

• この節と次の節は3.5節のヒープベースモデルを１歩ずつ前の節で示されたスタックベースモデルに近い効率に置き換えていく
• この節ではダイナミックチェーン、またの名を制御スタックを実際のスタックに配置する。スタティックチェーン、またの名を環境はヒープのまま。主な困難さは継続のサポートである。継続はダイナミックチェーンを、削除されたり上書きされた後も保持し復元できなければならない。

4.2.1 スナップショット継続

• ここでとられる解決方法は、スタックのコピー、すなわちスナップショットを継続に格納し、継続が呼び出されるときにそのコピーを復元する。
• この解決方法は機能するが、高いように感じるだろう。スタックはとても大きくなり、継続生成時の確保とコピーのオーバーヘッドや、継続呼び出し時のコピーのオーバーヘッドは大きい可能性がある。これが大きな問題にならない理由は、継続の生成と呼び出しは関数呼び出しに比べて稀だからである。

4.2.2 評価

• frameとreturnはスタックを見るようにして、継続はスタックのスナップショットを操作する

4.3 スタック確保のスタティックチェーン

• スタティックチェーンをスタック上に移動させるのはいくぶんか難しい。この節と続く３節で説明する。
• この節ではスタティックチェーンをスタックに移動し、第一級関数、代入、そして末尾呼び出しのサポートを除外する。続く３節でこれらの機能を取り戻す。

4.3.1 変数の値をコールフレームに含める

• スタティックチェーンをスタック上に移動するとは、制御情報がすでに入っているコールフレームに、関数への引数を置くことである。これは4.1節のスタックベースモデルと4.2節の修正ヒープベースモデルを混ぜることで達成できる。
• しかし、4.1節のシステムは第一級関数をサポートしていない、なぜならスタック上にあるスタティックチェーンの保持を要求するから。
• 末尾呼び出しもサポートしない、なぜなら変数バインディングが呼び出される関数で必要かもしれないので、呼び出しのフレームを削除することができるとは限らないから。
• さらに、継続が作られる可能性により、代入のサポートも難しい。スタックに確保された変数バインディングへの代入は継続の存在により扱いが難しい、なぜなら複数の更新の問題があるため。継続はスタックのコピーを持つため、同じスタックのコピーが１つ以上のメモリに存在することがある。もし4.1節のシステムのように変数バインディングがコールフレームに直接格納されると、変数の値は１つ以上の場所に格納されることを意味する。そのような変数への代入は、現在スタック上にあるものだけでなく、すべてのコピーの更新を要求する。
• これは深刻な問題で、なぜならコンパイラはいつ継続が生成されまた呼び出されるか検出できないため。そのため代入をサポートするために実行時に何か記録しておく必要があるが、これは代入を遅くさせ、追加のストレージオーバーヘッド（たぶんヒープ）を要求する。この問題の解決方法は4.5節。

4.3.2 変換と評価

4.4 表示クロージャ

• 第一級関数は継続と同じような問題がある。継続には、この情報は継続地点からのすべてのダイナミックチェーンと継続が必要とする変数バインディングを含むスタティックチェーンである。クロージャには、保持する情報の量はもっと小さい；１つのスタティックチェーンだけが必要で、ダイナミックチェーンは必要ない。
• この理由により、継続の生成時にしたようにスタック全体をコピーするのはとても非効率的である。代わりに、この節では関数が必要とする特定のスタティックチェーンだけ（実際には、特定の値だけ）を保持する戦略を説明する。新しい関数オブジェクト、表示クロージャを導入する。このオブジェクトの生成や維持はより一般的なブロック構造言語の表示(display)の生成や維持の実装と似ている。

4.4.1 表示

• 深くネストした関数やブロックのプログラムでは、特定のブロックの自由変数のアクセスはスタティックリンクを辿るため非効率的な可能性がある。スタティックリンクの走査はブロックレベルごとに１つ余計なメモリ参照を要求する。表示は自由変数のアクセスを改善するために用いられる。表示は表示ポインタの配列で、それぞれは現在のスタティックチェーンのフレームのアドレスを保持する。
• 表示のアプローチによりスタティックリンクは必要なくなる、なぜなら同じリンク情報は表示ポインタの集合で維持されているため。

4.4.2 表示クロージャの生成

• …

4.5 代入のサポート

• box