Camlp4 チュートリアル

Daniel de Rauglaudre 氏による Camlp4 - Tutrial を向井が勝手に訳したものです(9/23 2003版)。
訳の指摘などは mukai@jmuk.org まで。

1. 導入

Camlp4 は OCaml 用のプリプロセッサだ。プリプロセッサとして、 OCaml プログラムの構文拡張ができる。といっても、 Camlp4 は他にもさまざまな特徴を持っている。

文法構造
quotationsと呼ばれるマクロ
OCaml用の改訂版構文
OCamlプログラムの pretty printing システム
さらに: 拡張可能な関数、関数型ストリーム、 etc...

Camlp4 は構文と構文、それに構文だ。構文拡張をするために独自の構文システムを使う。しかも自力でそれをやっている。 Camlp4 は構文レベルでとどまる。意味論とか、型とか、コード生成とかは知ったことではない(このため、型宣言は type から始まる構文的なモノにすぎない)。

Camlp4 における p4 は、 Pre-Processor-Pretty-Printer の4つの p から来ている。

1.1 OCaml の構文を拡張する

初歩から始めるために、 OCaml に単純な構文拡張を加える方法について学ぼう。もし C 言語を知っているなら、 define 宣言を知っていると思う。その利用法は単純で、

#define FOO xyzzy

としておけば、プログラムに出現する FOO はみな、 xyzzy に置き換えられる。

Camlp4 では事はそう単純じゃない。構文拡張は単なるテキスト置換じゃないからだ。むしろ言語の文法におけるエントリに対する追加であり、構文木を作る必要がある。

そこで必要となるのが、(1) Camlp4 で提供される文法システムが何か知ること、(2) 構文木を作る方法を知ることの2つだ。このチュートリアルで我々がやろうとしているのはこの2つだ。この2点を説明すれば、言語の構文拡張をやってくれるツールを手に入れられる。

もしあなたがせっかちだとか、15分後には構文拡張を自分で作れるようにしたいとか、一切合切を勉強したいわけじゃないとかいうのであれば、すでにある構文拡張の説明を持ってきて、必要に応じて変更を加えればいいと考えるかもしれない。構文拡張は長いプログラムでは必要なものではないし(たとえばパスカル式の repeat..until を加えるのは6行で済む)、例を見れば「どう動くか」は推測がつくし、偉い人に聞いてもいいし……。

例なら7章に載っている。

しかし、あなたはこのマニュアルを読むときに、 Camlp4 が提供する文法のシステムそのものの勉強に興味があるかもしれない。それは OCaml 言語の拡張とは違った目的になる。このシステムは yacc の代替である。異なるアプローチだが、同じように自分の言語を記述できる。

1.2 Camlp4 をコマンドとして、もしくはトップレベルで使う

最初に知らなければならないのは、 Camlp4 はコマンドだということだ。この章では、コマンドの詳細とかオプションについては説明しない。もっとあとで説明しよう(8章参照のこと、もしくは "man camlp4" で man ページを参照)。

さしあたって、 foo.ml というファイルをコンパイルするための呪文は次のような感じになる。

ocamlc -pp "camlp4o pa_extent.cmo" -I +camlp4 -c foo.ml

このコマンドでは単に foo.ml という普通の OCaml ファイルをコンパイルするが、 Camlp4 によるパーシングがなされる。このチュートリアルの例(Camlp4 の文法) は基本的にはこのコマンドでコンパイルできる。さもなくば、コンパイルするためのコマンドが説明されている。

もうひとつ、 OCaml トップレベルを使う方法もある(こっちを推奨)。トップレベルで、

#load "camlp4o.cma";;
#load "pa_extend.cmo";;

とタイプするのだ。トップレベルで、このチュートリアルの例が使えるようになる。ファイルに保存して、 #use ディレクティブを使うという方法もある。

このチュートリアルの例はみな、 OCaml の通常の構文で書かれている。しかし、 Camlp4 の改訂版構文を知っていてそちらを使いたければ、 ocamlc の camlp4o の部分を camlp4r にするか、トップレベルなら "camlp4o.cma" ではなくて "camlp4r.cma" をロードすればいい。

1.3 Camlp4 ライブラリを使ってアプリケーションをリンクする

このチュートリアルの例の多くは、特定の Camlp4 ライブラリを使っている。トップレベルなら、全部が camlp4o.cma に入っているのでロードする必要はない。

スタンドアロンのアプリケーションをリンクするときは、 Camlp4 のライブラリが入ったディレクトリにある、 gramlib.cma というライブラリを加える必要がある。コマンドは次のようになる。

ocamlc -I +camlp4 gramlib.cma <リンクしたいファイル群>

1.4 パーシングの違い

もしあなたが通常の構文を知っていても、通常の ocamlc のパーサ(ボトムアップで LALR パーシング)と Camlp4 のパーサ(トップダウンで再帰降下パーシング)ではパーシングのふるまいが微妙に違う。この違いは、エラーのある入力が与えられたときに顕著になる。簡単な例として、次のような入力があったとしよう。

(* correct intended input *)
type t = Buf of Buffer.t
       | Str of string

この例のかわりに、二番目のofキーワードを忘れたとしよう。

(* file wrongsyntax.ml : wrong input - missing keyword *)
type t = Buf of Buffer.t
       | Str (*missing "of"*) string

ocamlc コンパイラ(ocamlc -c wrongsyntax.ml で呼ばれる)は string という単語で構文エラーを発見する。 ocamlc はファイル全体をある単一の型宣言にパースして、その中に構文エラーを発見する。

Camlp4 パーサは(通常の構文では) は構文エラーを発見しないが、入力を次の2つの要素にパースする。

type t = Buf of Buffer.t
       | Str

これは正しい型宣言(プログラマの意図とは違うが)である。このあとに

string

という式があると解釈する。これは let _ = string のように理解され、 Unbound value string というメッセージを生成する。

2. ストリームとパーサ

Camlp4 による最初の拡張はストリームとパーサである。ストリームは抽象型Stream.t の型を持つ値だ。リストに似ているが、最初の要素しか参照できない。2つめの要素を見るためには、1つめの要素を削除しなければならない。パーサは 'a Stream.t -> 'b の型を持つ関数で、ストリーム内部のパターンマッチを生成する。

2.1 ストリーム

2.1.1 ストリームコンストラクタ

ストリームを作る第一の方法は、カッコ [< >] を使うことだ。要素は2種類ある。' から始まる単純な要素と、そうでないストリーム要素だ。ストリームは、それらの書いた順序で構成される。

例を示す。

[< '3; '1; '4; '1; '5 >]

これは整数のストリームになる。

# let s = [< '"hello"; '"world" >];;
# let t = [< '"I"; '"say"; s; '"as"; '"an"; '"example" >];;

この例だと、 t は文字列からなるストリームで、順に "I", "say", "hello", "world", "as", "an", "example" となる。

ストリームの内部を(破壊的に)見るには、 Stream.next 関数を使う。この関数はストリームの最初の要素を削除し、自身を返す。

ストリームは遅延した値を持つ。無限ストリームを作ることもできる。次の例は全ての整数を意味するストリームである。

# let rec f n = [< 'n; f (n + 1) >];;
# let s = f 0;;

2.1.2 ストリームビルダ

ストリームを作る第二の方法はストリームビルダだ。次のものがある。

Stream.of_string: 引数として与えられた文字列から、文字型のストリームを返す
Stream.of_channel: 入力チャネルから文字型のストリームを返す
Stream.of_list: リスト要素からなるストリームを返す
Stream.from: 関数を引数として取り、その関数の返り値で構成されるストリームを返す。詳しくは Stream モジュールを参照。

警告: これらのストリームビルダで作られたストリームはストリームコンストラクタで作られたものより遥かに効率的だが、これらのストリームビルダはストリームビルダに挿入できない。

2.2 パーサ

パーサはストリーム内部を見るための関数である。

パーサはキーワード parser で導入される。これは function 文と似ているが、パターンのかわりにストリームパターンを使う。たとえば、 Stream.next 関数は次のように定義できる。

parser [< 'x >] -> x

パーサはの値の返しかたは3つある。

ストリームの最初がストリームパターンにマッチする場合、通常の値が返される。
最初の要素がマッチするパターンがない場合、例外 Stream.Failure が発生する。この場合、ストリームは変化しない。
パターンの最初の要素が入力ストリームにマッチするが、残りがそうでない場合、例外 Stream.Error が発生する。

例:

# let p = parser [< '3; '1; '4 >] -> "hey";;
# p [< '3; '1; '4 >];;
string : "hey"
# p [< '3; '1; '4; '1; '5; '9 >];;
string : "hey"
# p [< '1; '1; '4 >];;
Exception: Stream.Failure
# p [< '3; '2; '4 >];;
Exception: Stream.Error ""

例外 Stream.Error は引数として文字列をひとつ取る。この文字列は、パーサ中でストリームパターン要素やトークン??の後に指定することができる。例:

# let p = 
    parser [< '3; '1; ?? "1 expected"; '4 ?? "4 expected" >] -> "hey"
  ;;

最初のストリームパターン要素にミスすると Stream.Failure を発生するから、この例外を持たないことに注意しよう。

パーサは他のパーサを呼ぶこともできる。ストリームパターン要素を構文として指定できる。

pattern = expression

例えば再帰呼出しで、

# type tok = If | Then | Else | Let | In | Equal | Ident of int;;
# let rec expr =
    parser
      [< 'If; x = expr; 'Then; y = expr; 'Else; z = expr >] -> "if"
    | [< 'Let; 'Ident x; 'Equal; x = expr; 'In; y = expr >] -> "let"

パーサは構文システムではないことに注意すること。左のような再帰はできない。

(* 悪い例 *)
# let rec expr = parser [< x = expr; 'Equal; y = expr >] -> x;;

また、2つのパターンを同じ要素で始めてはいけない。最初の要素だけが適用される。

(* 悪い例 *)
# let rec expr =
    parser
      [< 'If; x = expr; 'Then; y = expr; 'Else; z = expr >] -> "if"
      [< 'If; x = expr; 'Then; y = expr >] -> "ifnoelse"
  ;;

もしこれをやりたければ、ルールを分解する必要がある。

# let rec expr =
    parser
      [< 'If; x = expr; 'Then; y = expr; v = expr_kont >] ->
  and expr_kont =
    parser
      [< 'Else; z = expr >] -> "if"
    | [< >] -> "ifnoelse"
  ;;

もしくは、無名パーサを使う。

# let rec expr = 
    parser
      [< 'If; x = expr; 'Then; y = expr;
         v =
           parser
             [< 'Else; z = expr >] -> "if"
           | [< >] -> "ifnoelse" >] -> v
  ;;

3. Camlp4 の文法

Camlp4 の文法は Grammar.g 型の値である。この値は関数 Grammer.make でつくる。この関数は字句解析器を引数として取る(他のつくり方としてはファンクタのようなインタフェースを見よ)。字句解析器のつくり方についてはちょっとの間は無視して、 Camlp4 で提供されているデフォルトの OCaml の字句解析器を使うことにしよう。これは Plexer モジュールにあって、 Plexer.gmake () でそのインスタンスをつくることができる。

3.1 文法、エントリー: 例

次のようにして自分の文法をつくることができる。

# let gram = Grammar.gcreate (Plexer.gmake ());;

ある文法はエントリーで構成される。エントリーは 'a Grammer.Entry.e 型の値だ。 'a 型パラメータは、そのエントリーが返す値の型になる。エントリーをつくるには Grammer.Entry.create を使う。この関数は2つの引数を取る。(1) 関連する文法と、 (2) エントリー名を意味する文字列で、後者はエラーメッセージにも使われる。

あるエントリーは変更可能な値である。つくったときは空で、その型は '_a Grammer.Entry.e で(一般化されてはいない。多相型のエントリーをつくることはできない)、その型パラメータはエントリーが拡張されたときに設定され、その型の値を返す意味になる。あるエントリー expr を作ってみよう。

# let expr = Grammar.Entry.create gram "expr";;

エントリーは、 Grammar.Entry.parse 関数で文字型のストリームに適用される。空のエントリー(たとえば作ったばかりのエントリーとか)を適用すると、例外 Stream.Failure が発生する。

エントリーにルールを定義するには、 EXTEND 文を使わなければならない。 EXTEND は OCaml の構文的なコンストラクタじゃないということに注意してほしい。これは Camlp4 で提供される構文拡張だ。 EXTEND の構文は次の通り。

extend-statement :: =
  EXTEND
    list-of-entries-extensions
  END

EXTEND は式である(つまり宣言ではない)ことに注目してほしい。トップレベルでも、関数の中でも評価できる。後者の場合、関数が呼ばれたときに構文の拡張が行われる。

あるエントリーの拡張は次の構文となる。

entry-extension ::=
   identifier : [ list-of-levels-separated-by-bars ] ;

識別子(identifier)はエントリーの名前だ。あるエントリーは1つ以上のレベルを持つが、これは優先順位と結合性を示している。

あるレベルは次の構文である。

level ::=
   [ list-of-rules-separated-by-bars ]

rule ::=
   list-of-symbols-separated-by-semicolons -> action

あるルール(rule)はパターンマッチングに似ている。パターン変数を導入し、 action パートで使うことができる。あるルールが受理されると、そのアクションが実行される。アクションの型は、 'a entry (より正確に言えば 'a Grammar.Entry.e) に対して 'a だ。

それでは、整数定数とカッコがある四則演算の代数式の計算をパースするエントリーを定義してみよう。次のように書く。

EXTEND
 expr:
   [ [ x = expr; "+"; y = expr -> x + y
     | x = expr; "-"; y = expr -> x - y ]
   | [ x = expr; "*"; y = expr -> x * y
     | x = expr; "/"; y = expr -> x / y ]
   | [ x = INT -> int_of_string x
     | "("; e = expr; ")" -> e ] ]
 ;
END;;

expr エントリーは3つのレベルを持つことになった。文法エントリーはいつでも拡張できる。もっと追加することで expr を拡張できる。すでにあるレベルにルールを追加することもできるし、新しいレベルを追加することもできる。これについては後で説明する。

個々のレベルはそれぞれ結合性を持つ。結合性は左、右、なしが指定できる。デフォルトでは左結合性だ。詳しくはまた後で見よう。

OCaml トップレベルでこの例を実験してみたければ、 expr が int entry の型であり、 int 型を返すことを確かめることができる。

試してみよう。

# Grammar.Entry.parse expr (Stream.of_string "2 + 3");;
- : int = 5

# Grammar.Entry.parse expr (Stream.of_string "8 * (5 - 2)");;
- : int = 24

こんな感じだ。

構文エラーがあるときはどうなる？　一般的には、例外 Stream.Error が発生し、ストリームでエラーが発生した場所を示す Exc_located という別の例外で包まれる。右カッコがない例で試してみよう。

# Grammar.Entry.parse expr (Stream.of_string "9 / (7 + 1");;
Uncaught exception:
Stdpp.Exc_located
 ((11, 12), Stream.Error "')' expected after [expr] (in [expr])").

正しい式のあとに予期しないシンボルが現れた場合には、パースエラーは発生せず、ストリームのパーシングが停止して、残りのシンボルは無視される。

# Grammar.Entry.parse expr (Stream.of_string "8 * (5 - 2) 7 foo");;
- : int = 24

入力ストリームにトークンが残ってないことを保証するには、他のエントリー expr_eoi を使って、 expr のあとには入力の末尾(end of the input) EOI だけがあるようなルールをつくることができる。

# let expr_eoi = Grammar.Entry.create gram "expr_eoi";;
# EXTEND expr_eoi: [ [ e = expr; EOI -> e ] ]; END;;

この時、

# Grammar.Entry.parse expr_eoi (Stream.of_string "8 * (5 - 2) 7 foo");;
Uncaught exception:
Stdpp.Exc_located
 ((12, 13),
  Stream.Error "end of input expected after [expr] (in [expr_eoi])").

3.2 字句解析器の注意点

"+"、"-"、"*"、"/"、EOIなどはこの文法の終端記号ではあるけど、 Camlp4 の文法システムで特別にあらかじめ定義されているものではないことに注意してほしい。こういったものは、関連する字句解析器の動き方によるのだ。思い出してほしい。現在の文法に関係する字句解析器として Plexer.gmake() を使ったのだった。他の文法、他の字句解析器では、これらの終端記号は何の意味もないこともある。

拡張をやる前に、 EXTEND 文はまずルールを全部スキャンして、出てくる終端記号について字句解析器に、それぞれの終端記号が正しいのかどうか尋ねる。これをやるには、字句解析器で定義されているレコード型にある関数が使われる(Tokenモジュールのインタフェースを参照のこと)。この関数はキーワードのリスト(というかハッシュテーブル)を更新するためにも使うことができる。

よし。でもこれは字句解析器の仕事だ……。このことについては、今は知る必要はない。ただ、 Plexer.gmake() の字句解析器では、認識できない終端記号が EXTEND 文で使われたときにはエラーメッセージを出力して例外を発生させるということは知っておいた方がいい。

# EXTEND expr_eoi: [ [ AAA -> 3 ] ]; END;;
Lexer initialization error.
The constructor "AAA" is not recognized by Plexer
Uncaught exception: Failure "Grammar.extend".

# EXTEND expr: [ [ x = expr; "a+b" -> x + 1 ] ]; END;;
Lexer initialization error.
The token "a+b" does not respect Plexer rules
Uncaught exception: Failure "Grammar.extend".

これに関する細かい内容は、リファレンスマニュアルの字句解析器のところに書いてある。 Token モジュールと Plexer モジュールも参照してほしい。

3.3 ラベルつきレベルと結合性

さて、 expr を拡張するとしよう。ところが、これまでの定義では、エントリーを指定することができない。指定するにはラベルが必要だ。

レベルの構文は、実はこうなっている。

level ::=
   optional-label optional-associativity
   [ list-of-rules-separated-by-bars ]

ラベルは文字列である。どんな文字列でもいい。結合性はLEFTA(左)、RIGHTA(右)、NONA(なし)のどれかになる。

さて、それでは expr をもう一度、ラベルと結合性つきで書いてみよう(空エントリーで開始するため、エントリーを再定義している)。

# let expr = Grammar.Entry.create gram "expr";;
# EXTEND
    expr:
      [ "add" LEFTA
        [ x = expr; "+"; y = expr -> x + y
        | x = expr; "-"; y = expr -> x - y ]
      | "mult" RIGHTA
        [ x = expr; "*"; y = expr -> x * y
        | x = expr; "/"; y = expr -> x / y ]
      | "simple" NONA
        [ x = INT -> int_of_string x
        | "("; e = expr; ")" -> e ] ]
    ;
  END;;

ところで、トップレベルで特に便利な関数として Grammar.Entry.print というのがある。これは、あるエントリーの中身(つまりルールだ)を表示してくれる。

# Grammar.Entry.print expr;;
[ "add" LEFTA
  [ SELF; "+"; SELF
  | SELF; "-"; SELF ]
| "mult" RIGHTA
  [ SELF; "*"; SELF
  | SELF; "/"; SELF ]
| "simple" NONA
  [ "("; SELF; ")"
  | INT ] ]

ここでは expr は全部 SELF に置き換えられている。どちらも同じ意味だ。エントリー自身を呼び出したいとき、その名前をつかってもいいし、 SELF というキーワードでもいい。これは現在のレベルか次のレベルか最初のレベルの意味になる。そのどれになるかは、結合性やルール中の SELF の位置による(ルールの最初なら現在のレベル、最後なら次のレベル、そうでなければ最初のレベルになる)。

あるエントリーを拡張するとき、デフォルトでは最初のレベルを拡張する。

# EXTEND expr: [ [ x = expr; "plus1plus"; y = expr -> x + 1 + y ] ]; END;;

この拡張は最初のレベル、つまり "add" のレベルに追加される。 Grammar.Entry.print で確認してみよう。

存在するどんなレベルにも追加できるし、新しいレベルを追加できる。エントリー拡張に関する本当の構文は次のようになっている。

entry-extension ::=
   optional-position
   identifier : [ list-of-levels-separated-by-bars ] ;

position ::=
   FIRST | LAST | BEFORE label | AFTER label | LEVEL label

3.4 あるレベルの拡張

特定のレベルの拡張なら、 LEVEL のあとに拡張したいレベルのラベルを書けばいい。

# let env = ref [];;
# EXTEND
    expr: LEVEL "simple" [ [ x = LIDENT -> List.assoc x !env ] ];
  END;;

Grammar.Entry.print expr をやってまた確認してみよう。

LIDENT というシンボルも、 Plexer で定義されているコンストラクタだ。小文字で始まる識別子の意味である。詳しくは Plexer モジュールのインタフェースを確認してほしい(plexer.mli やリファレンスマニュアル、ライブラリの章など)。

簡単なテストをしてみよう。

# Grammar.Entry.parse expr (Stream.of_string "foo + 1");;
Uncaught exception: Stdpp.Exc_located ((3, 4), Nof_found)

# env := ("foo", 27) :: !env;;
# Grammar.Entry.parse expr (Stream.of_string "foo + 1");;
- : int = 28

3.5 レベルの挿入

レベルの挿入なら BEFORE か AFTER で、存在するレベルから相対的に指定する。

# EXTEND
    expr: AFTER "mult"
      [ "power" RIGHTA
        [ x = expr; "**"; y = expr -> int_of_float (float x ** float y) ] ]
    ;
  END;;

レベルの数に制限はない。リストだからだ。 FIRST と LAST を使うこともできて、先頭または末尾のレベルに作成することができる。

3.6 中置演算子

EXTEND 文の中で、文字列があるべき場所には antiquotation を使うことができる。 antiquotation は2つのドル記号の間に入れることのできる式だ。典型的な例は、中置演算子 op をあるレベル lev に追加する関数である。

# let add_infix lev op =
    EXTEND
      expr: LEVEL $lev$
        [ [ x = expr; $op$; y = expr -> <:expr< $lid:op$ $x$ $y$ >> ] ]
      ;
    END;;

この関数は、自分で中置演算子を定義したいときに呼ばれる。中置演算子は自動的にキーワードになる(実際には、それは字句解析器の仕事)。 OCaml 文法における中置マクロを定義するために使うこともできる(7章参照)。

3.7 属性つき文法

属性つき文法、つまり引数つきの文法(我々の用語で言えば引数つきのエントリー)をつくるのは可能ではない。ただ、エントリーは関数を返すことができる。そこで、ある環境 env を取る関数を返すようなエントリー expr を書いてみよう。

# let expr = Grammar.Entry.create gram "expr";;
# EXTEND
    expr:
      [ "add" LEFTA
        [ x = expr; "+"; y = expr -> fun env -> x env + y env
        | x = expr; "-"; y = expr -> fun env -> x env - y env ]
      | "mult" RIGHTA
        [ x = expr; "*"; y = expr -> fun env -> x env * y env
        | x = expr; "/"; y = expr -> fun env -> x env / y env ]
      | "simple" NONA
        [ x = INT -> fun env -> int_of_string x
        | x = LIDENT -> fun env -> List.assoc x env
        | "("; e = expr; ")" -> e ] ]
    ;
  END;;

エントリーを呼ぶには、ある環境を引数として与えないといけない。

# Grammar.Entry.parse expr (Stream.of_string "foo + 1") [];;
Uncaught exception: Not_found.

これは foo が環境にないから。

# Grammar.Entry.parse expr (Stream.of_string "foo + 1") [("foo", 48)];;
- : int = 49

値に束縛されていない変数名を表示できるようエラーメッセージを工夫することもできる。

# EXTEND
    expr: LEVEL "simple"
      [ [ x = LIDENT ->
            fun env ->
              try List.assoc x env with
                Not_found -> failwith ("unbound variable " ^ x) ] ]
    ;
  END;;

このとき、 expr の "simple" レベルでは LIDENT のルールがすでに存在しているはずだ。こういう場合、 EXTEND 文は古いのを新しいものに置き換え、警告を表示する。このメッセージを出さなくするには、 Grammar.warning_verbose の値を false にセットすればいい。

さて、もっと詳しく表示できるようになった。

# Grammar.Entry.parse expr (Stream.of_string "foo + 1") [];;
Uncaught exception: Failure "unbound variable foo".

3.8 ソースの場所

上のエラーシステムをさらに改善して、エラーの場所を教えてくれるようにもできる。この例では短いテキストでしかテストしていないのでエラーをみつけるのも簡単だが、文法がもっと巨大になってもっと大きな入力ファイルを扱うとなると、ソース中のエラー箇所を正確に知るのがとても重要になる。

このために便利な関数が Stdpp.raise_with_loc で、入力場所と例外を引数として取る。この関数は、これまで見てきた例外 Stdpp.Exc_located を発生させる。

この例外 Exc_located を直接に発生させることもできるのだが、 raise_with_loc には Exc_located に引数として与えられた例外を再発生させてくれるという利点があり、しかも Exc_located をスタックに積まずに例外を伝播させることができる。

入力位置は、アクションパートで loc という変数を使うことができる。

# EXTEND
    expr: LEVEL "simple"
      [ [ x = LIDENT ->
            fun env ->
              try List.assoc x env with
                Not_found ->
                  Stdpp.raise_with_loc loc
                    (Failure ("unbound variable " ^ x)) ] ]
    ;
  END;;

# Grammar.Entry.parse expr (Stream.of_string "3 + foo + 1") [];;
Uncaught exception:
Stdpp.Exc_located ((4, 7), Failure "unbound variable foo").

次は、 "let" 構造で環境を拡張できるように拡張しよう。

このとき、エントリーのルールにおけるメタシンボルの概念を導入する必要がある。

3.9 メタシンボル: リスト、オプション、レベル

メタシンボルをルールで使うことができる。

シンボルのリスト、空でもよい:: LIST0 <symbol>
セパレータつきシンボルのリスト、空でもよい:: LIST0 <symbol> SEP <symbol>
1つ以上の要素からなるシンボルのリスト:: LIST1 <symbol>
1つ以上の要素からなるシンボルのリスト、セパレータつき:: LIST1 <symbol> SEP <symbol>
オプションシンボル:: OPT <symbol>
レベル:: [ <rule-list> ]

これで let 文を書くことができる。これには、 "and" というキーワードで分割される空でない束縛のリストが必要になる。

# let binding = Grammar.Entry.create gram "let_binding";;
# EXTEND
    expr: FIRST
      [ [ "let"; r = LIST1 binding SEP "and"; "in"; e = expr ->
            fun env ->
              let new_env =
                List.fold_right (fun b new_env -> b env :: new_env)
                  r env
              in
              e new_env ] ]
    ;
    binding:
      [ [ p = LIDENT; "="; e = expr -> fun env -> (p, e env) ] ]
    ;
  END;;

エントリーをテストするのに便利な関数を定義しておこう。

# let apply e s = Grammar.Entry.parse e (Stream.of_string s) [];;

というわけで例だ。

# apply expr "let a = 25 and b = 12 in a + b";;
- : int = 37

# apply expr "let a = 25 and b = a + 5 in a + b";;
Uncaught exception:
Stdpp.Exc_located ((19, 20), Failure "unbound variable a").

# apply expr "let a = 25 in let b = a + 5 in a + b";;
- : int = 55

3.10 局所エントリーと大域エントリー

今、エントリーは3つある。 expr_eoi、 expr、 binding だ。

大きな文法では細かなエントリーをたくさん作ることがよくあり、そのたびに Grammar.Entry.create で定義しないといけない。これはいくつかの理由によって実際的じゃない。 (1) 退屈だ (2) 一般にそれに直接アクセスする必要はない (3) 拡張されることがないエントリー(文法を完成させるときに出てくることがある)なので '_a entry 型になるが、モジュールの最後で ocamlc が失敗する。

こういったことを回避するために、そういう小さなエントリーを自動的に定義してくれるよう EXTEND に指定することができる。これは実際には間違った方法で、大域的に定義されたエントリーのリストを定義しなくてはいけない。他の方法は局所的な定義だ。実際、 EXTEND の定義は次のようになっている。

extend-statement ::=
   EXTEND
      optional-global
      list-of-entries-extensions
   END

global ::=
   GLOBAL : list-of-entries ;

警告: この文はちょっと読みづらい。 GLOBAL は、すでに定義されているエントリーのリストを導入する。つまり、他のエントリーは自動的に局所的な定義になる。デフォルトでは、 GLOBAL が存在しなければ次のように読まなければならない「すべてのエントリーは大域的だ」。

我々の例では、 expr_eoi だけが定義されていて見えるようにしたいなら、 GLOBAL エントリーに expr_eoi だけを追加すればよい。この場合、 expr と binding は局所定義になって拡張できなくなる。

あらかじめ定義されている expr や binding を間違っても使わないように、いったんトップレベルを終了して入力しなおそう。次の二行を忘れないように。

#load "camlp4o.cma";;
#load "pa_extend.cmo";;

さて、こうなる。

# let gram = Grammar.gcreate (Plexer.gmake ());;
# let expr_eoi = Grammar.Entry.create gram "expr_eoi";;
# EXTEND
    GLOBAL: expr_eoi;
    expr_eoi:
      [ [ e = expr; EOI -> e ] ]
    ;
    expr:
      [ [ "let"; r = LIST1 binding SEP "and"; "in"; e = expr ->
            fun env ->
              let new_env =
                List.fold_right (fun b new_env -> b env :: new_env)
                  r env
                in
                e new_env ]
      | "add" LEFTA
        [ x = expr; "+"; y = expr -> fun env -> x env + y env
        | x = expr; "-"; y = expr -> fun env -> x env + y env ]
      | "mult" RIGHTA
        [ x = expr; "*"; y = expr -> fun env -> x env * y env
        | x = expr: "/"; y = expr -> fun env -> x env / y env ]
      | "simple" NONA
        [ x = INT -> fun env -> int_of_string x
        | x = LIDENT ->
            (fun env -> try List.assoc x env with
               Not_found ->
                 Stdpp.raise_with_loc loc
                   (Failur ("unbound variable " ^ x)))
        | "("; e = expr; ")" -> e ] ]
    ;
    binding:
      [ [ p = LIDENT; "="; e = expr -> fun env -> (p, e env) ] ]
    ;
  END;;

# let apply e s = Grammar.Entry.parse e (Stream.of_string s) [];;

# apply expr_eoi "let a = 25 and b = 12 in a + b";;
- : int = 37

# apply expr_eoi "let a = 25 and b = 12 in a + b foo bar";;
Uncaught exception:
Stdpp.Exc_located
  ((31, 34),
     Stream.Error "end of input expected after [expr] (in [expr_eoi])")

3.11 ルールの削除

ルールの削除には DELETE_RULE 文を使う。構文はこうだ。

delete-rule ::=
   DELETE_RULE entry : list-of-symbols-separated-by-semicolons END

そのエントリーにあるルールの中で、シンボルの並びにマッチする最初のルールが削除される。

たとえば、上の例で「可算」ルールを削除したいとすれば、次のように入力すればいい。

# DELETE_RULE expr: SELF; "+"; SELF END;;

3.12 パースされた言語

文法のエントリーやレベルは、ストリームパーサを改善する。ストリームパーサは再帰派生パースを使っている(LL(1) に近いが実際にはちょっと強力さに欠ける)。改善点は2つある。

最左分解: つまり、 if..then と if..then..else ルールが同じシンボルで始まるように書くことができて、ちゃんと動作する。
結合性や優先順位の自動的な扱い、これについてはさんざん見てきた。

違うエントリーの間の最左分解はない。同じエントリーの違うレベルの間にある。

このことは問題にもなりうる。次の例は動かない。

x ::= y | z y ::= A B | ... z ::= A C | ...

入力 "A C" に対して Stream.Error が発生する。この問題について簡単な解決策はないが、(綺麗ではないが実際的な)解決策はある。あるパーサからエントリーをつくるのだ(関数 Grammar.Entry.of_parser 関数を使えばいい)。このパーサは、違いがわかるまで必要な数のトークンを、 Stream.npeek を使ってスキャンしなければならない。 unit が返されるか、場合によってはStream.Failure が発生する。

3.13 ファンクターのインタフェース

文法をつくるには別な方法もある。ファンクターのインタフェースを使うのだ。 Grammar モジュールを見てほしい。この場合、文法は値ではなくモジュールになる。 EXTEND キーワードに続けて文法モジュール名を置くことで文法の拡張もできる。

違いは次のとおりだ。

OCaml の通常の型付けでは、エントリーは同じ文法のエントリーのみを呼ぶことが保証される。なぜなら、個々の文法モジュールは自分のエントリー型を定義するからだ。ファンクターでないインタフェースでは、このチェックは実行時に行われる。
Entry.parse 関数への入力は文字型ストリーム直接ではなく、 parsable 型の値となる。 parsable 関数によって文字型ストリームから parsable の値をつくらなければならない。このことは、 Entry.parse を何度も呼ぶときにトークンの欠如がないことを保証する。通常のインタフェースでは、文字ストリームに対して Grammar.Entry.parse を呼ぶときに、文法システムは、使われない(エントリーによる)のではなくて文字ストリームから再開するときに失われたトークンを要求するかもしれない。

通常のインタフェースを使うか、ファンクターのインタフェースを使うかは個人の趣味による。

3.14 字句解析器を書く

自分で字句解析器を書きたいならば、すでに提供されている字句解析器のソース(plexer.ml)を取ってきて変更を加えるのがいい。

さもなくば、リファレンスマニュアルの「字句解析器を書く」の章を読むこと。

3.15 OCaml構文の文法

camlp4 コマンドは OCaml のファイルをパースするのにも使うことができる。この目的のため、現在記述されている文法を使うことができる(拡張可能なエントリーつきの文法として)。 OCaml の文法のメインのエントリーはアクセスでき、すなわち拡張できる。式も、パターンも、ストラクチャも、シグネチャも、その他諸々もだ。これは Pcaml モジュールで定義されている。7章、リファレンスマニュアル、ライブラリの章、もしくは pcaml.mli インタフェースを読んでほしい。

しかし、我々はまだ OCaml の構文拡張をする準備が整ってない。まずこれらのエントリーが返す構文木を作る必要があるからだ。

OCaml の構文木の作り方はあとの章で説明されている。まずは Camlp4 の quotation から説明しよう。

4. Quotation

Quotation というのは、特殊なカッコで囲まれた式またはパターンだ。特殊なカッコというのは <:id< と >> である(idは quotation 用の識別子)。 << >> で囲まれるものもある。

例としてはこんなかんじだ。

<:expr< let a = b in c >>
<< [x](x y) >>
<:myquot< quotations can be any text >>

quotation の中身は字句解析されない。 quotation は文字列みたいに、それ自体でトークンなのだ。したがって文字列の中身と同様に、その中身はいかなる構文ルールも反映する必要性はない。

4.1 OCaml の構文拡張

前の章で Camlp4 の文法システムについて見た。これは OCaml の構文拡張を書く方法としては最初の一歩にあたる。

次の一歩は、「OCaml の構文木のノードをどうやって作るか？」ということだ。その直接の答えが、「それを定義するモジュールを使え」ということだ。実際、そういうモジュールがある。 MLast モジュールだ。それを理解して使うこともできるが…… quotation を使うこともできる。

"let a = b in c" という OCaml 式の構文木を生成したいとしよう。 MLast を直接に使いたいとすればこうなる。

MLast.ExLet
  (loc, false, [MLast.PaLid (loc, "a"), MLast.ExLid (loc, "b")],
   MLast.ExLid (loc, "c"))

そんなにややこしくないと思うかもしれない。だが、構文木のノードすべてについて、パラメタや使い方の詳細が必要になる。勇気があれば、それがどう使われているか知るために Camlp4 のコードの内部を見てみるのもいいだろう。

けれども、 Camlp4 の quotation システムはこうした構文木を表現する簡単な方法を提供している。このシステムでは、正しいファイルがロードされていれば、上の例は次のように書くことができる。

<:expr< let a = b in c >>

簡単じゃないか？　内部にあるものは Camlp4 によるコンパイル時に扱われ、上にある「長い」バージョンと同じコードが生成される。

それでは、 Camlp4 の quotation システムの詳細を見ていこう。これは OCaml の構文の構文木のノードとしても使えるし、他の型としても使える。自分で quotation を定義して、自分の好きなどんな構文にも使うことができるのだ。

4.2 Camlp4 の quotation システム

quotation の中身は字句解析されないことは上にも書いたが、中身はパース時にもそのように扱われる。実際には、中身は(Camlp4 の) OCaml の字句解析器では解析されず、他の関数、 quotation expander というものによって解析される。この expander は文字列(quotation の中身)を引数として取り、OCaml プログラムの断片を返す。

quotation expander には二種類あり、どちらも同じことをやる。ただし、一方は簡単に使えるが一般性がなく、もう一方は一般的だが使うには知識が…… OCaml の構文木の quotation の知識が必要になる。

で、後者は quotation を学ぶのに quotation の知識が必要となるわけで…… OCaml の構文木の quotation については次の章で説明する。

OK。相互再帰な文章はスタックに積んで、「シンプル」で「使いやすい」方から始めよう。これで、 quotation expander の動きを説明する。その次のステップとして、 MLast の quotation を定義する必要のある一般的な quotation について説明しよう。

4.3 例: 定数を定義する

単純バージョンの quotation expander は文字列を返す。返される文字列はコードの断片だ。具体的な構文でソースコードに似ている。というより、 quotation 拡張のあとにパースされる必要があるという意味において実際にソースコードなのだ。

簡単な例を挙げよう。その名前の定数を定義する(この例はほとんど C での #define を単純な定数定義に使うのと同義である)。まずこれを入力する。

#load "camlp4o.cma";;

次に、このように打ち込む。

# let expand _ s =
    match s with
      "PI" -> "3.14159"
    | "goban" -> "19*19"
    | "chess" -> "8*8"
    | "ZERO" -> "0"
    | "ONE" -> "1"
    | _ -> "\"" ^ s ^ "\""
  ;;

つくる quotation を foo とする。ここで、 foo を上で定義した expand に関連づけるには次のように入力する。

# Quotation.add "foo" (Quotation.ExStr expand);;

この新しい quotation を試してみよう。

# <:foo<PI>>;;
- : float = 3.14159
# <:foo< hello, world >>;;
- : string = " hello, world "
# <:foo<ONE>> + <:foo<ONE>>;;
- : int = 2
# let rec fact x =
    if x = <:foo<ZERO>> then <:foo<ONE>> else x * fact (x - 1)
  ;;
val fact : int -> int = <fun>

この調子だ。しかも、 quotation はパターンとしても使える。

# let rec fib =
    function
      <:foo<ZERO>> | <:foo<ONE>> -> 1
    | n -> fib (n - 1) + fib (n - 2)
  ;;
val fib : int -> int = <fun>

ある quotation がある1つの型を持つわけではないことに気づいたかもしれない。その型は quotation が生成するものによる。この場合では、浮動小数点小数、整数、文字列のどれかになる。また、 quotation 内部の文字列は重要だということにも注意したい。 expander はこれを取ってくれない。そこで、

# <:foo< PI >>;;

これは " PI " とホワイトスペースつきで、 "PI" というスペースなしにはマッチしない。したがって PI の値を返すのではなく、

- : string = " PI "

となる。どちらの場合でも PI の値を返すようにしたければ、もっと巧妙な quotation expander を書かないといけない。 quotation expander は、他のどんなパース技術も使うことができる。文字列のパターンマッチング(今回の例)、ストリームパーサ、 ocamllex 、 ocamlyacc 、 Camlp4 文法などなど。重要なのは、引数として文字列を1つとり、プログラムの断片を返すということだけだ。

4.4 quotation とコンパイラ

これまでは quatation の例をトップレベルで見てきた。が、ここでの文脈ではコンパイルレベルとプログラムレベルが交ざっている。コンパイラに ocamlc を使うときには、 quoatation システムは2つの段階に分ける必要がある。

quotation expander と Quotation.add 文はコンパイに対するディレクティブ
quotation の使用はユーザプログラム内とする

「コンパイラパート」はあらかじめコンパイルされていなければならない。上の例をテストするには、 expand 関数の部分をコピーして、そのファイル(foo.ml)中で Quotation.add を呼ぶようにしなければならない。コンパイルは次のようになる。

ocamlc -I +camlp4 -c foo.ml

これで foo.cmo がつくられる。 Camlp4 では、すべての構文拡張は OCaml のオブジェクトファイルを通じて行われる。プリプロセッサ camlp4o はオブジェクトファイルのリストをコマンドの引数として取り、それをロードする。次に fib.ml を書く。

(* file fib.ml *)
let rec fib =
  function
    <:foo<ZERO>> | <:foo<ONE>> -> 1
  | n -> fib (n - 1) + fib (n - 2)
;;

最初に注意したように、ふつうの OCaml コンパイラは quotation のことを知らない。

$ ocamlc -c fib.ml
File "fib.ml", line 4, characters 4-6:
Syntax error

が、 Camlp4 は知っている……

$ ocamlc -pp camlp4o -c fib.ml
File "fib.ml", line 4, characters 4-16:
While expanding quotation "foo":
Uncaught exception: Not_found
Preprocessing error

……ので、 quotation expander のオブジェクトファイルをパラメタとして与える( ./foo.cmo と書かないといけない。というのも、 camlp4 はカレントディレクトリをデフォルトのサーチパスに持っていないからだ)。

$ ocamlc -pp "camlp4o ./foo.cmo" -c fib.ml

4.5 結果をpretty printing

quotation が正しく拡張されていることを確認するにはどうしたらいいだろう？　quotation expander を完成させたり、すでに手元に quotation expander があり、結果を見たければ、 camlp4 を使って結果を見ることができる。

このためには、 "pr_o.cmo" というあらかじめ設定されているプリントキットと一緒に camlp4o をコマンドとして使う。

$ camlp4o ./foo.cmo pr_o.cmo fib.ml
(* file fib.ml *)
let rec fib =
  function
    0 | 1 -> 1
  | n -> fib (n - 1) + fib (n - 2)
;;

quotation はその値で置き換えられている。

4.6 構文木を返す quotation

これまでの quotation expander の ``expand'' 関数は文字列を返した。内部的には、 camlp4 は ``foo' という quotation に遭遇すると、この関数を読んでその結果の文字列を得ていた。この文字列は文法エントリ ``expr''(式)かまたは ``patt''(パターン)でパースされていた。

しかし、この方法は次の欠点がある。

新しいパースフレーズが必要になる(それには時間がかかり、よろしくない)
expander の書き方がまずくて結果の文字列は構文的に不正確な場合、デバグは非常に難しい(が、 camlp4 の -QD オプション参照)。
囲まれる構文に依存する。同じ expander は改訂した構文ではうまく動くかもしれないが、通常の構文では動かないかもしれない。

2番目については、次の例を打ち込んでみよう。

# <:foo< to"to >>;;

結果は次の妙なメッセージになる。

# <:foo< to:to >>;;
  ^^^^^^^^^^^^^^^
While parsing result of quotation "foo":
(consider setting variable Pcaml.quotation_dump_file)
Parser error: end of input expected after [expr] (in [expression])

この理由は、我々の quotation expander がシンプルすぎたことにある。ダブルクォートを含む文字列を生成できてしまう。このとき、 quotation の中身は、

" to"to "

である。パーサはこの入力に対して失敗するのだが、このデバッグは非常にややこしい場合がある。特に、 expander がその結果を pretty print しない時や、冗長なカッコをたくさん加えたときなんかは悲惨だ。というわけで、解決法は "s" そのものではなく "String.escaped s" を使うことになる。

こういうことを避けたり他のややこしいことを回避するために、他の quotation システムがある。こちらでは、 expander は抽象的な構文木を返す。この場合には expand 関数は、文字列 "3.14159" を返すのではなくて「浮動小数点数 3.14159 を意味する構文木上の表現」とでも言うべきものを返す。この場合、ほかのパースフレーズは必要ないし、パースエラーの危険を冒すことなく、とりまく構文から独立にできる。

OCaml の構文木を作る方法については6章で扱う。構文木も quotation で書くことができて、 q_MLast.cmo という構文拡張キットを使う。

これまでと同じ quotation expander は次のように書くことになる。

(* file foo.ml *)
let loc = (0, 0);;
let expand_expr = function
  | "PI" -> <:expr< 3.14159 >>
  | "goban" -> <:expr< 19 * 19 >>
  | "chess" -> <:expr< 8 * 8 >>
  | "ZERO" -> <:expr< 0 >>
  | "ONE" -> <:expr< 1 >>
  | _ -> <:expr< $str:s$ >>
;;
let expnad_patt = function
  | "PI" -> <:patt< 3.14159 >>
  | "ZERO" -> <:patt< 0 >>
  | "ONE" -> <:patt< 1 >>
  | _ -> <:patt< $str:s$ >>
;;
Quotation.add "foo" (Quotation.ExAst (expand_expr, expand_patt))

この場合には ExStr のかわりに ExAst を使う。このコンストラクタは2つの expander を必要としている。一方は式の位置のための quotation で、もう一方がパターンの位置の quotation だ。 "goban" や "chess" がパターン版にないのは、 19*19 や 8*8 がパターンとして正しくないからである。

foo.ml のコンパイルは、 quotation expanderキット q_MLast.cmo が必要になる。

$ ocamlc -pp "camlp4o q_MLast.cmo" -I +camlp4 -c foo.ml

これでオブジェクトファイル "foo.cmo" が生成され、 "fib.ml" に使うことができる。

気になるようなら、この expander も pr_o.cmo で pretty print できる。やってみよう。

$ camlp40 q_MLast.cmo pr_o.cmo foo.ml

4.7 例: ラムダ項

というわけで、もっと大きな例をためすことができるようになったので、ラムダ項を操作してみよう。ラムダ項は次のように定義できる。

type term =
    Var of string
  | Func of string * term
  | Appl of term * term
;;

最初のケースの Var というのは変数を示している。

次の Func というのは関数だ。最初のパラメタは関数の引数で、次が関数本体になる。具体的には [paramter]body の構文で書くことにする。

三番目の Appl は2つのラムダ項の適用を意味している。これは具体的には(term1 term2) で書くことにする。

などと term 型を定義したので、コンストラクタを使ってこれらの項を書こう。次のが例だ。

let id = Func ("x", Var "x")
let k = Func ("x", Func ("y", "Var "x"))
let s =
  Func ("x", Func ("y", Func ("z",
    Appl (Appl (Var "x", Var "y"), Appl (Var "x", Var "z")))))
let delta = Func ("x", Appl (Var "x", "Var "x"))
let omega = Appl (delta, delta)

うまい quotation expander があれば具体的な構文を使うことができる。これと同じプログラム断片がずっと読みやすくなる。

let id = << [x]x >>
let k = << [x][y]x >>
let s = << [x][y][z]((x y) (x z)) >>
let delta = << [x](x x) >>
let omega << (^delta ^delta) >>

じゃあ、対応する quotation expander を書くことにしようか。

ここで、 quotation の中身は複雑で、文字列のパターンマッチではパースできない。ストリームパーサを使うこともできるが、簡単なのは文法だ。

字句解析器を書かなくても、デフォルトの Plexer を使うことができる。我々の Camlp4 文法(前章参照)に関する知識を使うと、ラムダ項に関する quotation expander は次のようになる(ファイル名は q_term.ml)。

let gram = Grammar.gcreate (Plexer.gmake ());;
let term_eoi = Grammar.Entry.create gram "term";;
let term = Grammar.Entry.create gram "term";;
EXTEND
  term_eoi: [ [ x = term; EOI -> x ] ];
  term:
    [ [ "["; x = LIDENT; "]"; t = term -> <:expr< Func $str:x$ $t$ >>
      | "("; t1 = term; t2 = term; ")" -> <:expr< Appl $t1$ $t2$ >>
      | x = LIDENT -> <:expr< Var $str:x$ ] ]
    ;
END;;
let term_exp s = Grammar.Entry.parse term_eoi (Stream.of_string s);;
let term_pat s = failwith "not implemented term_pat";;
Quotation.add "term" (Quotation.ExAst (term_exp, term_pat));;
Quotation.default := "term";;

この quotation expander に関して注意点いくつか。

expr quotation の内側(termエントリのアクションパート)では、ドル記号を使うことができる。これは antiquotation だ。 antiquotation は式(やパターン)の断片を quotation の中に埋め込むことができる。これはすぐあとで見る。
この quotation では、 Func や Appl といったコンストラクタはカッコなしで適用できる。この理由は、あらかじめ定義されている OCaml の構文木の quotation の中が「改訂版構文」だからだ。普通の OCaml の構文に近いが、小さな違いがいくつかある。コンストラクタの適用では、 Func (x, y) と書くかわりに Func x y と書ける。これは5章を参照。
最後の文 Quotation.default := "term" というのは、 camlp4 に "term" がデフォルトの quotation であると伝えることを意味している。このとき、 << と >> で指定できる。
このファイルでは term 型を定義する必要がないことに注意。コンストラクタは構文木の中でのみ使われていて、内部的には文字列だ。
パターンバージョンは書かない。これは最終版で加えることになる。

これをコンパイルするには

EXTEND 文のために pa_extend.cmo 構文拡張が、
OCaml の構文木 quotation のために q_MLast.cmo の quotation 拡張が、

必要になる。

コンパイルコマンドは次のようになる。

ocamlc -pp "camlp4o q_MLast.cmo pa_extend.cmo" -I +camlp4 -c q_term.ml

いま生成した q_term.cmo 構文拡張を使ってラムダ項を作ることができる。トップレベル上で(camlp4o.cma をロードしたあとで)これをロードすれば、ラムダ項 quotation を直接使うことができる。ただしトップレベルでは、 term 型を定義しないといけない。でないと、

# let id = << [x]x >>;;
           ^^^^^^^^^^
Unbound constructor Func

となる。というわけで term の定義をトップレベルで打ち込もう。そうすれば、

# let id = << [x]x >>;;         
val id : term = Func ("x", Var "x")
# let k = << [x][y] x >>;;
val k : term = Func ("x", Func ("y", Var "x"))
# let s = << [x][y][z] ((x y) (x z)) >>;;
val s : term =
  Func ("x",
   Func ("y",
    Func ("z", Appl (Appl (Var "x", Var "y"), Appl (Var "x", Var "z")))))
# let delta = << [x](x x) >>;;
val delta : term = Func ("x", Appl (Var "x", Var "x"))

こんなもんだ。 omega の定義は特殊なケースで、次の章を見ることになるからちょっと待って欲しい。今のところは、次のようなつれない返事を返すだけだ。

# let omega = << ^delta ^delta ) >>;;
                 ^
While expanding quotation "term":
Parse error: illegal begin of term

構文エラーの場所が正しいことに気づいただろうか。これは文法システムのおかげである。構文エラーが出る場合、例外 exc_located がエラー位置を返してくれる。このエラーを捕捉して、 quotation 拡張は機械的に quotation の位置を加えて入力テキストに正しく表示してくれる。

それじゃ、変数 omega の定義について見てみよう。これは antiquotation で解決できる。

4.8 Antiquotations

Antiquotation というのは、 quotation 内部にコードを挿入する方法だ。 quotation と違って、 antiquotation は Camlp4 であらかじめ定義されている構文ではない。これは単なるプログラミングテクニックなのだ。

我々の例では、 omega を「deltaにそれ自身を適用したもの」としたかった。ところが「delta」について言うときには、そのラムダ項(Var "delta" かもしれない)の文脈で「delta という変数」を指定したいわけじゃない。そうじゃなくて、すでに定義されている定義されている「変数 delta の値」を使いたいわけだ。新しいラムダ項を作るときに、その値を挿入したい(この例では2回)のだ。

最初のバージョンでは、次のように書いた。

let omega = Appl (delta, delta)

ふむ。これを使うこともできるしそれは正しいが、我々は quotation のシステムを持っていて、具体的な構文としてこれを表現したいのだ。適用(2つの項をカッコで囲む)でだ。

我々の具体的な構文では、「とりまく環境の値」を指定するある特殊な場合を追加しないといけない。ここでは、キャレット ^ でやってみることにした。

このとき、構文ルールに次のようなものを加えないといけない。「もしキャレットと識別子が来たら、識別子それ自身を変数とみなして構文木を返す」。このルールは EXTEND 文で次のように書ける。

"^"; x = LIDENT -> <:expr< $lid:x$ >>

この右辺の "expr" quotation は、 OCaml の構文木で "x" という名前の変数を意味する。6章を見て欲しい。このルールを加えた quotation expander をコンパイルしなおして、トップレベルでテストしてみよう。

# let delta = << [x] (x x) >>;;
val delta : term = Func ("x", Appl (Var "x", Var "x"))
# let omega = << (^delta ^delta) >>;;
val omega : term =
  Appl (Func ("x", Appl (Var "x", Var "x")),
   Func ("x", Appl (Var "x", Var "x")))

4.8 antiquotation の位置

警告: このセクションはちょっと瑣末な、特定の問題を解決するものである。このセクションを飛ばしてもかまわない。

可能な構文エラーの位置に関する問題について。デフォルトでは quotation 全体がアンダーラインされる。

# let omega = << (^delta ^xxx) >>;;
              ^^^^^^^^^^^^^^^^^^^
Unbound value xxx

これは quotation 上の変数 xxx の位置ではない。文法システムは位置の面倒を見てくれるはずだし、文法ルールからアクションパートへ、 loc という変数で渡されて OCaml の構文木の quotation が使うのだった。でも正しい位置は失われてる。どういうことだろう？

この理由は、 Camlp4 のquotation 機構は構築した構文木が正しい位置を持っているかどうか無視するということにある。これは単なる構文木を受け取るが、君の使うテクニックについては知らない。 quotation expander はとんでもない位置に挿入されるかもしれない。この場合、エラー位置は入力テキストのどこにでもなりうる。 quotation の中で間違った場所かもしれないし、 quotation の外かもしれない。テキストの外の可能性だってある。

この問題を避けるため、 Camlp4 の quotation 機構は結果の構文木をちゃんとスキャンして、 quotation 全体の位置になるようにする。構文的なエラーが入力テキストのどこかに行ったり quotation の間違った場所を指定する危険よりは quotation 全体とした方がマシだ。

このため、デフォルトでは quotation は quotation expander のプログラマを信用してない。ただ、位置を正しく伝える方法もある。何らかのかたちで正しい位置を含んだ構文木を返せばよい。

これには、「antiquotation」ノードを作ればいい。これは、式 e やパターン p に対して、

<:expr< $anti:e$ >>
<:patt< $anti:p$ >>

とすればいい。ここでのルールは次のようなものだった。

"^"; x = LIDENT -> <:expr< $lid:x$ >>

右辺は識別子 x のノードである。これは識別子の位置を含んでいる(実際にはキャレット込みで)。ただしこれは「antiquotation」ノードで囲まれていないので、 quotation 機構は位置を無視して quotation 全体の位置に置き換える。

antiquotationノードの部分木はその変数 x を表わす木だ。ただし <:expr<$lid:x$ >> を直接使うことはできない。というのは、 antiquotation そのものも位置を示す loc を持っているからで、我々が必要としているのは antiquotation の始点からの相対的な位置だからだ。その位置は次のようなものだ。

(0, String.length x)

こうした点に注意すると、 antiquotation は次のようなものになる。

"^"; x = antiquot -> x

で、 antiquot エントリは次のようになる。

antiquot:
  [ [ x = LIDENT ->
       let ast =
         let loc = (0, String.length x) in
         <:expr< $lid:x$ >>
       in
       <:expr< $anti:ast$ >> ] ]
;

自分の antiquotation の構文は好きなようにできるし、他の quotation と分けることもできる。この例では、 antiquotation は "^" で導入されている。

しかし、 antiquotation をある種の「カッコ」の間に置きたいときはどうすればいいだろう。この場合、 antiquotation の構文木を構築する必要がある。こうすればよい。

Grammar.Entry.parse Pcaml.expr_eoi (Stream.of_string s)

ここで s は antiquotation 文字列だ。これは自分で antiquotation 部分木をつくる(quotation がパターンなら patt_eoi だ)。

たとえば、あらかじめ定義されている構文木(6章参照)はふたつのドル記号で囲まれ、次のように書くことができる。

<:sig_item< value $x ^ string_of_int n$ : unit -> unit >>

この antiquotation の構文木を作るために、「sig_item」なる quotation を上の antiquotation 文字列呼び出しに適用する。ここでの s は antiquotation の中身、つまり

"x ^ string_of_int n"

だ。

デフォルトでは antiquotation 部分木は quotation全体の位置を継承することに注意すること。もし自分自身の位置を持ちたければ(これは型エラーの場合に興味深い)、 antiquotation ノードと一緒に囲むのを忘れないようにすること。 antiquotation 文字列の構文エラーの位置の場合は try...with で囲み、エラー位置を再計算する必要がある。

let ast =
  try Grammar.Entry.parse Pcaml.expr_eoi (Stream.of_string s) with
    Stdpp.Exc_located (bp, ep) exc ->
      raise_with_loc (fst loc + bp, fst loc + ep) exc
in
<:expr< $anti:ast$ >>

4.9 ラムダ項の例: 完成編

そういうわけで、前章の antiquotation の場所システムとパターン版を加えたラムダ項の quotation expander は次の通り。

let gram = Grammar.gcreate (Plexer.gmake ());;
let term_eoi = Grammar.Entry.create gram "term";;
let term = Grammar.Entry.create gram "term";;
EXTEND
  GLOBAL: term_exp_eoi term_pat_eoi;
  term_exp_eoi: [ [ x = term_exp; EOI -> x ] ];
  term_exp:
    [ [ "["; x = LIDENT; "]"; t = term -> <:expr< Func $str:x$ $t$ >>
      | "("; t1 = term; t2 = term; ")" -> <:expr< Appl $t1$ $t2$ >>
      | x = LIDENT -> <:expr< Var $str:x$>>
      | "^"; x = exp_antiquot -> x ] ]
  ;
  exp_antiquot:
    [ [ x = LIDENT ->
        let ast = let loc = (0, String.length x) in <:expr < $lid:x$ >> in
          <:expr< $anti:ast$ >> ] ]
  ;
  term_pat_eoi: [ [ x = term_pat; EOI -> x ] ];
  term_pat:
    [ [ "["; x = LIDENT; "]"; t = term_pat -> <:patt< Func $str:x$ $t$ >>
      | "("; t1 = term_pat; t2 = term_pat; ")" -> <:patt< Appl $t1$ $t2$ >>
      | x = LIDENT -> <:patt< Var $str:x$ >>
      | "^": x = pat_antiquot -> x ] ]
  ;
  pat_antiquot:
    [ [ x = LIDENT ->
        let ast = let loc = (0, String.length x) in <:patt< $lid:x$ >> in
            <:patt< $anti:ast$ >> ] ]
  ;
END;;
let term_exp s = Grammar.Entry.parse term_exp_eoi (Stream.of_string s);;
let term_pat s = Grammar.Entry.parse term_pat_eoi (Stream.of_string s);;
Quotation.add "term" (Quotation.ExAst (term_exp, term_pat));;
Quotation.default := "term";;

このファイルをコンパイルしたら、同じ実験をトップレベルでやってみよう(ロードするのを忘れないように)。

# let omega = << (^delta ^xxx) >>;;
                   ^^^^^
Unbound value delta
# let delta = << [x](x x) >>;;                                          
val delta : term = Func ("x", Appl (Var "x", Var "x"))
# let omega = << (^delta ^delta) >>;;
val omega : term =
  Appl
   (Func ("x", Appl (Var "x", Var "x")),
    Func ("x", Appl (Var "x", Var "x")))
# match omega with << (^a ^b) >> -> a | x -> x;;
- : term = Func ("x", Appl (Var "x", Var "x"))

ずいぶんと改善されている。たとえば最後の例では、任意のパターン "_" も使うことができる。

match omega with << (^a ^_) >> -> a | x -> x;;

4.10 結論

これで quotation に関する主な点は理解したことになる。 OCaml に構文拡張を加える道のりで、次の一歩を踏み出すことができる。 Camlp4 の一般的な quotation システムだ。今や、すでに定義されている OCaml の構文木の quotation の詳細を見ることができる。すでにそのいくつかは説明してきた。しかし、「改訂版構文」を使うためにはこれを導入しないといけない。

5. 改訂版構文

改訂版構文は、 OCaml のもうひとつの構文である。その目的は (1) 通常の構文の問題点の修正(閉じてないために曖昧な構造、コンストラクタのアリティ、トップレベル式の終端、ストラクチャの要素などなど)。 (2) 重複のある構造( := と <- 、 fun と function、 begin..end とカッコなど)や概念(型と型宣言)の回避 (3) いくつかのアイディアの付与(リストや型で)。言うなれば、よりロジカルで、単純で、一貫していて、パースや整形が簡単な構文を提案しようということだ。

改訂版構文はあまり使われていないが、普通のものよりも歴史からの制約が薄い。「どう過去のバージョンと互換性を保つか」じゃなくて「どうするべきか」という疑問に答えている。

あるいは別のモチベーションとして、(1) 構文が言語の「外郭」にすぎないことを示すこと。バックグラウンドを変更することなく構文を変えることができる。 (2) 構文拡張をする上での Camlp4 の限度を調べること、の二点が挙げられる。

改訂版構文は完全な言語構文なので、すべての OCaml プログラムで使うことができる。ところで Camlp4 自身もこの構文で書かれている。これは制約ではないことに注意しよう。通常の構文と相互に変換しあうのは、 Camlp4 の pretty print でいつでも可能だ。

注意: プログラミング言語の構文はほとんど個人的な趣味に依っている。この構文は私を表現している。いくつかの選択は気紛れ(他の解決が可能)に見えるかもしれない。けれども私は、もとの構文からあまりにかけ離れることなく、ある種の一貫性を保とうと努力した。改訂版構文で書かれたプログラムは、この章を読まなくても理解できると私は思う。

改訂版構文のほとんどの構造はこのため、普通の構文と同じにしてある。この章はその違いだけを説明して、その理由を明らかにする。

次の章で見る OCaml の構文木の quotation はこの改訂版構文を使っている。

5.1 実際的なこと

改訂版構文で書いた foo.ml をコンパイルするには次のようにする。

$ ocamlc -pp camlp4r foo.ml

改訂版構文をトップレベルで使う場合はこうだ。

$ ocaml
# #load "camlpr4.cma";;

5.1 フレーズ

改訂版構文では、ストラクチャやシグネチャ、オブジェクトの終端には単純にセミコロンをつける。このセミコロンは必須だ。二重セミコロンはトークンではない。複文との曖昧性はない。そちらを特殊な構造にしているから(後述)。
大域変数の宣言は value というキーワードで始められる。 let は let..in の構造のために用意される。

OCaml Revised

let x = 23;; value x = 23;

let x = 23 in x + 7; let x = 23 in x + 7;
インタフェースでは、 val のかわりに value を使う。

OCaml Revised

val x : int;; value x : int;

セミコロンのわけ

OCaml で二重セミコロンが使われているのは歴史的な理由からだ。最初のパーサはトークンで駆動していた。ルールによらなかったので、全ての構造が特定のトークンを必要としていたのだ。

しかし OCaml にモジュールが導入されることで、 Caml Light では必須だった二重セミコロンはオプショナルなものになってしまった。その理由といえば、 OCaml では「フレーズ」と「ストラクチャの要素」は実質的に同じものになったからだ。問題は、二重セミコロンがなにものかの終端という概念と関連づけられていることだ。なにものかとはフレーズだが、ストラクチャの要素ではなくて、というのも他のストラクチャの要素や end キーワードが続くからだ。

通常の構文で二重セミコロンをオプショナルにしたことにはいくつか問題がある。

あるストラクチャの要素は実際には次のストラクチャの要素の先端で終了する。つまりはストラクチャのすべての要素はキーワードから開始しないといけないということだ。でないと曖昧になる。たとえば、次のように書くことはできない。
```
print_string "hello, world"
print_newline ()
```
なぜならこれは、 print_string を3つの引数で呼ぶことになるからだ(したがって型エラーになる)。提唱されている解決策はこうだ。
```
let _ = print_string "hello, world"
let _ = print_newline ()
```
ムムム……。
また、この解決策はインタラクティブには解決されない。トップレベルでは、現在の文の結果を見るのに次の文の先端を書けということはできない。だから二重セミコロンは現存しているのだ！　ソースファイルで書くように書く機会は、トップレベルでは失われている。
ストラクチャやオブジェクトでは、ストラクチャやオブジェクトの要素を終わらせることができないという事実はプログラムを読みづらくしている。短い要素なら1行に書くことができるが、どこで要素が始まり、終わるのか知るのはかなり難しい。

私の意見は、ストラクチャの要素はある種のトークン、このコンテキストでは他のトークンとして読まれることのないトークンで終わらせるべきだということだ。このことでインタラクティブなトップレベルでの正しいふるまいも保証される。改訂版構文では、シーケンスを閉ざすことで単純なセミコロンを解法した。これで単純なセミコロンはストラクチャでもオブジェクトでも完全に要素を終了させることができる。改訂版構文では、セミコロンの終端は必須だ。

すべてのフレーズがあるトークンで終了するという言語を扱うのは簡単なことだ。文の終端では、トークンストリームが同期される(フレーズが終了しているのを見るために余計なトークンを読む必要はない)。この特徴は、他の扱いにも単純さを与えることができる(コメントの抽出や文書化、インデント、エディタモード、インタラクティブツールなどのコードで)。

value のわけ

let のかわりに違うキーワード value を使うことにしたのは、トップレベルの値定義で let..in の構造との差を明確にしたかったからだ。トップレベルで let と let..in を見ると、その let 束縛の最後まで見ないといけなくなる。

抽象的な構文木では、 let と let..in は全然違う。同じ型すら持たない。 let はストラクチャの要素だが、 let..in は式だ。これだけでも構文をもっと見えるようにするに値する。

なぜ val ではなくて value を使ったかって？　type とか exception とかいった他の宣言と一貫性を取りたかったからだ。こちらでは略語を使ってない。型宣言に typ とか、例外に exc とか使わないじゃないか。

5.2 命令的な構造

複文は do キーワードで始まり、 { が続いて } で終わる(最後の式のあとにセミコロンを置いてもいい)。

OCaml Revised

e1; e2; e3; e4 do { e1; e2; e3; e4 }
for とか while とかは同じ構文だ。

OCaml Revised

while e1 do while e1 do {

e2; e3; e4 e2; e3; e4

done }
lets は複文の最後まで適用する。

do とブレースのわけ

最初に、複文は閉じている必要がある。前記した理由のためと、他の構造に比べてあまりに曖昧だったからだ。リストの例は次のようなものだ。

[ a; b; c ]

我々はこれがリストで a と b と c から構成されることを知っている。ところがこれは、要素が1つのリストで、その要素とは "a; b; c" とかいう複文かもしれない。文法では、リストの要素は最上位の式(expr 文法エントリの最上位の式)ではないという仮定がある。これは、 expression-1 とか simple expression のようなものを文法で使うために必要なことだ。

改訂版構文では、こんなことは起きない。あるルールが式を必要とするなら、 expr エントリの最上位をいつでも使うことができる。文法は簡単になり、読んだり理解がしやすくなる。

do のあとにブレースとした理由は個人的な嗜好だ。といっても、 do というキーワードは何かを命令的に(関数的ではなく)やるという風に考えやすい。それにブレースは C 言語の構文を思い出させる。

普通の構文と同じく、複文中の let..in はその複文の終りまで適用されることに注意しよう。ただし普通の構文では、複文の構造が解法されているため、妙な結果になる。次の例を見てみよう。

if condition then
  a-simple-statement;
statement-2;
statement-3;

ここで「simple-statement」に let 束縛を加える必要があるとしよう。単に加えるとこうなる。

if condition then
  let v = expr in
  a-simple-statement;
statement-2;
statement-3;

ところがこれは次の意味になる。

if condition then
  let v = expr in
  a-simple-statement;
  statement-2;
  statement-3;

let は複文の残りを「吸着」してしまう。正確にするには、 begin..end とかカッコを加えないといけない。

5.3 タプルとリスト

タプルではカッコは必須とする。

OCaml Revised

1, "hello", World (1, "hello", World)
リストは常に ``['' と ``]'' の間に入る。したがって、
```
list ::= [ elem-list opt-cons ]
elem-list ::= expression; elem-list | expression
opt-cons ::= :: expression | (*empty*)
```
リストはセミコロンで分けられる式の連なりだが、 ``::'' と式の形式で終わらせることもできる。ただし全体はつねに角カッコで囲む。例を示す。

OCaml Revised

x::y [x::y]

[x; y; z] [x; y; z]

x::y::z::t [x::[y::[z::t]]]

x::y::z::t [x; y; z :: t]

最後のように2通りの書き方がある。

タプルにカッコが必要なわけ

数学では、タプルはつねにカッコで囲まれている。

さらに言うと、これは改訂版構文の一般的なポリシーでもある。なるべく多くの構造を閉じるというポリシーだ。この方が読みやすく、どうでもいい優先順位を学ばなくていい。

リスト構文のわけ

改訂版構文ではリストはつねに閉じられる。 cons には [a :: b] と書けばいいし、列挙であれば要素を [a; b; c] のように書く。どこでリストが開始され、どこでリストが終わるか、いつでも構文的にわかる。

この構文は Lisp のリストに似ているところがある。角カッコはカッコ、セミコロンがスペース、二重コロンはドットだ。

さらには、次のような構文

[ x; y; z :: t ]

これは、普通の構文でいうところの次のものよりも理解しやすいし、もっとロジカルだ。

x :: y :: z :: t

実際、通常の構文で読んでも方が明確でない。 x と y と z は t と同じ型じゃない。二重コロンは右結合性だということを思い出してほしい。これは自然じゃない。改訂版構文では、 x と y と z は同じように置いて(セミコロンで区切り)、異なる t だけを違うように置いている(二重コロンで区切る)。

改訂版構文では、 x と y と z がこのリストの先頭の要素だということがすぐわかる。というのは、構文は cons で終わってるかどうかで識別できるからだ。通常の構文ではこうはいかない。

5.4 反駁できないパターン

いくつかの構造で利用される「反駁できないパターン」というのがある。この手のパターンへのマッチングは絶対に失敗しない。「反駁できないパターン」というのはつまり次のようなものだ。

変数
ワイルドカード ``_''
コンストラクタ ``()''
反駁できないパターンで構成されるタプル
反駁できないパターンで構成されるレコード
型制約つきの反駁できないパターン

「反駁できない」という用語は、絶対に失敗しないパターンすべてにあてはまるわけではないことに注意しよう。たとえば型定義でコンストラクタしかない場合は、 ``()'' を除けば「反駁できない」とは言わない(それは単独であるとかパース時には決定できないとか言う)。

5.5 マッチングに関する構造

function というキーワードは存在しない。 fun を使わないといけない。
fun におけるパターンマッチングで、 match とか try とかは角カッコで囲む。

OCaml Revised

match e with match e with

p1 -> e1 [ p1 -> e1

| p2 -> e2;; | p2 -> e2 ];

fun x -> x;; fun [x -> x];

ただし、パターンがひとつしかなくてパターンが反駁不能であれば、角カッコは必須でないとした。この場合、改訂版構文は変化がない。

OCaml Revised

fun x -> x fun x -> x

fun {foo=(y, _)} -> y fun {foo=(y, _)} -> y

注意してほしいのは、改訂版構文では fun [ x -> x ] も fun x -> x も正しいということだ。カリー化されたパターンマッチングでも角カッコを省いてよい。ただし反駁不能なパターンに限る。

Ocaml Revised

fun x (y, z) -> t fun x (y, z) -> t

fun x y (C z) -> t fun x y -> fun [C z -> t]
空の関数を書くことができる。このとき、どんな引数が与えられても Match_failure の例外が発生する。空の match では式が評価されたあとで Match_failure が発生し、空の try は try なしと同じになる。
```
fun []
match e with []
try e with []
```
let や value のあとのパターンは反駁不能でないといけない。次の式、
```
let f (x::y) = ...
```
これは改訂版構文では次のように書かないといけない。
```
let f = fun [ [x::y] -> ... ]
```
where を使うことはできる。これは反転した let だが、1つの束縛しか書くことができない。

fun のみにしたわけ

fun と function があるのはどこかヘンだ。どちらも同じ意味だからだ。

改訂版構文では「反駁できないパターン」というのを加えることで、曖昧さをなくした。リストは反駁できないパターンじゃないので、角カッコを使った構文はパースのときに問題にならない。反駁できないパターンを使うとき、1種類しかない場合、閉じた構造が必要でないとき、この全てが満たされるときにみ単純な形式 fun x -> x が許される。

閉じた構造のわけ

「ぶらさがり bar」の問題(if における「ぶらさがりの else」問題と同じ)を避けるためだ。普通の構文で次のプログラムを考えてみてほしい。

match ... with
  case1 ->
    match ... with
      case11 -> ...
    | case12 -> ...
| case2 -> ...

これは間違って解釈される。これをやりたければ、カッコか begin..end を使って match の構造を閉じないといけない。同じ問題が、 else がオプショナルな if にもあった(後述)。

すべてのケースが同じトークンで始まらない(最初だけ左角カッコになる)のは認めるが、これはプログラムを書く上では現実的な問題にならない。最初のケースと他のを入れ替えるときには実際、面倒だ。しかしリーダビリティと曖昧性の除去はどちらも、使いやすさや無駄を省くことよりも重要だ。エディットしやすいがバグを入れやすかったり間違いやすいなら、それはベターではない。

なぜ閉じるときにキーワード、 end とかを使わなかったかって？　その理由はといえば、終端キーワードはどこか命令的な考えなので、 OCaml のように何かが返されると考えさせにくい。

空白形式のわけ

空白の関数は、繰り返し構造の初期や最初の参照値として有用だ。絶対に必要というわけではない。こういうのを書けばいい。

fun _ -> assert False

OCaml の assert 構造の初期化の前に空白マッチが存在する。 assert と同じように、空白の関数はファイル中のエラーの位置を示してくれる。

ここでのこうした構造は、マッチさせるパターンの数がゼロに達する制約があるために存在する。

let に反駁不能のわけ

通常の構文では、反駁可能な let 束縛をすると ``pattern matching is not exhaustive'' なるメッセージに出くわす。綺麗にしたかったり失われた場合を書きたくなたら、自分のソースに苦しめられることになる。実際たとえば、

let x :: y = a in b

は次のように書き直す。

match a with x :: y -> b | ...

改訂版構文ではこのようなものが禁止されているため、こういう状況に出くわすことはない。

where 構造のわけ

この構造はいにしえの ``Caml'' V3.1 (開発は90年代のはじめに停止)にあったもので、私はこれが好きだった。この構造には問題があった。というのは、これは and で分けられた束縛を加えることが可能だったからで、時にそれが衝突する(もう一つの「ぶらさがり」ケース)からだ。

let a =
  b where c = d
and e = f in ..

このコードでは、 where は let 束縛の and を「吸収」してしまう。というわけで、次のように解釈される。

let a =
  b where c = d and e = f
in ...

このため、 Caml Light と OCaml では where は削除されてしまった。しかし where は1つの束縛でしか動かなった。ともかく、いくつもの束縛を持つのはこういう構造では面白くもなければ便利でも、読みやすくもならない。

私個人としては、 let 束縛がある関数の定義とその関数の呼出し式のときは、この構造を使う。私は

loop 0 where rec loop i = ...

と書くのが、次の等価なものより好きだ。

let loop i = ... in loop 0

私はこの where 形式の方がこうした場合にはずっと読みやすいと考える。

5.6 可変な値と割当て

<- は := で書く。

OCaml Revised

x.f <- y x.f := y
ref 型はそのフィールドのラベル名として、 contents のかわりに val を持つ。 ! 演算子はもう使われることはない。また、参照と割当ては他の可変な要素と同じように扱う。

OCaml Revised

x := !x + y x.val := x.val + y

わけ

割当ての構造を2つも持ってるなんて異常だ。通常の構文では、 := は ref 型に特化されていて、これは古い時代の名残りだ。そのころの参照はコンストラクタで(つまり可変のコンストラクタで)実装されていて、参照値を取り出すコードがややこしかったのだ。

match x with Ref x -> x
match x with Ref x -> x <- y

これが "!x" とか "x := y" を持つための理由だった。今では参照はレコード型で実装されていて、次のように書くことができる。

x.contents
x.contents <- y

通常の構文では、参照へのアクセスと割当てに2つの方法があり、 contents というラベルを使った方法は滅多に使われることはない。改訂版構文では1つだけに限定する。ただし、私は contents というのは識別子として長すぎると思うので、これを val に変更した。これは ref の定義を変更したわけではなくて(Camlp4 は構文にしか働かない)、構文木を変えただけなので、本当のフィールド名は contents のままである。

ただ、 := は参照値の割当ての意味では使われず、 <- を使うことになっているので、パターンマッチングや関数での -> と一緒に使う場合には不自然になったりややこしくなる。

それから !x は x.val と書くことで回避する。これで2つのトークンを参照型のためだけに無駄遣いせずに済んでいる。

5.7 型

型コンストラクタは型パラメタを後に書き、カリー化される形式で書く。

OCaml Revised

int list list int

('a, bool) Hashtbl.t Hashtbl.t 'a bool

type 'a foo = type foo 'a =

'a list list;; list (list 'a);
抽象型は束縛されない型変数で表現する。

OCaml Revised

type 'a foo;; type foo 'a = 'b;

type bar;; type bar = 'a;
カッコは型のタプルでは必須とする。

OCaml Revised

int * bool (int * bool)
具体的な型の宣言では、コンストラクタ宣言を角カッコで括る必要がある。

OCaml Revised

type t = A of i | B;; type t = [ A of i | B ];
コンストラクタを使わないで空の型をつくることもできる。
```
type foo = [];
```
複数のパラメタを持つデータコンストラクタと、タプル型のパラメタを持つデータコンストラクタには構文的な違いがある。複数のパラメタを持つデータコンストラクタの型宣言では、型を and で繋ぐ。式やパターンでは、このコンストラクタはカリー化された形式で書くこと。 C x y;

OCaml Revised

type t = C of t1 * t2;; type t = [ C of t1 and t2 ];

C (x, y);;

タプル型のパラメタを持つデータコンストラクタの宣言では、タプル型を使う。式やパターンとして使う場合でもカリー化されない形式で書く。

OCaml Revised

type t = D of (t1 * t2);; type t = [ D of (t1 * t2) ];

D (x, y);; d (x, y);
あらかじめ定義されているコンストラクタとして True と False がある。
レコード型では mutable のキーワードはコロンの後に書く。

OCaml Revised

type t = { mutable x : t1};; type t = {x : mutable t1};

型の適用順序のわけ

順序はコンストラクタの値を見るようになっている。型宣言と同じ順序で値を読めるようにしている。カリー化スタイルの構文も、コンストラクタとして見るため。

抽象型構文のわけ

抽象型は実存主義的な型だ。というのは、抽象型は実際には何らかのかたちで存在に関する型だからだ。実存主義的な型がいつの日にか OCaml に取り込まれるなら、このことにも意味はあるかもしれない。

タプル型にカッコを要するわけ

なるべく多くの構造を閉じさせるためだ。タプルがそうであるように閉じる。さらに、2つのパラメタが必要な場合と1つのパラメタを要するタプルの場合を区別するときに便利だ。

コンストラクタの宣言のわけ

改訂版構文では、今後の拡張のためになるべく一般的にしようとしている。

レコード型はブレースで括る(変更なし)。対照的に、直積型(コンストラクタ宣言)は角カッコで括る。これも、これらを「型」として考えるひとつのやり方だ。型宣言以外の場所で書くときの場合を考えてみよう。たとえば、

fun (x : [ A | B ]) -> ...
type t = { lab : [ A | B ] }
type u = [ C of { lab : ... } ]

ところで最後の場合は SML の手法を使っていて、レコード型は常に無名である。

Camlp4 の抽象構文では、「型宣言」なるものはない。型宣言は型となる。直積型やレコード型が型宣言でしか受け入れられないというのは、抽象的な構文を ocamlc が使うやつに変換するときに行われる。

空白型のわけ

型コンストラクタ定義が閉じられているので、空白の型を考えることもできる。そんなに便利というわけではないが、これを持つことによる弊害はない。この型は何物も持たない。

コンストラクタでカリー化された構文を使うわけ

これは実際の意味論に基いている。実際には2つの場合があるが、この2つの場合の値は異なるように実装される。コンストラクタのアリティが明確になる。

通常の構文では、なぜ C が2つのパラメタを持つとき、次のように書けるが、

fun C (x, y) -> (x, y)

次のように書けないのか、わかりづらい。

fun C x -> x

改訂版構文では、次のように書かなければならない。

fun [ C x y -> (x, y) ]

改訂版構文では、 C なるコンストラクタの2つのパラメタはタプルとは考えにくいということを反映している。

このことはコンストラクタの「部分評価」ができることを意味しない。それを受け入れるかどうかは意味論の問題で、 OCaml の型付けの時に扱われる。

大文字の True と False のわけ

通常の構文では、 true と false は小文字から始まるコンストラクタにすぎない。これには歴史的な理由がある。 Caml Light では、(いかなる型の)コンストラクタも大文字から始めるという必然性はなかった。 OCaml ができたときにこれがなぜか変更され、 true と false はこのルールを逃れたというわけだ。それは構文的な構造でもなければその一部でもない。

改訂版構文では、 True および False と書かなければならず、これはキーワードではない。

レコードにおける mutable の順序のわけ

これは読みやすさの問題だ。「ラベル x は可変の整数だ」というのは「可変のラベル x は整数だ」というのよりもわかりやすい。

5.8 モジュール

モジュールの適用はカリー化された形式で書く。

OCaml	Revised
type t = Set.Make(M).t;;	type t = (Set.Make M).t;

わけ

カリー化された書き方の方が関数型言語では一般的だ。適用(どんな適用か問わず)に対して2つの構文を持つ理由はない。

5.9 クラスとオブジェクト

クラスとオブジェクトも改訂版構文を持つ。これを見る簡単な方法は、通常の構文で例を書いてみて、次のコマンドで改訂版構文に変換することだ。

camlp4o pr_r.cmo file.ml

(追加予定)

5.10 その他

else は if 文で必須。

OCaml Revised

if a then b if a then b else ()
真理値演算子の or と and は使われない。 || と && を使うこと。

OCaml Revised

a or b & c a || b && c

a || b && c a || b && c
begin..end はもうない。必要とあればカッコを使う。
演算子を関数として使う場合はバックスラッシュを使う。

OCaml Revised

(+) \+

(mod) \mod
特殊文字の演算子は自動的に中置できない。中置演算子を定義するには構文拡張する必要がある。
インタフェースや実装ファイルででいくつかの宣言をまとめることもでき、その時に declare と end で囲む。
```
declare
  type foo = [ Foo of int | Bar ];
  value f : foo -> int;
end;
```

else のわけ

「ぶらさがりの else」問題を回避するために else を必須とした。通常の構文では次のように書ける。

if a then
  if b then c
else d

この問題では、 else d が実際には if a でなくて if b の方に対応付けられてしまう。改訂版構文では、 else が必須なのでこの問題は起きない。

OCaml は関数型言語なので、 else を必須とするのは普通だ。実際、通常の構文で条件が偽のとき、式の値は明確でない。

このような「ぶらさがり」問題は pretty printing にある。ある構造がカッコで囲まれる必要があるかどうかを知るのは簡単じゃない。改訂版構文では、ぶらさがりの問題はないし pretty printing の問題もない。通常の構文で pretty printing をやるためには、あらゆる関数に余分に引数を渡すしかない。

改訂版構文である構造が閉じていなければ閉じる必要がないと覚えておこう。

or と and 演算子のわけ

or や and の意味で2つの構文を持つ意味はない。 or や & の構文は古い構造で、後方互換性を保つためだけにある。

begin..end をなくすわけ

通常の構文では、 begin と end で囲まれる部分はカッコで括るのと同じ意味になるが、個人的には疑問に思っていた。通常の構文では、カッコは必須で、プログラマによって "begin match..end" と "(match..)" の好きな方が使われている。

改訂版構文では、カッコで閉じる必要のある場合があんまりない。というのは、ほとんどの構造がカッコで閉じられているからだ。2つの構造は必要ない。

単独演算子の構文のわけ

単純に * 演算子をスペースなしで特定する場合を避けるためだ。 (*) は構文的にコメントの開始とみなされてしまう。

自動的に中置演算子にしないわけ

Camlp4 を使ってるわけで、 Camlp4 の機能を使えるからだ。

declare 構造のわけ

OCaml のストラクチャの要素がいくつかのストラクチャの要素を生成する場合の構文拡張で必要になる。たとえば、ある型宣言をするときには型宣言それ自体と、その型に適用する関数が必要になる。

OCaml の通常の構文木に変換する時には、この構造はインライン化される。

5.11 ストリームとパーサ

ストリームとストリームパターンは角カッコを使って [: ... :] で書かれる。 [< .. >] ではない。
ストリームの「終端」要素はクォートではなくバッククォートを使って書く。

OCaml Revised

[< '1; '2; s; '3 >] [: `1; `2; s; `3 :]
パーサは fun や match や try と同様に角カッコ [ ] で括られる。1つの場合は角カッコは必須ではない。

OCaml Revised

parser parser

[< 'Foo >] -> e [ [: `Foo :] -> e

| [< p = f >] -> f | [: p = f :] -> f

parser [< 'x >] -> x parser [ [: `x :] -> x ]

parser [< 'x >] -> x parser [: `x :] -> x
空のパーサを書くこともでき、適用されれば常に Stream.Failure を発生させる。空白のストリームは常に Stream.Failure を発生する。
```
parser []
match e with parser []
```

キーワードを parse ではなく parser としたわけ

ここでは通常の構文と同じキーワードと同じ選択をしている。

parser というキーワードは function というのに似ていて match には似ていない。 match や try といったキーワードは直接のアクションである。一方、パーサや関数は「概念」に過ぎない。そのパラメタをすぐに適用するわけではない。意味は「これはパーサだ」「これは関数だ」というものだ。

もし parse xxx with といった構造なら parse という単語を使ったかもしれない。これは match xxx with parser と書いてキーワードの無駄遣いを避けている。

[< じゃなく [: を使うわけ

これはリーダビリティによる疑問だ。我々の拡張言語では quotation があるので、大なりや小なりの記号を使うとややこしいことになる。

[<:expr< xx >>; <:expr< yy >>]

クォートをバッククォートにしたわけ

これは OCaml の通常の構文で Caml Light から OCaml に変わるときに行われるべきだった。というのはキャラクタの指定がバッククォートからクォートに変更されたからだ。これは忘れさられてしまった。

通常の構文では、文字のストリームを使う場合に問題となる。

parser [< '('a' | 'b') >] -> ...

字句解析器は最初のカッコを文字とみなすので、パースエラーとなる。これを回避するには空白を入れないといけない。

parser [< ' ('a' | 'b' ) >] -> ...

改訂版構文ならバッククォートなので、この問題は起きない。

パーサの構文を閉じるわけ

関数や match や try での「ぶらさがりバー」の問題と同じ。この構文で、同じように閉じる。

空白パーサのわけ

最初の参照値や繰返しの最初の場合では便利だ。

6. OCaml の構文木

この章では、 quotation を使って OCaml の構文木をつくる方法を説明する。

OCaml の構文木は MLast モジュール(mLast.mli)で定義されている。もちろん、こうした値を組み合わせることで、自分で構文木をつくることができる。ただしそのためには、これらのコンストラクタについて、どう使わなければならないか、対応する構文構造が何なのか、といったことについての正確な文書が必要になる。

4章では、具体的な構文で抽象的な値を表現するのに quotation が便利であることを説明した。構文木にとってもこれは適用できる。というのは、構文木は具体的な構文に対応しているからだ。この場合、学ぶことは何もない。もし具体的な構文を知っていれば、抽象的な構文も知ることになる。実際には改訂版構文(5章)を知る必要はある。これらの quotation では改訂版構文が使われているからだ。

提供される quotation 拡張は q_MLast.cmo ファイルだ。このファイルをロードすると、具体的な構文であるプログラム片ならどんなものでも書くことができる。たとえば、

<:expr< match f $x$ with [ $uid:p$ -> $x$ | C z -> 7 ] >>

この例は実際には次のコードに対応する(通常の構文で)。

MLast.ExMat
  (loc, MLast.ExApp (loc, MLast.ExLid (loc, "f"), x),
   [MLast.PaUid (loc, p), None, x;
    MLast.PaApp
      (loc, MLast.PaUid (loc, "C"), MLast.PaLid (loc, "z")), None,
    MLast.ExInt (loc, "7")]);;

この2つの形式は完全に一致している。ただし前者は単純で読みやすい。ドル記号で挟まれた式に注意しよう。これは antiquotation である(4章参照)。こういった quotation の使い方はこれから見ていく。

さしあたって、ここに q_MLast.cmo で定義されている quotation のリストを見せておく。

expr: 式のノード
patt: パターンのノード
ctyp: 型のノード
sig_item: シグニチャの要素ノード
str_item: ストラクチャの要素ノード
module_type: モジュール型ノード
module_expr: モジュール式ノード

これらの quotation はどれも改訂版構文(5章)を使う。この式形式のもの(つまりパターン以外)はすべて、 loc という名前の変数を含んでいることを知る必要がある。この変数によって、構文木に対してソースの位置がどこか特定できる。このため、 quotation が使われる環境では loc 変数が見える位置に存在しなければならない。

Camlp4 の文法システムでは loc 変数はルールの意味的なアクションで定義されていることに注意しよう。 Camlp4 の文法システムと Camlp4 の抽象的な構文の quotation は一緒に動くように作られている。

6.1 antiquotation

antiquotation は、他の抽象構文木の中に抽象構文木を入れる仕組みだ。ドル記号 $ で囲む。ドル記号の間には回りの構文にあるどんな式もパターンも入れることができる。

たとえば、 MLast.expr 方の変数 x があり、この式に対して何らかの関数 f を呼んだ結果に相当する構文木ノードを作りたいとする。そのときは次のように書く。

<:expr< f $x$ >>

注意しなければならないのは、 quotation がパターンの位置にある場合には quotation の中身もパターンでなければならないということである。(通常の構文で)正しい例を示す。

function <:expr< f $x$ >> -> x;;
function <:expr< f $_$ >> -> 1;;

6.2 ラベルつき antiquotation

このような antiquotation として、ラベルを使うこともできる(ラベルは antiquotation の始点からコロン : までである)。これは、具体的な構文だけでは何をしているか知るのに充分でない場合に使う。

たとえば、 x が文字列型の変数であるとして、 (1) x の値が変数名に対応する構文木のノードとしたいとき、 (2) x の値が文字列の中身に対応するような構文木のノードとしたいとき、 (3) x の値がコンストラクタ名に対応する構文木のノードとしたいときを考える。

ラベルはこれをやる。最初の場合は lid (小文字の(Lowercase)識別子(IDentifier))でないといけない。二番目は str (文字列(STRing))でないといけない。三番目の場合には uid (大文字の(Uppercase)識別子(IDentifier))でないといけない。というわけでこのようになる。

<:expr< f $lid:x$ >>
<:expr< f $str:x$ >>
<:expr< f $uid:x$ >>

このとき、

let x = "foo" in <:expr< f $lid:x$ >> は <:expr< f foo >> と同じ
let x = "foo" in <:expr< f $str:x$ >> は <:expr< f "foo" >> と同じ
let x = "Foo" in <:expr< f $uid:x$ >> は <:expr< f Foo >> と同じ

重要な注意: 文字列(str)や文字(chr)の antiquotation は「エスケープされた」文字列を含まなければならない。つまり、バックスラッシュやクォート、ダブルクォートなどの前にはバックスラッシュをつけなければならない。確実にこれをやるためには、 OCaml のライブラリ関数 String.escaped および Char.escaped を使うこと。

よく見るラベルに list がある。これは、この場所にリストがあることが構文的に期待できるときに使う。次のが antiquotation の例で、一方はラベルつき、もう一方はラベルなしだ。

<:expr< [| $list:x$ |] >>
<:expr< [| $x$ |] >>

最初の場合、 x は MLast.expr list 型でなければならず、 quotation としては「要素が x の中の要素に対応する配列」を意味する。
二番目の場合、 x は MLast.expr 型を持ち、 quotation としては1つの要要素を持つ配列となる。

注意点として、 antiquotation は周囲の構文ルールに制限を受ける。 x と y が MLast.expr 型の値で z が MLast.expr list 型の値のとき、

<:expr< [| $list: x::y::z $ |] >>

は通常の構文で正しい。しかし改訂版構文を使っているときには、次のように書かないといけない。

<:expr< [| $list: [x; y :: z] $ |] >>

6.3 他

いや、全部のノードをひとつひとつ解説することもできるんだが、それはもうリファレンスマニュアルで説明されている。そっちを参照してほしい。

7. OCaml の構文を拡張する

7.1 導入

OCaml の構文拡張は OCaml の文法エントリを拡張することで可能となる。全ての文法エントリは Pcaml という名前のモジュールで定義されている。これは、必ず MLast モジュールで定義されている型の値を返す。これらの型のノードは q_MLast.cmo であらかじめ定義されている quotation expander を使う。

PCaml のエントリは次の通り。

expr: 式。 MLast.expr の値を返す。
patt: パターン。 MLast.patt の値を返す。
ctyp: 型。 MLast.ctyp の値を返す。
module_type: モジュール型。 MLast.module_type の値を返す。
module_expr: モジュール。 MLast.module_expr の値を返す。
sig_item: シグニチャの要素。 MLast.sig_item の値を返す。
str_item: ストラクチャの要素。 MLast.str_item の値を返す。

こうしたエントリのほとんどは何らかの「レベル」で定義(拡張)されている(3章を参照)。この中のいくつかは、拡張したり他のレベルを挿入するためにラベルづけされる。

レベルと可能なラベルはあらかじめ定義されているわけではない。それは構文の定義による。どのラベルが定義されているか、どのルールがそれを含むか見るには、トップレベルで次のように打ってみよう。

#load "camlp4o.cma";;
Grammar.Entry.print Pcaml.expr;;
Grammar.Entry.print Pcaml.patt;;
(* などなど…… *)

改訂版構文では、代わりに "camlp4r.cma" をロードする。他の構文を定義していたりした場合には、そっちをロードした上で Grammar.Entry.print をそれぞれのエントリで呼ぶ。可能な構文と拡張については、 camlp4 の man ページを参照すること。

ひとたび拡張したい文法エントリのリストと可能なレベルのラベルを手にしたら、あとは拡張するだけだ。

7.2 例: Pascal のような repeat until

このチュートリアルを全部読んでいれば、この例を理解できると思う。もし理解できなければファイルを作って試してみてほしい。

最初に foo.ml なる名前のファイルを作る。その内容は以下の通り。

open Pcaml;;
EXTEND
  expr: LEVEL "expr1"
    [[ "repeat"; e1 = expr; "until"; e2 = expr ->
          <:expr< do { $e1$; while not $e2$ do { $e1$; } } >> ]];
END;;

このファイルを次のコマンドでコンパイルする。

$ ocamlc -pp "camlp4o pa_extend.cmo q_MLast.cmo" -I +camlp4 \
-c foo.ml

次に、実際に repeat..unitl 構文を使ったファイル bar.ml を用意する。

let main () =
  let i = ref 0 in
  repeat print_int !i; incr i until !i = 10;
  print_newline ()
let _ = main ()

これをコンパイルするには次のようにすればいい。

$ ocamlc -pp "camlp4o ./foo.cmo" bar.ml

実行してみよう。

$ ./a.out
0123456789

もしくは、拡張構文のプログラムを表示してみる。

$ camlp4o ./foo.cmo pr_o.cmo bar.ml
let main () =
  let i = ref 0 in
  begin
    begin print_int !i; incr i end;
    while not (!i = 10) do print_int !i; incr i done;
  end;
  print_newline ()
;;
main ();;

7.3 例: 定数

C の #define の代替が欲しければ、次のようにすればいい。もし FOO を式とパターンの両方で 54 という値に置き換えたければ、

open Pcaml;;
EXTEND
  expr: LEVEL "simple"
    [[ UIDENT "FOO" -> <:expr< 54 >> ]];
  patt: LEVEL "simple"
    [[ UIDENT "FOO" -> <:patt< 54 >> ]];
END;;

このファイルをコンパイルするには次のようにする。

$ ocamlc -pp "camlp4o pa_extend.cmo q_MLast.cmo" -I +camlp4 \
-c foo.ml

ここで定数 FOO を含むファイル bar.ml を用意する。

FOO;;
function FOO -> 22;;

これをコンパイルするには次のようにする。

$ ocamlc -p p"camlp4o ./foo.cmo" bar.ml

拡張構文を表示してみたければ次のようにする。

$ camlp4o ./foo.cmo pr_o.cmo bar.ml
54;;
function 54 -> 22;;

7.4 例: C のような for ループ

次に、 C のような for ループを書くことを許す構文拡張の例に行こう。この構造は、ループ変数と3つの単純な式であるパラメタからなる。最初が初期値、次がテスト、最後がループ変数を変化させる方法だ。

ここで注意。構文拡張を行うソースでは #load ディレクティブを使うことができる。これを camlp4o でパースすることで、コマンドラインでこれらのファイルを指定する必要がなくなる。

ファイル cloop.ml の中身はこうなる。

#load "q_MLast.cmo";;
#load "pa_extend.cmo";;

open Pcaml

let gensym =
  let cnt = ref 0 in
  fun var ->
    let x = incr cnt; !cnt in
    var ^ "_gensym" ^ string_of_int x

let gen_for loc v iv wh nx e =
  let loop_fun = gensym "iter" in
  <:expr<
    let rec $lid:loop_fun$ $lid:v$ =
      if $wh$ then do { $e$; $lid:loop_fun$ $nx$ } else ()
    in
    $lid:loop_fun$ $iv$ >>

EXTEND
  expr: LEVEL "expr1"
    [ [ "for"; v = LIDENT; iv = expr LEVEL "simple";
        wh = expr LEVEL "simple"; nx = expr LEVEL "simple";
        "do"; e = expr; "done" ->
          gen_for loc v iv wh nx e ] ]
  ;
END

このファイルをコンパイルするには次のようにする。

$ ocamlc -pp camlp4o -I +camlp4 -c cloop.ml

トップレベルで試してみよう。

$ ocaml
        Objective Caml version 3.07+2
# #load "camlp4o.cma";;
        Camlp4 Parsing version 3.07+2
# #load "cloop.cmo";;
# for i = 0 to 10 do print_int i; done;;
012345678910- : unit = ()
# for c 0 (c<10) (c+1) do print_int c; done;;
0123456789- : unit = ()
# for c 0 (c<10) (c+3) do print_int c; done;;
0369- : unit = ()

この構造を使ったプログラムをコンパイルする場合は次だ。

$ cat foo.ml
for c 0 (c<10) (c+2) do print_int c; done
# ocamlc -pp "camlp4o ./cloop.cmo" -c foo.ml

もしこのプログラムを調べるならこうなる。

$ camlp4o ./cloop.cmo pr_o.cmo foo.ml
let rec iter_gensym1 c =
  if c < 10 then begin print_int c; iter_gensym1 (c + 2) end
in
iter_gensym1 0;;

7.5 例: 型に対する表示関数の生成

ここでは、ある構文拡張を定義しようとしている。これにより全ての型宣言に対して、その型の値の表示関数の定義を自動的に追加する。この例では、直和型(コンストラクタによる型)に限定しているが、レコード型や抽象型や別名の型にも簡単に拡張できる。

7.5.1 最初の例: 定コンストラクタによる単相直和型

テストのために col.ml なるファイルを用意しよう。

type colour = Red | Green | Blue

やりたいのは、正しい構文拡張で前処理することで、このファイルを次のように解釈させることだ。

type colour = Red | Green | Blue
let print_colour =
  function
    Red -> print_string "Red"
  | Green -> print_string "Green"
  | Blue -> print_string "Blue"

構文拡張は pa_type.ml というファイルで定義しよう。まずは、どのように構文拡張を挿入するか見てみる。表示関数を生成する関数 gen_print_funs はとりあえず適当な文を入れておく。

#load "pa_extend.cmo";;
#load "q_MLast.cmo";;

let gen_print_funs loc tdl =
  <:str_item< not yet implemented >>

let _ =
  EXTEND
    Pcaml.str_item:
      [ [ "type"; tdl = LIST1 Pcaml.type_declaration SEP "and" ->
            let si1 = <:str_item< type $list:tdl$ >> in
            let si2 = gen_print_funs loc tdl in
            <:str_item< declare $s1$; $s12$; end >> ] ]
    ;
  END

注意点。このファイルの最後にある str_item 構文木にある declare 文はストラクチャの2つの要素(型宣言とその表示関数)をまとめることに使われる。

このファイルは次のコマンドでコンパイルできる。

$ ocamlc -pp camlp4o -I +camlp4 -c pa_type.ml

この例を試すことができる。ただしまだコンパイラを使えない。というのは、 not yet implemented なる部分で構文エラーをおこすからだ。 pretty printer を使おう。

$ camlp4o ./pa_type.cmo pr_o.cmo col.ml
<W> Grammar extension: in [str_item], some rule has been masked
type colour =
    Red
  | Green
  | Blue
let _ = not yet implemented

この余分な文 not yet implemented を見てほしい。また、最初に警告があることに気付くと思う。これは、 str_item に追加した構文ルールが使っている文法にもう存在することを意味している。

この警告を回避するには、 EXTEND 文の前に DELETE_RULE 文を追加する。

DELETE_RULE
  Pcaml.str_item: "type"; LIST1 Pcaml.type_declaration SEP "and"
END;

次に gen_print_funs に取り組もう。これは型宣言のリストを受け取る(型宣言はいくつもの型を定義でき相互再帰的かもしれない)。つまり、型の数と同じだけの表示関数の定義を再帰的に宣言しなければならないということだ。次の関数 gen_one_type_print_fun は、あるひとつの型宣言を生成する。とりあえず、本体は not yet implemented としよう。

let fun_name n = "print_" ^ n

let gen_one_print_fun loc ((loc, n), tpl, tk, cl) =
  <:patt< $lid:fun_name n$ >>, <:expr< not yet implemented >>

let gen_print_funs loc tdl =
  let pel = List.map (gen_one_print_fun loc) tdl in
  <:str_item< value rec $list:pel$ >>

構文拡張ファイルを再コンパイルして、 col.ml でテストしてみよう。関数名が print_colour になったはずだ。

次に gen_one_print_fun を改良する。これは let 束縛の定義を生成しなければならず、これはパターン(関数の名前)と式の組で構成される。我々の関数は引数として4つの値のタプルからなる型宣言を受け取る。(1) 型の名前(位置つき)、(2) パラメタのリスト、(3) その型の種類(実際には型)、(4) 制約のリストだ。

最初のバージョンでは、型パラメタ tpl は無視しよう。これが生成された関数とコードにどう関わるかはあとで見ることにして、今は単相型だけを対象とする。

それから「直和」型(コンストラクタによる型)に限定する。他の型では関数の生成に失敗するとする。

こうした直和型を対処する関数 gen_print_sum を追加しよう。この関数は、それぞれのコンストラクタについて match を生成し(gen_print_cons 関数)、結果のリストから関数を構築することで対処する。

gen_print_cons 関数は、コンストラクタ定義、すなわち (1) 位置と (2) 文字列(コンストラクタ名)と (3) パラメタ型のリスト(ctyp list) のタプルを一組受け取る。とりあえずコンストラクタへのパラメタは無視する。関数 gen_print_cons_patt はこの場合のパターン部分を生成し、 gen_print_cons_expr は式部分、つまり表示命令を生成する。

というわけでこれが最初の(完全版でない)構文拡張である(pa_type.ml ファイル)。

#load "pa_extend.cmo";;
#load "q_MLast.cmo";;

let fun_name n = "print_" ^ n

let gen_print_cons_patt loc c tl =
  <:patt< $uid:c$ >>

let gen_print_cons_expr loc c tl =
  <:expr< print_string $str:c$ >>

let gen_print_cons (loc, c, tl) =
  let p = gen_print_cons_patt loc c tl in
  let e = gen_print_cons_expr loc c tl in
    p, None, e

let gen_print_sum loc cdl =
  let pwel = List.map gen_print_cons cdl in
    <:expr< fun [ $list:pwel$ ] >>

let gen_one_print_fun loc ((loc, n), tpl, tk, cl) =
  let body =
    match tk with
      <:ctyp< [ $list:cdl$ ] >> -> gen_print_sum loc cdl
      | _ -> <:expr< fun _ -> failwith $str:fun_name n$ >>
  in
  <:patt< $lid:fun_name n$ >>, body

let gen_print_funs loc tdl =
  let pel = List.map (gen_one_print_fun loc) tdl in
    <:str_item< value rec $list:pel$ >>

let _ =
  DELETE_RULE
    Pcaml.str_item: "type"; LIST1 Pcaml.type_declaration SEP "and"
  END;
  EXTEND
    Pcaml.str_item:
      [ [ "type"; tdl = LIST1 Pcaml.type_declaration SEP "and" ->
          let si1 = <:str_item< type $list:tdl$>> in
          let si2 = gen_print_funs loc tdl in
	      <:str_item< declare $si1$; $si2$; end >> ] ]
    ;
  END

このバージョンを再コンパイルして、 col.ml でテストしてみよう。

$ ocamlc pp camlp4o -I +camlp4 -c pa_type.ml
$ camlp4o ./pa_type.cmo pr_o.cmo col.ml
type colour =
    Red
  | Green
  | Blue
let rec print_colour =
  function
    Red -> print_string "Red"
  | Green -> print_string "Green"
  | Blue -> print_string "Blue"

希望通りだ！　pretty printing の段階なしでコンパイラに直接使うこともできる。

$ ocamlc -pp "camlp4o ./pa_type.cmo" -c col.ml

さらに、 #load "./pa_type.cmo";; ディレクティブを col.ml の最初に加えれば、次のようにコンパイルするだけで済む。

$ ocamlc -pp camlp4o -c col.ml

ただこれはいいアイディアじゃない。というのは、同じソースを前処理ありでやったりなしでやったりしたくなるかもしれないからだ。

7.5.2 次のバージョン: パラメタつきコンストラクタ

パラメタつきコンストラクタを持つ直和型の場合も追加しよう。この例については、 4.7 でやったラムダ項の定義で試そう。 term.ml の中身は、

type term =
    Var of string
  | Func of string * term
  | Appl of term * term

だった。望ましい結果はこうだ。

type term =
    Var of string
  | Func of string * term
  | Appl of term * term
let rec print_term =
  function
    Var x1 ->
      print_string "Var"; print_string " ("; print_string x1;
      print_string ")"
  | Func (x1, x2) ->
      print_string "Func"; print_string " ("; print_string x1;
      print_string ", "; print_term x2; print_string ")"
  | Appl (x1, x2) ->
      print_string "Appl"; print_string " ("; print_term x1;
      print_string ", "; print_term x2; print_string ")"

この結果のために、パラメタについて x のあとにパラメタの数を足した名前をつける関数 param_name を定義する。

let param_name cnt = "x" ^ string_of_int cnt

さらに関数 list_mapi が必要になる。これは List.map に似ているが、引数として与える関数の最初の引数としてリストの要素数が与えられる。これにより、型リストを探索する段階でコンストラクタのパラメタ名を生成できる。

let list_mapi f l =
  let rec loop cnt =
    function
      x :: l -> f cnt x :: loop (cnt + 1) l
    | [] -> []
  in
  loop 1 l

パターン部分を担当する gen_print_cons_patt 関数は次のように変更する。

let gen_print_cons_patt loc c tl =
  let pl =
    list_mapi (fun n _ -> <:patt< $lid:param_name n$ >>)
      tl
  in
  List.fold_left (fun p1 p2 -> <:patt< $p1$ $p2$ >>)
    <:patt< $uid:c$ >> pl

この変更によって、生成される関数 print_term のパターン部分が正しくなった。試してみよう。

式部分は、コンストラクタのパラメタ全てに対して表示関数を呼ぶようにしなければならない。新しく gen_print_type 関数を加え、ある型に関係する表示関数を生成させよう。とりあえず、この関数は単純な型名にしか対応しない。他の型は省略する旨を表示する。

let gen_print_type loc =
  function
    <:ctyp< $lid:s$ >> -> <:expr< $lid:fun_name s$ >>
  | _ -> <:expr< fun _ -> print_string "..." >>

コンストラクタのパラメタに対してこの表示関数への呼出しを生成する関数も必要になる。

let gen_call loc n f = <:expr< $f$ $lid:param_name n$ >>

さらに、余計な構造としてスペース、カッコ、カンマを加える関数も用意する。

let gen_print_con_extra_syntax loc el =
  let rec loop =
    function
      [] | [_] as e -> e
    | e :: el -> e :: <:expr< print_string ", " >> :: loop el
  in
  <:expr< print_string " (" >> :: loop el @
  [<:expr< print_string ")" >>]

では、これらの関数を使って gen_print_cons_expr を変更しよう。

let gen_print_cons_expr loc c tl =
  let pr_con = <:expr< print_string $str:c$ >> in
  match tl with
    [] -> pr_con
  | _ ->
      let pr_params =
        let type_funs = List.map (gen_print_type loc) tl in
        list_mapi (gen_call loc) type_funs
      in
      let pr_all = gen_print_con_extra_syntax loc pr_params in
      let el = pr_con :: pr_all in
      <:expr< do { $list:el$ } >>

これらの関数全部をまとめることで、 pa_type.ml のバージョン2が完成した。これは term.ml に適用できる。やってみよう！　また、直和型の定義をもつ自分のプログラムで試してみよう。

7.5.3 最終版: 多相型

今度は、多相型、つまり型変数による型でも生成してみよう。今度の例は mlist というものだ。 mlist.ml の中身はこうなっている。

type 'a mlist = Nil | Cons of 'a * 'a mlist

このような型の表示関数は、引数として個々の型の表示関数を受け取るとしよう。たとえば、 int mlist に対しては print_mlist print_int を呼ぶことができ、 string mlist には print_mlist print_string で、というわけだ。

望ましい結果はこうなる。

type 'a mlist = Nil | Cons of 'a * 'a mlist
let rec print_mlist pr_a =
  function
    Nil -> print_string "Nil"
  | Cons (x1, x2) ->
      print_string "Cons"; print_string " ("; pr_a x1;
      print_string ", "; print_mlist pr_a x2; print_string ")"

ある型変数に対する表示関数の名前は、 pr_ のあとに型変数名が来るとしよう。

let fun_param_name n = "pr_" ^ n

表示関数への引数である関数(let print_mlist pr_a = ...)を加えるために、 gen_one_print_func 関数を変更して body にこれらを加えるようにしよう。

let body =
  List.fold_right
    (fun (v, _) e ->
       <:expr< fun $lid:fun_param_name v$ -> $e$ >>)
    tpl body
in

ある型変数を表示させる(pr_a x1)ために、 gen_print_type 関数で型変数の場合を加える。

| <:ctyp< '$s$ >> -> <:expr< $lid:fun_param_name s$ >>

さらに、これらのパラメタの型を表示する部分(我々の例だと再帰的に 'a mlist 型のコンストラクタの引数に対して print_mlist pr_a x2を呼ぶ部分)を生成するために、型を適用する場合に同じ関数を加える。ただし、再帰呼び出しの必要があるため、 gen_print_type 関数は内部で再帰的に定義されるよう書き直す。

完全版は以下の通り。

7.5.4 改善点

同じようにすれば、他の種類の型、レコード型や抽象型などにも対応できる。

他の興味深い改良点としては、 print_string を使うかわりに Format ライブラリの関数を使うというのも考えられる。

さらには、個々の場合で表示関数を羅列するのではなく Format.fprintf をひとつだけ生成し、フォーマット文字列の内部で @ を接頭辞とする便利な簡約表現を使うという改善点が考えられる。

8. camlp4 のコマンドたち

Camlp4 はシェルから使うことのできるコマンドである。これにはいくつかのバージョンがある。 camlp4、camlp4o、camlp4rなど。実のところ基本となるのは camlp4 で、他はあらかじめロードされている構文を含むショートカットである。

オプションは2つにわけられる。ロード関係のオプションとそれ以外だ。入力ファイル(.mli とか .ml とか)は他のオプションになる。

8.1 ロードオプション

ロードオプションが先に来なければならない。このオプションは OCaml のオブジェクトファイル(cmo)またはライブラリファイル(cma)で、他の操作の前に camlp4 のコアに読み込まれる。このファイルはパスから探索される。このパスには -I で指定できる。デフォルトではこのパスは camlp4 ライブラリディレクトリを含む。

現在のディレクトリはパスに含まれない。カレントディレクトリに属するファイルをロードするときは、 -I . オプションを使うか、 ./ をつける必要がある。

camlp4 コマンド単独で何もロードしないと、入力ファイルに対して何もせずに失敗する。すくなくとも1つはパーサとプリンタをロードしなければならない。パーサをひとつも指定しないと、 ``Failure: no loaded parsing module'' というメッセージを表示する。プリンタを指定しないと ``Failure: no printer'' だ。実行時には、 camlp4 はパーサを入力ファイルに適用して構文木を構築し、それをプリンタによって出力するのである。

8.2 他のオプション

他のオプションがそのあとに続く。ここは曖昧になる危険性がある場合には、-- を指定することでロードオプションと他のオプションを分離することができる。実は、他のオプションはコアにロードされるオブジェクトファイルによって拡張されうる。たとえば pr_depend.cmo は他のオプションに -I を加える。

可能なオプションを見るには camlp4 -help を実行する。もしくはオブジェクトファイルがオプションを拡張する時は、 camlp4 <load-options> -help を使う。ここで <load-options> は指定したいロードオプションだ。具体的に、次の例を比較してみよう。

camlp4 -help
camlp4 pa_r.cmo pa_extend.cmo -help
camlp4 pr_depend.cmo -help

8.3 あらかじめ定義されているオブジェクトファイル

あらかじめ定義されているオブジェクトファイルは、 camlp4 のライブラリディレクトリにあり、2つの種類に分けられる。

パーサファイル。ファイル名は pa_ で開始される。構文定義もしくは拡張を意味する(pa は PArser の意味)。 quotation 拡張の場合は 'q_' となる。
プリンタファイル。 pr_ から始まる(pr は PRinter)。

camlp4 のライブラリディレクトリにあるパーサやプリンタのリストは、 man ページに載っている。主なものとしては以下のものがある。

pa_o.cmo: 通常の OCaml の構文
pa_r.cmo: 改訂版構文
pr_dump.cmo: 抽象構文木をそのまま出力するプリンタ
pr_o.cmo: 通常の OCaml の構文で出力するプリンタ
pr_r.cmo: 改訂版構文で出力するプリンタ

注意して欲しいのだが、 pr_dump.cmo は抽象構文木をバイナリ形式で表示する。デフォルトでは camlp4 は標準出力に書き出す(-oオプションを指定すると変更できる)。このため、注意してほしい。バイナリ形式をファイルにリダイレクトせずに表示してしまうと、ターミナルをめちゃくちゃにしてしまうことがある。バイナリはエスケープシーケンスを含んでいて、それが解釈されてしまうからだ。このプリンタは OCaml コンパイラへの入力として使われる。

他のプリンタはパース結果を表示し、構文拡張や quotation expander をテストするのに便利だ。通常の構文で表示してもいいし改訂版でもいい。通常から改訂版への変換もその逆もできる。

プリンタも拡張可能だ。これについては文書化していないが、そのわけは表示機能が完遂しておらず、使うのがちょっとややこしいからだ。しかしあらかじめ定義されているプリンタを使うことはできる。これらプリンタは初期のフォームでプログラムを再構築する。たとえば、 pr_extend.cmo は EXTEND 文を再構築する。

あらかじめ定義されている quotation expander の中でも興味深いものに q_phony.cmo がある。これは quotation を擬似変数に変換する。quotation はこのため、そのままに出力される。 quotation を含むプログラムを、それを展開することなしに pretty print するには便利だ。

8.4 camlp4o と camlp4r

camlp4o と camlp4r は実際のところ、それぞれ次のもののショートカットだ。

camlp4 pa_o.cmo pa_op.cmo pr_dump.cmo
camlp4 pa_o.cmo pa_rp.cmo pr_dump.cmo

これらのコマンドにも、他のパーサやプリンタを追加することができる。

8.5 トップレベル

トップレベルで Camlp4 を使うには、まず camlp4 機構をロードしなければならない。 pa_r.cmo や pa_o.cmo をロードするだけではうまく動かない。トップレベルには次のものを含むオブジェクトファイルが必要になるのだ。 (1) Camlp4 のものを使ってパースすることを教えるプラグイン、 (2) camlp4 のライブラリ、 (3) camlp4 パーサで使われるオブジェクトファイル、だ(camlp4 の pretty printing はトップレベルでは動かない)。

全部を含むファイルが2つある。 camlp4r.cma は改訂版構文、 camlp4o.cma は通常版構文だ。次のように入力してどちらかをロードしなければならない。

#load "camlp4r.cma";;

また

#load "camlp4o.cma";;

これによって Camlp4 の機構の中にいることになる。入力したものはすべて Camlp4 でパースされる。特に、改訂版構文を選択したら他の #load 文は単独のセミコロンで終端する。これは改訂版構文の通りだ。 camlp4 の文法システムを使うには、 pa_extend.cmo をロードし、 OCaml の構文木であらかじめ定義されている quotation を使うなら q_MLast.cmo をロードすること。

OCaml	Revised
let x = 23;;	value x = 23;
let x = 23 in x + 7;	let x = 23 in x + 7;

OCaml	Revised
while e1 do	while e1 do {
e2; e3; e4	e2; e3; e4
done	}

OCaml	Revised
x::y	[x::y]
[x; y; z]	[x; y; z]
x::y::z::t	[x::[y::[z::t]]]
x::y::z::t	[x; y; z :: t]

OCaml	Revised
match e with	match e with
p1 -> e1	[ p1 -> e1
\| p2 -> e2;;	\| p2 -> e2 ];
fun x -> x;;	fun [x -> x];

OCaml	Revised
fun x -> x	fun x -> x
fun {foo=(y, _)} -> y	fun {foo=(y, _)} -> y

Ocaml	Revised
fun x (y, z) -> t	fun x (y, z) -> t
fun x y (C z) -> t	fun x y -> fun [C z -> t]

OCaml	Revised
int list	list int
('a, bool) Hashtbl.t	Hashtbl.t 'a bool
type 'a foo =	type foo 'a =
'a list list;;	list (list 'a);

OCaml	Revised
type 'a foo;;	type foo 'a = 'b;
type bar;;	type bar = 'a;

OCaml	Revised
type t = A of i \| B;;	type t = [ A of i \| B ];

OCaml	Revised
type t = C of t1 * t2;;	type t = [ C of t1 and t2 ];
C (x, y);;

OCaml	Revised
x.f <- y	x.f := y

OCaml	Revised
(+)	\+
(mod)	\mod

OCaml	Revised
type t = D of (t1 * t2);;	type t = [ D of (t1 * t2) ];
D (x, y);;	d (x, y);

OCaml	Revised
type t = { mutable x : t1};;	type t = {x : mutable t1};

OCaml	Revised
a or b & c	a \|\| b && c
a \|\| b && c	a \|\| b && c

OCaml	Revised
parser	parser
[< 'Foo >] -> e	[ [: `Foo :] -> e
\| [< p = f >] -> f	\| [: p = f :] -> f
parser [< 'x >] -> x	parser [ [: `x :] -> x ]
parser [< 'x >] -> x	parser [: `x :] -> x