（関数の実行時データ構造の一般論）p.124

• 殆どの現代的なプログラミング言語では関数が呼び出される度に生成される局所変数を備えている。
• しばしばある一つの関数が同時に複数個実行され各々が局所変数のインスタンスを持つ。

• 関数fが呼び出される度にxのインスタンスが生成されfの呼び出し元によって初期化される。
• 再帰呼び出しの存在によって同時に複数のxが存在する。
• yについても同様に関数fが呼び出される度にインスタンスが生成される。

• 多くの言語(C、PascalやTiger)では局所変数は関数の実行が終了して呼び出し元に復帰すると破棄される。
• ここで、呼び出した関数が全て復帰した後に呼び出し元の関数は復帰するが故に、この挙動はLIFO風であると言える。
• 従って局所変数が関数の実行開始時に生成され終了時に破棄されるのならば、局所変数の格納にはLIFOなデータ構造、つまりスタックを用いることができる。

（関数の実行時データを格納するのにスタックを用いる際に問題となる機構：高階関数）p.125〜p.126

• 入れ子になった関数及び関数を値として持つ変数という仕組みを共に備える言語では関数の実行終了後にも局所変数を維持しなければならない！

• f(3)実行に際して新たな局所変数xが割り当てられる。
• f(x)の結果として関数gが返されるがgは呼び出されていないのでyはまだ生成されていない。
• f(3)が返した関数をh(5)として呼び出す際にx=3が必要となるのでf(3)の終了後もxは破棄できない。
• ところがこの間にf(4)が実行されxの異なったインスタンスが生成されてgの異なったインスタンスもx=4について返される。

このように（外側の関数の変数を内側の変数が使用できるような)入れ子になった関数宣言の仕組みと関数が値として返値になったり変数に代入できるような仕組みの組み合わせにおいて局所変数は関数の実行を越えた寿命を持つ。

• この問題について下表のように各種の言語についてまとめた。

• この中でMLやSchemeにあるように入れ子定義と関数を値として扱うという特徴を共に備えた機構を高階関数(higher-order functions)と称する。このような場合はそれ以外の場合とは異なりスタック内に全ての変数を保管することはできない。
• 高階関数の仕組みは言語の表現力を増すが実装には特別な工夫を必要とする。
• 以下この章では局所変数がスタックで保管できる場合を扱う。高階関数については15章で扱う。

(一般的なスタックフレームの概観)p.126〜p.128

• スタックとは言うもののここでは単純なpushとpopを備えただけのデータ構造ではなく、スタックポインタという特別なレジスタを備えたメモリ配列と見る。

• push、とpopという二つの操作を備えるデータ構造と言うのがスタックの最も単純な見方である。
• とはいえ、（関数の実行開始時に）局所変数を大きなまとまりとしてpushし（終了時に）大きなまとまりとしてpopしなければならないということになる。
• その上、必ずしも正しい方法で初期化されない局所変数が生成されてしまう。
• 最後に決定的なのは、多くの局所変数がpushされている時でもスタックの深いところにある変数にも引き続きアクセスしたいということである。

• スタック・ポインタ（stack pointer）は大きな配列のある場所を指している。
• スタック・ポインタが指している所までは使用中の有効なデータのために「割り付けられ（allocated）」ている。
• 一方、スタック・ポインタを越えた領域は未使用領域あるいは用済みの無効なデータ、つまり「ゴミ（garbage）」が存在している。
• 普通、スタックは関数の実行が開始さた際に全ての局所変数が保持できるように割り付けられている部分が増加されて「成長（grows）」する。
• そして関数の実行が終了する直前、割り付けられている部分が開始時に増加されたと同じ分だけ「縮む（shrinks）」
• 歴史的な事情で実行時のスタックは高位のメモリアドレスを起点に低位、つまり小さな値のアドレスに向かって成長する。（このことはどちらかと言えば混乱を呼びそうだが、スタックはツララの如く下に向かって成長し上に向かって縮む。）

• 関数が呼ばれるときにスタック内に確保される領域には局所変数だけでなく関数に与えられた実パラメータ、リターン・アドレス、その他関数が必要とする一時的なデータが含まれていて「activation record」あるいは「スタック・フレーム（stack frame）」と呼ばれる。
• スタック・フレーム内の配置設計は対象アーキテクチャにおける命令セットの特徴やコンパイルされるプログラミング言語に配慮して行われる。
• とは言うものの計算機製造者はしばしば全てのプログラミング言語、全てのコンパイラについてそのアーキテクチャ上で使用可能な「標準的」なフレーム内配置を規定する。
• その配置が特定の言語やコンパイラにとって最も便利なものの一つでしかないことは時折ある。
• しかしそのような「標準的」配置を皆で採用すれば、ある言語で書かれた関数がその他の言語で書かれた関数を呼ぶことができるようになるという少なからぬ利点を得ることができる。

• 現在実行中の関数に「渡された引数（incoming arguments）」。（技術的には呼び出し元関数のフレームの一部であるがフレーム・ポインタ（次節参照）から既知のオフセットを利用してアクセスできる。）
• CALL命令によって生成され、現在実行中の関数の実行終了後に（呼び出し元の関数内で）制御を戻す先の命令の位置を示す「リターン・アドレス（return address）」
• その関数の「局所変数（local variables）」の内レジスタに保持しないもの。
• レジスタに保持される局所変数のための場所を空けるために「退避される（saved）」レジスタの値。
• その関数が他の関数を呼び出す際に「渡す引数（outgoing arguments）」。

（フレーム・ポインタの説明）p.128

• 関数g(…)が関数f(a_1,…,a_n)を呼ぶと考えるときgを「呼び出し元（caller）」、fを「呼び出し先（callee）」と称する。
• fの実行開始時にスタック・ポインターはgがfに渡す引数の先頭のものを指している。
• fの実行開始時にスタック・ポインタSPからフレームの大きさを単に引くことによってfはフレームを割り付ける。
• かつてのSPの値は現在実行中の関数の「フレーム・ポインタ（frame pointer）」FPとなる。

• 幾つかのフレーム内配置においてFPは独立のレジスタを割り当てられている。
• 関数の実行開始時、古いFPは（フレーム内の）メモリ領域に退避され、新たなFPの値はかつてのSPの値になる。
• 逆に関数の終了時、FPの値はSPに書き戻され、退避されていたFPの値がFPに書き戻される。
• このような設計の場合、fの各実行に際してフレームの大きさは自由にできるし、スタック上でフレームが連続的に配置されていなくても良くなる。
• しかし、もしフレームの大きさが関数毎に固定されているなら、関数fの各実行に際してFPはSPの値から既知の定数を引いただけのものとなり、実際にレジスタを割り当てる必要がなくなる(つまりFPはSPにフレームの大きさを足した値を持つ架空のレジスタとなる)。

（レジスタの退避について）p.128〜p.129

• 現代の計算機は多くのレジスタを備えている(典型的には32個)。
• コンパイルされたプログラムを早くするため、局所変数や式の計算の中間結果やその他をスタックに置かずレジスタに保持することは有用である。

• レジスタの値は直接に算術演算命令の対象となる。
• 多くの計算機では（相対的にCPUの動作より遅い）メモリへのアクセスはレジスタへの読みこみとレジスタからの書き出しの命令に限定されている。
• またメモリ上の値を直接算術演算命令の対象とできる計算機であってさえもレジスタの値だけで演算したほうが高速である。

• 計算機は（通常は）ただ一組のレジスタの集まりを備えているが、様々な関数がレジスタを利用したがっている。レジスタを安全に利用するためには適宜退避させる必要がある。

• レジスタrを利用している関数fが、それ自身レジスタrを計算に利用する関数gを呼び出す。
• このときレジスタrの値は関数gがレジスタを用いる前に（スタック・フレーム内へ）退避され、gが使い終えた後でレジスタrへ書き戻す必要がある。
• ここで、退避と書き戻しの責任を負うべきであるのはどちらであるかが問題である。
• 責任を負うのが呼び出し元（caller）（ここではf）であるとした場合を「呼び出し元退避（caller-saved）」と称する。
• 責任を負うのが呼び出し先（callee）（ここではg）であるとした場合を「呼び出し先退避（callee-saved）」と称する。

• 殆どの計算機では「呼び出し元退避（caller-saved）」と「呼び出し先退避（callee-saved）」のどちらを実現する機構もハードウェアに組み込んではいない。
• が、ハードウェアのリファレンス・マニュアルにはどのような慣習に沿って行われるべきかが記述されている。
• MIPSの例

• 時折、退避は必要でないことがある。もしfがある変数xは呼び出しより後では必要でないと知っているならば、「呼び出し元退避（caller-saved）」のレジスタに格納して退避せずに置けば良い。

• 逆に何度かの関数呼び出しを越えて必要になることがわかっている局所変数iを関数fが持っているならば、「呼び出し先退避（callee-saved）」レジスタr_iに格納し、（fの実行開始時に）一度だけ退避して（fが終了する前に)一度だけ書き戻せばよい。
• 故に「呼び出し元退避（caller-saved）」レジスタと「呼び出し先退避（callee-saved）」レジスタを局所変数や一時使用領域毎に賢く選べば退避と書き戻しの回数が減らせる。
• レジスタ割り当て子が局所変数や一時的な値毎に適切な種類のレジスタを選ぶことに頼るようになるだろう。

（引数の渡し方について）p129〜p.131

• 1970年代に設計された殆どの計算機の呼び出し規約で引数はスタックを介して渡されていた。（1960年代以前はメモリ上に静的に割り当てられた領域を使って渡されており、再帰呼び出しを妨げていた。）
• このことはメモリとの不要なやり取りを引き起こす。
• 実際のプログラムを調べた研究によれば4つ以上の引数を持つ関数は相当稀であり、6つ以上の引数を持つ関数は皆無であった。
• 故に現代の計算機の呼び出し規約では関数の最初の引数k個（典型的にはk=4あるいはk=6）はレジスタr_p,…,r_p+k-1を介して渡され、残りはメモリを介して渡される。

• ここで関数f(a_1,…,a_n)（レジスタr_1,… ,r_nで各引数を受取るとする）が関数h(z)を呼ぶとする。
• zはr_1に渡されねばならないから、fは古いr_1の内容（値はa_1）をhの呼び出しに先立ってスタック・フレーム内に保存する。
• すると、レジスタ渡しによって回避したと考えていたメモリとのやり取りが発生している。どうレジスタを利用していたら時間が節約できたのか？

1. 関数を呼び出さない「末端（leaf…葉）手続き」と称する関数がある。末端手続きの割合に着目すると（楽観的な）見積もりとして平均的な関数呼び出しではそれ以上全く関数が呼び出されないか少なくとも2つの関数を呼び出すので、関数呼び出し関係から「木」を描くと末端でない内部の節点より末端の節点が多い。つまり最も多いのは末端手続きなのである。末端手続きは渡された引数をメモリに退避する必要がない。実際、しばしば全くスタック・フレームを必要としない。これは重要な節約である。
2. 全プログラムの全ての関数を一度に解析して「手続きを跨いだレジスタ割り当て（interprocedural register allocation）」を行う最適化コンパイラがある。この場合、レジスタに保持する局所変数と受取る引数について異なった手続きには異なったレジスタを割り当てる。故に例えばf(x)はxをr_1に受取るが、h(z)を呼び出す際にはzをr_7で渡す。
3. fが末端の関数でなくてさえ関数hの呼び出しに際して引数xの利用は多分終了している（技術的にはhが呼ばれた時点でxは「死んだ変数（dead variable）」である。）。この場合、退避することなしにr_1は上書きできる。
4. 「レジスタ・ウィンドウ（register windows）」という仕組みを備えているアーキテクチャがある。レジスタ・ウィンドウは関数が実行されるたびにメモリとのやり取りなしに新規のレジスタを一組提供する。

• 理想的にはfの実装だけの問題。率直なやり方でいけば呼び出し元はa_1,… ,a_kをレジスタで渡し、a_k+1,… ,a_nを自身のフレームの後端（図6.2で「渡す引数（outgoing arguments）」と記されている部分）の呼ばれた関数の「渡された引数（incoming arguments）」となる部分に置く。レジスタの引数を退避する必要があるなら局所変数と記されている部分に置けば良い。

• C言語では引数についてもアドレスが取れて、全ての引数は連続的なアドレスを持たなくては行けない。
• 連続的であることはprintf()などが利用しているvarargs機能のために必要である。
• プログラマがアドレスを取れることはフレームの外の無効な値を参照するなど「ぶらさがり参照（dangling reference）」の問題を引き起こす（例えばint* f(x){return (&x);}）。
• これがバグを引き起こさなくてさえ、連続的なアドレスということはコンパイラとスタックフレーム内配置をより複雑に制約する。最初のk個の引数がレジスタで渡され、かつ連続したアドレスを持つという矛盾を解決しなければならない。
• このため関数の実行開始時に最初のk個の引数はレジスタで渡される一方、全ての引数はアドレスが取れるようにメモリ上にも書き出す。printf()の要求を満たすためには当然書き出す場所はk+1,k+2番目の引数と連続していなければならない。
• C言語においてはある引数とそれ以外の引数が別の場所に退避されてはならず、連続的に退避されねばならない。（可変個であってさえもそうなので関数が呼び出されるまでスタックフレームの大きさが確定しない。）

• 現代の標準的な計算機の呼び出し規約ではレジスタ渡しする引数の退避領域もスタックフレーム上k+1番目の引数に続いた場所に準備する。
• が、呼び出した関数は実際にそこへ値を書き出したりはせず、呼び出された関数が、何らかの理由で必要なときだけそこへレジスタの内容を退避する。

• 局所変数のアドレスを取って利用するためのより品位ある方法として「参照渡し（call-by-reference）」がある。

• 参照渡しによればプログラマが表立って変数xのアドレスを操作することがなくなる。
• 変数xが関数f(y)の引数yに参照渡しで渡されるとするならば、プログラマの代わりにコンパイラがxのアドレスを取って関数に渡すコードを生成し、渡された関数ではその引数yを介してxを利用する部分に参照外しのコードを追加する。
• 参照渡しを用いればfが終了した後でyが現れることはないし、xの寿命が終る前にfは終了するので「ぶらさがり参照（dangling reference）」の問題は発生しない。（C++の参照型では返値にするなどできるので必ずしもそうではない。）

（戻り番地について）p.131

• 関数gが関数fを呼ぶとき、いずれfは終了復帰しなければならないのでどこへ戻ったらいいかをfは知っている必要がある。gのcall命令のアドレスがaであれば、その正しいアドレスは（通常は）gにおける次の命令のあるa + 1である。これを「戻り番地（return address）」と呼ぶ。
• 1970年代の計算機ではcall命令の実行中にスタックへ戻り番地をpushしていた。
• が、現代の研究成果によって戻り番地はレジスタに入れて渡したほうが余計なメモリとのやり取りを削減し、ハードウェアに特別な規制を課さないのでより高速で柔軟であることが示された。
• 現代の計算機でcall命令は単に指定されたレジスタに戻り番地を保管するだけである。末端でない手続きだけが（「手続きを跨いだレジスタ割り当て（interprocedural register allocation）」が行われていなければ）その値をスタックに書き出すが、末端手続きではその必要もない。

（値がスタック・フレーム内に置かれる場合のまとめ）p.131〜p.132

• 以上のように現代の手続き呼び出し規約では関数の引数、戻り番地、そして関数の返値もレジスタを介して渡る。多くの局所変数や式の中間計算結果もレジスタに割り当てられるだろう。

1. その変数は参照渡しされ、メモリ上にアドレスを持つ必要がある。（あるいはその変数はC言語で&演算子によってアドレスを取られる。）
2. その変数はそれが定義されている関数の中で入れ子に定義されている関数からアクセスされる。（とは言え、「手続きを跨いだレジスタ割り当て（interprocedural register allocation）」が行われているなら、レジスタに置かれていても入れ子になった関数はその変数にアクセスできるので構わない。）
3. その変数の内容は一つのレジスタに置くには大きすぎる。（とはいえ、効率のため大きな値を幾つかのレジスタに展開するコンパイラもある。）
4. その変数は配列にあり内容を取り出すには配列演算が必要である。
5. その変数を保持しているレジスタが特別な目的（既に述べた引数渡しのためなど）のために必要になった。（もっともコンパイラはメモリに退避せずに他のレジスタに置こうとするだろう。）
6. 局所変数や一時的な値が多すぎて全てをレジスタに収め切れなくなり、それらのうちの幾つかをスタック・フレームに「こぼし（spilled）」た。

• 参照渡しされる変数、（Cの&演算子を用いるなどして）アドレスが取られる変数、そして入れ子になった関数からアクセスされる変数は「抜け出し（escapes）」ていると称する。
• 仮引数や局所変数の宣言された時にそれらの場所が（レジスタかスタック・フレームか）決定できれば便利であるし、プログラムを処理する過程の中で適当でもある。そうであれば式の中でそれらが現れたとき正しい場所を参照するコードに翻訳できる。
• しかし不幸なことに、それら定義はそれ自身では十分な情報を明らかにしない。コンパイラが変数の定義を見つけた段階ではそれらが参照渡しされたり、（Cの&演算子を用いるなどして）アドレスが取られたり、そして入れ子になった関数からアクセスされたりするかどうかは判らない。その上、一体幾つのレジスタが計算に必要になるかわからない。（幾つかの局所変数はレジスタに置かずにスタックに置くほうが望ましいだろう。）
• 産業用（industrial-strength）コンパイラは暫定的な場所を全ての仮引数と局所変数に割り当て、後で本当にレジスタに置くべきものを決定する。

（ブロック構造の実現）p.132〜p.134

• （Pascal、MLやTigerのような）入れ子の関数宣言を許す言語において内側の関数は外側の関数で定義した変数をつかってよい。言語のこのような特徴を「ブロック構造（block structure）」と称する。

1. 関数fが呼ばれたらその関数宣言を囲むように定義されている関数のフレームへのポインタを渡すことができる。このポインタを「スタティック・リンク（static link）」と称する。
2. 最近に実行を開始した手続きから「関数宣言が静的に入れ子になった深さ（static nesting depth）」がiであるような関数のフレームへのポインタがi番目に収められた配列が維持できる。この配列を「ディスプレイ（display）」と称する。
3. 関数gが関数fを呼んでいるとき、関数fから実際にアクセスされる関数gの各変数を追加の引数として渡す。これを「ラムダ・リフティング（lambda lifting）」と称する。

• 以下ではスタティック・リンクについて詳説する。どの手法が実際的であるかに付いては → Exercise 6.7 。
• 関数fを呼ぶときに、関数fの定義を直接に取り囲む関数gの「現在（current）」（最近に実行された関数）のスタック・フレームへのポインタを渡す。

• このように各手続きは変数をアクセスするのに0回以上スタティック・リンクの連鎖を辿る必要がある。この連鎖の長さは二つの関数をくるむ静的な入れ子の深さの「差（difference）」である。

（Tigerコンパイラにおけるスタックフレームの抽象化）p.134〜p.136

• 対象となる各計算機の標準スタック・フレーム内配置はそれぞれ異なっている。
• ここでもしTigerからCの関数を呼び出したいと思うならば標準の配置を採用しなければならない。
• が、Tigerコンパイラの意味解析モジュールの実装にはどんな特定の計算機の仕様も混ぜ込みたくない。
• 故に抽象化が必要である。ちょうどSymbolモジュールが簡明なインターフェースを提供してtableの内部表現を利用者に隠しているようにフレームにも抽象表現を用いなければならない。（例では抽象的なインターフェースを示すsignature FRAMEの一部を抜粋している。）

• このインターフェースに対する実装は対象計算機毎に提供される。（例ではFRAMEシグネチャを持つMipsFrameストラクチャが定義されている。）
• 一般にコンパイラの機種独立部分はFRAMEのインターフェースを通じてこの実装にアクセスすると仮定する。（例ではFRAMEシグネチャを持つ構造体FrameとしてMipsFrameが束縛されている。）

• 以上によってコンパイラの残りの部分では対象計算機が何であるかを知らないままFrameにアクセスできる。

• frame型はこのフレームに割り当てられている仮引数と局所変数の情報を保持する。
• 関数fについて新しいframeを作成するには引数をレコード{name=f, formals=l}としてnewFrameを呼び出す。ここでlは関数の各引数の属性を示すbool値のリストでtrueならば対応する仮引数は抜け出しており、falseならばそうではない。newFrameの結果はframe型のオブジェクトである。（例では三つの仮引数の内、最初の引数をメモリに保持する必要のあるような名前gなる関数のためのframeオブジェクトを生成している。）
• access型は仮引数や局所変数がフレームかレジスターのどちらに保持されるかを記述する。この型は「抽象データ型（abstract data type）」であってその実装であるdatatypeはFrameモジュール中でのみ可視である。（例では具体的なデータ・タイプとしてフレーム・ポインタからのオフセットを示すint型の値を取るInFrame構築子とレジスタを指定するTemp.temp型の値を取るInReg構築子が実装されている。このaccess型の値はこれら構築子がモジュールの外からは見えないため、次章で説明するインターフェース関数を通じてしか操作できない。）
• Frame.formalsインターフェース関数は仮パラメータが実行時に呼び出される側から見てどこにあるかを示すk個のaccess型の値から成るリストをframe型の値から取り出す。
• 仮引数は呼び出される側と呼び出す側では異なった場所に見え得る。
• 例えば、スタックを介して渡されるとき呼び出し側でスタック・ポインタからオフセット４に置いた値は呼び出された側ではフレーム・ポインタからオフセット4の位置に見える。また呼び出し側がレジスタ6に置いた値は呼び出される側では動かされてレジスタ13に置かれているかも知れない。Sparcアーキテクチャのレジスタ・ウィンドウの下では呼び出し側が引数をo1に置いてもsave命令によってレジスタ・ウィンドウがずれ、呼ばれた側では引数がレジスタi1にあることになる。
• この「見え方のズレ（shift of view）」は対象計算機の呼び出し規約に依存し、newFrameを始めとしてFrameモジュールで取り扱われねばならない。newFrameは以下の二つのことを計算せねばならない。

• 例えば、フレームに置かれる引数は「フレーム・ポインタからオフセットXのメモリ領域」にあり、見え方のズレは手続き開始時にスタック・ポインタがフレーム・ポインタにコピーされることで実装されるといった具合。

（抽象的なフレームでの仮引数の取り扱い）p.136〜p.137

Frameモジュールはframe型の表現に関する秘密をFrame型の利用者から守らねばならないが、内部では以下のようなデータ構造を保持している。

• 全ての仮引数の保管場所
• 「見え方のズレ」を実現するのに必要な命令
• 現時点までに割り当てられた局所変数の数
• 関数の命令列が始まる位置のラベル（p.140参照）

• p.135の関数で例に挙げたg(x_1, x_2, x_3)を例に取っている。1つ目の引数だけが「抜け出し」ている。
• Pentium、MIPS、Sparcという三つの異なるアーキテクチャについて上段ではnewFrameが三つの引数をどう割り当てるかを示し、下段では「見え方のズレ」を実装するために必要なコードを示す。
• accessに付いては１つ目の引数は「抜け出し」ているのでいずれのアーキテクチャでもInFrameとして生成されている。その他の引数に付いてはPentiumではInFrameで生成されているがその他のアーキテクチャではInRegで生成されている。
• 見え方のズレを実現するために新たに生成された一時領域t_157とt_158へ値を移動させる命令が生成されている。（MIPSではr4とr5から、Sparcではi0とi1から）
• 直接アクセスしないでこの一見余計な命令を生成している理由は以下の例を考えると判る。

• 最後にレジスタ割り当て器は一時領域t_157やt_158を実際に保持すべきレジスタを決定する。関数mの例で見られたような干渉がなければ割り当て器はそれぞれをr_4とr_5に割り当て、その時点で不用になったmove命令を削除する。
• 「見え方のズレ」に関するより詳しい議論はp.168及びp.261を参照。

（抽象的なフレームでの局所変数の扱い）p.137〜p.138

• フレームfに新たな局所変数を追加割り当てするには意味解析フェーズでframe型の引数を与えてFrame.allocLocalを呼び出し、その返値の関数に「抜け出し」ているかどうかを示すbool型の値（trueなら「抜け出し」ており、falseならそうではない。）を与える。その結果の値は適当なaccess型の値である。（例ではフレームfについてallocLocalを呼び出しその返値の関数をbool値にtrueを指定して呼び出しているので結果はInFrameを利用して構築されたaccess型の値となる。例ではSparcを想定しているので引き続く２度の呼び出しでInFrame(-4)、InFrame(-8)が返っている。一方bool値にfalseを指定していれば恐らくはInRegを利用して構築されたaccess型の値となるだろう。例ではSparcを想定しているのでInReg(t_481)が返ると想定している。）
• allocLocalの呼び出しはframeが生成された直後でなくても良い。TigerやCのような言語では変数宣言のあるブロックが関数本体の中で入れ子になることがあるためである。（例では入れ子になったブロック中でvという名の変数が計３つ宣言されている。）コンパイラはTigerプログラムの処理中に各変数宣言に出会うとallocLocalが呼びframe内に一時領域が確保する。ブロックの終りに出会うとvとの関連付けは忘却するが一時領域はframe内に残る。故に関数全体で区別されるフレーム内のスロットが各変数に付いて存在する。
• レジスタ割り当て器は一時的な領域について極力少ない数のレジスタを使おうとする。この例では、２番目と３番目に現れる変数vは同じ一時領域に保持できる（それぞれ7と8に初期化する）。賢いコンパイラはフレームに割り当てられた２つの変数が同じスロットに割り当て得ると知れば、フレームの大きさを最適化するだろう。

（FindEscape：抜け出しを調べる関数）p.138〜p.139

• 局所変数が「抜け出し」ていなければレジスタに割り当てることができるが、「抜け出し」ていればスタックに割り当てなければならない。FindEscape関数は「抜け出し」ている変数を見つけ出し抽象構文のescapeフィールドにそのことを記録する。

• 最も単純な方法は抽象構文全体を辿り、全ての変数について「抜け出し」ているような使い方を探すことである。
• 意味解析を行う構造Semantは全ての変数についてその最初の出現時に「抜け出し」ているかどうか「即座（immediately）」に知る必要があるから、このフェーズは意味解析の前に行う必要がある。

• 抽象構文を辿るFindEscape関数はまさに型検査関数のようであって、抽象構文中の式expとvarについて相互に再帰する必要がある。さらに型検査関数のように変数を束縛に写像する環境を必要とする。ただこの場合の束縛は極単純で変数が「抜け出し」ている場合にtrueを記録するbool値refと変数や仮引数の宣言を見つけた静的な関数宣言の入れ子の深さを示すdepth（int型と同じ型）値dである。
• 例のように抽象構文中の入れ子の深さdで変数や仮引数の宣言を見つけたらrにfalseを代入して束縛a→(d,r)を環境に追加する。
• その変数のスコープ内ではこの新しい環境で式を処理し、深さがdより深いところでaが使われていたらrをtrueにする。
• プログラマが明示してアドレスを取れるような言語、または仮引数が参照渡しされている場合は似た方法でFindEscapeは「抜け出し」ている変数を見つける。

（抽象化された一時領域とラベル）p.139〜p.140

• コンパイラの意味解析フェーズでは仮引数や局所変数のためのレジスタ選択や関数宣言本体の機械語のアドレスを選択したい。が、利用可能なレジスタを正確に決定したり関数宣言本体の位置を正確に決定したりするには早すぎる。
• そこで「一時領域（temporary）」という語をレジスタに一時的に保存される値の意味で使う。
• そして「ラベル（label）」という語を機械語の位置が正確に決まらないある場所、アセンブリ言語のラベルの意味で使う。

• Temp.tempは局所変数の抽象的な名前である。
• Temp.labelは静的なメモリアドレス抽象的な名前である。
• Temp.newTemp()はtempの無限集合から新規の一時領域を返す。
• Temp.newLabel() はlabelの無限集合から新規のラベルを返す。
• Temp.namedLabel(string) は指定された文字列をアセンブリ言語での名前として持つ新規のラベルを返す。
• 宣言function f(…)を処理する際にfの機械語アドレスを生成するにはnewLabelを使う。
• これに対して（L123などというよりfという名を用いたほうがアセンブリ言語のプログラムがデバッグしやすくなるから）namedLabel(“f”)を使いたくなるが不幸なことに異なったスコープにあり共にfという名を持つ異なった2つの関数がありうる。

（フレーム周りのTigerコンパイラの構成）p.140〜p.142

• Tigerコンパイラは意味解析とフレーム内配置の詳細の間に2つの抽象された層を備えている。
• FRAMEとTEMPはメモリに配置された変数とレジスタに配置された変数について機種独立なインターフェースを提供している。
• FRAMEの提供する抽象レイヤーの本質は、ソース言語の意味と機種に依存したフレーム内配置とを分離することである。
• Translateモジュールは入れ子になったスコープの概念を取り扱うことでこれを強化し、Semant意味解析モジュールにTRANSLATEインターフェースを提供する。
• SemantとTranslateを分離するTRANSLATEインターフェースは必須というわけではない。単に型検査と意味的な変換の双方を扱う巨大なかさばったモジュールを避けたかっただけである。
• 7章において説明するようにTranslateモジュールは抽象構文から中間表現を生成するために有用なML関数を提供する。
• ここではTranslateがSemantのために局所変数と静的な関数の入れ子をどのように管理するかについて考える。

1. Tigerコンパイラの意味解析フェーズにおいて各関数宣言についてtransDec関数が呼ばれるとtransDecはTranslate.newLevel関数（引数は関数が定義されている入れ子レベルlevelとlabel型の関数名name、引数の「抜け出し」を示すbool値のリストformalsからなるレコード）を呼び出して新たな「入れ子レベル（nesting level）」を作る。
2. この関数はFrame.newFrame関数を呼んで新たなフレームを作る。
3. この時Semantは関数のため環境に保持されるFunEntryデータ構造内にこの入れ子レベルを保持する。
4. この後、関数呼び出しに出会ったらこの入れ子レベルをTranslateに返す。FunEntryには関数のコードの開始位置を示すlabelも格納される。
5. 入れ子レベルlevでSemantが局所変数の宣言を処理するとき、Translate.allocLocal関数にlevを渡して呼び出し、その返値である関数にbool値で「抜け出し」の有無を渡してこのレベルでの変数を生成する。生成結果の最終的な返値は抽象データ型Translate.accessである。（これはスタティック・リンクについて知っているが故にFrame.accessと同じ型ではない。）
6. Semantは変数のため環境に保持されるVarEntryデータ構造内にこのTranslate.accessを保持する。
7. 抽象データ型Translate.accessは変数のlevelとFrame.accessの対で実装できる。だから、Translate.allocLocalはFrame.allocLocalを呼び出して得たFrame.accessと共に変数のあるlevelも覚えておく。
8. この後でその変数が式中で使用されたときSemantはこのTranslate.accessをTranslateに返してTranslateが変数にアクセスするコードを生成できるようにする。（異なったレベルにある変数にアクセスするときはTranslate.access内のlevel情報を使ってスタティック・リンクを辿る。）

（スタティック・リンクの受け渡し）p.142〜p.143

• Frameモジュールはコンパイルされる特定のソース言語から独立でなければならない。多くのソース言語は入れ子の関数宣言を持たないのでFrameはスタティック・リンクについて知っていてはならない。スタティック・リンクを管理するのはTranslateモジュールの責任である。
• Translateモジュールは各フレームにスタティック・リンクが含まれていることを知っている。スタティック・リンクはレジスタを介して関数に渡されフレームに格納される。故にスタティック・リンクは関数の仮引数に大変良く似た振る舞いを示すし、可能な限りそう扱っても良い。
• k個の「普通」の引数を持つ関数について、lをその仮引数に対応するbool値のリストとする。するとlの先頭に「抜け出し」を示すtrueを付け足したl’という新しいリストを考えると、この先頭に追加されたtrueはスタティックリンクを「抜け出し」のある「追加の引数（extra parameter）」として表している。

• 関数f(x, y)が関数gの中に入れ子で定義されているとし、gの入れ子レベルをlevel_gとする。
• Semant.TransDecは

• Translate.newLevelは仮引数リストにスタティック・リンクのために追加の引数を加えて

• こうして新しいframeが返ってくる。このフレームにはFrame.formals(frame)を介してオフセットでアクセスできる3つの値がある。最初のものはスタティック・リンクであり、あとの２つはxとyである。
• SemantがTranslate.formals(level)を呼ぶとき、この関数はこれらののオフセットを二つ入手して適切なaccessの値に変換できる。

（Semant内でのlevel値の管理）p.143

• 各newLevelの呼び出しに伴って、Semantはそれを覆うlevel値を渡さねばならない。
• 「main」Tigerプログラムのレベル（どのTiger関数の内部でもない）とき、Semantは特別なlevel値Translate.outermostを渡す。
• これはTigerにおいてメインプログラムのレベルではない。このレベルの中でプログラムは入れ子になっている。全てのライブラリ関数（5.2節の終りを参照）はこのフレームも仮引数もない最外側のレベルで宣言されている。
• transDec関数はTigerの各関数宣言について新しいレベルを作るだろう。しかしnewLevelは関数を取り囲む関数のlevelを伝えられねばならない。このことはtransDecが各宣言を処理するときに現在の静的入れ子レベルを知っていなくてはならないことを示す。
• これは簡単である。TransDecに対応するnewLevelの呼び出しから与えられた現在のレベルを追加の引数（型、及び値の環境にも追加する）として与えれば良い。そしてtransExpにもまた引数を追加して、transDecがlevelをtransExpに渡せるようにし、それがまたtransDecにまた渡されるようにして入れ子になった関数の宣言を処理する。同様の理由でtransVarもまたlevel引数を必要とするだろう。

（この章に関連するサンプルソースについて）p.143〜p.144

（10/01現在http://www.cs.princeton.edu/~appel/modern/ml/chap6/のディレクトリは空だった。）

意味解析モジュールSemant (semant.sml)：局所変数に場所を割り当て、入れ子の深さを追跡する。簡単にするためには全ての引数が「抜け出し」ていると仮定する。

変換モジュールTranslate (translate.sml)

抽象フレーム配置FRAMEに対する具象フレーム配置モジュールSparcFrame (sparcframe.sml)：Sparcアーキテクチャ用フレーム配置を表している。機種依存性はこの中に閉じ込めること。簡単にするためには全ての引数が「抜け出し」ていると仮定する。NewFrameではescapeとしていつもtrueを渡す。（MIPSやSparcなど）RISC計算機で動かすには最初のk個の引数をレジスタに保持し、残りをスタックに置く。簡単にするためにはkより少ない数の引数だけを扱う。ちなみにMipsFrameはMIPSアーキテクチャ用フレーム配置を表している。

選択：「抜け出し」検出関数モジュールFindEscape：これが全ての変数の「抜け出し」フィールドを適切に設定するよう実装する。

選択：関数がk個以上の関数を扱えるようにする。サポートファイルは$TIGER/Chap6にある。

一時領域とラベルのためのサポート・モジュールTemp (temp.sigとtemp.sml)

（この章の参考文献）p.144

[McCarthy1960]　Lispで単一の連続的なスタック上に変数と戻り番地を積んだ。

[Naur et al. 1963]　Algolで単一の連続的なスタック上に変数と戻り番地を積み、入れ子関数宣言を含むブロック構造を導入した。

[Leonard 1987]　殆どのプログラムが変数をメモリに置き「抜け出し」について心配していなかった1960〜1970年代。その終り1978年にプログラム・カウンタ、フレーム・ポインタ、引数へのポインタ、引数の数と全ての引数、そして呼び出し先退避レジスタを示すマスクをスタックに積む手続き呼出し命令を備えるVAX計算機を作った。

[Patterson 1985]　RISC革命。

[Chitin 1982]　RISC革命時、デフォルトで引数や局所変数をレジスタに置き、レジスタ割り当て器が溢れて必要が起こるまでメモリからの読みこみやメモリへの書きこみを行わないようにしてメモリとのやり取りを減らす手続き呼び出し規約のアイディアをもたらした。

[Tanenbaum 1978]　殆どの手続きは５つ以上の引数と５つ以上の局所変数を持たないことを明らかにした。

[Chow et al. 1986]と[Hopkins 1986]　上記の結果を発展させて以下のように最適化した呼び出し規約を設計した。最初の4つの引数をレジスタで、稀なそれ以上の引数をスタックで渡すこと。局所変数についてコンパイラが呼び出し元退避と呼び出し先退避のレジスタを使い分けること。末端手続きが呼び出し元退避のレジスタで演算し自身のスタック・フレームが不要なことさえあること。戻り番地さえスタックに積まなくていい場合があること。

（この章の練習問題）p.144〜p.147

• a　引数はvarargsのためにスタックにも置かねばならない。
• b　aと同様の理由に加えてアドレスが取られているから。
• c[]　配列であるから。

その他は極力レジスタに置く。a、bはアーキテクチャによってはレジスタにも置く。

フレームの参照関係は indent -> show -> prettyprintであるので読みこむ命令3個とオフセットの足し算1個。

Displayから必要なフレームへのポインタを取り出してアクセスするだけだからレジスタにディスプレイへのポインタがあった場合、読みこむ命令2個とオフセットの足し算1個。

読みこむ命令　d_2 - d_1 + 1 個とオフセットの足し算1個。

深さの差に関わらず、レジスタにディスプレイへのポインタがあった場合、読みこむ命令2個とオフセットの足し算1個。

自分より一つ深いところの関数を呼ぶ場合は、書き出し命令1個。戻るときには何もしない。

自分自身を呼ぶときには読みこみ命令1個と書き出し命令1個。

自分より浅いところの関数を呼ぶ場合は読みこみ命令d_2 - d_1個と書き出し命令1個。戻るときは何もしない。

呼ばれた関数がD(i)をスタックフレームに保存し、フレーム・ポインタをD(i)に書きこみ、

終了後D(i)に書き戻すのに読みこみ２つと書き出し３つ。

D(i)のアドレス計算とスタック・フレーム内退避場所のアドレス計算のために足し算が二つ。後者が不用ならば足し算は一つ。

• スタティック・リンクでなくディスプレイを用いるべきでないのか？恐らくそうだろう。しかし結果はより複雑になる。PascalやTigerのようにブロック構造があるだけの言語ではディスプレイは上手く働く。
• しかしブロック構造に加えてSchemやMLのように関数を返値にできる高階関数機能があればブロック構造は最大限に力を発揮する。それがある場合、閉包を構築する手間など変数のアクセス時間や手続きの開始、終了時の手間以上の問題を考える必要がある。この問題は必要のないデータも閉包に保持することで避けられる。この問題に関しては15章で説明する。