情報科学実験II資料 (3)
CPSの定義

田浦

15/10/98

Min-SchemeFix実現の概要

さて先週は, Schemeの多くの部分を包含する十分強力な言語が, 究極的にはたっ たの4つのessential syntaxから成る言語に還元できることを見た. その4つの essential syntaxとは,

ここでprimitiveは, target machineに依存した, machine命令またはその簡単 な組合せで, 多くのregisterを破壊せずに実現可能な機能の集合である. 特に fixは強力さの源であり, これを元にlambda式, loopなどの数々の有用な構文 が実現できたのであった. また, letは意味的にはfixとapplyの組に還元する ことができるが, 次の二つの理由で, essential syntaxとしてある.

さて, 構文解析が終った後のcompilerのphaseは, Min-Schemeのsourceを, ま ず中間言語であるところのContinuation Passing Style (CPS)といわれ る形式に変換し, その上で必要な解析を行ない, 実際にコードを生成する. Algorithmicには, Min-SchemeからCPSへの変換規則を理解することが最初の stepになる. 変換規則を述べる前に, 最終的にどのような機械語に変換される べきなのかを説明しておく.

変数および定数

変数は最終的にregister allocation phaseにおいて, その変数の値を保持す べきregisterが割り当てられる. 定数は通常machine命令にそのまま埋め込め られるが, 命令に入り切らない大きな定数は一度registerにloadされる.

組み込みのprimitive

例として次のような式を実行した時に何を起こすべきかを考える.

(E (+ tex2html_wrap_inline487 tex2html_wrap_inline489 ))
tex2html_wrap_inline491 は足し算を受けるoperandであり, Eは足された結果を「使う」式 で, 上の式全体で, 足し算を行なう状況の雛型(template)を示している.

Min-Schemeとassembly言語の大きなgapの一つは, Min-Schemeはあらゆる operationは任意の複雑な式をoperandとしてとれるのに対し, assembly言語で はoperation (例えば足し算)のoperandはregisterや定数などの単純なもので なくてはいけないということである. つまり上の式を評価する時の問題は, 足 し算を行なう前に何とかして tex2html_wrap_inline487tex2html_wrap_inline489 の値を(それらが小さな定数でない 限り)registerの上に載せて, その後に実際に足し算を行ない, その結果を何 とかして, Eに教えてやる, ということである. したがって生成するmachine 語の列は以下のような感じになれば良い.

displaymath483

その他の多くのprimitiveも大体同じような構造を持つと思って良い.

条件分岐

(E (if C T F))
を実行させた時, 何を起こせば良いかを考えよう. Assembly言語の制限: 「操 作を施すための値はregisterに載っているか, constantでなくてはならない」 を思いだすと, まずCを評価した結果をどこかのregisterに載せ, その後に そのregisterの値に基づいて適切な方向へ分岐をする. 分岐した先ではそれぞ れ, TまたはFの評価した値をどこかのregisterに載せ, それをEに渡せ ば良い. つまり,

displaymath509

のような感じの命令列を出すことができれば良い.

局所変数定義

例えば1変数の束縛を行なうlet式である,

abcl168

を実行する時にすべきことは,

ということである. つまり,

displaymath533

局所関数定義

さて, Min-SchemeFix に存在しているfix式, つまり局所的な, 自由変数を持 つような関数を定義した時に何を起こせば良いか. Fixの例は,

(fix ((f (x) (+ x y))) ...)
で, この場合, yが自由変数となる.

前回にも少し紹介したように, fの正体はfを実現するコードの番 地および, 自由変数であるyの値の組(レコード)である(このレコードを closureという). したがって生成すべきコードの列は以下のようなかんじにす れば良い.

     fのclosureをheapに作り、それ(へのpointer)をfとする
	   		  ...部を実行

注意: Min-Scheme においては関数は必ずtoplevelで定義されたものだ が, Min-SchemeFix においては関数は, toplevelのdefineで定義された ものかも知れないし, fixで局所的に定義されたものかも知れない. こ こではfixで定義された関数の表現が, closureであると述べたが, fixを supportする以上, toplevelも便宜上そうしておく必要がある. Toplevelで定義された関数は固有の自由変数を持たないため, もし世の 中にtoplevelで定義された関数しか存在しないのなら, 関数の正体(表 現)はその関数のアドレスだけでこと足りる(これが実際, C compilerで行なわ れていることであるし, Min-Scheme ではそうすることが可能である). しかし 二つの表現が混ざっているのは話しがややこしくなる. そうしてしまうと, 例えば以下のような関数において,

(define (map f l)
  (if (null? l) '()
      (cons (f (car l)) (map f (cdr l)))))
fを呼び出す時にfがtoplevelで定義された関数であるかどうかで 異なった呼び出し方法を用いなければならない(具体的には, fixで定義された ものであれば, コード番地をclosureから取り出す必要があるが, toplevel であればfそのものがコード番地になっている). したがって toplevel関数もfixとの統一をはかって, closureとして表現しておく(実際に はコード番地1 wordしか中身のないrecordができる). 単純な物の見方は, toplevelの関数定義の羅列全体が一つの大きなfix式になっているとみなすこ とである.

関数呼び出しおよび復帰

ここが一番自明でないところである(気合いを入れて聞いて下さい). 例えば,

(define (f x y z)
  (+ z (g x y)))
の様な関数内において, (g x)への呼び出しを実行することを考える. ここでgは, Min-Scheme の場合toplevelで, Min-SchemeFix の場合どこ かのfixで定義された関数である. まず行なわなくてはいけないのは,
1. パラメータのsetup
である. Machine毎に関数呼び出しの慣例というのが決まっており, そこでは 関数の第○parameterはどのregisterにおけ, などということが決まっている. (関数がどこから呼び出されるかわからない以上, あらゆる関数に共通の決ま りをつくっておかなくてはならない.) ここでは, 第i parameterを第i registerにおくとする. したがって呼び出す時には, xyの値を それぞれ第1, 2 registerに動かす必要がある. その後, gを実行するコー ド列が格納されている番地にjumpする(Min-SchemeFix においてはgはレ コードを指しているため, その番地をclosureから取り出す).

これで無事, gは実行を開始することができる . . . とここで非常に 大事なことを一つ忘れている. それは, どうやってgから戻って, fの続きを実行するかということである. 一般には, gは自分の 実行が終了した後どこへ戻って続きを実行すればよいかをcompile時に知って いるわけではないので, 呼出時に何らかの形でその情報を渡してやらな ければいけない. ではそれも関数呼び出しのconventionに含めることにする. つまり, 第0 registerには, 呼びだし側が制御を戻して欲しい場所をおいた上 で, 目標となる関数を呼び出すことにしよう. つまり,

2. fが, gの終了後, 実行を再開する場所をsetup

さて, それだけで足りるだろうか. 実はまだ足りない. 上のようにgに 呼びだし側の戻り番地を渡してやり, 首尾良くgから制御が戻ってきた としよう. この時またまたmachine conventionで, 第1 registerに返り値が返っ ているものとしよう. では, 次にfは何をするかというと, 返ってきた 戻り値とzを足し算しなくてはならない. しかしその時zはどこに ある???? という話しになる. fが呼ばれた時点ではzは第3 registerにあったのに違いない. しかしgが復帰した時点でそれが残っ ていると期待できるはずがない(これはどんな慣例を定めたところで解決でき る問題ではない. 例えばgが引数を3つ以上持つ関数を呼び出すとすると その時, gは第3 registerを上書きする).

一番単純な解決方法は, 関数を呼び出す側は, 復帰後に必要な値を, gに制御を移す前にmemoryに退避するというものである. その memoryへのpointerもどこかにおいておかなくてはいけないから, それもまた conventionによって定める(第-1 register, とでも呼んでおく). この,

復帰後に必要な値を格納したrecordを作り, setup
このrecordを, をその呼び出しの, continuation recordと呼ぶ.

. . . 以上でようやくきちんと動く方式ができた. 詳細は後日, 若干変更し た形で(特に, Min-Scheme とMin-SchemeFix との違いにも触れながら)また紹 介することにして, 今は概念的にまとめておくと, 関数呼び出しは,

      continuation recordを作り、所定のregisterに格納
		戻り番地を所定のregisterに格納
		引数を第1register以降に並べる
			宛先にjump
で, 実行され, 関数から戻る時は,
      渡されたcontinuation recordを所定のregisterにおく
		返り値を第1registerにおく
			戻り番地にjump
となる.

Continuation Passing Style

さて, いよいよ我々が採用する中間言語である, Continuation Passing Style (CPS)について説明する. Min-Schemeと少し似ているが違うもう一つの新しい プログラム言語を覚えるつもりで理解して欲しい. 今回の目標は, 複雑 に組合わさった式の評価や, 関数呼びだしなどが, CPS上でどのように表 現されるかを見ることで, Min-SchemeをどのようにCPSに変換するかの algorithmは, 来週説明する. また, CPSそのものをどのようにmachine命令に translateするかはそれ以降のテーマになる(もちろんそれ以前に一定のイメー ジを頭に持っておかなくてはならないが).

文法

abcl251

(注) 記法上の慣習として, CPS関係の文法クラスおよび命令名は大文字で, Min-Scheme のそれは小文字で書くとする.

OPは命令(例えば足し算)のoperandとして使われる対象を指している. まず最 初に注目すべきなのは, OPがIDまたはCONSTANTしかないという点で, ここが Min-Scheme の, 「任意の式が値を持ちそれらを組み合わせてまた式ができる」 というのと大きく違うところである(その点でCPSは一歩, assemblyに近い).

文法クラスCPSがCPSの命令を表しており, それには大きく分けて3種類ある. まず注意しておくと, CPS自体はMin-Scheme の式のように値を持たない. 値を 持つものはIDまたはCONSTANTだけであり, 複雑な式の評価は, OPに演算を施し て変数にbindし, 次の命令を実行して. . .という風に行なわれる. 一つ一 つ順に見ていく.

Primitive

まず, primitiveは次の文法をしている.

abcl272

ここで, X*はXの任意個の並びを表す. PRIMSYMが実際の命令の種類を規定し, それらには, +, -などの命令や, RECORD-REFなどの命令が含まれ る(これらもMin-Scheme のprimitive同様machine依存である). PRIMSYMのすぐ 後に続くのがその命令への引数である. 実際の引数の個数は命令毎に決まって いる(任意個の引数をとれるものもある). その次の[ID*]は, 命 令の結果を格納する変数名を指定する. 実際にはこのfieldには0個または1個 の変数しか入らない. 最後のfieldは再び任意のCPS命令の列を格納できるよう になっている. これは, この命令の実行後, 実行すべきCPS命令列を格納した ものであり, その命令のcontinuationと呼ぶ. 実際にはこの continuationの数は1個または2個で, branch命令の場合だけ2個(それぞれ成立, 不成立に対応), それ以外は1個である. 例えば以下は, Xを2倍して, tにbindし, それが10より大きいかどうかで分岐するCPS programの断片 である.

(* [x 2] [t] 
   [(< [t 10] [] 
     [(... ) ; then part 
      (... )])]) ; else part
CPSが, 制御の流れをただの命令の「並び」としてではなく, CPSの再帰的な式 の構造によって明示的に表している点に注目せよ. このことはcompilerにとっ て必要な情報(例えばプログラムのある時点での, ``今後使用する変数の集合'') を求めるalgorithmを, 式の再帰的traverseにより単純に美しく書くことを可 能にしている.

APP

次に, APPについて見る. 2種類(APPFAPPB)あって, 文法はそれぞれ,

abcl281

または,

abcl284

である.

(APPF f (x y z))
は, x, y, zを引数として, fを呼びだす. また,
(APPB k (r))
もやはり, rを引数として, kを呼び出す. ただしAPPB は Min-Scheme またはMin-SchemeFix の関数から返るために使われ, APPF は関数を呼び出すために使われる(F, Bはそれぞれforward, backwordの意味).

これらがMin-Scheme の関数呼び出しと大きく違うのは, APPそれ自体はあくま で, 「片道のjump」であり, Schemeの関数のようにそれ自体で値を返して続き を実行するわけではない, という点である. それはAPPの文法にも現れており, APPの後で実行すべき「続き」に相当するものはない.

FIX

さて, 最後にFIXである. FIXにも2種類あって, それぞれ, FIXS , FIXH と書くが, 違いは後で説明する. 文法はともに,

abcl294

で, BIND*にしたがって局所関数を定義し, CPS以降を実行する. FIXも primitive同様, 再帰的な構造によって次に行なうべき命令を指定している. 例えば,

(FIXH [(f (x) (+ [x 1] [y] [(...)]))]
  ...)
は, fという関数を定義して, 以降を実行する. fは引数x を受けとり, それに1を足して. . .という動作をする.

ここでFIXで定義される関数は自由変数を含んでいて良い. 我々はまだCPSの自 由変数を定義していないが, つまり, FIX式の外側で定義され, FIX式で定義さ れる関数の内側で参照される変数があっても構わないということである.

さて, FIXHFIXS の違いはちょうどAPPFAPPB の違 いに対応している. まずFIXH はMin-SchemeFix のfixを実現することに使う. つまりFIXH によって定義される関数は元はといえばMin-SchemeFix の関 数である. 一方FIXS によって定義されるものは実はMin-Scheme または Min-SchemeFix の関数呼び出しのためのcontinuationである. いいかえれば, FIXH で定義された関数はAPPF で呼び出され, FIXS で定義された continuationはAPPB で呼び出される.

実際に「continuationを作る」という作業がどのようにCPSで書かれるか, 疑 問になると思うが, これは次の例を見た方がはやいので, 例を使って説明する. 今,

(define (g x y)
  (+ x (f y)))
という文脈で, fを呼び出すことを考える. それをCPSでは, FIXとAPPの 組合せにより以下のように書く(便宜上gもFIXを使って書いておく).
(FIX [(g (k x y)
  (FIXS [(c (v) (+ [x v] [t] [(APPB k (t))]))]
    (APPF f (c y))))]
  ..)
2行目のFIXSが, fから戻った後のcontinuationを作っている部分である. 作られているのは, vという1引数の関数である. これはfの返り 値をvに受けとり, それをxに足して. . .という動作をする. fはここには書かれていないが, 返り値を戻す時に,
(APP c (v))
という式を実行して, 関数から復帰する.

さて, continuationを作ったら, 実際にfをAPPを使って呼び出す. それは

(APP f (c y))
である. 注目すべきは, fが後できちんとcを呼び出すことができ るように, 作られたcが追加引数として渡されている点である.

FIXS , FIXH のmachine code上での動作

CPS命令の中で, FIXはやや抽象的で, 実際の動作をimageしにくいoperatorで ある. CPSのFIXも自由変数を含み得るので,

abcl315

を実行した時, fixの定義部(この場合E)に含まれる自由変数および, fを実現するコード番地からなるレコードを作る動作をする. それを fとして, Bを実行する, というのが動作である.

したがって, FIXを一度実行するたびにどこかにmemoryが割り当てられなくて はいけない. 当然そのためのmemory管理の方式が必要になる. 概念的に一番単 純なのは, garbage collected heapを実装してしまい, そこからmemoryを割り 当て, 必要になったらGCをするというものである.(注) しかしその方法だと, とりあえず動くものを作るの にも必ずGCが必要になる.

妥協案として, FIXを2種類用意してある. 一つはFIXH でこれはheapからレコー ドを割り当てる. もう一つはFIXS でこれは, stackからレコードを割り当て, 定義された関数は一度しか呼ばれないという前提の元に, 一度呼ばれたらその memoryをstackからpopする, というものである. Continuation recordがstack から割り当て/解放できるのはすぐにわかる. また, すでにstack上に格納され ている変数は何度もpush/popを繰り返さないような最適化を解こす余地を残し ておくためにも, その両者は区別しておこう. (注) 結果として得られる二つのFIXは, memory managementの方法を除けば全く同じ ものであり, 特にCPS levelでの意味の違いはない.

注: CPSレベルにおけるMin-Scheme とMin-SchemeFix の違い

これは, Min-Scheme にはMin-SchemeFix におけるfixがないので, 当然のこと ながら, Min-Scheme を変換して得られたCPSにはFIXH がでてこない, という のがその答である. ただし, toplevelの関数定義を書くsyntaxとしてFIXH と いう記号が使えると便宜上都合が良いので, FIXH はMin-Scheme においても 使うことにする. それは唯一toplevelに並んだ関数を変換するために使う. つ まり,

Min-Scheme を変換して得られたCPSにおいては, FIXH はtoplevelにしか出現 しない
と覚えておく.

CPSの特徴

中間言語に望まれる性質は,

ことである. ここでCPSがcompilerにとってなぜ扱いやすい言語なのかをいく つかの例を用いて示す.

Inlining as Substitution

SchemeやMLのような言語では関数呼びだしのinline展開が重要な最適化となる. 例えば,

(define (g x)
  (fix ((f (y) (+ y y)))
    (+ (f (+ x 10)) 1)))
において, fの呼び出しを最適化したいと思ったとする(今は, fixを使っ ているが, fがtoplevelの関数でも, 定義がわかっていれば同じことで ある). これは以下のようなCPSに変換される(便宜上, gもFIXを使って 定義しておく).
(FIXH ([g (k x)
  (FIXH ([f (c y) (+ [y y] [t] [(APPB c (t))])])
    (+ [x 10] [s]
       [(FIX [(d (t) (+ [t 1] [r] [(APPB k (r))]))]
          (APPF f (d s)))]))])
   ...)
ここで, fの呼び出しをinline展開することは,
(APPF f (d s))
を, FIXHで定義されたfのbody, つまり
(+ [y y] [t] [(APP c (t))])
において, freeなparameterの出現をを対応するargumentで置き換えれば良い. この例でいえば, freeなcdで, freeなysで, 置 き換えれば良い. つまり,
(FIXH [(f (c y) (+ [y y] [t] [(APP c (t))]))]
  (+ [x 10] [s]
     [(FIXS [(d (t) (+ [t 1] [r] [(APP k (r))]))]
        (+ [s s] [t] [(APP d (t))]))]))
である. ここで, この最適化を施した後, fがもはやどこでも使われな いとわかったならば, fの定義そのものを消去してしまって良い.

そしてさらに, この例の場合,

(APPB d (t))
もinline展開できる. これを行なってさらに不必要な定義を取り除くと,
(+ [x 10] [s]
   [(+ [s s] [t] 
       [(+ [t 1] [r] 
           [(APP k (r))])])])
となる. そして, substitionは非常にやさしい操作である.

ところで, substitionはSchemeにおいても同様に優しい操作であるが, 残念な がらSchemeでは,

Inlining = Substition
とはならない(なぜか?)

``Live'' Variables as ``Free'' Variables

プログラム中のある時点で, 「生きている変数」とは, その時点で値が定義さ れていて, 今後使われる可能性がある変数のことである. これはcompilerにとっ てもっとも重要な情報の一つであり, ある関数呼び出しを行なう場合に, memoryに退避すべきなのはその時点で生きている変数でありまた, register allocationを行なう際にも, その時点での演算結果の保持場所として再利用可 能なのは, もはや生きていない変数のregisterである. これはあらゆる言語で, 何らかの形で定義されなくてはいけない概念である. 逆にこの情報が簡単な symbolicな操作で計算できる言語はcompilerにとって扱い良い言語である.

CPSはある命令のfree variable (自由変数)がそのままlive variableになって いるという優れた特徴を持つ. Free variableの定義はまだきちんと述べてい ないが, 例からは容易に納得することができる. 例えば先の例である,

(define (g x)
  (fix ((f (y) (+ y y)))
    (+ (f (+ x 10)) 1)))
を, CPS変換した,
(FIXH [(g (k x)
  (FIXH [(f (c y) (+ [y y] [t] [(APPB c (t))]))]
    (+ [x 10] [s]
       [(FIXS [(d (t) (+ [t 1] [r] [(APPB k (r))]))]
          (APPF f (d s)))]))])
   ...)
の, dの定義
[d (t) (+ [t 1] [r] [(APP k (r))])]
に注目する. tはparameterなので束縛変数. rは式の中で定義さ れるのでやはり束縛変数. 結局自由変数はkである. kはもともと gに渡されたcontinuationであった.

実際これは, (f (+ x 10))の呼び出しを行なう際にしなくてはならない ことを良く表している. 実現の概要でも述べたように, 関数呼出時に行なわな くてはならないことは, 関数復帰後に必要な変数をmemoryに退避することであ り, この場合関数復帰後に行なうことは返り値に1を足してそれをg自身の callerに返すことだけだから, 結局g自身が戻るために必要な情報だけ を退避しておけば良い. このdの自由変数がkのみからなる集合で あるということがこのことを表している. そして自由変数の計算はやはり簡単 な記号操作である(今までに見つかった, 束縛変数と自由変数の集合を保持し ながら式を再帰的にたどっていき, 束縛変数の集合に表れない変数が使われた 時点で, それを自由変数に加えていけば良い).

比較として, Schemeを見てみよう.

(define (app f x g y)
  (+ (f x) (g y)))
において, (f x)呼出時の生きている変数(注)は何か? 実はそれは答えようがない. 実際それは足 し算のoperandをどの順番で評価するかに依存する. (f x)を先に評価す るのであれば, 自由変数は,
	{g, y, (fのcontinuation)}
となるであろうし, 逆であれば,
	{(g y)の評価結果, (fのcontinuation)}
となるであろう. Schemeは何らかのevaluation orderを仮定しない限り, 生き ている変数が定義できない言語である.

次に``traditionalな''中間言語である4つ組を見てみる. 例えば,

s = 0;
for (i = 0; i < n; i++) s += f (i);
から生成されるであろう,
  s := 0
  i := 0
CHECK:
  if (i < n) goto END
  r := f (i)
  s := s + r
  goto CHECK
END:
のような中間コードを見てみる. ここでf (i)の呼出時にsaveすべき変 数, つまりその時点で生きている変数の集合を求めたい. もちろん我々は生き ている変数を定義していないが, その目的を思い出せば, 以降の命令をscanし て, 必要とされる変数を追加していけば良いことがわかる. 例えば直後の命令 を見ると, sが使われているので, sは生きている. rはそ の命令で定義されるので生きていない(生まれていない, というのが雰囲気を 良く表している). このように後ろのinstructionを見ながら使われている変数 を加えていってすむのなら良いのだが, 残念ながら話しはそう簡単ではなく, goto CHECKがあるために, 我々は命令列を後ろに戻らなくてはならない. すると, inも実は生きているということがわかる. そしてまたたどっ ていって元の場所に戻ってきて. . .

ここではややこしいということだけを指摘するにとどめる(さて, 結局 algorithmとしてはどのようにすれば良いのか?)

No ``Hidden'' State

上の関数dの自由変数を求めた例で, 結局自由変数はkであった. 結論はdを定義するFIXを実行する際に, memoryにkおよびd のコード番地をmemoryに退避せよということであった. これが実に自然に関数 呼び出しに伴うsetupを行なっていることに注意して欲しい.

実現の概要のところで, Min-Scheme の関数呼び出しを実行する際に何を memoryに退避したら良いかについて, CPSを用いずに自然言語で複雑な議論を 行なったことを思いだして欲しい. その際の複雑さの要因の一つに, 関数呼び 出しに伴って「暗黙に」渡されていながらもプログラムの表面に表れていない 情報(戻り番地etc.)があったことがあげられる.

(define (g x)
  (fix ((f (y) (+ y y)))
    (+ (f (+ x 10)) 1)))
において, gのcontinuationをfを呼び出す際に退避すべきだとい うことは, 気をつけて実行の様子をimageしてみないとわからない. CPSではそ の情報が自然にprogramの表面に表れている.

実現の概要まとめ

以下に, Min-SchemeFix の各essential syntaxがどのようなCPSで実現され, それがどのようなmachine codeになるのかについて表にまとめる.

tabular380

逆に, 各CPS primitiveが何のためにあるか, という観点からまとめると,

tabular384

課題

CPSを理解し, CPS変換アルゴリズム(Min-Scheme /Min-SchemeFix の関数定義 を, CPSのそれに変換するプログラム)を完成させよ.

デバッグのためのヒント:

CPS式自体, 簡単な置き換えでScheme のプログラムと見なすことができる. 例えば, 以下のScheme関数:
(define (f x)
  (+ x 1))
をCPS変換したらでてくるはずの, 次のCPS関数定義:
(f (k x) 
   (+ [x 1] [t]
      [(APPb k (t))]))
は, 形式的に次のSchemeプログラムに書き換えることができる.
(define (f k x) 
  (let ((t (+ x 1)))
    (k t)))
そしてこの関数はScheme処理系に実行させることができる. このようにして, 変換の結果出力されたCPS関数をScheme関数と見なして実行したものが, もと もとのSchemeプログラムと同じ結果を返すかどうか(kとしては受け取っ た結果を表示するような関数=(lambda (x) (display x))を渡す)で, CPS変換が正しいことを確認できる.

締切り: 10月28日(水)

...最適化を簡略化するため
もしletをsyntax sugarとして実現したとすると, let文を一度実行 する毎に, 関数呼び出しが一回起こる. さらにいえば, begin文は最終的には, それが含む文の数の分だけ, let文が重なった式に展開され, その数だけ関数 呼び出しが起こることになる. もしこの方法をとるのならばそのようにして生 成されたたくさんの関数呼び出しをinline展開によって取り除く という最適化が必須になる. それを認識し, 取り除くことは概念的には単純な 作業で, compilerは, 「ただ一度だけ呼ばれ, それ以外に使用されない関数を 見つけ, その呼びだしをinline展開し, 呼ばれた関数の定義を取り除く」とい う最適化を行なえば良い(letをsyntx sugarとして展開した時に局所的に定義 される関数はたった一度だけ呼ばれ, それ以外には使われない関数であること に注意せよ). そして一度だけ呼ばれる関数を見つけることは容易にでき, inline展開自体はただのsubstitutionに過ぎない. しかもこの最適化routine を実装すれば, let以外で同様の性質を持つ関数も自動的に最適化できる, と いうおまけがつく. この方法はletをessential syntaxとする方法よりも美し く, かつ得られるcompilerの性能も良い. しかしこの方法はcompilation speedにかなり大きな影響を及ぼすようである. Naiveな実装では大きなCPS式 のtraverseおよびmodificationを何回も繰り返すはめになる.
...必要になったらGCをするというものである.
この方法は実際, SML/NJで使われている.
...その両者は区別しておこう.
この方式を採用するのはひとえに, assemblyでGCを書きたくない, という動機に基づいている. Continuation recordをstackを使って割り当て/解放するのが常に得策ではないということは すでに認識されている事実である. 自作CPU上に完全なsystemを構築するため のstepは, という手順になるだろう.
...x)呼出時の生きている変数
変数というよりは ``値''というべきである
 

 

〔トップページへ〕 〔「コンパイラ演習レジュメ」のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 10 May, 1999