DLT’14に論文採択

単著論文が国際学会 DLT’14 (18th International Conference on Developments in Language Theory) に short paper として採択されました.論文は僕のページにて公開しています.
DLTは1993年に A. Salomaaと G. Rozenberg (2人ともヨーロッパ理論計算機科学協会元会長!) が発起人となり始められた形式言語・オートマトン理論のガチ專門会議です(参考)。理論色が強い学会という印象を持っています.

論文内容

Graph Spectral Properties of Deterministic Finite Automata“という,かなり一般的なタイトルの論文となっています.ある正規言語Lを認識するDFA達は無限に存在するのですが,そのDFA達の隣接行列(の固有値)構造に着目した時に,どういった秩序があるのかということを探った研究です.DFAに関して,その隣接行列(の固有値)構造について考察するというのは,いくつか似てる研究はあるものの,新しいと考えこのような一般的なタイトルをつけました.

ここでいうDFAの隣接行列とは,DFAから文字を忘れて単なる多重有向グラフとして見た時の隣接行列のことです.例えば
fib

というDFAに対応する隣接行列は[[1, 1],[1,0]]となります.任意のDFAから隣接行列は一意に定まりますが,隣接行列からそれに対応するDFAは一意に定まりません.隣接行列はDFAから「文字の情報を削ぎ落した構造」なのです.

最小定理

この論文ではDFAと隣接行列の関係に関していくつかの性質を示しています.その中で最も重要なものとして最小定理

DFAが最小 ⇔ DFAの隣接行列の階数と退化次数が共に最小

という最小DFAの線形代数的必要十分条件があります.階数(rank)は線形写像の像空間の次元,退化次数nullity)は線形写像の核(kernel)の次元ですね.ここでいう最小とは「同じ言語を認識するDFAの中で最小」ということを意味しています.最小DFAの存在や構成法は情報科学科の学生さんであれば学部で習う基礎事実です.最小DFAの必要十分条件というfundamentalな内容を「文字の情報を削ぎ落した構造」である隣接行列から導けたということで,僕的にとても気に入っている成果です.

⇐ の方向は階数・退化次数の定理より自明ですが,⇒の方向は自明ではありません.なぜなら,「状態数が小さい ⇒ 階数と退化次数が共に小さい」は一般的に成り立たないからです.次の図がそれを示しています.

Screen Shot 2014-05-03 at 8.08.02 PM

A1,B1,C1はそれぞれ同じ正規言語を認識するDFAで,M(A1),M(B1),M(C1)がそれぞれの隣接行列です.なお,A1は最小DFAとなっています.よく見るとB1はC1よりも状態数が少ないにも関わらず階数はC1の方が小さいことが分かります.同様の事実が退化次数に関しても言えます.A1においては定理に矛盾していない,つまり階数と退化次数がB1やC1に比べ小さいことに注意して下さい.

スペクトラルグラフ理論

この定理の証明には「スペクトラルグラフ理論」というグラフの隣接行列の固有値構造を調べる理論の基礎的な道具:Equitable partition が使われています.スペクトラルグラフ理論は一年前から一年かけて僕が主催して後輩と書籍を輪講をしていたのですが,輪講開始から半年たって Equitable partition がDFAに使えることに気づきました.実は Equitable partition を使わないバージョンの上記定理の証明は輪講を始める前から思いついてたのですが,Equitable partition のおかげで証明を大分ゴルフすることができたのです :-D  とはいえ,スペクトラルグラフ理論の輪講を決定したのは「DFAの解析に使える道具があるのでは?」と思ったから始めたので,当時の僕GJ!

証明は,スペクトラルグラフ理論の道具である Equitable partition と,オートマトン理論の道具である Nerode partitionの2つの登場人物を出会わせるものです.準備や初等的な事実・補題を除くと実質1ページぐらいのとてもコンパクト証明です.異なる2つの理論で使われていた2種類のpartitionが強く関連しているのは興味深いものです.証明が読みたい方は論文を参照して下さい

正規言語による文字列圧縮とのつながり

そもそもこの研究は「正規言語による文字列圧縮の計算量が低いような正規言語のクラス」に興味を持ったところから始まりました.正規言語による圧縮については,過去のエントリ

をご覧下さい.

研究の流れとしては

  1. 正規言語による文字列圧縮はDFAの隣接行列の冪乗が計算大変!
  2. 階数が1の行列は効率よく冪乗が計算できる超単純な構造を持っている.
  3. DFAの階数が1であるような正規言語のクラス:rank-one langugaes を解析しよう!
  4. でも,DFAの階数ってどれが最小なんだろう? 同じ言語を認識するDFAって無限にあるんだけど…
  5. 最小DFAの階数が最小っぽいよな… 常識的に考えて…
  6. 示そう! あ,退化次数も同時に最小になるっぽい!

という流れで上記の定理にいきつきました.線形代数の初等的事実ですが,階数が1の行列はその冪乗(の要素)がO(1)で計算できます(参考: “On rank one matrices and invariant subspaces” ).

発展

実は,この論文では rank-one languages のDFAにおける canoncial form を示しただけで,その性質を十分に解明することができませんでした.正直言うとわからないことだらけです.2つの正規言語が与えられた時,それらから新しい正規言語を作り出す様な演算は正規言語においてはたくさんあります.例えば和集合や積集合,shuffleや連接などなど.このような正規言語の演算とDFAの隣接行列(の固有値)構造がどのように対応するのかということを調べたかったのですが,これがまた難しいのです.むしろDFAだと無理なのでは?という感じです(投げやり).

論文では「ここがわかっていない〜」「こうすれば上手くいくはずなんだけど難しいんだ〜」ということを正直に書き連ねています.発展途中の研究ということで, short paper という結果は納得しています.が,もうちょっと頑張って full paper で通したかったなぁ…

論文採択について

学部〜修士では正規表現マッチングの並列化やコード生成,修士〜博士では正規言語による文字列圧縮,そして今はDFAの固有値構造の解析という流れを見ると,僕自身の興味が応用から基礎理論に向かっていることが分かります.これからは理論バリバリな成果をガンガン出していきたい所存ですが,その意味でDLTという理論色の強い会議にこのような成果で採択されたのは嬉しいです.論文に適切なコメントを着けてくれた @ranha 君,研究生活を全面的に支援してくださった首藤先生,アイディア段階の時に議論に付き合ってくれた @kinaba さんや京大・京産大の研究者方々に感謝を.

応用畑で育った人間として,理論の世界に身を投げるのはなかなか勇気のいる行動でした.実際この一年間は成果もろくに出さずほとんど輪講や論文読みのいわゆる「基礎学習」に時間を費やしてました.分野を変えるまではいきませんが,一般に研究者としての方針を変えるのは時間がかかると思います.今回の結果がDLTに reject されていたら「やっぱり応用の世界で生きていこうかな…」と迷ってた可能性が高いです.怖い.怖くない?怖い!

とはいえこのような結果になったわけですし,いろんな分野の道具をバリバリ使いこなして新たな正規言語の定理をガンガン生み出せるような人間になるために,これからも頑張って行きたい所存です.

正規言語で修士号を取得しました.修論を公開します.

 

2013年3月に東京工業大学大学院情報理工学研究科数理・計算科学専攻の修士過程を卒業しました.

現在は同専攻で博士課程学生としてお勉強&研究に打ち込んでいます(あ,所属研究室が佐々研から首藤研に変わりました).

 

修論を

せっかくなので修士論文を公開します.

cover

正規言語上の Abstract Numeration System の 文字列圧縮への応用(PDF)

 修士論文のタイトルは

「正規言語上の Abstract Numeration System の文字列圧縮への応用」

というものです.タイトルは厳めしいですが,内容は非常にシンプルです. この論文では正規言語の数え上げ理論,及びその計算量や圧縮率(+いくつかの応用策)について論じています.

簡単に言うと以前ブログで扱ったRANSの理論の話です(正規表現を使ってデータ圧縮等するツールを作りました)

 

目次

  • 図目次
  • 図や記号に関する注意
  • 1章 はじめに
  • 第1部 準備
    • 2章 正規言語とオートマトン
      • 2.1 形式的定義
      • 2.2 決定性,無曖昧性,非決定性
      • 2.3オートマトンの行列表現
    • 3章 Combinatorial Complexity
      • 3.1 数え上げ関数
      • 3.2 数え上げ関数に関するShurの定理
    • 4章 Abstract Numeration System
      • 4.1 形式的定義
      • 4.2 $n$数法との関係
      • 4.3 平方数に関するEilenbergの定理
  • 第2部2 正規言語上のAbstract Numeration Systemの文字列圧縮への応用
    • 5章 DFAを用いたANSのアルゴリズム
      • 5.1 valS の計算
      • 5.2 repS の計算
      • 5.3 計算量
    • 6章 ANSによる文字列圧縮
      • 6.1 ANS間の基数変換
      • 6.2 圧縮率
    • 7章 応用
      • 7.1 URIの圧縮
      • 7.2 符号
      • 7.3 分割基数変換
    • 8章 議論
      • 8.1 文脈自由言語への拡張の困難さ
      • 8.2 エントロピーベース圧縮法との対比
      • 8.3 圧縮に適した正規言語
    • 9章 まとめ
  • 謝辞
  • 付 録
    • RFC 3986 定義のURI文法
      • 拡張BNFによる定義
      • 拡張正規表現による定義
    • RFC 3986 定義のURI文法
      • 正規言語の同定問題の困難性
      • 順序の問題
  • 索引
  • 参考文献

 

実は

一般の方(正規表現とかオートマトンとか良く知らない人)向けに,解説を付加したり,お話風にしたり,構成を変更したバージョンも作成して公開しようとしていたのですが,色々あって見送りという形になりました.いずれ書きたいものです(書かないフラグ).

URLにマッチする真の正規表現 – RFC3986定義のURIの話

RFC3986定義の厳密なURIの正規表現 (file)

[a-z][-+.0-9a-z]*:(//(([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=])*@)?(\[(([0-9a-f]{1,4}:){6}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|::([0-9a-f]{1,4}:){5}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|([0-9a-f]{1,4})?::([0-9a-f]{1,4}:){4}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:)?[0-9a-f]{1,4})?::([0-9a-f]{1,4}:){3}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,2}[0-9a-f]{1,4})?::([0-9a-f]{1,4}:){2}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,3}[0-9a-f]{1,4})?::[0-9a-f]{1,4}:([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,4}[0-9a-f]{1,4})?::([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,5}[0-9a-f]{1,4})?::[0-9a-f]{1,4}|(([0-9a-f]{1,4}:){0,6}[0-9a-f]{1,4})?::|v[0-9a-f]+\.[!$&-.0-;=_a-z~]+)\]|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])|([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,;=])*)(:\d*)?(/([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])*)*|/(([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])+(/([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])*)*)?|([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])+(/([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])*)*)?(\?([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,/:;=?@])*)?(#([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,/:;=?@])*)?

*大文字小文字の区別をしてません.エンジン側で大文字小文字を無視するオプションを付けて解釈してください.

RFC3986定義の厳密なHTTP URIの正規表現

schemeをhttpまたはhttpsに固定すれば良いだけなので,

https?:(//(([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=])*@)?(\[(([0-9a-f]{1,4}:){6}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|::([0-9a-f]{1,4}:){5}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|([0-9a-f]{1,4})?::([0-9a-f]{1,4}:){4}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:)?[0-9a-f]{1,4})?::([0-9a-f]{1,4}:){3}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,2}[0-9a-f]{1,4})?::([0-9a-f]{1,4}:){2}([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,3}[0-9a-f]{1,4})?::[0-9a-f]{1,4}:([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,4}[0-9a-f]{1,4})?::([0-9a-f]{1,4}:[0-9a-f]{1,4}|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]))|(([0-9a-f]{1,4}:){0,5}[0-9a-f]{1,4})?::[0-9a-f]{1,4}|(([0-9a-f]{1,4}:){0,6}[0-9a-f]{1,4})?::|v[0-9a-f]+\.[!$&-.0-;=_a-z~]+)\]|(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])\.(\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])|([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,;=])*)(:\d*)?(/([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])*)*|/(([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])+(/([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])*)*)?|([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])+(/([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,:;=@])*)*)?(\?([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,/:;=?@])*)?(#([-.0-9_a-z~]|%[0-9a-f][0-9a-f]|[!$&-,/:;=?@])*)?

*こちらも同様に大文字小文字の違いを無視

解説

URIの厳密な文法は,

RFC3986 – Uniform Resource Identifier (URI): Generic Syntax

で定義されています.なお,RFCの定義ではURIでは大文字小文字を区別していません.

文法はRFC仕様のABNF(拡張文脈自由文法)という記法で定義されています.

理論的にはABNFは文脈自由文法をフルで記述できる能力を持ちますが,

URIの定義に関して言えば実は正規表現(正規文法)に変換可能です.

 

ABNFから正規表現への変換系は,Tanakaさんの abnf というツールを使いました :-)

 

歴史小ネタ

URIの文法は1998年にRFC2396で定義されたのが最初です.

現在のURIはいわばバージョン2で,2005年のRFC3986で定義が大幅に変更しました.

 

では,初期の文法(RFC2396)に比べて,URIの文法はどの程度複雑になっているのでしょうか?

意味的な複雑さを比べるのは一般に難しいですが,正規表現的に複雑さを評価するのは簡単です.

「(最小)DFAの状態数で比べる」という方法があります.

 

バージョン1のRFC2396によるURIの文法(正規表現)は,以下のDFAが対応します.

uri.rfc2396

バージョン2のRFC3986によるURIの文法(正規表現)は,以下のDFAが対応します.

 

なんと,7年の期間を経たアップデートによって,URIの文法は10倍以上(DFAの状態数が13→180)も複雑になってしまったのです!

 

宣伝

以上の話は,ソフトウェアデザイン5月号の特集「正規表現をマスターしていますか?」に起稿した記事でも扱っています.

 興味がある人は是非読んでみてくださいね!
Software Design 5月号に10ページほど記事を書きました.「正規表現をマスターしていますか?」という特集の最終章(コアな章)です.是非読んでみて下さい.発売(4/18)が楽しみです.http://t.co/beVFMUVFUk#gihyojp #fb
@sinya8282
Ryoma Sin'ya

 

追記: ソフトウェアデザインの原稿を公開

処理速度にも影響する!? 正規表現エンジンの種類と仕組み

 

また,この記事で使っているDFA図はRANSというツールで作成したものです.

基本的な使い方はチュートリアルページにまとまっているので,興味が有る方は触ってみて下さい.

「数学文章作法 基礎編」という本を結城さんが出すらしい.


【お知らせ】4月10日に刊行される結城浩の最新刊『数学文章作法 基礎編』(ちくま学芸文庫)を抽選で無料プレゼントいたします。 (^^)http://t.co/beAowBStFx
@hyuki
結城浩

ま,また僕に本を買わせる気ですか結城さんー!

IMG_7475]

実のところ,僕の所属する研究室には大分優遇してもらってて,技術書や数学書は研究費で購入してもらうことが多いです.修士二年間で買ってもらった本の総額はちょっとこの場では言えないぐらいになっています.

しかし,なぜか「数学ガールは自費で買う」という謎の制約を自分に課しており,これまでもそうしてきました.

閑話休題

今回結城さんが出す本は「数学文章作方(さくほうと読むらしい) 基礎編」という本で,おそらくは「数学ガール」を始めとした「一般人でも分かりやすく興味をひく数学本」を多く買いている結城浩さんの作法エッセンスがツラツラと書かれているのでしょう.「基礎」と言ってるのであまり崩せないでしょうが,結城さんらしい「作法」が読んでみたいです.

正直な話,僕みたいな学生にとっては「理科系の作文技術」という大定番があるので,文章作法本のような本を心待ちにしていたわけではありません.結局論文・文章を読み&書きまくることが一番の方法だと思いますしね.

しかし結城さんですよ.数学ガールの作者ですよ.それなら読みたいですよ.という感じで,この記事を書いた次第です.

作法本の発売が楽しみです.どのような内容になってるのでしょうか.

個人的には「数式と数式を繋ぐ論理の流れ,滑らかに説明(それでいて硬くなり過ぎない)する流麗な文章の書き方」などなど期待しています.一般向けの方々に文章を書くコツ等があるのかもしれませんしね.

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

僕のポスター「正規言語の列挙:プログラミングへの応用」はこんな感じです.テックちゃんが右上に居るのがポイント!(ぉぃ 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を使ってみて下さい.
 
Better Tag Cloud