プログラミング言語Grassは正規表現と相性が良い – RANSによるプログラム列挙

このエントリーをはてなブックマークに追加
はてなブックマーク - プログラミング言語Grassは正規表現と相性が良い – RANSによるプログラム列挙
Share on Facebook
Post to Google Buzz

僕のポスター「正規言語の列挙:プログラミングへの応用」はこんな感じです.テックちゃんが右上に居るのがポイント!(ぉぃ http://t.co/CNgcCsxo9t
@sinya8282
Ryoma Sin'ya

PPL2013でポスター発表をしてました.

失礼ながらPPLは規模の小さい学会だと思ってたので,実際参加してみて各方面のガチ勢が多かったのが嬉しびっくりでした.

 

さて

PPLでのポスターでも話したネタですが,プログラミング「Grass」の話をしたいと思います.もちろん正規表現ぽい話.

Grassは”W”,”w”,”v”の三文字のみでプログラムを書けるチューリング完全な言語です.イカれてますよね :-)

さて,この言語Grassですが,文法はもちろんきちんと定義されていて

  • app ::= W+ w+
  • abs ::= w+app*
  • prog ::= abs | prog v abs | prog v app*
といったシンプルな文法となっています.

正規表現!!

この文法はBNFで記述されていますが,実は線形文法で書けます.つまり「正規表現で書ける」.
w([vw]*(W+w)*)*
が構文的に正しいGrassのプログラムを表現する正規表現です.シンプルですね.
プログラムの列挙
さて,RANSと言う僕が開発しているソフトウェアがあります.これは正規表現と数を食わせて「長さ–辞書順でその数に対応する受理文字列を返す」というものです.その逆もできます.
凄い点は「文字列から数は線形時間で,数から文字列は準線形時間で計算できる」
さて,プログラミング言語Grassの構文は正規表現で書けます.では,プログラムと数の対応をいくつか列挙してみましょう.

Hello, world

% cat hello.www
wwvwwwWWWwwWwwWWWWwvwWWwwwWwwvwWwwwWwwvwWWwWWWWWwvwWWWwwwwWWWWwWWWWw
WWWWWWwWWWWWWWwWWWWWWWwWWWWWWWWwWwwwwwwwwvwWWWwwwwwWWWWWwWWWWWwWWWWW
WWwWWWWWWWWwWWWWWWWWWwWwwwwwwwvwWWWWwwwwwwWWWWWWwWWWWWWwWWWWWWWwWWWW
WWWWWwWWWWWWWWWwWwwwwwwwvwWWWWWwwwwwwwWWWWWWWwWWWWWWWWwWWWWWWWWwWWWW
WWWWWWwWWWWWWWWWWwWwwwwwwwvwWWWWWWWwwwwwwwwWWWWWWWWwWWWWWWWWWwWWWWWW
WWWwWWWWWWWWWWWwWwwwwwwvwWWWWWWWWwwwwwwwwwWWWWWWWWwWWWWWWWWWwWWWWWWW
WWWWwWWWWWWWWWWWwWWWWWWWWWWWWWwWwwwwwwwvwWWWWWWWWwwwwwwwwwwWWWWWWWWW
wWWWWWWWWWWwWWWWWWWWWWWwWWWWWWWWWWWWWwWwwwwwwvwWWWWWWWWWWwwwwwwwwwww
WWWWWWWWWWwWWWWWWWWWWWwWWWWWWWWWWWWWwWwwwwwvwWWWWWWWWWWwwwwwwwwwwwwW
WWWWWWWWWWWwWWWWWWWWWWWWWwWWWWWWWWWWWWWWwWWWWWWWWWWWWWWwWWWWWWWWWWWW
WWWWwWwwwwwwwvwWWWWWWWWWWwwwwwwwwwwwwwwwwwWwwwwwwwwwwwwwwwwwwwWWWwww
wwwwwwwwwwwwwwwwWwwWWWWWWWWWWWWWWWWWWWWwvwWWwwwwWWWwwwwwwwwwwWWWWwww
wwwwwwwWWWWWwwwwwwwwwwwwwWWWWWWwwwwwwwWWWWWWWwwwwwwwwwwwWWWWWWWWwwww
wwwwwwwwwwwwwwwwwwvwWWWWWWWWWWWWWWWWwwwwwwwWwwvwWWWWwwwwwwwWWWWWwwwW
WWWWWwwwwwwwWWWWWWWwwwwwwwwWWWWWWWWwwwwwwwwwwwwwwWWWWWWWWWwwwwwwwwww
wwwwvwWWwWWWWWw
これは「Hello, world」を出力するGrassプログラムです(こちらから拝借しました).イカれてますよね.
このプログラムはGrassの文法的に「何番目」のプログラムなのでしょうか?RANSがあればお気軽に計算出来ます.
% cat hello.www | rans 'w([vw]*(W+w)*)*' --tovalue
16276174481634706127730787006880531370466380062973401969614529593658
83958803429956101907280299748822841594957446604850712567590269550047
04442396791176156604038955035748328503682524926066804754823248092598
88431440137005387911828231622152001940020161961290610781750518034051
89101265159339318336722855919281300746470264479856011884839769266736
50505379491629371259037681514934225197925358244649970308443675866436
6464026061342507810037583

などという10進数400桁以上の巨大な数が出てきます.ちなみにRANSは凄いので0.1秒程度でこの数が求まります.

百億番目のGrassプログラム

では逆に,「キリの良い数」に対応するプログラムを生成してみましょう.
「百億番目のGrassプログラム」は何か?簡単です.
% echo '10000000000' | rans 'w([vw]*(W+w)*)*'
wwWwvWWwwwwvwvwvWwvwWwwvv
さて,これは何を出力するプログラムでしょうか?実は
% echo '10000000000' | rans 'w([vw]*(W+w)*)*' > hoge.www
% ./yagi.rb hoge.www
w
なんと!「w」を!出力するプログラムなんです!
「百億番目のプログラムがwを出力する」なんて,Grass凄い.どこまで草を生やすんだ.
(yagi.rbはrubyによるGrass処理系実装です.まめめもさんから拝借しました.)

ちなみに

PPLではGrassの開発者である上野先生が参加されていて,この記事に相当する話をしたら.
え,文法は正規なんですねwww これは面白いwww
などという予想外の反応をされました.「文法が正規なのは意図してなかったのかよ」というオチです.面白いですね.
チューリング完全なプログラミング言語で,文法が正規言語のクラスなモノなんて恐らく他にあまり無い?と思うので,Grassは正規表現と相性が良いと言ってOKでしょう(ぇ

RANS使いましょう

このように,RANSを使えば色々なことができます.今回はGrassという面白いネタを扱いました.
ソースコードも公開していますので,皆さんも是非RANSを使ってみて下さい.
  1. コメントはまだありません。

  1. トラックバックはまだありません。

 
Better Tag Cloud