** Min-Caml & Objective Caml 版
   コンパイラ・CPU演習用レイトレーサ **

                                    2001.12.21 Yutaka Oiwa

****************
1. これは何？
****************

このプログラムは、Kawamichi Ryoji, Motohiko Nagano 両氏による
Chez Scheme 版レイトレーサ (1996年版) を Min-Caml に移植したものです。

移植に当たっては、次の点に留意してプログラムを書き換えているので、
普通の Caml のプログラムとしては不自然な点があります。

・基本データ型として整数、論理値、実数 のみを使用。

  - 論理値は 1, 0 の整数としても問題が生じないように配慮。

・配列と tuple 以外のデータ構造を使っていない。

  - 参照 → 1要素の配列に書き換え
  - リスト → 配列に書き換え
  - option (None/Some) → 論理値 + 別の変数

・実行時、初期化フェーズ以外では動的なメモリ確保を行なわない。

  - グローバルに確保した配列を用いた関数間の受渡し
  - ベクトル様のデータはすべてグローバル配列を使い回し

・比較プリミティブ (=, <, <= etc.) は整数にのみ使用。
  実数比較は外部関数 (fless, fequal) 化。

・ローカル変数（引数や計算途中の値を含む）の数が多くなり過ぎる
  場所を中心に、グローバル配列を一時変数として用いることで
  想定されるレジスタ使用数を削減。

・一時変数が（2項演算子の引数を左→右に評価した際に）少なくなる
  ように一部の式に let を挿入。

・その他、Min-Caml の構文に合わせたプログラムの書き換え。

  - begin, end → ( )
  - 関数本体に ; で逐次実行される複数の式 → ( ) で括る
  - 単体で現れる比較 → if E then true else false など

****************
 2. 使い方
****************

* 2-1. Min-Caml でのコンパイル

min-rt.ml は Min-Caml の構文規則に沿っているので、そのまま
コンパイルできると思います。miniMLRuntime.mli を参考にして、
プログラムが必要とするランタイム関数を機械語か Min-Caml で
提供して下さい。
また、グローバル変数に必要な領域は、globals.ml を元にして
別に確保して下さい。

* 2-2. Objective Caml での実行

まず、プログラムの先頭にある (*NOMINCAML*) でコメントアウト
されている2行を復活させ、(*MINCAML*) のある1行を削除して下さい。
その上で付属の Makefile を使えばコンパイルできます。

    いちいち書き換えるのがめんどくさい人は、付属の preprocess.sh を
    使って、Makefile の PP オプションを有効にすれば、自動的に
    OCaml Compiler が処理してくれますが、エラーメッセージが
    違うファイル (min-rt.ppo) を指すので気をつけて下さい。

テキスト形式の .sld ファイルを標準入力から入れてやると、
アスキー形式の .ppm ファイルを標準出力に吐き出します。

* 2-2-1 プリミティブ関数の追加

Min-Caml に持っていった時に困らないように、min-rt.ml を
コンパイルする際には、miniMLRuntime.mli で定義した関数しか
使えないようにコンパイルオプション -nopervasives を
指定してあります。

Min-Caml にプリミティブを追加する前提で、プリミティブを
追加したい場合は、次のようにして下さい。

(1) OCaml に既にある関数を追加する場合。

| 良く分からなかったら Makefile から -nopervasives を
| 取ってしまえばとりあえず標準の関数は全部使えるように
| なります。その場合は使っちゃいけないものを使っているか
| どうかは自分でチェックして下さい。

例えば、整数除算 (/) を追加する場合は、
次のようにします。

 - miniMLRuntime.mli に 

    val ( / ) : int -> int -> int

   の1行を追加。

 - miniMLRuntime.ml の適当な場所に

    let ( / ) = ( / )

   または

    let ( / ) = Pervasives.( / )

   の1行を追加。

   | Pervasives モジュールは。Ocaml で
   | デフォルトでそのまま使える関数を定義しているモジュールです。

   | 提供した miniMLRuntime.mli で既に定義されている関数に
   | 関しては、高速化のため external 宣言を使っています。
   | 特に気にしなくてもいいですが、詳しくは ocaml マニュアル参照。

(2) OCaml に既にない関数を追加する場合。

 - miniMLRuntime.mli に適当な宣言を追加。

 - miniMLRuntime.ml (の先頭) でその関数を実装。
   比較関数を整数以外で使う時は必ず先頭で定義しないと
   型エラーが起こります。

****************
 3. その他
****************

もともとの Scheme 版のソースだけを見ても、実はこのプログラムは
まだまだアルゴリズム的にも性能改善の余地があります。が、
その辺りにはほとんど手をつけていないので、余裕のある人は
いっそ1からプログラムを書き直すというのもいいでしょう。

このプログラムの Objective Caml 対応の部分については、
質問があったら <oiwa@yl.is.s.u-tokyo.ac.jp> までメールして下さい。

****************
 4. おまけ
****************

ひょっとするとはまるかも知れない落し穴 :-)

- オブジェクトのデータ構造は如何様にも書き換えられるように
  プログラムの先頭で定義したアクセス関数を必ず使うように
  プログラムを書いてあります (読み込みルーチンを除く)。
  この関数くらいはインライン化されることを前提にしてあります。
  一部のデータは2段の間接参照になっていますので、
  気になる人はプログラムを読んで最適化して下さい。

- オブジェクト読み込みルーチンは、もともとの Scheme のバージョン
  では「全データ読み込み→全データ変換」という順序で
  処理していましたが、今回のバージョンでは
  「1データ読み込み→データ変換」を繰り返すようになっています。

  シリアル通信の処理を簡略化して、制御信号を使わないように
  している場合、ひょっとすると変換している間に次のデータを
  取り落とす可能性があります。タイミングを計算して問題が
  生じるようだったら、Scheme 版などを参考に適当に書き換えて下さい。

  | 4年前に自分たちがやった時は、Scheme 版の Read-Environ の中の
  | sin/cos の計算で見事にはまりました。:-)

**** End of Text ****