まとめ

インタープリタについて

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

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

整数データとそれに対する操作(足し算やかけ算など)
真理値データに対する操作(if-then-else)
let式による変数束縛
関数定義と関数適用

作成したインタープリタは、評価の対象となる式(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言語の処理系では非常に重要な地位を占めているものであり、興味をもった人は、是非、型推論器の実装に取り組んでほしい。

コンパイラについて

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

対象となる高級言語(本実験ではminiOCaml言語、あるいは、それを各自が拡張したもの) のプログラムを、抽象機械のプログラムに変換するコンパイラ。
抽象機械のプログラムを実行する処理系(インタープリタ)。

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

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

最終課題

最終レポートは以下の「必須課題」をすべて解くこと。なお、必須課題をすべてこなせば、単位の取得は可能だが、発展課題を1つ以上解くことを推奨する。(ただし発展課題7-5, 7-6, 7-7については3つすべてやった場合のみ、発展課題1つ分としてカウントする。)

[全員必須] これまで作成したプログラムと解答した課題を整理し、 1つのまとまったインタープリタ、型検査器およびコンパイラとして仕上げよ。
[全員必須] 上記のインタープリタおよびコンパイラに、ミニOCaml言語のプログラムとして面白いものを与え、正しく動作するかチェックするとともに、性能(実行速度)を調べよ。なお、例題として与えるプログラムは、エラーとなるものを必ず含むこと (構文エラー、型エラー、実行時エラーなど)。「面白い例題」としては、再帰呼び出しを使って書ける関数を選べばよい。たとえば、階乗、べき乗、最大公約数、n番目の素数、McCarthyの91関数などが考えられる。

[全員必須] 本実験で学んだことについての考察および感想を記述せよ。たとえば、このインタープリタは素朴でわかりやすい実装を優先したために、効率がよくない点があるので、それについての改善案を思いつけば、それを記述せよ。また、関数型プログラム言語の利点と欠点について、自分の考えを述べよ。

[全員必須] 自分なりの工夫(インタープリタの拡張、型検査器の拡張、型推論器の実装、コンパイラの高速化など) を1つ以上すること．

形式: A4サイズで表紙には実験名、氏名、学籍番号を記載。 2ページ目以降がレポート本体であり、末尾に、作成したプログラム、テストプログラム、テストの実行結果を添付すること。レポートは、プログラムの概要の説明のほか、自分が工夫した点や苦労した点については詳細に説明すること。

トップ. 前へ,

亀山幸義