日本ソフトウェア科学会第 32 回大会 (2015 年度) 講演論文集

構造的部分型付けと解析表現文法によるスキーマ言語
山口 真弥

倉光 君郎

スキーマによる検証は，Web 上の半構造化データの信頼性を高める重要な技術である．しかし，JSON データを扱う多くのアプリケーションではスキーマ検証はほとんど活用されていない．本論文では，よりアプリケーション開発者が利用しやすいスキーマとして，構造的部分型付けと解析表現文法 (PEG) による JSON 向けスキーマ言語
Celery を提案する．構造的部分型付けは，スクリプト言語など多くの動的言語で暗黙的に用いられており，JSONデータの柔軟さと相性が良いと考えられる．PEG は、正規表現を上回る表現力があり，統合的な文字列パターンの検証が可能になる．また，PEG を用いる利点は，スキーマ構造を PEG に変換することができ、再帰降下構文解析法でスキーマ検証自体を行える．本論文では，Celery の基本的な特徴と，PEG によるスキーマ検証アルゴリズムについて述べる．

Schema validation is an integral part of reliable semi-structured data on the Web. However, the schema
validation in many applications that handle JSON data is rarely taken advantage. In this paper, we present
a JSON schema language:Celery that is based on Parsing Expression Grammar (PEG) and structural subtyping for developer’s usability. Structural subtyping has been used implicitly in many dynamic languages,
such as scripting language, so we consider that there is a compatibility with JSON. PEG has expressive
power that beyond the regular expression and allows validation for integrated string patterns. It is also
advantage of adapting PEG that we can convert schema structures to PEGs and validate by recursive descent parsing. In this paper, we present the principles of Celery’s design and PEG-based schema validation
algorithm.

めとした動的言語ではダックタイピングによってオブ1 はじめにジェクトを参照するため，プロパティの存在や，デースキーマによる検証は，Web 上の半構造化データタの型が保証されないという問題がある．の信頼性を高める重要な技術である．Web アプリケー

また，効率的なスキーマ検証器の実装が簡単でない

ションはスキーマ検証によって，入力，あるいは出力ことも，スキーマが活用されない一因と言える．一般

データが期待される内容を持っていることを保証する的なスキーマ検証器は木オートマトン理論に基づいことができる．ている．すなわち，スキーマ検証を実行する際，入力Web アプリケーションでのデータ交換に広く用いサイズに比例して木を構築するためのメモリを必要られているフォーマットの一つとして JSON がある．とするため，効率的な検証器の実装にはコストが掛かJSON には標準化されたスキーマ言語が存在しないる．理論上ではストリーミングによる検証アルゴリ

ため，アプリケーションの開発者はスキーマ検証を

ズムは研究されているが [4] [6]，依然として既存の実活用しない場合が多い．しかし，JavaScript をはじ

装のほとんどは木オートマトンを利用しているため，

A Schema Language Based on Structural Subtyping
and PEGShinya Yamaguchi, 横浜国立大学, Yokohama National
University.
Kimio Kuramitsu, 横浜国立大学, Yokohama National
University.

データのサイズが大きくなるほど性能が劣化してしまうという欠点を持つ．
本論文では，構造的部分型付けと解析表現文法による JSON 向けスキーマ言語 Celery を提案する．構造的部分型付けはスクリプト言語などの多くの動的型付け言語で暗黙的に用いられている型付けの形式値として undefined が返される．動的な言語におけであり，柔軟性のある JSON データとの相性が良い

るこのような柔軟な性質はダックタイピングと呼ばれと考えられる．また，Celery のスキーマ検証は解析ている．ダックタイピングによって，プログラマは型表現文法 (PEG) に基づいている．スキーマ制約を定義に縛られないコーディングが許される．一方で，PEG に変換することによって，再帰降下構文解析法

オブジェクトプロパティの存在そのものやデータの型でスキーマ検証そのものを実行できる．本論文では，は保証されない．これは，Web 上でのデータ交換をCelery の基本的な特徴と PEG によるスキーマ検証考える上で重大な問題になる．本論文では，柔軟性をアルゴリズムについて述べる．

保ちつつ，型安全にオブジェクトの交換が行われることを目指す．

2 動機
スキーマの主な役割は，データベース設計の仕様を2. 2 構造的部分型付け表すことである．Celery は，開発者にとっての扱い構造的部分型付けは，部分型の関係が構造によってやすさを重視して設計されている．本節では，Celery決定される型付けの形式であり，OCaml や Scala のの設計動機を，例を交えて説明する．

ような強力な静的型付けプログラミング言語で採用されている． [9] また，多くの動的言語において暗黙的

2. 1 JSON と JavaScriptに用いられていることが知られている．Java や C#JSON(JavaScript Object Notation, [1]) は，Ecmaに採用されている名前的部分型付けとは異なる．

International によって標準化されたデータフォーマットである．その名前が示す通り，JSON は，JavaScriptのオブジェクトリテラルとして用いられている．また，形式がシンプルであり，可読性が高いため，多くのプログラミング言語やデータベースシステムにおいてデータ交換形式として採用されている．
以下に JSON オブジェクトの簡単な例を示す．
book = {"title": "Paper Towns","year": 2009}class T1 {x, y, z}class T2 {x, y}class T3 extends T2 {z}例として，T 1, T 2, T 3 という 3 つの異なる型が定義されている場合を考える．上記の例はそれらの型をJava に似た記法を用いて定義したものである．キー
ワード extends は，T3 が T2 の全てのプロパティを継承することを明示していることに注意されたい．名
前的型付けと構造的型付けの差異は型の等価性と部分型の関係性にある．T1 と T3 は名前的型付けにおいて，型名が一致しないため，全く異なる型として扱{} はオブジェクトのコンストラクタであり，そのプロパティはコロン記号 ( : ) で区切られたキーと値の組み合わせによって表される．

JavaScript は動的型付け言語であるため，JSON オブジェクトには型が付けられていない．すなわち，オブジェクトの構造を定義するための記法が用意されていない．プログラマは book というオブジェクト中のtitle という値を，book.title や book["title"]と記述することで自由に参照することができる．nameの型は実行時に動的に決定され，特定のプロパティがオブジェクト中に存在しなかった場合には，未定義のわれる．一方で，構造的型付けにおいては 2 つの型は全く同じプロパティを持つため，T1 と T3 は同じ型として扱われる．同様に，名前的型付けでは継承関係が明記されていないため T1 は T2 の部分型ではないが，構造的型付けでは T1 は T2 の部分型であるとみなされる．このように，構造的部分型付けは柔軟に型を判別することが可能である．特に半構造化データ
では様々なデータを追記可能であるため，構造的部分型付けとの相性が良いと考えられる．
注意しなければならない重要な点は，同名のプロパティである T1 の x と，T3 の x がそれぞれ異なる内容を持っていた場合である．構造的型付けではこれらの不一致を検知することができない．一方，名前的{" title " : " Go Set a Watchman " ," author " : " Harper Lee " ," year " : 2 0 0 9" rate ": 4.53" related " : [{" title " : " All the Light " ," author " : " Anthony Doerr "},{" title " : " The Martian "" author " : " Andy Weir "}]型付けでは，型名は名前空間の接頭語として作用するため，2 つの同名プロパティを区別することができる．この点で，名前的型付けは，より厳格なスキーマ検証を提供するといえる．しかしながら，この問題は他のプロパティが 2 つのスキーマ間で全て一致している場合でのみ発生する．現実にそのようなケースが発生することは稀であり，問題にはならない．
以上より，構造的部分型付けはスキーマ検証に適しており，十分に実用的な型付け形式であると考えら}れる．

3 スキーマ言語 Celery

図2

JSON の例

Celery はデータ構造を表現するためのスキーマ言語である．本節では，Celery を形式的に定義し，例を挙げて Celery の基本的な特徴を説明する．

struct によって宣言されたオブジェクト型のプロパ
ティは [プロパティ名]:[型] という形式で表され，順不同に扱われる．プロパティには主キー制約が存在し，3. 1 型定義同名同型の組み合わせが重複することは認められない．

Celery で用いられる型 T は以下の形式で定義さまた，型宣言では，Book 型のプロパティ related のように，外部のオブジェクト型 RelatedBook を参照れる．

することが可能である．このようにオブジェクトごとT:=X
booleanint
float
stringanyT[]enum { v* }
図1

型名
真偽値型
整数型
浮動小数点数型
文字列型
すべての JSON 形式
配列型
列挙型

Celery 形式定義にスキーマを定義することによって，型定義を繰り返し書く必要がなくなり，可読性が向上する．

Celery のスキーマ検証器は，構造的部分型付けによって検証を行う．図 3 のスキーマにおいて rate は未定義のプロパティであるが，図 2 のオブジェクトは Book 型の全ての要素を持っている．そのため，スキーマ検証器は図 2 のオブジェクトを Book 型の部分型として受理する．

ここで，型名 X は以下の形式で定義されたオブジェ
クト型の名前を表す．
structX = ( n: T )*4 解析表現文法
解 析 表 現 文 法 (Parsing Expression Grammar,PEG, [3]) は，様々なプログラミング言語のコミュ
3. 2 構文

ニティから注目されている，実用的な文法基盤である．

図 2 は，JSON データの一例であり，プロパティのPEG の表現力と構文解析のアルゴリズムは，データ一つ（related）がネストした構造を持っている．図のスキーマ検証に適していると考えられる．本節では

3 はこの例に対応する Celery のスキーマ定義を表し

PEG の性質を端的に説明し，スキーマ検証に対するている．

実用性について述べる．

p2 が連接しているかどうか試し，もし失敗すれば開struct Book =title : string
author : string
year : int
related : RelatedBook []始位置までバックトラックする．p1 /p2 は最初に p1を試し，もし p1 が失敗した時にのみ p2 を試す．表
現 &p は p を試し，マッチしても文字列を消費しない．一方で表現 !p は p とのマッチングが失敗した時

struct RelatedBook =title : string
author : stringに成功し，p が成功した時は失敗する．
例として JSON の構文に対応する PEG 文法を図4 に示す．文法は読みやすさのため単純化されている
図3

Celery の例

が，14 の文法規則によって JSON の構文を定義することができており，シンプルかつ強力であると言え

表1

PEG の演算子る．PEG では字句解析を用いないため，文法には字PEG

TypeDescription句的な要素と構文的な要素の両方を統合して定義す’’

Primary

Matches textることに注意されたい．

[]

Primary

Matches character class.

Primary

Any character

4. 2 構文解析アルゴリズム

A

Primary

Non-terminal application

スキーマ検証において，処理が高速であることと，(p)PrimaryGrouping

実装しやすいことは重要な要素である．通常，PEG

p?

Unary suﬃx

Optionによる構文解析器は，入力長に対する空間計算量が一p∗

Unary suﬃx

Zero-or-more repetitions

定であるトップダウン型再帰下降構文解析アルゴリズp+Unary suﬃx

One-or-more repetitions

ムによって実装される．また，多くのプログラミング&p

Unary suﬃxAnd-predicate

言語において，再帰下降構文解析器の実装は単純か!p

Unary suﬃx

Negation

つ簡単である．既存のパーサジェネレータの存在が，

p1 p2

BinarySequencing

その実装のしやすさを裏付けている．

p1 /p2BinaryPrioritized Choice

PEG の有名な欠点として，バックトラックによる最悪指数時間計算量が挙げられる． [2] しかしながら，

4. 1 文法，表現，演算子

JSON の構文規則は非常に限定されているため，1 シ

解析表現文法 G は 4 つの要素からなる組 G =ンボル先読みすることによってバックトラックを回避(N, Σ, P, ps ) によって形式的に表される．N は非終することが可能である．つまり，PEG による JSON

端記号の有限集合，Σ は終端文字の有限集合，P はデータの構文解析は線形時間で行われると考えられ表現の有限集合，ps は開始記号を表す．ここで，我々る．加えて，PEG ではアルゴリズムレベルでの最適は，変数 a, b, c を終端記号，A, B, C を非終端記号，化が多く存在し，それらを適用することによって更なp を解析表現として扱う．各文法規則は，バッカスナる高速化が期待できる．これらの PEG の性質が，スウア記法に似た形式 A = p で表される．これは非終キーマ検証器の実装において実用性をもたらすもの

端記号 A から解析表現 p へのマッピングである．と考える．

表 1 は，PEG の演算子とその説明をまとめたものである．文字列 ′ abc′ は同一の入力にマッチし，[abc]5 スキーマ検証のための PEG 変換は a, b, c のいずれか一つにマッチする．. 演算子は任Celery のスキーマ検証は，PEG ベースの再帰下意の 1 文字とマッチする．p?，p∗，p+ 表現は，最長降構文解析器によって行われる．すなわち，Celery位置まで貪欲にマッチすることを除けば，一般的な正で記述された構造的な制約を，JSON の構文を表す規表現と同様に振る舞う．p1 p2 は 2 つの表現 p1 とPEG へと変換して実行される．本節では Celery をFileValue= S* Value S* !.
= String / Number / Object / Array/ Null / True / False= ’\{’ Member (’,’ Member )* ’\}’= String ’:’ Value= ’[’ Value (’,’ Value )* ’]’= ’"’ (!’"’ .)* ’"’ S*= ’true’ S*= ’false S*= ’null’ S*= ’-’? INT (FRAC EXP? / ’’) S*= ’0’ / [1-9] [0-9]*= ’.’ [0-9]+= [Ee] ( ’-’ / ’+’)? [0-9]+= [ \t\r\n]ObjectMemberArrayStringTrueFalseNullNumberINTFRACEXPS• PX = ′ {′ ( Px1 / Px2 / ... / Pxn / PANY ) ∗ ′ }′• Pxn = ′ ”xn ”′ ′ :′ τ (xn )構文規則 PX 内の最後の選択肢である PANY は構造的部分型付けを許すための表現である．Pxn は，オブジェクト型 X で定義されている n 番目のプロパティを表している．オブジェクト型のプロパティは順不同であるため，このような変換は正確ではない．加えて，純粋な PEG では，いわゆる主キー制約を表現することができないため，実際には PEG の拡張構文を利用する必要がある．ただし，基本的な変換の形式は変化しないため，本節ではこのまま議論を進める．拡張構文による実装については後述する．

図4

JSON の構文を表す PEG の文法

構文規則 Pxn 内で定義されている τ (x) は，オブジェクト型のプロパティx を入力とし，対応する PEG= ’{’ PMEMBER ( ’,’ PMEMBER )* ’}’= PSTRING ’:’ PANY
= ’[’ PANY ( ’,’ PANY )* ’]’= ’”’ ( !’”’ . )* ’”’= ’true’ / ’false’= ’0’ / [1-9] [0-9]*= PINT ’.’ [0-9]+= POBJECT / PARRAY / PBOOLEAN/ PFLOAT / PINT / PSTRINGPOBJECTPMEMBERPARRAYPSTRINGPBOOLEANPINTPFLOAT
PANY
図5

JSON 構文を表現する構文規則を出力する変換関数である．図 1 で定義した Celeryの型は以下のように変換される．

• τ (X) = PX
• τ (boolean) = PBOOLEAN• τ (int) = PINT
• τ (float) = PFLOAT• τ (string) = PSTRING• τ (any) = PANY• τ (T[]) = ′ [′ τ (T) (′ ,′ τ (T) ) ∗ ′ ]′PEG へと変換するアルゴリズムと，検証器の実装に• τ (enum {v1 , ..., vn }) = ′ ”v1 ”′ / ... /′ ”vn ”′

ついて説明する．
変換アルゴリズムの説明では，JSON におけるオ

5. 2 変換器の実装

ブジェクトやプロパティの名前 n に対応する PEG の前節で述べたように，純粋な PEG では順不同な構文規則を Pn という形式で表す．また，JSON の構シーケンスや主キー制約を直接表現することができな文を表すための基本的な規則を図 5 に予め定義してい．それらのスキーマ制約を表現するためには，PEGおく．これらの規則は Celery から PEG への変換に処理系に実装されているセマンティックアクションやおいて共通して用いられる．

拡張構文を用いる必要がある．したがって，変換器の実装に際して，強力な表現力を持つ PEG 処理系を選5. 1 変換アルゴリズム択することは重要である．

まず，Celery で定義されたオブジェクト型の変換

本論文では，PEG パーサライブラリの一つであるから説明していく．なお，変換後の構文規則は簡略化

Nez [7] を利用して Celery-to-PEG 変換器の実装を行されていることに注意されたい．

う．Nez は文法変換器やパーサ生成器のためのフレー

struct で宣言されたオブジェクト型 X に対応するムワークを提供しており，我々の変換器の実装もそのPEG の構文規則を PX とすると，X は以下のように変一部として統合されている．つまり，Celery ファイ換される．

ルを Nez の文法定義として直接読み込み，Nez に備わっているインタプリタ型のパーサでスキーマ検証を

表2

PEG
<uniq e><set x y e>

XDuce は純粋な正規表現を用いているため，順不同

Nez 拡張構文なシーケンスや主キー制約をスキーマ自体に定義する

Description
構文規則 e が 1 回のみ受理される
構文規則 e で受理された文字列がシンボル x と y を含むことはできない．その他にパターンマッチやタグの検査，部分木の抽出，動的なスキーマ検証など，XMLを処理する様々な機能を提供している．

行うことができるため，個別のスキーマ検証器を用意する必要がないという利点がある．また，Nez の文

7 結論法には，シンボルテーブルや AST の生成を可能にす

本論文では，JSON 向けスキーマ言語 Celery のる PEG の拡張構文が存在するためスキーマ制約の変特徴と PEG ベースのスキーマ検証アルゴリズムに換に適している．

ついて述べた．Celery はユーザにとって分かりやす拡張構文を用いた変換の簡単な例として，オブジェ

くシンプルな構文でスキーマを表現することができ

クト型 X が int 型のプロパティx1 と string 型のプる．また，構造的部分型付けを採用することによって，ロパティx2 を持つ場合を考える．

JSON データを柔軟に検証する能力を持つ．さらに，Celery を拡張された PEG へと変換し，再帰下降構
文解析器でスキーマ検証を実行することで，PEG のstruct X = x1 : int

強力な解析能力を得るだけでなく，スキーマ検証器のx2 : string

実装コストを抑えられることを示した．
このとき，Nez の文法への変換は以下のように表参 考 文 献

される．
′ ′

• PX = { < set Px1 Px2 ( Px1 / Px2 / PANY )∗ >′′ ′}′ ′ ′• Px1 = < uniq ”x1 ” : PINT >• Px2 = < uniq ′ ”x2 ”′ ′ :′ PSTRING >5. 1 節で定義した変換との差異は，拡張構文である
set, uniq が追加されたことである．今回の実装で用いる拡張構文とその意味を表 5. 2 にまとめる．
構 文 規 則 PX に お け る 表 現 set 演 算 子 は ，( Px1 / Px2 / PANY )∗ によって受理される入力が，シンボル Px1 と Px2 を含んでいれば成功する．また，Px1 ，Px2 では，uniq 演算子によってそれぞれが 1 回のみ受理される．結果として，この 2 つの拡張構文によって，順不同なシーケンスと主キー制約を PEGで表現することが可能になる．

6 関連研究JSON と比較して，XML ではスキーマ検証や処理系の様々な研究が行われてきた．静的型付けプログラ
ミング言語 XDuce [5] は型システムと木オートマト
ン理論 [8] に基づいている実用的な XML 処理系の一つである．XDuce では，XML データに対応するスキーマを正規表現型という形式で表現する．しかし，[1] ECMAInternational: The JSON Data Interchange Format. http://www.ecma-international.
org/publications/standards/Ecma-404.htm.
[2] Ford, B.: Packrat Parsing:: Simple, Powerful,Lazy, Linear Time, Functional Pearl, SIGPLAN
Not., Vol. 37, No. 9(2002), pp. 36–47.
[3] Ford, B.: Parsing Expression Grammars: A
Recognition-based Syntactic Foundation, SIGPLAN Not., Vol. 39, No. 1(2004), pp. 111–122.
[4] Green, T. J., Gupta, A., Miklau, G., Onizuka,M., and Suciu, D.: Processing XML Streams
with Deterministic Automata and Stream Indexes,
ACM Trans. Database Syst., Vol. 29, No. 4(2004),
pp. 752–788.
[5] Hosoya, H. and Pierce, B. C.: XDuce: A Statically Typed XML Processing Language, ACM
Trans. Internet Technol., Vol. 3, No. 2(2003),
pp. 117–148.
[6] Konrad, C. and Magniez, F.: Validating XML
Documents in the Streaming Model with External Memory, ACM Trans. Database Syst., Vol. 38,No. 4(2013), pp. 27:1–27:36.
[7] Kuramitsu, K.: Nez Parsing Library. http://github.com/nez-peg/nez.
[8] Murata, M., Lee, D., Mani, M., and Kawaguchi,
K.: Taxonomy of XML Schema Languages Using
Formal Language Theory, ACM Trans. Internet
Technol., Vol. 5, No. 4(2005), pp. 660–704.
[9] Pierce, B. C.: Types and Programming Languages, MIT Press, 2002.