ソフトウェアの作成

「ソフトウェア」と一言でいっても、 と、いろいろあります。普通、「コンパイラ係」と「ソフトウェア係」の二人で分担します。
コンパイラの作り方 プロセッサ実験で作るコンパイラは、正確には

の2つから構成されていて、コンパイラ係が作るのは狭義のコンパイラです。
また、以下ではアセンブリ言語のことを「機械語」と書くことがよくあります。(コンパイラから見れば同じようなものですし。(^^;)

コンパイラ作成に関しては、「コンパイラ作成演習」という「プロセッサ実験」 とは半ば独立した演習があります。この演習には 田浦助手 の懇切丁寧なレジュメがあり、「レジュメさえ読めば(理解すれば)誰でもコンパイラが書ける」ような演習になっています。

田浦助手のレジュメ('98年度版)へ

ここではおおよその作業のながれを説明します。

(注: 以降の文章は'98 年度の演習に沿っています。また「何週目」というのは理想値です。(^o^))

なお、3年夏学期の萩谷先生の講義「言語処理系論」もコンパイラの作成を取り扱いますが、そちらとこの演習ではコンパイラの対象言語や手法などが違っているので、混乱しがちになるかもしれません。お気をつけ下さい。(^^;


1週目 --- 言語仕様を決める

まず、コンパイルする対象となる言語とコンパイラ自身を記述するための言語を 決めます。

この演習では、Scheme 「のような」言語を コンパイルするコンパイラを Scheme で書く場合に基づいて解説がされるので、 それに合わせて作る人がほとんどです。 すなわち、

です。

(また、この頃に浮動小数点演算ライブラリ担当の人やハードウェア担当の人と相談して、 他のデータより記憶容量が必要な浮動小数点をどのように扱うのかなどなどを決めることになります。浮動小数点については浮動小数点演算ライブラリの説明を参照。)


2週目 --- 字句解析と構文解析を行なう

次に、対象言語で書かれたプログラムのソースファイルを構文木(文章の構成を考えるときに使う形式。詳しくは萩谷先生の言語処理系論を参照。)に変換する 構文解析という操作を考えます。

本来構文解析の前にやるべき字句解析の部分は、お手軽に(手間の軽減)scheme の組み込み関数 read を使ってしまいます。 この関数を使うと、テキストファイルからプログラムをSchemeが扱いやすい形式で 取り出すことができて、とても幸せです。

さて、構文解析なのですが、 あとあとでの手間を考えて、生成される構文の種類を極力減らす ことを目指します。 当然、構文解析ルーチンは複雑になるのですが、あとで楽できるので我慢します。
具体的には、if、let(ここでは関数の中で局所的に変数を定義するための構文)、fix(ここでは関数の中で局所的に関数を定義するための構文)、関数適用 という4つの構文に変換します。 この4つの構文からなる言語を Min-Scheme と呼びます(Mini-Scheme の更に縮小版にあたります)。


3、4週目 --- CPS に変換する

ここでは、構文木をCPSと呼ばれる形式の中間言語に変換します。

今回および次々回が山場(落後者が大勢出るところ)です。 ここまででできた Min-Scheme の式を Continuation Passing Style(CPS) という中間言語に変換します。 この変換を行なう意味は以下の 3 つです。

  1. 「関数適用」の動作を明確にする
  2. 計算に順序をつける
  3. primitive(+,eq? 等)とユーザ定義の関数(f,g とか)を区別する

特に 1. が重要で、このために CPS があるといっても過言ではありません (と思います)。 簡単に言うと、関数適用の際に、「そっちの仕事が終ったら次はこれをやってくれ」 みたいに仕事を引数とともに渡します。で、呼ばれた方は、自分の仕事をやって それが終ったら、引数とともに渡された仕事にとりかかる、という感じです。 この渡された「仕事」というものが 継続(continuation) と呼ばれるわけですが、 CPS では何もかもが継続で表されています。 例えば「足し算を実行し結果をどこそこに入れたら この継続を実行する」とか「もし〜だったらこっちの継続を実行し、そうでなかったら そっちの継続を実行する」などなど。

CPSで使われる命令は、以下の 3 種類です。
5週目 --- 最適化を行なう

ここで、最適化と呼ばれる、計算時間を短縮するための種々の技法を組み込みます。CPSに変換したことにより、この辺の操作が楽にできます。

η reduction、β-contractionはほとんど必須と言ってよいですが、β-expansionについては下手にやるとかえって計算時間が長くなるはめになるので、注意が必要です。


5、6、7週目 --- Closure 変換を行なう

ここでは、変数を正確に扱うための処理を加えます。

Closure 変換 は、関数型言語で重要な関数内自由変数(その関数の外で定義されている変数)を扱うためのものです。 関数を定義するときに、その関数の自由変数を格納するための record を作り、 自由変数への参照は、この record への参照に置き換えます。


8週目 --- 抽象機械語コードを生成する

ここまで来ると、アセンブリ言語のコードの生成はもうすぐです。 が、1つクッションをおいて、実際の計算機(プロセッサ)より少しおおざっぱに機能を考えた(細かい制限を気にしない) 抽象機械用の アセンブリコードを生成します。

例えば抽象機械では、(実際の計算機にはある)足し算に使う値の範囲への制限などは考えません。この段階では、レジスタ割り当て(どのレジスタにどの値を入れてどう使うか)のみを考えれば、あとは単純な変換だけということになります。

レジスタ割り当てはこれまた最適なものを目指して色々と工夫をします。


8週目 --- 実機械語コードを生成する

ここでは、いよいよ実際のハードウェア(プロセッサ)がどのような機能を持っているかを考えなければなりません。

例えば、浮動小数点数は32bitで表す必要が(コンテストにおけるルール上)ありますが、プロセッサ(実機)のレジスタの大きさが 16 bit だと、浮動小数点数はレジスタを2つ使うか、ヒープ(メモリ上の一時的利用のための記憶領域)上にデータを置いてそのアドレスで表すことになります。 レジスタを2つ使う場合は、抽象機械のレジスタ1つが実機のレジスタ2つ に対応するため、使用できるレジスタ数が半分になってやりくりに大変です。また、ヒープ上にデータを置く場合は実際に計算する時にメモリ操作や管理(後述のGC)に時間がかかります。

このあたりが高速化を目指す際の悩みどころです。


9週目 --- GC のルーチンを作る

記憶領域(メモリ)を効率良く活用する方法である Garbage Collection(GCと略される。直訳すれば「ゴミ集め」)を考えます。GCとは簡単に言うと、メモリのもう使わないデータが入っている部分を空にしてしまう操作です。

Scheme はメモリをかなり使うという性質を持つ言語なので、当然の機能として GC があります。 小さいプログラムでは関係ないのですが、レイトレのような大きなプログラム を動かそうとする時には必須の機能です。

ただし、今回のレイトレではメモリをあまり使わないようにすることが可能なので、実際にGCの操作を組み込んだ人は少ないようです。


10週目以降 --- レイトレプログラムをコンパイルする

コンパイラが完成すれば、あとはレイトレプログラムをコンパイルしてしまうだけ!です。

ただし(^^;、その前に小さなテストプログラムのコンパイルとバグの発見・訂正を 繰り返すことになります。
正しくコンパイルできたかどうかは、たいていまだハードウェアは でき上がっていないのでシミュレータ(ここではハードウェアのふりをして 機械語を解釈・実行してくれる端末で動くプログラムのこと)を使って確かめていきます。

実際には更に、ハードウェアの機能変更や浮動小数点演算ライブラリとの連係など 乗り越えなければならない山があったりします。(^^;


浮動小数点ライブラリ

はじめに

「浮動小数点ライブラリ」とは、何でしょう?

「ライブラリ」は「よく使う便利なプログラムの部品の集まり」ですから、「浮動小数点ライブラリ」は「浮動小数点に関する、よく使う便利なプログラムの部品の集まり」です。
それでは「浮動小数点」の方は何なのでしょうか。

コンピュータグラフィックスをするにあたって、小数の計算をすることは避けては通れません。
整数だけでは、表示できる図形に限りがあるからです。
小数をコンピュータの中で表現する方法には大きく分けて2種類あって、「浮動小数点」はそのうちの一つです。(ちなみに、もう片方は「固定小数点」です。)

従って、「浮動小数点ルーチン」とは「小数の計算をするプログラムの集まり」なのですが、何故これらを特別に扱う必要があるのでしょうか。
理由の一つ目は、小数の計算をプロセッサが直接サポートしてくれることは(ほとんど)ない、という事です。小数の計算は、整数の計算に比べてとても複雑なので、プロセッサの中には入り切らなくなってしまうのです。だから、プロセッサがサポートしてくれる命令だけを使って、小数の計算を出来るようなプログラムを用意しておかなくてはなりません。
理由の二つ目は、プロセッサ実験ならではの問題です。プロセッサ実験は「画像を速く表示すること」を目標にしているのですが、画像を表示するのにかかる時間のほとんどは、小数の計算をしている時間なのです。それで、小数の計算を速くすることに特別の労力を費やす必要があるのです。

具体的には、以下のような計算をするプログラムを用意するのが普通です。
これらのプログラムは、機械語で記述します。レイトレーシングプログラムと同様にSchemeで記述してもいいのですが、そうすると実行が遅くなってしまいます。

このうち、特に使われる回数が多いのは足し算・引き算・かけ算です。
これらの演算を少しでも速く実行できるようにしようと、各班工夫を重ねます。


アセンブラ

「アセンブラ」とは何でしょう?

上で説明した通り、「コンパイラ」は「Schemeで書かれたレイトレーシングプログラムを機械語に直してくれるもの」ですが、この表現は、実は余り正確ではありません。また、「浮動小数点ルーチン」は「機械語で記述されている」のですが、これも余り正確な言い方ではありません。この2つは、実は「アセンブリ言語」です。「アセンブリ言語」は「機械語」と似ていますが、ちょっとだけ違います。

プロセッサ(コンピュータ)が理解できるのは、0と1だけなので、機械語は0と1だけで書かなくてはなりません。「0000000100100001は、ここに記憶してある数からそこに記憶してある数を引く」という感じです。
でも、そんなことをしたら、どこまで書いたか分からなくなったりして大変です。そこで、0と1に直すのは後でまとめてすることにして、とりあえずアルファベットを使って表現します。これが、アセンブリ言語で、アセンブリ言語を機械語に直すのが、アセンブラです。
アセンブリ言語では「sub "ここ" "そこ"」という具合に記述します。さっきよりも、ぐっと人間的になりましたね(笑)。

アセンブラは、「sub "ここ" "そこ" → 00000"ここ" "そこ"0001」という具合に、アセンブリ言語と機械語を1:1で対応付けしています。どんな命令がどんな0と1の組合せになるのか、ということは、プロセッサに依存します。


シミュレータ

コンパイラや浮動小数点ライブラリを作っている時に「本当に正しく動いてくれるだろうか」と、不安を感じることがあります。
ハードウェアが完成するまで確かめることが出来ないのでは、うまく動かなかった時に誰が悪いのか分からなくて直すのが大変なので、先にソフトウェア部分だけ正しく動くかどうか確かめておきます。
シミュレータはそのためのソフトウェアで、プロセッサの様に機械語プログラムを受けとって計算をします。

シミュレータで正しく動くのに実際の機械で動かなかったら、機械の方にバグがある、と判断することができます。(まれに、シミュレータにバグがある場合もありますが、それでも、シミュレータのバグを探す方がずっと簡単なのです)

一般に、シミュレータでの実行は、実際の機械での実行よりも時間がかかります。レイトレーシングのプログラムを実行する時に、1時間〜2時間かかる、ということは珍しくありません。


レイトレプログラムの作り方

はじめに

コンピュータで3次元の(リアルな)絵を描く、確実な方法は何でしょう?
コンピュータ内に(仮想的な)3次元空間をつくり物体を配置して、 それを(仮想的な)スクリーンに投影したらどうだ、ということで 生まれた(?)レイトレの成長過程を見ていくことにしましょう。

「物体を配置する」というのは、例えば半径 r の球を 座標 (a, b, c) に置く ということですが、それを

                2          2          2     2
         (x - a)  + (y - b)  + (z - c)  <  r

という方程式で表します。 つまり、1つの物体(の定義)が1つの方程式に対応するわけです。 複数の物体の存在する空間は、上のような方程式の列で表されます。

「スクリーンに投影する」というのは、 スクリーンを格子状に区切り、その1マス1マスに対してそこにあるべき色を 求めるということです。 具体的には、視点 (xe, ye, ze) と スクリーン上の1マスの中心 (xt, yt, zt) を結ぶ直線

        (x - xe)    (y - ye)    (z - ze)
        --------- = --------- = ---------
        (xt - xe)   (yt - ye)   (zt - ze)

と空間内の物体とが交点を持つかどうかを調べれば、そのマスの大体の色は 分かります。 つまり、交点を持つ物体のうちで最も視点に近い物体の色がそのマスの色という わけです。 ただ、やってみれば分かりますがこれだけではべたーっとした絵になり、 質感も何もありません。
sample-beta.gif

明暗

この絵に明暗を付けるには、物体と光の位置関係を考える必要があります。 すなわち、光が多く当たる面は明るく、そうでない面は暗くするということです。 上で求めた交点における物体の法線ベクトル N = (nx, ny, nz) と光源からの光の方向 L = (lx, ly, lz) を用いて、明暗の度合 br は N と -L のなす角の cos 、 つまり式で表すと、

                       nx*lx + ny*ly + nz*lz
        br = - -----------------------------------------
               sqrt(nx^2+ny^2+nz^2)*sqrt(lx^2+ly^2+lz^2)

となります。ただし、物体の裏側で全く光が当たらない(br < 0)とき は br = 0 にしなければなりません。 br を、物体の持つ色 (r, g, b) に掛け合わせることによって、ある程度 質感のある絵ができます。
sample-meian-32.gif

質問: この絵で足りないと感じるものはどれでしょうか?

  1. ハイライト

自然界の「かげ」というのには2種類あります。 物体の裏側のようにもともと光が当たらないためにできる「陰」と、本当は光が当たるべき所に他の物体が邪魔してできる「影」です。
「陰」というのは前に述べた明暗の「暗」のことですが、では、「影」はどのようにして判定するのでしょうか?

物体上の1点が「影」かどうかは、その点から光に向かって直線を伸ばし、 その直線と交わる物体があるかどうかで調べられます。もちろん、 交わる物体がある場合が「影」で、「影」の場合は「陰」と同様に br = 0 に します(すなわち物体の色を無視するわけです)。
sample-kage-32.gif

ハイライト

プラスチックのようなものだと、青い物でも視点によっては白っぽく見える部分が ありますよね? それをハイライトといいます。 今までの手法(明暗)では、青い物体を白くすることはできません。 また、明暗は視点が動いても変化しませんが、ハイライトは視点が動けば動きます (実際に試してみると良いでしょう)。 これはすなわち、視線の方向・交点における物体の法線・光の方向 の3者によって 色(目に見える色)が決定されるということを示しています。 当然(?)、光の反射方向と視線の方向が(逆向きに)一致したとき最もまぶしく (明るく)、 2つの方向がずれるにしたがって急速に暗くなります(「暗くなる」といっても あくまで、ハイライトの成分のみを考慮した場合のことです)。

例えば、法線ベクトルを N, 光の入射方向を L とすると、 光の反射方向 L' は

        L' = L - 2 * N・L

で求められますが、L' と視線方向 E の成す角θからハイライトの強さ hl を

                    4
        hl = (cosθ)                 (90°< θ < 180°)
             0                       (0° < θ < 90°)

として hl を明暗で求めた色 (r, g, b) の r,g,b それぞれに加える、 という方法があります。 当然、「影」の部分でハイライトを求めてはいけません。
sample-hilight-32.gif

鏡の表現こそ、レイトレならではの醍醐味でしょう。 光が鏡に当たると、その点での法線と対称な方向に反射します(飛んでいきます)。 それを逆にたどると鏡上の1点が何色に見えるかが分かるじゃないか、 というわけです。 簡単にいうと、光と逆方向に同じように(難しく言うと「再帰的に」)視線を出して そこで見える色をその物体(鏡)の色とします。

ただ、2枚の鏡を向かい合わせたようなものに対してこれをそのまま適用して 永久に計算が終らないと困るので、 「10回反射したらそれ以上は計算しない」のように反射回数を制限したりします。

また、 反射方向に見える色と物体の色を適当に混ぜ合わせることによって、金属のような 質感を出すことができます(物体の色を黄色にすると「金」、灰色にすると「銀」 みたいな感じです)。
sample-kagami-32.gif

テクスチャマッピング

物体の持つ色は1色とは限りません。そこで物体の持つ色を交点の位置によって 物体の色を変化させるという手法がテクスチャマッピングです。 平面に貼られたタイルがその好例で、たとえば

               x          y
        ((int)--- + (int)---) mod 2
               l          l

が0か1かによって色を変えればタイルができます (交点の座標を (x,y,z) として l をタイル1枚の長さとした時)。
sample-texture-32.gif

他にもいろんな技法がありますが、基本的な部分としてはこんなところです。


〔トップページへ〕 〔「完成までのプロセス」のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 31 May, 1999