言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella

生成文法とタイルスクリプト

  • いくつかのタイル用意されている状況、例えば [turtle forwardby 10] を考える。
  • 違う所から別のタイル [turtle turnby 30] を取ってきてくっつける。
  • 「二つのタイルはタイルなので、くっつけた [turtle forwardby 10][turtle turnby 30] もタイルである。」これが「文法」
tile ::= [turtle forwardby 10]
tile ::= [turtle turnby 30]
tile ::= tile tile

これで、「何故タイルスクリプトが簡単か」の説明になる。文法に則って作られたタイルスクリプトのシステムは、タイルスクリプト以外の文を作り出すこと、つまり文法エラーが起こりえない。目をつむってマウスをガチャガチャ動かしても絶対エラーを起こさないプログラムを書ける。

という事で、またメモです。タイルスクリプト生成文法で、プログラムのソースコードは分析的文法、別の物として考える必要があるという話。二つの文法の違いがどういう物かというと、

  • 生成文法の例: X が文の時 XX も文である。
  • 分析的文法の例: 文の先頭を調べる。X なら文である。文の先頭を削除して同じ手続きを進める。

つまり、書き換えルールによって現れるパターンの集合が生成文法で、検索にマッチするパターンの集合が分析的文法。この二つはお互いに変換可能だけど応用可能な場所が違う。

分析的手法はソースコードを読むのに使われる。パーサージェネレータは生成文法で示したルールを分析的手法に変換する方法だ。それなら最初から分析的手法で文法も書けば良いじゃないかという話になって、それが PEG なのだろう。

生成文法は、むしろタイルスクリプト向きだ。タイルスクリプトだけじゃなくて、動的に文法をチェックしたり部分的にコンパイルする IDE にも使える。

形式的なタイルスクリプトの表現の必要性は前から感じていたんだけど、具体的なイメージがわかなかった、PEG を知って、生成文法の性質がはっきりしてきた。これはタイルスクリプト的だ。

こういう言い方も出来る。プログラムのパーサーとは、プログラム構造を一旦頭の中でシリアライズしてテキストに変換した物をコンピュータが解析するという事。タイルスクリプトは、テキストを間に挟まずプログラム構造(パースツリー?)をそのまま操作出来る。その場合、プログラムはどう解析されるかでは無く、どう生成されるかで定義される。

http://ja.wikipedia.org/wiki/%E5%BD%A2%E5%BC%8F%E6%96%87%E6%B3%95

追記: 生成文法とタイルスクリプトを超えて。

生成文法の厳密な適用により、目をつむってマウスをガチャガチャ動かしても絶対エラーを起こさないプログラムを書ける。それで充分か?構文エラーを起こさないプログラミング環境は第一歩に過ぎない。本当にやりたい事は意味エラーを起こさない事。

本当にそんな事可能なのか。コンピュータには意味が分からないからそりゃ不可能。しかし、意味を変えないでプログラムを変える事なら出来る。最初の第一歩として、これだけで大きな意味があると思う。どんな形式化をすれば可能になるのかさっぱり分からないけど、これが次にやらないといけない事。

追記2 Intentional programming

某メーリングリスト で話題になった面白いビデオ http://youtube.com/watch?v=tSnnfUj1XCQ これを開発中止にするなんてマイクロソフトも度量が無い。わー。これはまさに大人の eToys だな。また、Generative programmingという言葉さえある事が分かった。でも私の考えの Generative ってソースコードを自動的に吐き出す事じゃなくて、Generative に文法が定義されてある事だから意味合いはかなり違います。

参考