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

• いくつかのタイル用意されている状況、例えば [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

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

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

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

追記２ Intentional programming

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

参考

• インテンショナルプログラミング

OMeta で書く、右再帰と左再帰

前回 http://d.hatena.ne.jp/propella/20071122/p1 S式電卓を作ると書いたけど、もう一度右再帰と左再帰について確認します。左再帰を書くと無限ループになるのが PEG の特徴らしいですが、OMeta では、どういうトリックかちゃんと左再帰も処理できます。とある数字(文字列)からとある数字(データ)を生成するプログラムを書いて、右再帰と左再帰の違いを確かめてみましょう。前回説明した以外に => によるアクションと、パラメータ付きのルールを使ってます。

まず左再帰を使った例。

ometa LNum {
  digit  ::= ('0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'):x
                                   => [x digitValue].
  number ::= <number>:n <digit>:d  => [n * 10 + d]
           | <digit>.
}

LNum matchAll: '4649' with: #number

短くて分かりやすい。では右再帰の例。

ometa RNum {
  digit        ::= ('0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'):x
                                                          => [x digitValue].
  number       ::= <numberSub 0>.
  numberSub :n ::= <digit>:d <numberSub (n * 10 + d)>:ds  => [ds]
                 | <empty>                                => [n].
}

RNum matchAll: '4649' with: #number

右再帰にこだわるほうが美しいと言ったけど、ちょっと分かりにくい。でも状態が必要であるという事がよく分かってむしろ良いような気もする。