正規表現を超える

まずは、Audrey さんが言った Haskell の殺し文句を思い出して頂きたい。

正規表現ベースのパーサはメンテナンスしにくいのに気づいた？ Parsec を使って 15分で Perl6 の完全なパーサを書く方法を勉強しましょう。

15分というのは誇張が入っていると思うが、正規表現が保守しにくく、Haskell の Parsec は強力で保守し易いのは事実だ。その理由を Perl と Haskell のコードを示しながら説明してみたいと思う。

Perl を愛する方に：この記事は Perl を攻撃するために書いたのではない。Perl を選んだのは、正規表現を広めた言語であり、僕がそれなりに Perl のコードを書けるためである。この記事の目的は、正規表現よりも関数型パーサー(Parsec)の方が優れていると示すことだ。

例題

この記事では例題として、IPv4 アドレスを解析する関数を書くことにする。たとえば、こんな文字列を解析したい。

192.168.0.1

返り値は、0 〜 255 の数値の配列/リストとする。上記の例に対する返り値はこうだ。

[192,168,0,1]

配列/リストの長さは 4 である。

用語

あらかじめ「再利用」という言葉を定義しておこう。この記事で言う再利用とは、定義した関数を(別の機会に)加工しないで利用できることである。切り貼りし加工して利用した場合、再利用できたとは言わない。

数字の解析 (Perl)

プログラムを書く際は、まず問題を小さな問題に分割し、それらの小さな問題から解いて行く。今回も、IPv4 アドレスを分解し、まず 0〜255 の数字にマッチするコードを書いてみよう。

最初に Perl の正規表現を考えてみる。正規表現自体で「0 から 255 まで」を表現すると、あまりに煩雑になるので、簡単な正規表現を書き、Perl のコードでエラーチェックすることにする。

sub digit_byte {
    local ($_) = shift;
    unless (/(\d+)/) {
        die 'Illegal IPv4';
    }
    die 'Illegal IPv4' if (split(//,$1))[0] eq '0';
    die 'Illegal IPv4' if $1 > 255;
    return $1;
}

「もっと短く書ける」などの指摘は、本質ではないので、遠慮して頂きたい。

Perl は文脈に応じて文字列と数字を変換するので、このコードは明示的に型を変換していない。

数字の解析 (Parsec)

Parsec で「数の文字列」にマッチし、数値を返す関数を書こう。

いろんな方法があるが、ここでは Parsec が提供する digit という関数を使って、まず「数の文字にマッチし数値を返す」補助関数 nDigit を書く。

nDigit :: Parser Int
nDigit = do c <- digit
            return $ digitToInt c

digit は、数の文字にマッチし、その文字を返す。nDigit は、この文字を digitToInt を使って数値に変換して返している。

念のため述べれば、digit という関数は特殊な関数ではない。nDigit を定義したのと同じような感じで、digit も定義できる。違いは、Parsec があらかじめ提供しているということだけだ。

勘のよい人へ、Parsec の素晴らしさを示すのには、この例だけで十分だろう。Parsec の部品は、すべて単なる Haskell の関数である。そして、この関数は「マッチ」と「仕事」(この場合は型変換)の両方をこなす。

nDigit が手に入ったら、0 〜 255 にマッチする関数は、以下のように書ける。

digitByte :: Parser Int
digitByte = do ns <- many1 nDigit
               when (head ns == 0) (unexpected "Illegal number")
               return $ nsToInt ns

Parsec が用意している many1 を使っており、ns には数値のリストが入る。nsToInt では、数値のリストを数値に変換する。この関数は次のように定義できる。

nsToInt :: [Int] -> Int
nsToInt ns = foldl (\x y -> x * 10 + y) 0 ns

IPv4アドレスの解析 (Perl)

次に正規表現で、IPv4 アドレスを解析するコードを書いてみる。

先ほど書いた数字の解析する関数を部品として扱いたい。せっかくエラー処理も書いたのだから。しかし、正規表現では消費した対象物を単純には制御できないので、関数をコピペして、正規表現を拡張することになる。こんな感じだ。

sub ipv4 {
    local ($_) = shift;
    unless (/(\d+)\.(\d+)\.(\d+)\.(\d+)/) {
        die "Illegal IPv4";
    }
    die 'Illegal IPv4' if (split(//,$1))[0] eq '0' ||
                          (split(//,$2))[0] eq '0' ||
                          (split(//,$3))[0] eq '0' ||
                          (split(//,$4))[0] eq '0';
    die "Illegal IPv4" if $1 > 255 || $2 > 255 || $3 > 255 || $4 > 255;
    return [$1,$2,$3,$4];
}

IPv4アドレスの解析 (Parsec)

Parsec で IPv4 アドレスを解析するコードを書いてみよう。Parsec が提供する sepBy1 を使い、そしてここが重要なのだが、digitByte を利用して、以下のようなコードが書ける。

ipv4 :: Parser [Int]
ipv4 = do ns <- sepBy1 digitByte (char '.')
          check ns
          return ns
    where
      test n = when (n > 255) (unexpected "IPv4 should be 0-255")
      check ns = do when (length ns /= 4) (unexpected "IPv4 should be 4 bytes")
                    mapM_ test ns

IPv4アドレスへの完全マッチ (Perl)

Perl で書いた ipv4 は、任意の位置の IPv4 アドレスにマッチする。

Web のフォームなどに入力された IPv4 アドレスを検査するには、完全マッチにする必要がある。そこで、ipv4 を完全マッチに変えてみよう。またしても、Perl の関数は再利用できず、ipv4 をコピペして、こう書き直す必要がある。

sub exactIPv4 {
    local ($_) = shift;
    unless (/^(\d+)\.(\d+)\.(\d+)\.(\d+)$/) {
        die "Illegal IPv4";
    }
    die 'Illegal IPv4' if (split(//,$1))[0] eq '0' ||
                          (split(//,$2))[0] eq '0' ||
                          (split(//,$3))[0] eq '0' ||
                          (split(//,$4))[0] eq '0';
    die "Illegal IPv4" if $1 > 255 || $2 > 255 || $3 > 255 || $4 > 255;
    return [$1,$2,$3,$4];
}

IPv4アドレスへの完全マッチ (Parsec)

実は、Persec では対象物の最初にマッチすることを要請する。つまり、単純に関数を書いたのでは、正規表現で言う /^pattern/ を実装したことになる。

任意の場所の IPv4 アドレスにマッチ(/pattern/)する関数が欲しければ、ipv4 を再利用して、以下のようなコードを書けばよい。

inFixIPv4 :: Parser [Int]
inFixIPv4 = try ipv4 <|> do anyChar; inFixIPv4

対象物の先頭が ipv4 にマッチしなければ、try で消費した文字を元に戻し、anyChar で任意の一文字を消費して、自分自身に再帰する。

このパターンはよく使うので、inFix という関数に抽出してみよう。するとこうなる。

inFix :: Parser a -> Parser a
inFix p = try p <|> do anyChar; inFix p

inFixIPv4 :: Parser [Int]
inFixIPv4 = inFix ipv4

再帰を見てギョっとする人もいるかもしれない。Haskell には繰り返しはないので、こういう場合必ず再帰を使う。

「再帰しか使えないのは Haskell の欠点だ」と言うのは的外れな指摘だ。そもそも繰り返しは、力を限定された特殊な再帰である。あなたは、単に繰り返しという表現に慣れているだけだ。

僕には昔、左手を鍛えるために、箸を左手で握っていた時期がある。最初は、ご飯を食べている気分になれなかったが、その内「どうして今まで右手で箸を握っていたのだろう」と思うようになった。要は慣れの問題なのだ。

さて、今度は IPv4 アドレスに完全マッチ(/^pattern$/)するコードを書く。これは、以下のように書ける。

suffix :: Parser a -> Parser a
suffix p = do x <- p
              eof
              return x

exactIPv4 :: Parser [Int]
exactIPv4 = suffix ipv4

ついでだが、対象物の最後にマッチ(/pattern$/)する IPv4 アドレスのコードは、こういう風になる。

suffixIPv4 :: Parser [Int]
suffixIPv4 = suffix inFixIPv4

正規表現は異分子

正規表現では、問題を小さなコードに分割して解き、それをつなぎ合わせることができないと実感できただろう。正規表現は結局モノリシックになって、保守しにくく、再利用もできない。

一方 Parsec では、完全に再利用可能な5つの関数(nDigit,digitByte,ipv4,inFix,suffix)を定義できた。それを元に inFixIPv4、exactIPv4、suffixIPv4 も定義できた。

Perl で正規表現が再利用できない本質的な理由は、正規表現は別の言語であって、Perl ではないからだ。Perl にとって、正規表現は異分子なのだ。Perl の関数を書いても、正規表現のメタ文字が増える訳ではない。

Perl と正規表現の関係は、細胞とミトコンドリアのそれに似ているという人がいる。嫌気であった太古の細胞は、酸素を利用した燃焼エンジンであるミトコンドリアを細胞内に取り込んで巨大な力を手に入れた。現在、両者はよく親和しているが、結局 DNA は異なるのだ。(ミトコンドリアの DNA は、母親からしか受け継げないし。)

Parsec は、単なる Haskell 関数の集合だ。よって、Haskell の型推論や型検査が利用できる。実際、僕は Parsec のおかげで、電子メール関連の RFC/Internet-Draft に定義してある BNF のバグを 2 つ発見できた。(many に空文字列にマッチするパーサーを渡すと警告を出す。)

高い次元へ

正規表現と Parsec の能力の差にも注意を払うべきだ。チェムスキー階層によれば、正規表現が解析できるのは最下層の正規言語であるのに対し、Parsec では文脈自由言語どころか文脈依存言語まで解析できる。

単純な例を挙げるなら、正規表現では入れ子構造を解析でないが、Parsec には簡単だ。これは、関数型パーサーが再帰的に呼び出せることと深い関係がある。

Parsec を知れば、字句/構文解析という問題を高い次元から眺められるようになるのだ。

問題を高い次元から眺める重要性を僕は交流回路を通して学んだ。大学受験の勉強をしていたとき、物理の問題に交流回路が出てきた。交流回路を解いたことのなかった僕は、焦って勉強したが、その解法はベクトルを使う柔軟性のないもので、結局習得できなかった。後にから思えば、大学入試に交流回路が出題される訳がない。

大学に入り、交流回路を虚数を使って解く方法を学んだ。実数しか知らなければ、問題を x 軸の一次元で考えることになる。虚数を使えば、視野は y 軸方向に広がり、問題を二次元で捉えられるようになる。二次元の視野があれば、交流回路を解くのは難しくない。

あなたも正規表現に凝り固まった思考から脱却し、Parsec を学んで視野を広げてみないか？