6-1. インタープリタに対する様々な工夫と拡張

• 性能の向上; インタープリタであるのでやむを得ない面があるが、 いろいろなところで性能向上をはかる余地がある。たとえば、 環境は、変数と値のペアを単純にリストの形で並べてしまったので、 変数の値を調べる lookup関数は、 リストの長さに比例する時間がかってしまい、非常に効率がわるい。 これを改善せよ。(改善した場合は、どのくらいの改善になっているか 実行速度を測定せよ。)
• exp 型や value 型の式が、そのまま印刷されると読みにくい。 そこで、これらの型の式を、なるべくきれいに(OCaml での表現 になるべく近い形で)印刷する関数 pretty_print_exp と pretty_print_value を作成せよ。
  たとえば、

     Let("x", IntLit 1, Plus(IntLit 2, Times(Var "x", IntLit 3)))
  

  という式を、

     let x = 1 in 2 + (x * 3)
  

  あるいは、さらに頑張って

     let x = 1 in 2 + x * 3
  

  と印刷するというものである。括弧を常に印刷するなら、簡単であるが、 上記の2番目の印刷例のように、「括弧を省略しても意味がかわらない場合に は省略する」ということを実現するのは、かなり難しい。

  どこまでやれば「きれい」かについては特に基準をもうけず、 各自の判断と工夫に任せる。 OCaml 処理系の出力と同程度になれば素晴しい。

  なお、このような変換を行う関数は、 pretty printer と呼ぶ。また、 構文解析の逆の処理なので unparse という名称で呼ばれることもある。 つまり、理想的には、parse と「ちょうど逆」をやる関数を作りたい。

• 今回のインタープリタは、 入力がおかしければ、"unknown expressoin" といった Failure 例外を出し、 実行途中におかしくなれば、"wrong value" といった Failure 例外を出す、 という形をとっている。これでは、具体的に、入力されたもののどの部分が どうおかしかったかわからないし、そもそも、例外を出してプログラムが終了してしまうので、 複数のプログラムを次々に評価することもできず、 使い勝手が悪い。この点を改善せよ。具体的には、以下の2点を考えよ。
  1. エラーの種類をなるべく丁寧に表示せよ。(たとえば、"unknown expression" という場合には、どういう式が unknownかを示せ。)
  2. エラーが起きた場合、そのエラーを表示した後、停止せずに、 次の式を評価するよう、main関数を改良せよ。
• インタープリタへの理解を深めるために、 評価の過程を一歩一歩表示させたい。 たとえば、(1+2)*3 という式が与えられると、まず 3*3 にして、 次に 9 を得るというステップを順番に表示させることにより、 入力式の誤りや、インタープリタ自体の実装誤りを発見しやすくなる。 いわゆる debugger における「ステップ実行」のようなものである。 この機能を実装せよ。
• 本実験で作成したインタープリタの適用範囲を広げ、なるべく OCaml に近付けよ。そのための拡張の例を以下にあげる。 (多くの拡張で、parser の拡張も必要である。これは、詳細をTAに聞くこと。 本実験では、parser の書き方を 説明してはいないので、TA に拡張してもらってもよい。)
  • 相互再帰関数の追加 (相互再帰関数とは、2つ以上の再帰関数の定義が 他の関数を参照しているものであり、「同時に定義」しないといけない ものである。OCaml では、相互再帰関数は、 let rec fun1 x = ... and fun2 x = ... という形で定義される。)
  • OCaml では、"+" という2項演算子を関数として使いたいときは "(+)" として使えばよい。たとえば、(+) 10 20 は 30という答えを返す式である。 この場合、面白いのは (+) 10 というように、引数を1つだけ与えても 意味がある式であり、たとえば、

       let f = (+) 10 in
         (f 20) + (f 30)
    

    という式を書くことができる。 同様に、他の演算子についても、演算子を括弧で囲うと、関数として使えるよ うに拡張せよ。
  • パターンマッチ構文の導入; たとえば let (x,_,z) = e1 in ... とい う形で、パターンマッチができると、使い勝手が向上する。
  • match式の追加; match ... with ... (一般的な match式は難しい ので、適度に制限したものでよい。)
  • 逐次実行文の追加; C言語のように e1; e2; e3 と順番に実行する
  • 「例外」機構の追加; OCamlの例外機構である try や raise を使えるようにする。
  • 本授業資料の次の節で述べている、リストデータ型の導入。
  • 本授業資料の後半で「オプショナル」として述べている型検査、型推論機構の実装。

亀山幸義