Haskell入門ハンズオン! #3: 当日用資料 2/5
はじめに
構文解析器をつくり、それを使って四則演算の式を読み込み、評価する。たとえば、つぎのような式を読み込む
3+(5*4)
そして、この結果を計算して、つぎのように表示する。
23
このように、文字列を決められたルールで解釈することを、構文解析とよぶ。今回は構文解析と、数値への評価を同時にやってしまう。
パーサコンビネータ
まず「パーサコンビネータ」を構成する関数群を定義する。「パーサコンビネータ」とは、構文解析器(パーサ)を組み上げるための道具だ。この道具を対話環境で試しながら作っていく。内容としては、拙書「Haskell - 教養としての関数型プログラミング」第20章の内容(P.298 - 310)を「ほぼ、まるまる」といった感じだ。
モジュールの導入
対話環境で使う関数をファイル内で導入しておく。こういうことは本番コードでは、あまりやらない。ここでは、ハンズオンでの便宜のため、このようなかたちとした。ファイルcalc.hsを、つぎのように作る。
% vim calc.hs
import Data.Maybe (listToMaybe, fromJust)
import Data.Char (isDigit, isSpace, digitToInt)
予約語importを使って、モジュールを導入する。対話環境に読み込んでおこう。
*Main> :load calc.hs
パーサの型
ここで、「パーサ」の型を考える。「文字列を読み込んで値をかえす関数」だと
String -> a
Haskellで標準的な文字列はString型の値だ。String型の値とは、実はChar型の値のリストだ。
*Main> ['x', 'y', 'z']
"xyz"
['x', 'y', 'z']と"xyz"とは、おなじものだ。また、「String -> a」の「a」は型変数だ。型変数は、実際に型が使われるときには、具体的な型(Char, Bool, Doubleなど)に置き換えられる。
ふたつのパーサをつなげることを考える。まえのパーサでパースしきれなかった文字列を、つぎのパーサにわたすことを考えると、パーサは結果の値だけでなく、「残りの文字列」もかえしたほうがいいだろう。すると、パーサの型は、つぎのようになる。
String -> (a, String)
(Foo, Bar)のような構造をタプルとよぶ。ふたつ以上の値をまとめるのに使うことができる。
さらに、パースの結果として、最終的には、ひとつにしぼるとしても、解析の途中では複数の候補が必要になることもある。パーサの型はさらに、つぎのようになる。
String -> [(a, String)]
[Foo]という表記は「Foo型の値のリスト」の型を意味する。この型全体の意味は、つぎのようになる。
文字列を引数としてとり
「パースの結果と残りの文字列」のリストをかえす関数
これから、パーサをあつかう関数をいくつか作る。そのたびに、String -> [(a, String)]を書くのは冗長だ。このようなとき、型に別名(型シノニム)をつけられる。ファイルcalc.hsに、つぎのように追加する。
type Parse a = String -> [(a, String)]
予約語typeを使って、型シノニムParseを定義した。型引数aのところには具体的な型がはいる。
Parse Char ===> String -> [(Char, String)]
Parse Bool ===> String -> [(Bool, String)]
Parse Double ===> String -> [(Double, String)]
パーサコンビネータを構成する関数群
いつも成功するパーサ
「いつも成功して、決められた値をかえすパーサ」を作る関数。
succeed :: a -> Parse a
succeed v inp = [(v, inp)]
いまは「何のためにあるか」は、わからなくていい。対話環境で試してみよう。
*Main> :reload
*Main> (succeed 123) "hello"
[(123,"hello")]
文字列を消費せずに123をかえすパーサに、文字列"hello"をあたえたら、ひとつの「結果の値123と残りの文字列"hello"」に解析された。
条件つきで1文字、読み込むパーサ
条件を満たす1文字を読み込むパーサを作る関数。
check :: (Char -> Bool) -> Parse Char
check p (c : cs) | p c = [(c, cs)]
check _ _ = []
関数checkの定義には、パターンマッチとガードという、ふたつの構文が使われている。第2引数のところの(c : cs)はパターンマッチだ。第2引数の文字列のうち、先頭の文字で変数cを束縛し、残りの文字列で変数csを束縛している。ちなみに、「値で変数を束縛する」は「値を変数に代入する」のように、頭のなかで変換するとわかりやすいかもしれない。
| p cのところがガードだ。これは、p cを評価した結果がTrueのとき、全体が=の左辺の[(c, cs)]に評価されるということだ。これらのパターンマッチとガードの、どちらかを満たさなければ、2行目にうつる。定義の2行目の_(アンダースコア)は、第1引数と第2引数とが、使われないということだ。引数は無視されて、全体はに評価される。これは、1文字目cが条件を満たさなければ、パースは失敗するということだ。対話環境で試してみる。
*Main> :reload
*Main> check isDigit "123"
[('1',"23")]
*Main> check isDigit "abc"
[]
1文字目が数字なら成功し、そうでなければ失敗するパーサを作り、使った。
指定した1文字を読み込むパーサ
指定した1文字を読み込むパーサを作る関数。
char :: Char -> Parse Char
char c = check (== c)
(== c)は演算子の部分適用だ。演算子の第1引数のところが空いている。部分適用によって作られた関数に引数をあたえると、その「空いているところ」にはいる。たとえば(== c) 'a'のようにすると、'a' == cとしたのとおなじことになる。つまり、(== c)は引数と値cとを等値比較する関数になる。関数checkに「値cとの等値比較をする関数」をあたえると、指定した1文字cを読み込むパーサになる。対話環境で試してみる。
*Main> :reload
*Main> char 'a' "abc"
[('a',"bc")]
*Main> char 'a' "bcd"
[]
1文字目が指定した文字'a'であるとき、パースは成功し、文字'a'が消費され、文字'a'が結果になる。そうでなければ、パースは失敗する。
ふたつのパーサのうち、どちらか
ふたつのパーサのうちのどちらかで解析するパーサを作る。パーサは「リストをかえす関数」なので、かえされたリストを結合すればいい。
alt :: Parse a -> Parse a -> Parse a
(p1 `alt` p2) inp = p1 inp ++ p2 inp
演算子(++)はリストを結合する。パーサの失敗を空リストとするので、パーサp1が失敗したとき、パーサp2の結果が全体の結果になる。逆も成り立つ。
まえに、演算子は()でかこむと、関数になると説明した。
*Main> 3 + 5
8
*Main> (+) 3 5
8
逆に、2引数関数は``(バッククォート)でかこむと、演算子になる。
*Main> mod 8 3
2
*Main> mod 8 `mod` 3
2
「``(バッククォート)で演算子になる」のは、関数を使うときだけでなく、関数を定義するときにも成り立つ。つまり、関数altの定義は、つぎとおなじことだ。
alt p1 p2 inp = p1 inp ++ p2 inp
「パーサp1とp2とを足し合わせる感じ」を表現したくて、定義にも演算子の構文を使った。対話環境で試してみよう。
*Main> :reload
*Main> (char 'a' `alt` check isDigit) "123"
[('1',"23")]
*Main> (char 'a' `alt` check isDigit) "abc"
[('a',"bc")]
「文字'a'、または、数字」の1文字をパースするパーサを作り、使った。
パースの結果を加工する
パースした結果の値に関数を適用して、べつの値に変換する関数。
build :: Parse a -> (a -> b) -> Parse b
(p `build` f) inp = [ (f x, r) | (x, r) <- p inp ]
ここで使っているのは、リスト内包表記という構文糖だ。文字列inpに関数pを適用した結果としてリストができる。そのリストの要素すべてに対して、パターン(x, r)を使って、変数x, rを束縛し、式(f x, r)によって新しい値を作っている。対話環境で試してみよう。
*Main> :reload
*Main> (check isDigit `build` digitToInt) "123"
[(1,"23")]
関数digitToIntは数字の1文字を数値に変換する関数だ。check isDigitだけだと、結果は文字'1'になる。それに関数buildを使ってdigitToIntを適用することで、数値の1にしている。
ふたつのパーサをつなげる
ふたつのパーサをつなげる演算子を定義する。
(>@>) :: Parse a -> Parse b -> Parse (a, b)
(p1 >@> p2) inp = [ ((x, y), r') | (x, r) <- p1 inp, (y, r') <- p2 r ]
ここでもリスト内包表記を使っている。パーサp1で解析した結果の残りの文字列rが、パーサp2の引数としてわたされている。パーサp1の複数の結果すべてに対して、パーサp2の複数の結果すべてが計算される。全体の結果として、それぞれのパースの結果の値x, yがタプルとして、まとめられて、それにさらに、パーサp2による解析の残りのr'を追加した。対話環境で試す。
*Main> :reload
*Main> (char 'a' >@> check isDigit) "a123"
[(('a','1'),"23")]
文字'a'をパースするパーサと、数字をパースするパーサとをつなげたパーサだ。
つなげたパーサの、かたほうの結果だけを残す
ふたつのパーサをつなげるとき、どちらかのパース結果を捨てたいときがある。たとえば「123,456」のような文字列をパースするとき、,(カンマ)はパースの結果には必要ない。まえの結果と、うしろの結果について、それぞれを残す(他方を捨てる)ような、結合用の関数を定義する。
(>@) :: Parse a -> Parse b -> Parse a
p1 >@ p2 = (p1 >@> p2) `build` fst
(@>) :: Parse a -> Parse b -> Parse b
p1 @> p2 = (p1 >@> p2) `build` snd
関数fstとsndは、それぞれ、タプルの第1要素、第2要素を取り出す関数だ。これを関数buildによって、パースの結果に適用している。対話環境で試す。
*Main> :reload
*Main> (char 'a' >@ check isDigit) "a123"
[('a',"23")]
*Main> (char 'a' @> check isDigit) "a123"
[('1',"23")]
それぞれ、まえの値、うしろの値だけ結果として残る。
文字列のおわりを調べる
文字列のすべてを解析したことを確認するパーサを定義する。
eof :: Parse ()
eof "" = [((), "")]
eof _ = []
型()はユニット型と呼ばれる型であり、値()のみを値とする。情報量は0になる。簡単に言うと、パーサeofにはかえす結果がないということだ。対話環境で試す。
*Main> :reload
*Main> (char 'a' >@ eof) "a123"
[]
*Main> (char 'a' >@ eof) "a"
[('a',"")]
解析されていない文字列が残っていれば、パースは失敗する。
まとめ
構文解析に使う基本的な道型を定義した。以下のパーサやパーサをあつかう関数だ。
succeed, check, char, alt, build, (>@>), (>@), (@>)
これらを使って、パーサを組み立てていく。