まとめ

インタープリタについて

今回の実験では、関数型プログラム言語 OCaml で、 ミニOCaml に対するインタープリタを作成し、それによって、OCaml 言語自身への 理解を深めることを目的とした。 これを通して、 今まで大雑把に理解していたプログラム言語の意味が、 厳密に理解できたであろう。

ここまでの作業で、以下の要素を含むミニOCaml言語(ただし、リストなどは 未実装)に対するインタープリタを作成することができた。

作成したインタープリタは、評価の対象となる式(exp型のデータとして 表現されたもの)と、環境を引数にとり、 束縛が起きるごとに環境を拡張することによって 計算を進めるインタープリタである。(評価の過程で、 環境を受け渡すことから、環境渡し方式environment-passing style と言われる。)

このタイプのインタープリタは、「OCaml を利用して記述された プログラムであり、OCaml(のサブセット)の評価をするプログラムである」 ことから、meta-circular interpreterと呼ばれる。 「自分で、自分自身の評価をする」というものである。 実は、ここで述べた環境渡し方式の meta-circular interpreterは、 関数型プログラム言語のルーツといえる Lisp 1.5の時代 (Lisp は John McCarthy が考案した関数型プログラム言語であり Lisp 1.5は その最も初期のバージョンの1つである)からあるものである。 (ただし、Lisp 1.5 は、動的束縛であった。)

meta-circular interpreter を作って何の意味があるのか、と 思う人もいるかもしれないが、 meta-circular interpreter の構造が(簡潔に)記述できる、という こと自体が、関数型プログラム言語の優位性を物語っている。 また、このインタープリタの作成を通じて、 OCaml の主要な機能を深く知ることができる。 (ソーティングなどのプログラムをいくら書いても、 OCaml 言語の変数束縛や関数適用の順番などがわかるようになる わけではない。)

型推論について

プログラム言語の処理系の2つの作り方の基本を学ぶことができた。 インタープリタの実装に続いて、「型システム」への理解を深めるため、 型検査器の実装を行った。 型検査器がおこなうことは、インタープリタとはまったく異なるが、 型検査器のプログラムは、インタープリタとよく似ており、 インタープリタで実装した lookup関数などは型検査器においても再利用でき る等もわかったことと思う。 型検査の対象とした言語は、時間の都合上、 ミニOCaml言語をさらに小さくして 以下の要素からなる言語とした。ただし、本実験で述べた方法を使えば、 ミニOCaml言語全体の型検査器を作るのは、容易である。

型検査済みの式は、プログラムの実行時に (1 + "abc")のような実行を行う ことがないので、より安全であると言える。 なお、 OCaml言語のように、変数の型を(通常は)宣言しない言語では、 型検査をさらに強力にした型推論が必要である。 型推論は、 OCaml言語の処理系では非常に重要な地位を占めているものであり、 興味をもった人は、是非、型推論器の実装に取り組んでほしい。

コンパイラについて

簡単なコンパイラの実装を行った。 コンパイラに基づくプログラムの処理は以下の構成を取る。

gccコンパイラでは、C言語のプログラムを、x86 CPU などの機械語のプログラムに変換するので、 実行時にインタープリタは必要なく、より高速に実行される。 一方、本実験の方式は、Java言語の javac コンパイラや OCaml言語の ocamlc コンパイラなどで採用されている方式であり、 抽象機械インタープリタさえあれば、どんなハードウェアでも実行することができ、可搬性が高い、という利点がある。 また、本実験では、実行性能の向上のための対策(いわゆる optimization (最適化))は、 ほとんどやらなかったが、やろうと思えば、上記の方式の範囲内でも相当の高速化が図れる (逆にいうと、コンパイルすることにより、インタープリタより高速に実行できるようになるのは、 「記述言語を、高級言語から機械語に近い低級言語に変換した」ことが主たる理由ではなく、 「変換途中で、静的情報を用いて、高速化のための工夫をいろいろしている」ということが要因ということになる。)

本実験では、「2種類の言語間の変換」ということに焦点を絞った課題としたが、 OCaml言語を使った実装が、 驚くほど素直に(教科書に書いてあるアルゴリズムをそのまま書き写すような処理だけで) 実現できた、ということがわかってもらえたことだと思う。

最終課題

最終レポートは以下の「必須課題」をすべて解くこと。 なお、必須課題をすべてこなせば、単位の取得は可能だが、 発展課題を1つ以上解くことを推奨する。(ただし発展課題7-5, 7-6, 7-7については3つすべてやった場合のみ、発展課題1つ分としてカウントする。) 形式: A4サイズの紙に記載: 表紙には実験名、氏名、学籍番号を記載。 2ページ目以降がレポート本体であり、末尾に、 作成したプログラム、テストプログラム、テストの実行結果を添付する こと。レポートは、プログラムの概要の説明のほか、自分が工夫した 点や苦労した点については詳細に説明すること。
トップ.

亀山 幸義