正規表現とオートマトンを取り上げ始めたキッカケは、Catyの型システムに正規表現型（regular expression type）を導入しよう、って話です。配列の項目パターンを正規表現で書きたいということですね。正規表現といえば、そりゃまーオートマトンでしょ。
配列以外の型には、オートマトンを使わない検証方式を使い続けることもできます。ですが、どうせやるなら、どんな型も一律にオートマトンで処理したほうがスッキリするでしょう。そこで、オートマトンを使ってJSONオブジェクト型の妥当性検証をする方法を紹介します。
内容：
準備：JSONオブジェクトのリストっぽい解釈
オートマトンは、文字列、リスト、ストリームのようなシーケンス・データの処理に向いています。JSONオブジェクトはそのままではシーケンスではありません。JSONオブエジェクトをシーケンス的に処理するために、プロパティに順序を入れます。プロパティ名の辞書式順序を考えればいいでしょう。
例えば、{"name" : "坂東トン吉", "age" : 26} というJSONオブエジェクトは、[("age" : 26), ("name" : "坂東トン吉")] というリストのように扱います。プロパティの出現順は、前もってソートされているとします。
以下では、JSONオブジェクトを、テキストストリームから読み込む状況でお話しますが、この仮定はまったく本質的ではありません。メモリ内に展開したJSONオブジェクトデータをトップダウンに舐めていく場合でも、SAXと似たようなコールバックインターフェースを使う場合でも理屈は同じです。
有向グラフと状態遷移
オートマトンを図示すればそれは有向グラフです。状態を表すノードと遷移を表す有向辺からなります。有向辺にはラベルが張り付いています。
通常、オートマトンに入力（例えば文字a）が来たき、その入力が“現状態ノードから出ている辺のラベル”と等しいならば、その辺をたどって状態遷移ができます。つまり、遷移ができる条件は input = label です。
有向辺のラベルとして、リテラルではなくてタイプを使ってみましょう。例えば、stringとか。そして、入力データがノードから出ている辺の型に所属しているならばその辺をたどって状態遷移ができる、とします。つまり、遷移ができる条件は input ∈ label です。
妥当性検証にオートマトンを使うときは、「型を有向辺のラベルにする」ことが基本です。
基本的な型に対応するオートマトン
では早速、次の4つの基本的な型に対応するオートマトンを見てみましょう。
- string
- number
- integer(minimum = 1)
- any
「この機会にマスターしようぜ、正規表現、構文図、オートマトン」と同じく、マイナス記号が開始、プラス記号が終了を表します。この図の描き方においては、開始／終了は、始状態／終状態とはちょっと違った概念です（いずれ説明する機会があると思いますが、今は気にしなくていいです）。以下では、マイナスのノードをスタートノード、プラスのノードをゴールノードと呼びます。
注意しておきますが、マイナス記号とプラス記号は、特定の状況下での「ノードの役割」を表す記号です。ノード自身の内在的性質ではありません。マイナス・プラスの記号を取り外していつでも単なる状態ノードにすることもできます。マイナス・プラス記号は帽子のようなものですね。
stringとnumberについては、スタートノードとゴールノードを結ぶただ1本の有向辺に型がラベルされているだけです。スタートノードからゴールノードにたどり着くには、ラベルである型のインスタンスデータが1個入力されなくてはなりません。そうでないと、受理は失敗します。
integerのオートマトンは意外でしょう。図の菱形のノードは述語ノードと呼び、入力されたデータに対して条件判定を行います。「isInteger = true」という述語ノードは、入力が整数であるかどうかを判定します。そのまえに、numberとラベルされた有向辺を通ってくるので、「入力は数値であり、しかも整数である」となります。直後にもうひとつ述語ノードがあり、ここで「minimum = 1」、つまり、input ≧ 1 という不等式の真偽が判定されます。numberの辺と2つの述語ノードを通り抜けるとゴールノードに到着です。
anyを見てみましょう。anyと書かれた辺は、入力が何であっても通過できます。次のSkipという四角形はデータのひとかたまりを読み飛ばします。四角の箱は、何らかの機能を実行するマシンやネストしているサブオートマトンを表すために使います。
簡単な例
まず、{"a" : X, "b" : Y} というオブジェクトのパターンを考えてみます。XとYは実際の型ではなくて、この場所に後から型が入る場所、つまり型のプレースホルダー（型変数）です。このパターンに対応するオートマトン（のテンプレート）は次のとおりです。
X, Yと書かれた箱の部分には、サブオートマトンがはめ込まれる予定です。状態遷移を表す有向辺には、マッチングする記号がラベルとして貼ってあります。記号'{'と'}'はそれぞれ、JSONオブジェクトの開始と終了です。prop/"a", prop/"b" はプロパティ名です。単に "a"と書くと、文字列データ（stringインスタンス）と誤解されるので、prop/"a" と書きました。
さて、次の図は、プレースホルダーX、Yを実際の型に置き換えたものです。Xをstring, Yをnumberとして具体化しました。どんなふうに動作するかは、見れば分かりますよね。
JSONオブジェクト型に対応するオートマトン
JSONオブジェクトを認識するオートマトンは、プロパティに対応する「プロパティ名（辺とラベル）、値の型（箱、サブオートマトン）」を数珠つなぎにしたものです。（次の図； prop/"a" と書くのを忘れて、単に"a"と書いてあるけど、… いいよね。）
プロパティが省略可能であるときは、ショートカットする有向辺が付け加わります。その実例は後で出てきます。
JSONスキーマでは、スキーマ属性で色々な制約が書けます。スカラー型に関するスキーマ属性の例は既に述べました。オブジェクト型に対するスキーマ属性では、処理のタイミングが二箇所考えられます。オブジェクト開始記号 '{' の直後とオブジェクト終了記号 '}' の直後です。
上の図のPとQは、スキーマ属性に対応する述語ノードです。どの位置に述語ノードを挿入するのが適切かはスキーマ属性により、また実装により異なります。（図のなかの、白丸の状態ノードとQを結ぶ点線はあまり意味が無いので気にしないでください。*1）
複雑な例
少し複雑な例を考えます。まずはプレースホルダーを含んだ型パターン（オートマトンのテンプレート）から。
[追記]ウッ、まじい！ "a"でも"b"でもないプロパティ名を許してますが、その他のプロパティがソート順で"a", "b"の後に来るとは限らないので、上の図のワイヤリングではダメですね。単なるワイルカードじゃなくて、(not "a" and not "b") のようなパターンとマッチさせて、プロパティ名がこのパターンにマッチしたら箱Zに遷移する、というやり方で修復できるでしょ、たぶん。[/追記]
[さらに追記]真面目に対処するとノード数が増えるし、プロパティ名の順序付けが効果的に使えないし … 姑息な対処としては； オートマトンは変えないで、このオートマトンへのプロパティ名入力が"a", "b"以外のときは、辞書式順序で後ろに来るような接頭辞をプロパティ名に付けてしまう。すると、「その他のプロパティがソート順で"a", "b"の後に来る」ことが保証されるので、このままで問題ない。せこっ。[/さらに追記]
[さらにさらに追記]「正規表現とオートマトン：JSONオブジェクトの妥当性検証への補足」で対処しました。[/さらにさらに追記]
このJSONオブジェクト型のプロパティセットは "a" : X?, "b" : Y, * : Z? で、プロパティ"a"は省略可能、"a", "b"以外のプロパティも、型がZならば出現可能です。省略可能プロパティやプロパティ名ワイルカードがあると、ショートカットやループの辺が加わります。
(maxProperties = 10) は（Catyで追加した）オブジェクト型のスキーマ属性で、プロパティの個数の上限を10個に制限しています。このスキーマ属性に対応する述語ノードが出口（ゴールノード）の直前に配置されています。'{' の直後のほうが効率的には有利そうですが、X、Y、Zの奥深くに存在するエラーを先に見つけたいときは、述語を後に配置した方がいいでしょう*2。また、ストリームからJSONオブジェクトを読み取っているときは、オブジェクトをすべて読みきらないとプロパティの個数を勘定できません。
Xにstring、Yにinteger(minimum = 1)、そしてZにanyをはめ込むと次のようです。
辺に赤で番号を振ってあります。それぞれの辺が、もとの形表現のどの部分に対応するかを示してみました。
サイズを小さくして横に並べると、次のようです。
と、まーこんな具合ですね。
