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

ドメイン特化言語処理系実装支援ライブラリのメタプ
ログラミングによる設計と実装
塩田 雅人

岩崎 英哉

特定用途の扱いに特化したドメイン特化言語 (以下，DSL) は，C や Java といった汎用プログラミング言語に比べ，その特定用途において生産性や品質を向上させる．DSL の処理系を実装するための従来の手法では，Yacc 等で生成した構文解析器を用いて抽象構文木を生成し，それを解釈実行したり，あるいはさらに中間コードに変換して実行することが多い．しかし，この手法では DSL の処理系の構築の前に Yacc 等による処理があるため構築手順が複雑になるのに加え，文法と処理系を記述する言語が別となるため処理系の拡張が困難である．この問題点を解決するために，本研究では D 言語のメタプログラミングによって，与えられた DSL の文法や命令の定義を基にして構文解析器と仮想マシンをそれぞれ生成するシステムを設計し実装した．メタプログラミングで実装することで，処理系の構築はコンパイラのみで行え，拡張も自然かつ容易に行うことが可能となる．

仮想機械を生成するための DSL(vmIDL [2] 等) も1 はじめに存在し，構文解析器を生成する Yacc [7] も DSL の一

一般的な用途に用いられる C++ や Java といっ種とみなすことができる．構文解析器や仮想機械を記た汎用プログラミング言語に比べ，特定領域の処理述した DSL を C++ 等の処理系の実装を行うプログに特化したプログラミング言語であるドメイン特化

ラム言語 (以下，ホスト言語) に変換し，他のホスト言語 ( Domain - Specific Language，DSL ) は，ソ言語のプログラムと一緒にコンパイルを行うことでフトウェア開発の生産性を向上させ，成果物であるDSL 処理系を生成する．

ソフトウェアの品質を高めることができる．DSL の本研究では，従来ではホスト言語とは別の言語で例として，文字列処理を記述する sed，データベース行っていた部分をホスト言語のメタプログラミングをへのクエリを記述する SQL，XML 変換を記述する用いて行う．構文解析器によって生成した抽象構文木

XQuery 等が挙げられる．

を仮想機械命令列にコンパイルし，その仮想機械命令DSL を使用したソフトウェア開発を行うためには，DSL の処理系を実装する必要がある．DSL 処理系の列を仮想機械によって実行するような DSL 処理系を対象とする．

実装では，まず DSL プログラムの構文解析を行い，本論文の構成は以下の通りである．2 章では簡単な抽象構文木を生成する．生成した抽象構文木を実行す

DSL の例を通して 既存の DSL 処理系の実装手法をるには，直接解釈実行を行ったり，仮想機械の命令や説明する．3 章では本研究の処理系実装のためのライ機械語に変換し実行を行う．しかし，構文解析器や仮ブラリの設計と実装について，実装例を通して説明す

想機械の実装は面倒である．

る．4 章では実際に本研究を使用して処理系を実装す

Design and implementation by metaprogramming of
support library for DSL implementation
Masato Shioda, Hideya Iwasaki, 電 気 通 信 大 学 大 学
院 情 報 理 工 学 研 究 科, Graduate School of Informatics and Engineering, The University of ElectroCommunications.

る方法を説明する．5 章では本研究と関連しているライブラリ，研究について説明する．最後に 6 章で本論文をまとめ，今後の課題を示す．

ここで，二次元平面上の点を表すユーザ定義型

2 DSL の実装例

Point 構造体について，同様の DSL を使用すること

ここで，C# で使用されているコンテナの要素を考える．

を列挙するための DSL である統合言語クエリ [4](Language-Integrated Query，LINQ) に似た DSLの処理系を実装することを考える．DSL 処理系は，抽象構文木を仮想機械の命令列に変換し，仮想機械で実行する．
ホスト言語は D 言語 [1] を使用する．D 言語は C
言語の後継言語の 1 つであるオブジェクト指向プロ
グラミングや関数型プログラミング等をサポートするマルチパラダイム言語で，関数のコンパイル時実行やテンプレート等の強力なメタプログラミング機構を備えている．また，C 言語で実装された関数を呼び出すこともできる．
実装する DSL の文法は以下の様になる．

struct Point{
int x, y;}Point[] points =[Point(0, 0),Point( 3,4),Point(2, 8),Point(-2,4),
Point(4,-5),Point( 5,0)];while(true){write(">");
string s = readln();if(s.length == 0) break;Point[] result;foreach(Point p; runQuery(s, points)){result ~= p;}writeln("result:",result);}

以下に実行例を示す．
<query> ::= "from" identifier <where><where> ::="where" <condExp>| ε<condExp> ::= D言語の条件式>from p where p.x*p.x + p.y*p.y <= 5*5
result:[Point(0, 0), Point(3, 4), Point(-2, 4),Point(5, 0)]

この DSL は以下のように，配列の要素を列挙する

装した時には存在していなかったため，処理系の実装際に使用する．

時にその型について考慮することができない．また，

このようなユーザ定義型は，先に DSL 処理系を実構文解析器や仮想機械を記述する言語とホスト言語
int[] v = [2,4,8,10,23,17,20,9,12,25];
string s;
write(">");
while((s = readln()).length > 0){
int[] result;foreach(int i; runQuery(s, v)){
result ~= i;}write("result:",result,"\n>");}が異なっているため，ホスト言語の型情報を構文解析以下に実行例を示す．

いた構文解析器と仮想機械を，ホスト言語のメタプロ器や仮想機械の生成で使用することができず，上記のようなユーザ定義型に対応するためには，DSL 処理系にユーザ定義型に関する全ての処理を登録し，処理系が必要になった時点で登録された処理を実行する等というような面倒な処理が必要となってしまう．
本研究では，ホスト言語とは別の言語で実装されてグラミングを用いて行うことで，ホスト言語の型情>from x
result:[2, 4, 8, 10, 23, 17, 20, 9, 12, 25]>from x where x%2 == 0
result:[2, 4, 8, 10, 20, 12]>from x where x<=5result:[2, 4]>from x where 5<=x && x<=10result:[8, 10, 9]報などを使用することを可能とし，この問題を解決する．

3 設計と実装
本研究が提供するライブラリは，メタプログラミン
グによって構文解析器と仮想機械の両方を生成する．
構文解析器，仮想機械のどちらもホスト言語のメタプ

ログラミングによって構成を行うため，ホスト言語のメタプログラミングによって構文解析器や仮想機械に変更を加えることが可能となる．

3. 1 方針
DSL プログラムの実行を行っている runQuery 関

Rule!("exp",
Expression!(expAct,nonterm("exp"),"+",nonterm("num"))),
Rule!("num",
Expression!(numAct, int)

数では，渡された DSL プログラムの構文解析を行っ

このとき，[Token(1) , Token("+") , Token(2)て抽象構文木を生成し，仮想機械命令列にコンパイル, Token("+") , Token(3)] というトークン列を解して仮想機械で実行している．ここで，メタプログラ

析した場合，対応するアクション関数は次のように呼ミングによって runQuery 関数の引数として渡されび出される．

た配列の型情報を取得することができる．そのため，DSL 処理系を実装した時に考慮されていないユーザ定義型の配列がこの関数に渡されたとしても，そのユーザ定義型の型情報を知ることが可能となる．
そこで，この型情報を使用して，仮想機械にそのexpAct(expAct(numAct(Token(1)),
Token("+"),
numAct(Token(2))),
Token("+"),
num(ActToken(3)))

型の操作に必要な処理を命令として追加する．Point
構造体であれば，x メンバ変数にアクセスするため

3. 2. 1 構文解析器の定義の getMember x 命令等を仮想機械に追加することで，構文解析器の生成には IntSyntax テンプレートを仮想機械で実装する時に存在せず，考慮することがで用いる．引数に，開始記号の非終端記号，アクションきなかった Point 構造体もこの仮想機械で扱うこと関数の戻り値の型，構文規則をとる．構文規則は Ruleが可能となる．

テンプレートと Expression テンプレートによって記述する．

3. 2 構文解析器
構文解析器を生成するため，解析する構文の構文規則とその構文規則が適用されたときに呼び出される関数 (以下，アクション関数) をテンプレートで指定する．アクション関数には，引数として構文規則を適用する記号列が渡される．非終端記号はその記号を得るために構文規則を適用した際に呼び出したアクション関数の戻り値を引数として渡す．
例として，次のような単純な構文規則を考える．

<exp> ::= <exp> "+" <num><num> ::= int

alias IntSyntax!(
nonterm("query"), SyntaxTree,Rule!("query",
Expression!(query,"from",string,nonterm("where"))),
Rule!("where",
Expression!(where,"where",nonterm("condExp")),Expression!(none)),...
Rule!("AndAndExp",
Expression!(binope,nonterm("AndAndExp"),"&&",
nonterm("OrExp")),...
) querySyntax;

こ れ ら の 構 文 規 則 の ア ク ション 関 数 を そ れ ぞ れ

構文規則の記述では，nonterm 関数に名前を渡し，expAct，numAct としたとき，構文規則は以下の様に非終端記号として扱う．終端記号は D 言語の型，テ定義する．

ンプレートで使用できる値を使用することができる．
字句解析器から読みこんだトークンが終端記号として扱われている値であった場合は値が，そうでない場合はその値の型を終端記号として扱う．与えられた構文規則より，LALR(1) の構文解析表を生成し，構文呼び出しを生成ている．例えば，両辺が int 型の==解析表を用いて構文解析を行い，非終端記号が還元さ演算子の二項演算子の場合，"==int"という仮想機械れる度にアクション関数を実行し，開始記号が還元さ命令の呼び出しを生成している．このとき，仮想機械れた時点でアクション関数の戻り値を結果とする．に指定された命令が存在しない場合は実行時エラー

3. 2. 2 抽象構文木の生成と命令列生成となる．

仮想機械の命令列を生成するためには，仮想機械が用意した命令列生成用のインターフェースを継承し実装したクラスのインスタンスオブジェクトを使用する．命令列生成用のインターフェースは命令列生成を行うためのオブジェクトを引数として渡され，そのオブジェクトに対して実行したい命令等を指定することで命令列が生成される．命令を指定する際には，その命令の引数の数だけ命令が要求している引数と同じ型を返す命令を生成する命令列生成オブジェクト，その命令の分岐先の数だけ命令が返す型と同じ型をclass BinOpe : SyntaxTree {SyntaxTree l, r;
string ope;
string type;
public this(string ope,SyntaxTree l, SyntaxTree r){
this.ope = ope;
this.l = l; this.r = r;}void compile(Context c){c.callOpe(ope~type, l, r);}}

返す命令を生成する命令列生成オブジェクトが必要となる．分岐先として指定された命令列はは，その命令が実行された後にどれか 1 つ実行されるか，いずれ3. 3 仮想機械も実行されない．

仮想機械を生成するには，仮想機械命令をテンプ

アクション関数は抽象構文木を表すオブジェクトをレートで指定する．仮想機械命令は，命令の名前，命生成し，それを返す関数とした．字句解析器による令を実装した関数，命令が別の命令へ処理を分岐す

トークンを表す Token 型は，期待されている型を指る必要がある場合は分岐先の数，命令の戻り値の型，定し，トークンが保持している値の型と一致した場合命令の引数の型を渡す．テンプレートはこれを基にしに限りその値を取り出すことができる．二項演算子をて仮想機械を生成し，その仮想機械で実行できる命令処理するアクション関数では，中置演算子の文字列を列を生成するためのライブラリも生成する．このラトークンより取り出し，二項演算子の抽象構文木を表

イブラリは，定義した仮想機械命令の実行以外にも，すクラスのインスタンスオブジェクトを生成するコン

即値読み込み，変数宣言と変数アクセス，関数の定義

ストラクタへの引数として使用している．と呼び出し，ループの定義を行うことができる．

3. 3. 1 仮想機械命令の定義
auto binope(SyntaxTree l,Token op,SyntaxTree r){return new BinOpe(op.peek!string,l,r);}例として，int 型の数値を同値比較する命令を定義する．この命令は int 型の引数を 2 個受け取り，bool 型を結果として返す．この関数の第一引数である context とは仮想機械の状態を操作するためのオブジェクトであり，setResult 関数を呼び出すこと

抽象構文木を表すオブジェクトは，実際に仮想機械命令列を生成する場合は compile メソッドを引数に仮想機械命令列を生成するために操作するオブジェク
トを引数として与えて呼び出される．
この二項演算子の抽象構文木を表すオブジェクト
は，演算子と型の文字列を連結した仮想機械命令ので結果を指定している．第二，第三引数はこの命令への引数である．

auto opEqualsInt(alias context,alias l, alias r)(){return context.setResult(l==r));}alias Machine!(
DefOpe!("==int", opEqualsInt, 0,bool, ArgsType!(int,int)),
DefOpe!("&&bool", opAndAnd, 1,bool, ArgsType!(bool)),...

次の例として短絡評価を伴った論理式の論理積を行う命令を定義する．この命令は C 言語の&&演算子と) QueryMachine;

同様に，途中で偽となった場合は残りの式の評価をせ生成した仮想機械はスタックマシンとして実装され，ずに直ちに偽を結果として返す．つまり，この命令は各命令の引数はスタックから取得され，各命令の結果同値比較命令と異なり，処理の分岐が発生する可能性はスタックに保持される．

がある．同値比較命令と同様に第一引数は仮想機械の状態を変更するためのオブジェクト，第二引数は命

4 使用例

令への引数である bool 型の値である．第三引数はこ

構文解析器を使用して文字列を解析するためには，の命令から分岐を行う分岐先を表している．この命

parse 関数のテンプレート引数に構文規則を渡し，関令が分岐を行う場合は分岐先を表す引数を関数の戻数の引数に字句解析器を使用して字句解析した文字り値として返す．分岐先に処理を分岐しない場合は，列を渡す．字句解析は DSL 実装者が実装する必要がこの命令内で結果を指定する必要がある．

ある．構文解析した結果は，開始記号を還元したとき

auto opAndAnd(alias context,alias l, alias next)(){if(!l) {return context.setResult(false);}else{
return next;}}に実行したアクション関数の結果となる．
仮想機械命令を生成し，仮想機械で実行するためには，仮想機械で定義されている SyntaxTree イン
ターフェースを継承したクラスのインスタンスを仮
想機械のコンストラクタに引数で与える．これで，引数で与えたオブジェクトが生成する仮想機械命令列を備えた仮想機械を用意することができる．あとは，3. 3. 2 仮想機械の定義

この仮想機械の run 関数を呼び出せば仮想機械に設定義した仮想機械命令を用いて仮想機械を定義する

定された仮想機械命令列を実行する．その際に，仮想には，Machine テンプレートを使用する．Machine テ

機械に引数を与えることもできる．結果は仮想機械命

ンプレートの引数に，実行する仮想機械命令を DefOpe令列を実行した結果となる．

テンプレートを使用して以下のようにして渡す．

runQuery 関数の実装は以下の様になる．このとき，tokenize 関数は文字列を字句解析する関数，

DefOpe!("命令名", 関数, 分岐先数,戻り値型, ArgsType!(引数型))

makeOpes テンプレートは，引数で渡された型を操作するための仮想機械命令を生成するためのテンプレー

上記で定義した OpEqualsInt 関数や opAndAnd 関数

トであり，==int 命令や &&bool 命令，getMember xを用いた命令等を定義した仮想機械を QueryMachine

命令等が生成される．runQuery 関数は，Point 構造という名前で定義すると以下の様になる．

体を含め，任意のユーザ定義型を扱える処理系となる．

パイル時にテンプレートを生成しており，本研究とは対象が異なる．
auto runQuery(T)(string src, T[] array){// 型Tを操作可能な仮想機械の生成
alias Machine!(makeOpes!T) QueryMachine;// 構文解析し，抽象構文木を生成する
QuerySyntaxTree ast =parse!(querySyntax)(tokenize(src));// 抽象構文木を仮想機械命令列にしたQueryMachine machine = QueryMachine(ast);

6 おわりに
本研究ではホスト言語と DSL 処理系の実装を密に連携させるために，処理系の実装にホスト言語のメタプログラミングを使用する手法を提案し，D 言語を用いて実装を行った．処理系の生成を D 言語のメタプログラミングを用いて変更することが可能となり，// 仮想機械を実行し，結果を返す
return machine.run(array);

DSL 処理系の実装時に考慮されていないユーザ定義型も扱うことができる処理系を実装することができ}るようになった．

5 関連研究本研究で実装した構文解析器は，D 言語プログラ仮想機械を生成する DSL として，vmIDL が挙げムのコンパイルを行っている時に実行し，文字列定数られる．vmIDL は入力された仮想機械の命令の定義に構文解析を行うことが可能となっている．そこで，から仮想機械を生成する DSL で，生成する仮想機械コンパイル時に構文解析を行い，得られた抽象構文はスタックマシンであり，仮想機械の各命令は，ス木を用いて仮想機械命令列を生成するのではなく，仮タックや仮想機械の状態への操作を行う C 言語の文

想機械命令の実装に使用した関数を直接呼び出すよとして記述する．入力された仮想機械命令の定義を基うなテンプレート関数を生成することで，その関数に，それらの命令を実行することができる仮想機械は D 言語コンパイラによって機械語にコンパイルすの C 言語プログラムを生成する．ホスト言語と別のることが可能となる．これによって，実行時に DSL言語で仮想機械を記述する必要があるので，本研究のプログラムを与えられるが実行時にオーバーヘッドがように型情報を使用して仮想機械を生成することは発生してしまう仮想機械での実行と，コンパイル時にできない．

DSL プログラムが決定している必要があるが効率的

C++ で一般的に使用されている Boost ライブラに動作するネイティブ実行の 2 種類の処理系を一度リにも，テンプレートを使用して構文解析器を生成すの実装で得ることが可能となる．それぞれ特性が異なる Boost.Spirit [3] や，テンプレートで記述された抽るため，適した実行方式を選択することが可能とな

象構文木を操作する Boost.Proto [5] が存在する．こる．今後の課題としては，上記のような実装を行うた

れらのライブラリは C++ のテンプレートによってめに，抽象構文木からテンプレート関数を生成するた記述されているため，本研究と同様に C++ のテンめの機構の実現が挙げられる．

プレートメタプログラミングによってそれらの動作を変更することは可能である．しかし，Boost.Sprit は

参 考 文 献生成した構文解析器は実行時にしか動作することが[1] Alexandrescu, A.：The D Programming Language,Addison-Wesley Professional; 1 edition, 2010
[2] Gregg, D. and Ertl, M. A.：A language andtool for generating eﬃcient virtual machine interpreters, Domain-Specific Program Generation,
Springer Berlin Heidelberg, 2004, pp. 196–215[3] Guzman, J.：Boost.Spirit,
http://boost-spirit.com/home/, 2008[4] Meijer, E., Beckman, B. and Bierman, G.：Linq:
reconciling object, relations and xml in the. netframework, Proc. 2006 ACM SIGMOD interna-できず，また，Boost.Proto はテンプレートで表現された抽象構文木を対象としているので，実行時に生成される抽象構文木を操作して仮想機械命令を生成している本研究とは対象が異なっている．

C++ のテンプレートを用いて構文解析を行い，得られた抽象構文木を使用してテンプレートを生成する研究 [6] も行われているが，この研究も同様にコンtional conference on Management of data, ACM,
2006, pp. 706–706.
[5] Niebler, E.：Proto Expression template library andcompiler construction toolkit for domain-specificembedded languages, http://www.boost.org/, 2008
[6] Porkolab, Z. and Sinkovics, .：Domain-specific lan-guage integration with compile-time parser generator library, ACM SIGPLAN Notices, Vol. 46, No. 2(2011), pp. 137–146.
[7] Johnson, S. C.：Yacc: Yet another compilercompiler. Murray Hill, NJ: Bell Laboratories, 1975.