読者です 読者をやめる 読者になる 読者になる

A Play on Regular Expressions読んだ

Haskell

A Play on Regular Expressions

最後まで読みました.

対話的に書かれていて読みやすかったのと, ソースコードがほとんどそのまんま動いたため楽しかったです.



正直言って, 正規表現のエンジン書いたのは初めてでした.

この論文の素晴らしい所は, そんなぼくでも, ACT1を読むだけで, 取り敢えずなんか動くエンジンが作れてしまうことですね. ただ, 指数関数的にメモリーを食うからがんばろうって言ってACT2に続くわけですが...



ACT2からもすごく良かった.

Semiringを使って正規表現の返す値を一般化する方法は, とても美しく, 気持よかったです. そして, 最終章のLazinessにきた時, 興奮が収まりませんでした.





少しコード貼っておきます.

最初に出てくる, 正規表現を表すデータ型はこんな感じです.

data Reg = Eps
         | Sym Char
         | Alt Reg Reg
         | Seq Reg Reg
         | Rep Reg

instance Show Reg where
  show Eps = ""
  show (Sym a) = [a]
  show (Alt a b) = "(" ++ show a ++ "|" ++ show b ++ ")"
  show (Seq a b) = show a ++ show b
  show (Rep a) = "(" ++ show a ++ ")" ++ "*"

例えば,

main = do
  let a = Sym 'a'
  print a
  let b = Sym 'b'
  print b

  let ababs = Seq a (Seq b (Rep (Seq a b)))
  print ababs

  let aorb = Alt a b
  print aorb

とかだと

a
b
ab(ab)*
(a|b)

のようになります. ええ.



で, で, で!!!

Haskellのlaziness使えば { a{n}b{n} | n >= 0} == /|ab|aabb|aaabbb|aaaabbbb|.../みたいな, 無限長の正規表現を作れるよ的な話が最後にあって,

main = do
  let a = Sym 'a'
      b = Sym 'b'
      anbn = Alt Eps (Seq a (Seq anbn b))

\ほれ, できた/

んでもって

  print a
  print b
  print (match_w (weighted anbn) "" :: Bool)
  print (match_w (weighted anbn) "ab" :: Bool)
  print (match_w (weighted anbn) "aabb" :: Bool)
  print (match_w (weighted anbn) "aaaabbbb" :: Bool)
  print (match_w (weighted anbn) "aaabbbb" :: Bool)
  let a300b300 = let n = 300 in replicate n 'a' ++ replicate n 'b'
  print (match_w (weighted anbn) a300b300 :: Bool)

とかすると,

a
b
True
True
True
True
False
True

みたいに返ってきます (論文の最後までちゃんと読めばmatch_wやweightedの意味が分かります).


気になったので, nを変化させた時の実行時間の変化をプロットして見ました. コードは

import System
main = do
  let a = Sym 'a'
      b = Sym 'b'
      anbn = Alt Eps (Seq a (Seq anbn b))
  args <- getArgs
  let n = read (head args) :: Int
  let str = replicate n 'a' ++ replicate n 'b'
  print n
  print (match_w (weighted anbn) str :: Bool)

みたいな感じね.

うげげ, 指数関数的... 結構ゆっくりだけど...

でも1000*2=2000の長さの文字列をHaskellで20秒ほどで評価できたからまぁいいかな(´・ω・`)



取り敢えず読んで下さい. 面白いです.




読みきった後に知ったのですが, ソースコードリポジトリgithubで公開さています. 今から落としてコード読みます. 素晴らしい論文を有難う御座いました.

Weighted RegExp Matching (ソースコードは見ずに論文を読みながらコード書いたほうが絶対楽しいです)