MyC言語からOCamlへの「コンパイラ」

 インタプリタが完成したら,次はコンパイラを作りたくなるのが人情だろう。普通はコンパイラといえば,アセンブリ言語や機械語,仮想機械コードなど,低水準言語への変換器を意味する。しかし,ここではちょっと趣向を変えて,MyC言語からOCamlへの「コンパイラ」を考えてみよう。

 MyC言語からOCamlへの最も簡単(というか怠慢)なコンパイラは,先のインタプリタを呼び出すだけのプログラムだ。より正確にいえば,「MyC言語のプログラムPを入力として受け取り,interpret Pを出力として返す」ようなプログラムということになる。例えば,「n = 3」というMyCプログラムを入力したら,「interpret (Const("n", 3))」というOCamlプログラムを出力するわけだ。

 これだけではコンパイラといっても実際の処理はインタプリタと何ら変わらず,あまりありがたみがない。しかし,実はこのような怠慢なコンパイラを少し改良すれば,もっとまともなMyCからOCamlへのコンパイラらしきものができるのだ。

 例えば,先の「n = 3」の例を考えてみよう。「interpret (Const("n", 3))」というOCamlプログラムに対して,interpret関数の定義をインライン展開し,さらにパターンマッチングの処理を行えば,「Hashtbl.replace table "n" 3」になる。

 同様に,例えばa = b + cというMyCプログラムに対して,interpret (Add("a", "b", "c"))というOCamlプログラムを考える。intepret関数をインライン展開し,パターンマッチングの計算をすれば,Hashtbl.replace table "a" (Hashtbl.find table "b" + Hashtbl.find table "c")というOCamlプログラムが得られる。

 つまり「interpret関数をインライン展開して,パターンマッチングを計算する」という処理を記述すれば,コンパイラが作れそうである。この処理を機械的に書き下してみると,次のようなcompile関数になる。

open Syntax

let rec compile s = match s with
  | Const(x, i) ->
      Printf.printf "Hashtbl.replace table \"%s\" (%d);\n" x i
  | Add(x, y, z) ->
      Printf.printf "Hashtbl.replace table \"%s\"\n" x;
      Printf.printf "  (Hashtbl.find table \"%s\" +\n" y;
      Printf.printf "     Hashtbl.find table \"%s\");\n" z
  | While(x, y, s2) ->
      Printf.printf "while Hashtbl.find table \"%s\" >\n" x;
      Printf.printf "  Hashtbl.find table \"%s\" do\n" y;
      compile s2;
      Printf.printf "done;\n"
  | Seq(ss) ->
      Printf.printf "(\n";
      List.iter compile ss;
      Printf.printf ")\n"
  | Print(x) ->
      Printf.printf "Printf.printf \"%%d\\n\"\n";
      Printf.printf "  (Hashtbl.find table \"%s\");" x

let main =
  let s =
    Parser.statement Lexer.token
      (Lexing.from_channel stdin) in
  Printf.printf "let table = Hashtbl.create 10 in\n";
  compile s

 ただし,while文の場合だけは少し注意しなければならない。interpret関数を単純に「インライン展開」し続けるとコンパイラが無限ループに陥ってしまうからだ(引数の変わらない再帰呼び出し「interpret s」があるため)。ここでは少し工夫して,MyC言語のwhile文をOCamlのwhile文に変換している。

 このコードをcompile.mlというファイルに保存する。以下のようにすれば,MyC言語のプログラムをOCamlのコードにコンパイルして実行できる。

> ocamlc syntax.ml parser.mli parser.ml lexer.ml compile.ml -o compile
> ./compile < sum.myc > sum.ml
> ocamlc sum.ml -o sum
> ./sum
55

 試しにコンパイルされたプログラムsum.mlを見てみると,下のようになっている(読みやすくするために手で整形した)。sum.mycをinterpretで実行したときと同じ動作を行うコードになっていることがわかるだろう。

let table = Hashtbl.create 10 in
Hashtbl.replace table "zero" 0;
Hashtbl.replace table "minus_one" (-1);
Hashtbl.replace table "sum" 0;
Hashtbl.replace table "n" 10;
while Hashtbl.find table "n" >
  Hashtbl.find table "zero" do
  (Hashtbl.replace table "sum"
     (Hashtbl.find table "sum" +
        Hashtbl.find table "n");
   Hashtbl.replace table "n"
     (Hashtbl.find table "n" +
        Hashtbl.find table "minus_one"))
done;
Printf.printf "%d\n"
  (Hashtbl.find table "sum")

 ちなみに,Hashtblライブラリの中まで踏み込んで,Hashtbl.replaceやHashtbl.findをインライン展開すれば,もっと高速なOCamlコードを生成することもできる。

 このようにインタプリタからコンパイラを導出する手順は,部分評価(partial evaluation)という手法の一種で,二村射影(Futamura projection)と呼ばれている。部分評価や二村射影は,名前からもわかるように日本人研究者である二村良彦氏が1970年前後に考案した手法で,Partial Evaluation and Program Manipulation (PEPM)という専門の学会ができるほどの一大分野になった。部分評価や二村射影を使えば,狭い意味でのプログラミング言語処理系を実現できるだけでなく,「言語Xで記述された『言語Yの解釈器』」から「言語Yから言語Xへの変換器」を導出できる。このため,動的コード生成やXML処理などにも応用されている。

MyC言語の数学的定義

 インタプリタやコンパイラを開発するには,対象とする言語の定義をきちんと理解する必要がある。ところが,ほとんどのプログラミング言語の仕様は自然言語(多くの場合は英語)で記述されており,あいまいさや複雑さのせいで,どうしても「きちんと理解」できない場合がある。例えば,Javaのジェネリックスや動的クラスローディングの仕様は,微妙な文章で「定義」されており,実際に様々なバグが過去に発見されている(参考リンク1参考リンク2参考リンク3)。

 では,どうすればプログラミング言語の仕様を正確に定義できるのだろうか?

 一般にプログラミング言語の定義は「構文」と「意味」の二つからなる。構文については,BNF記法(Backus-Naur form notation)による定義が有名だ。例えばMyC言語の構文は,以下のような一種のBNF記法で定義できる(変数の名前(variable)や整数定数(constant)の定義,および空白や改行については省略している)。

<statement> ::= <variable> "=" <constant>
             |  <variable> "=" <variable> "+" <variable>
             |  "while" "(" <variable> ">" <variable> ")" <statement>
             |  "{" <statement_list> "}"
             |  "print" <variable>
<statement_list> ::= <statement> ";" <statement_list>
                  |  ""

 この定義によれば,例えば{ }は正しい文になる。<statement_list>は空でもよいとされているからだ。前回の「言葉による」説明では,このような言語仕様の詳細はあいまいになっており,OCamlYaccによる実装でしか定義されていなかった。

 さて,上のBNF記法による定義を言葉で書き下してみると次のようになる。

  • 「変数の名前 = 整数定数」は文である。
  • 「変数の名前 = 変数の名前 + 変数の名前」は文である。
  • Xが文ならば,「while ( 変数の名前 > 変数の名前 ) X」は文である。
  • Yが文のリストならば,「{ Y }」は文である。
  • 「print 変数の名前」は文である。
  • Xが文で,Yが文のリストならば,「X; Y」は文のリストである。
  • 「」(空文字列)は文のリストである。
  • 以上の規則によって定義されるものだけが文や文のリストである(それ以外のものは文や文のリストではない)。

 以上のようなルールを数学的(というか論理学的)な論理式で表現すれば,「文」や「文のリスト」の集合を厳密に定義できる。こうした定義の仕方を一般に帰納的定義(inductive definition)という。BNF記法による定義は,帰納的定義の一種とみなすことができる。

 実は,帰納的定義を用いると,プログラミング言語の構文だけでなく,意味も定義できる。例えば,MyC言語の「文」の意味は,下のように定義できる。ただし,EXEC(S1, X, S2)は,状態S1と文Xと状態S2の間の関係(relation)を表しており,直観としては「状態S1のもとで文Xを実行すると状態S2になる」ということを意図している。状態(state)の定義は省略するが,変数の名前を受け取って整数定数を返すテーブルのことだと思ってほしい。

  1. UPDATE(S1, x, i, S2)ならば,EXEC(S1, x = i, S2)が成り立つ。ただし,UPDATE(S1, x, i, S2)は「状態S1におけるxの値をiに更新したら状態S2になる」という関係を表すとする。
  2. LOOKUP(S1, y, i)かつLOOKUP(S1, z, j)かつUPDATE(S1, x, i + j, S2)ならば,EXEC(S1, x = y + z, S2)が成り立つ。ただし,LOOKUP(S1, y, i)等は「状態S1におけるyの値はiである」等の関係を表すとする。
  3. LOOKUP(S1, x, i)かつLOOKUP(S1, y, j)かつi <= jならば,EXEC(S1, while (x > y) X, S1)が成り立つ。
  4. LOOKUP(S1, x, i)かつLOOKUP(S1, y, j)かつi > jで,さらにEXEC(S1, X, S2)かつEXEC(S2, while (x > y) X, S3)ならば,EXEC(S1, while (x > y) X, S3)が成り立つ。
  5. 以下,{ X1; ...; Xn }とprint xの場合は省略

 1番と2番のルールは,x = iとx = y + zという形の文の意味を定義している。3番のルールは,while (x > y) Xという形の文で,条件x > yが成立しない場合の意味を定義している。文Xは全く実行されないので,状態S1は変わらないわけだ。4番のルールは少し長いが,「while (x > y) Xという形の文で,条件x > yが成立したら,まず文Xを1回だけ実行し,状態S2を経て,再びwhile (x > y) Xを実行する」という意味を定義している。わからなくなったら,先のインタプリタと見比べるとよいかもしれない。

 MyCのような簡単な言語だと,「何を大げさな」と思うかもしれない。しかし,JavaやMLのように大規模な言語になると,数学的定義のありがたみが出てくる。OCamlには残念ながら数学的定義がないが(マニュアルと実装だけ),同じML系言語であるStandard MLには帰納的定義による厳密な言語仕様が存在する。Standard MLのような言語の型安全性を数学的に証明し,さらにその証明を計算機でチェックするという研究もある。定義に用いられている理論は異なるが,Schemeという言語にも数学的仕様が存在する。Javaについても数学的な仕様を定義して,安全性などを厳密に検証しようという研究が数多く進められている(参考リンク)。

著者紹介 住井 英二郎

 東北大学 大学院 情報科学研究科 助教授。今回のような「帰納的定義」は,プログラミング言語の数学的仕様だけでなく,いわゆる「形式的手法」一般の基礎となっています。現状の形式的手法は,研究者でない一般の技術者やプログラマにはまだまだ敷居が高いと思いますが,例えば建築家が力学を利用したり,電気技術者が電磁気学を利用したりしているように,意識しなくても使える「パッケージ化」された理論を目指したいところです。

この先は会員の登録が必要です。今なら有料会員(月額プラン)登録で5月末まで無料!