Interpreterパターンとミニ言語

その他

GoFの23デザインパターンの一つ、インタプリタパターン。最近、インタプリタパターンを使ってミニ言語を実装したので、その際に参考にした資料をまとめてみました。実装については触れませんので、各記事を参考にしてください。

インタプリタパターンは頻繁に使うパターンではないけれど、知っているとものすごく役に立ちます。
GoF23パターンの中でも用途がとびきり具体的で、そのため理解も容易です。ほかの応用範囲の広い(そしていまひとつピンとこないような)デザインパターンとは毛色の異なるものです。
名前の通り、インタプリタを実装するためだけのパターンです。特にミニ言語向きで、複雑な言語向きではありません。ミニ言語を解析したり、実行/評価するために使います。
小難しく言うと構文木(Abstract Syntax Tree)を表現して、構文木への操作を簡単に記述する方法です。主な用途は構文木の解析と実行ですが、必要なら、構文木に対するほかの様々な操作も簡単に拡張できる特徴があります。

このパターンはオブジェクト指向による実装ですが、ミニ言語という手法は古くから使われており、たとえばC言語のprintfの「%3d」みたいな表記、正規表現、sendmailのコンフィグなどが広く使われています。
最近ではドメイン特化言語(DSL:Domain Specific Language)として、ミニ言語が脚光を浴びているようです。
Martin Fowler's Bliki「http://capsctrl.que.jp/kdmsnr/wiki/bliki/?DomainSpecificLanguage」

ミニ言語なんて使わない/使ったことがないって人は「達人プログラマ」や「プログラム作法」を読むと、あのとき使えたな〜とか、ここに使える！とか気づくかもしれません。ミニ言語という手法自体は、オブジェクト指向とは関係なく大きな価値のある考え方です。設計者やプログラマは、知っていれば楽ができるので勉強してみてくださいね。(ミニ言語程度なら勉強ってほどのことでもないけど)

ミニ言語を作って使うことにより、コードを短くシンプルにし、問題領域に近いところで直接命令を書くことができます。オブジェクト指向とは別の視点からコードをまとめあげるテクニックです。「プログラミング作法」9.1の冒頭の説明を引用します。「我々がコンピュータに向かって言いたいことと仕事をさせるために言わなければならないこととの間には、常にギャップが存在する。このギャップは狭ければ狭いほど望ましい。優れた記法を利用すれば言いたいことが言いやすくなるし、うっかり間違ったことを言ってしまう危険も低下する。場合によっては優れた記法によって新しい視点がもたらされ、難しすぎて不可能だと思っていた問題を解決できるようになったり、新しい発見が得られたりすることもある。」


インタプリタパターンは本格的な言語を作るのには向いていません。簡単な文法の小さな言語を、手早く作る、拡張や保守を容易にするのに向いています。

向き不向きの特徴を箇条書きにしてみると、こんな感じ。
・文法が単純な場合に向いている。
・実行効率は悪め。
・実装が簡単で製造、改造、保守が楽。

もっと言うと、
・BNFさえ定義できてしまえば、あとはほとんど機械的にコーディングできる。
・BNFに変更が入っても、改造もとても簡単。ただし、単純な文法に限る。
・文法が複雑な場合は、パーサジェネレータを使ったほうがよい。ジェネレータはyacc、bison、JavaCCなどがある。
・本格的な言語を実装するなら、コンパイラ、オートマトン、アルゴリズムなどを勉強してね。
というところ。

結城浩さんの「増補改訂版Java言語で学ぶデザインパターン入門(isbn:4797327030)」(http://www.hyuki.com/dp/index.html)では、構文解析を取り扱っています。
スペースで区切られたシンプルな文法を定義し、それを解析して構文木にする例を解説してあります。また練習問題とその回答では、実行する部分を扱っています。

結城さんの書籍のサンプルを中西 庸文さんがC#/VBへの移植したもの。
http://hccweb1.bai.ne.jp/tsune-1/index.html


GoF本「オブジェクト指向における再利用のためのデザインパターン」(isbn:4797311126)では、簡単な正規表現の一致判定の実装をSmalltalkで行う例、C++でBool表現を操作実行する実装例が載っています。


インタプリタパターンの解説と実装はこの２冊で解析と実行の例があるんだけど、肝心のミニ言語はどう設計するの？ってところが問題です。上にも書いたように、ミニ言語のBNFによる設計が肝です。

artonさんによるCodeZineの記事「http://codezine.jp/a/article.aspx?aid=78」では、XMLで言語を記述しています。今どきはこの手がよさそうです。わりと本格的な汎用のプログラミング言語を作っています。すごい。自由に使ってよいというのが、またすごい。拡張していくベースに使えますね。

もっと簡単で短い記法でミニ言語を書きたいときは、１行に１トークン(命令)にするとか、トークンの間は必ずスペースで区切るとか決めてしまえば、字句解析が楽です。ちょっとかっこ悪いけど気にしないｗ
lex/flexなんかが必要な文法になってしまうようなら、このパターンを使うよりもそっちを使ったほうが楽で効率もよいコードが生成できるはずです。

BNF記法は@ITの「http://www.atmarkit.co.jp/fxml/ddd/ddd004/ddd004-bnf.html」が参考になります。ISOになってるけど、テキトーに使われてるようです。いろんな記法に出会いますよね、BNFって。

記法だけ分かってもしょうがないので、様々な例などは id:tanakh さんのパーサ関連の一連の記事がとても参考になります。


ミニ言語についての参考資料。

「達人プログラマー(isbn:4894712741)」第2章セクション12。専用の言語というタイトルで、「問題領域に近いところでプログラミングを行うこと」というヒントとともに、専用の言語の例と考察があり、大変参考になり、おもしろく、そして考えさせられる文章です。設計者にはぜひ読んで欲しい。
ただし、いきなり立派な言語を作ろうとは思わないこと。本格的な言語を作りたければ、オートマトンやコンパイラの勉強をしたり、いくつかミニ言語を作って経験を積んでからでイイジャン。

「プログラム作法(isbn:4756136494)」第9章。数千行のコードが数百行になった例がおもしろい。ほかにも構文木解析後の評価(実行)や最適化のあたりの導入的な話題がある。
この本、ものすごくおもしろい本です。扱っている話題はなんだか教科書的なんだけど、文章は読みやすくておもしろいし、知的好奇心を刺激する話題ばっかりで、読み始めると止められないおもしろさがあります。第3章のマルコフ連鎖アルゴリズムってのを、C/Java/C++(STL)/Awk/Perlで実装して速度を比較する話題はおもしろすぎです。Cはコード行数が最も多く(150行)、実行速度が最速。ついで早いのが、なんとPerl。Perlは行数が最も短い(18行)。まさにPerl向きの問題ってこともあるんだろうけど、STLを抜いてしまうってにはびっくり。ちなみにこのCコードは「珠玉のプログラミング」でダメ出しされ、半分の長さのコードが載っている。

IBMのDeveloperWorksの記事。BNFやJavaCCの話題など。
http://www-6.ibm.com/jp/developerworks/xml/030221/j_x-javacc1.html
http://www-6.ibm.com/jp/developerworks/xml/030228/j_x-javacc2.html

はっぴぃさんによるデザインパターンの分類は直感的で秀逸。
http://hp.vector.co.jp/authors/VA020635/system/dpattern.html


え〜っと…、アフィリエイトしてないのに、調子に乗って資料を挙げすぎました。どれか一つというなら、結城さんの本をお勧めします。