第5章　パーサコンビネータ―小さなパーサを組み合わせて大きなパーサを作る

この章では、関数型の至宝であるコンビネータライブラリについて説明します。

コンビネータとは何か？

この章でいうコンビネータとは、ある型の部品と部品を組み合わせて、同じ型のより大きな部品を作るための関数のことです。たとえば、パーサのコンビネータライブラリは、パーサを組み合わせるための各種コンビネータを提供しており、簡単にパーサを作成できます。コンビネータライブラリは、言語内DSL（Domain Specific Language）と表現してもよいでしょう。

関数型では、パーサに加えて、データを文字列でわかりやすく表示するプリティプリンタ、SQL、XML、ハードウェア記述、そしてデリバティブ（金融商品）記述、楽譜記述など多様なコンビネータライブラリが作られ、実際に使われています。この章では、パーサのコンビネータライブラリを取り上げます。

CSVのパーサ

たとえ簡潔でも、実用的でないパーサの例だと興味が持てないでしょうし、一方実用的であっても長いと理解が難しくなるでしょう。そこで、実用的で手頃な大きさで、またみなさんが馴染み深いと思われるCSVのパーサを作ることを考えましょう。

CSVのBNF

CSVのBNF[1]は、RFC 4180で定められています[2]⁠。リスト1に、説明を簡単にするために1行目だけ手を加えたCSVのBNFを示します。

リスト1　CSVのBNF

csv = 1*(record CRLF)   （1）
record = field *(COMMA field)   （2）
field = (escaped / non-escaped)   （3）
escaped = DQUOTE *(TEXTDATA / COMMA / CR / LF /
2DQUOTE) DQUOTE   （4）
non-escaped = *TEXTDATA
TEXTDATA = %x20-21 / %x23-2B / %x2D-7E
COMMA = %x2C
CRLF = CR LF
CR = %x0D
LF = %x0A
DQUOTE = %x22

*、1*、2はそれぞれ、0回以上、1回以上、2回の繰り返しを意味します。%xは、ASCII文字を16進数表記していることを表します。

csv、record、fieldの意味

これを見ると、csvとはrecordの集まりであり、recordとはカンマで区切られたfieldの集まりであることがわかります。次に例を示します。

boo,foo,woo
goo,zoo,qoo

たとえば、全体がcsv、boo,foo,wooがrecord、fooがfieldに当たります。これはみなさんの理解通りでしょう。

fieldの内部

難しいのはfieldです。データ中にカンマや二重符号が出てこない場合はそのままでよいのですが、出てくる場合は二重符号で囲みます。二重符号でカンマを囲むと、区切り文字のカンマと区別がつきます。

boo,"foo,woo",goo

一方、二重符号に囲まれた二重符号は、囲みなのか二重符号文字そのものなのか区別がつきません。そこで、二重符号を重ねます。

boo,"foo""woo",goo

この例の"foo""woo"は、foo"wooを表します。

正規表現でCSVパーサを実装する場合

みなさんは、CSVパーサを正規表現で実装したくなるかもしれません。しかし、CSVパーサを正規表現で作るのは、とても難しいことが知られています。『⁠詳説正規表現第3版』（⁠注3）の5.4.2項には、CSVパーサを実装した例が載っていますので、興味があれば見てください。

正規表現がパーサを作るための技術としてあまり適していない理由は2つあります。まず第一に、正規表現が入れ子構造を表現できないことです。第二に、正規表現は部品化できないため、正規表現が長くなりがちで、保守しにくくなることです。

関数型言語でも正規表現のライブラリは提供されています。しかし簡単な問題であればリスト操作で解決できますし、複雑な問題だとパーサを書きます。そのため、正規表現はあまり使われていません。

パーサコンビネータParsecでCSVパーサを実装

では、CSVパーサをコンビネータライブラリを用いて実装してみましょう。今回は、Haskellのライブラリの中で、とても有名なパーサのコンビネータライブラリParsecを使用します。Parsecを用いると、BNF通りにパーサを作っていけば、魔法のように目的のパーサができあがります。

これから示すコードは、csv.hsというファイルに記述してください[4]⁠。そのファイルの先頭には、必要なライブラリを読み込むために、次のコードを入れます。

import Control.Applicative ((<*),(*>))
import Text.Parsec
import Text.Parsec.String

今から、CSVのBNFを元にトップダウン的に実装していきます。そして、最後に動かしてみましょう。

csvを実装する

まず、BNFのリスト1（1）の部分を実装します。このパターンにはコンビネータendBy1を使います。endBy1は、第二引数で終端される第一引数のパーサを1回以上繰り返すコンビネータです。

csv :: Parser [[String]]
csv = endBy1 record crlf

csvの型を見てください。Parserとは、パーサというコンテナ型を表しています。このようにパーサをコンテナとして実装するのが常套手段です。このParserというコンテナ同士をくっつけるのがParsecのコンビネータです。

内側の型は、Stringのリストのリストになっています。Stringとは[Char]の別名です。外側のリストが行を、内側のリストが列を意味します。つまり、CSVファイルをパースした結果は、文字列を要素に持つ二次元のリストになります。

recordとcrlfはこれから実装するパーサです。

recordを実装する

次はリスト1（2）に従いrecordを書きましょう。このパターンには、コンビネータsepBy1が利用できます。sepBy1は、第二引数で区切られる第一引数のパーサを1回以上繰り返すコンビネータです[5]⁠。

record :: Parser [String]
record = sepBy1 field comma

fieldを実装する

次はfieldです。BNFはリスト1（3）です。/の部分を、選択を表すコンビネータ<|>に単純に置き換えるだけです。

field :: Parser String
field = escaped <|> nonEscaped

escapedを実装する

次に、BNFで一番長い部分であるリスト1（4）を実装します。次のようになります。

escaped :: Parser String
escaped = dquote *>
          many (textdata <|> comma <|> cr <|> lf
            <|> try (dquote *> dquote))
          <* dquote

コンビネータ*>は、左のパーサを実行したあとに右のパーサを実行し、右のパーサの結果を返します。一方、<*は同じ実行順序ですが、左のパーサの結果を返します。このことから、二重符号で囲まれた部分に対し、両端の二重符号を捨てて、中身を返していることがわかります。

コンビネータmanyは、引数を0回以上繰り返すためのコンビネータで、リストを返します。manyの引数では、textdataやcommaが<|>で区切られて列挙されているのがわかります。このコンビネータは、BNFでは前述の通り/に当たります。

tryの意味

最後に列挙されているのは、

try (dquote *> dquote)

です。これは2DQUOTEを実現しています。このコードは、二重符号が2回連続すると、1つだけ（どちらでもよいがこの場合は右）返すことを意味します。では、なぜtryで囲まれているのでしょうか？

Parsecでは、パースが成功し消費された入力データは忘れ去られます。しかし、tryで囲んだ場合は、入力データを覚えていて、パースが失敗した場合は入力を巻き戻し、ほかの可能性を探ります。

escapedの最初には、あとで定義する二重符号文字をパースするdquoteパーサがありますから、tryの部分が試されるのは、二重符号で囲まれた中です。このとき現れる二重符号には2通りの可能性があります。

① 二重符号文字を表すための連続した二重符号
② 囲みの終わりを示す二重符号

仮にtryがないコードを書いて、囲みの終わりを示す二重符号が来た場合のことを考えてみましょう。この場合、(dquote *> dquote)の左側は成功します。その二重符号は忘れさられます。次に右側は失敗するので、manyが終了し、escapedの最後のdquoteが試されます。しかし、もうその二重符号は忘れ去られているので、うまくパースできません。

このように(dquote *> dquote)の右側が失敗する場合は、左側が消費した二重符号をもとに戻さなくてはいけません。それを実現するのがコンビネータtryの役割です。

nonEscapedとtextdataを実装する

nonEscapedやtextdataは簡単に定義できます。

nonEscaped :: Parser String
nonEscaped = many textdata

textdata :: Parser Char
textdata = oneOf (" !" ++ ['#'..'+'] ++ ['-'..'~'])

oneOfは文字通り、引数に取ったリスト中の文字のどれかにマッチするというコンビネータです。++はリストを連結する演算子です。

残りを実装する

あとは、前述のdquoteも含め、文字をパースするパーサを作れば完成です。これにはcharを使います。charは引数に文字を取り、その文字をパースするパーサを返します（文字という型を表すCharとは違うものです⁠）⁠。

comma :: Parser Char
comma = char ','

crlf :: Parser Char
crlf = cr *> lf

lf :: Parser Char
lf = char '\x0a'

cr :: Parser Char
cr = char '\x0d'

dquote :: Parser Char
dquote = char '"'

使ってみる

定義したCSVのパーサを使ってみましょう。

% ghci csv.hs

対話的に使うには、parseTestにパーサと入力文字列を与えます。

> parseTest csv "boo,\"foo,woo\",goo\r\nboo,\"foo\"\
"woo\",goo\r\n" 実際は1行
[["boo","foo,woo","goo"],["boo","foo\"woo","goo"]]

うまくパースできましたね。今回作った各部品も同じ方法で利用できます。

コンビネータライブラリの真価

パーサのコンビネータライブラリを使うと、BNF通りにパーサが書けることがわかったと思います。今回はトップダウン的に書きましたが、通常はボトムアップ的に作っていきます。つまり、小さなパーサを定義し、テストして確信が持てたら、それらをコンビネータで組み上げて大きなパーサを作ります。

ここで強調しておきたいのは、コンビネータライブラリを使って書いたコードは、何も特別なものではなく、単にその言語で書いたコードになります。そのため、静的型付きの関数型言語であれば、コンパイル時に型検査の恩恵が受けられるのです。

さらに勉強するには

駆け足で関数プログラミングを紹介しました。

初めて関数プログラミングに触れた人に興味を持っていただいたり、挫折した人が再び挑戦する気になっていただいたり、「⁠実用的ではない」と勘違いしていた人が「けっこう使えるのかも」と思っていただけたりしたとしたら、幸いです。

これからも勉強していきたい人のために、アドバイスを書いておきます。このアドバイスは、何も関数型言語に限った話ではなく、どのプログラミング言語にも言えることです。

関数型言語を1つ選ぶ

まず、複数の関数型言語を調べてみて、どれか1つ言語を選んでください。直感的にクールだと思った言語がよいでしょう。また、ブログやTwitterのやりとりを観察して、優しく教えてくれる人が多い言語を選ぶとよいかもしれません。よく知らないで「関数型言語の人は恐い」と言っている人もいますが、関数型言語の熟練者には優しい人が多いと思います。

情報を集めコードを書いてみる

言語を決めたら、複数の本を読んでみましょう。1冊では駄目です。そして、実際にコードを書いてみましょう。また、公開されているブログ記事やチュートリアルもたくさん読みましょう。

既存の関数を再発明してみる

次に、基本ライブラリにどんな関数が定義してあるかを把握し、それらがどのように使われているのか調べます。

使い方がわかったあとは、自分でその関数を再発明してみましょう。この作業は、とても理解を深めてくれます。

勉強会に参加する

それから、勉強会に参加しましょう。最近は関数型言語の勉強会がたくさん開催されています。知り合いがいなくても、思い切って参加しましょう。そして、たくさん質問しましょう。

Happy functional programming!