リスト
フィリップ・ワドラー(Philip Wadler)は
「How to replace failure by a list of successes: a method for exception handling, backtracking, and pattern matching in lazy functional languages」(1985)で、失敗やバックトラックの可能性がある場合に結果をリストにして返すようにするというテクニックを紹介している。
すべての答えを探索してリストにして返す関数を呼び出しても、遅延評価言語ならば、実際にすべての答えを探索するわけではなく、必要に応じて必要なだけの答えを計算する。そのためリストを返す関数をバックトラック機構の代わりに使うことができるというのがこのテクニックのポイントになる(もちろんバックトラックが使われる全ての場合に適用できるわけではなく、そのことはワドラーも断っている)。
しかしここでは、このテクニックに基づいて関数を書くこと自体ではなく、このテクニックを繰り返し使いたい場合のことを考える。つまり
ある初期値v0をスタートにしてまず解の探索search0で複数の解を見つける。search0で見つけた複数の値のそれぞれを新しい初期値にして次の探索search1をおこなう。この探索で見つかった各値を次の初期値にして(以下続く)解を見つけたい。
とする。すでに探索関数は結果をリストで返す形で用意されているとする。
v0 :: A search0 :: A -> [B] search1 :: B -> [C] search2 :: C -> [D] ……
あとは、これらの関数を組み合わせるのだけど、そのためには次のような関数を用意すれば良い。
bindL :: [a] -> (a -> [b]) -> [b] bindL l f = concat (map f l)
この関数を使えば、
search0 v0 `bindL` search1 `bindL` search2 `bindL` ……
または
[v0] `bindL` search0 `bindL` search1 `bindL` search2 `bindL` ……
と書くことで、問題を解くことができる。
パーザ
同じ論文でワドラーは、結果をリストで返すテクニックを利用したパーザの書き方を紹介している。
パーザ関数は、
type Parser a = String -> [(a, String)]
という型で、
- まだパーズされていない文字列を引数として受け取る。
- 必要なだけ構文解析を進める。解析結果は、得られた構文要素と残りの文字列の組で表す。
- 構文要素と残りの文字列の組をリストにして結果として返す。
という動作をする。
小さい単純なパーズ関数を基本部品にして、それらをだんだん組み合わせていくことで、大きなパーザを構築していく。そのようにして作られるパーザは結果をリストで返すので、曖昧な文法を扱うパーザも作ることができる。
ワドラーが定義しているパーザをいくつかあげると次のようなものがある。
-- (lit c) 文字cを読み込むパーザ lit :: Char -> Parser Char lit c [] = [] lit c (x:xs) | c==x = [(c,xs)] | otherwise = [] -- (empty v) 文字列を消費せず構文要素vを返すパーザ empty :: a -> Parser a empty v xs = [(v, xs)] -- 構文解析に失敗するパーザ failure :: Parser a failure xs = []
もっと複雑なパーザを定義するには、小さなパーザを組み合わせる。組み合わせるための関数として、たとえば次のようなものが登場する。
-- (alt p q) パーザp、qの両方の解析の和を取るパーザ alt :: Parser a -> Parser a -> Parser a alt p q xs = (p xs) ++ (q xs) -- (sequ f p q) 二つのパーザp、qを連続して適用し、 -- 得られた値をfに渡して構文要素を作るパーザ sequ :: (a -> b -> c) -> Parser a -> Parser b -> Parser c sequ f p q xs = [(f v1 v2, xs2) | (v1, xs1) <- p xs, (v2, xs2) <- q xs1]
指定した文字列を読み込むパーザを作る関数は次のように定義できる。
-- (lits xs) 文字列xsを読み込むパーザ lits :: String -> Parser String lits [] = empty [] lits (x:xs) = sequ (:) (lit x) (lits xs)
> (lits "if") "if x=y"
[("if"," x=y")]他にも様々な組み合わせ方を定義して複雑なパーザを作ることが説明されている。
しかし説明されているのとは違う書き方を考えてみる。まず次のような関数を定義する。
bindP :: Parser a -> (a -> Parser b) -> Parser b bindP p f = \xs -> p xs `bindL` \(v, xs1) -> f v xs1
これを使えば、sequは次のように定義できる。
sequ :: (a -> b -> c) -> Parser a -> Parser b -> Parser c sequ f p q = p `bindP` \x -> q `bindP` \y -> empty (f x y)
また元論文で
app :: (a -> b) -> Parser a -> Parser b app f p xs = [(f v, xs') | (v,xs') <- p xs]
と定義されている関数は、
app f p = p `bindP` (empty . f)
とも定義できる。
bindPを使った定義は、元の定義より判りやすいとは必ずしもいえないけれど、組み合わせの中間にパーズ途中の文字列が明示的には登場しなくなるという利点がある。
関数適用との類似
bindLとbindPは、定義は違っているけど
- 合成するメカニズムを隠しながら合成をおこなう。
- 合成した結果は、次の合成の部品として使うことができる。
という点で良く似ている。
さらに外面的には関数適用とも似ている。これは、通常の関数適用とは引数と関数の位置が逆になっているものを考えて、それと比較してみると判りやすい。
bindL :: [a] -> (a -> [b]) -> [b] bindP :: Parser a -> (a -> Parser b) -> Parser b -- 通常の関数適用をひっくり返したもの bindF :: a -> (a -> b) -> b bindF x f = f x
これらは型が似ているだけでなく、次のように良く似た性質が成り立っている。
list1 x = [x] list1 x `bindL` f == f x m `bindL` list1 == m (m `bindL` f) `bindL` g == m `bindL` (\x -> f x `bindL` g)
empty x `bindP` f == f x m `bindP` empty == m (m `bindP` f) `bindP` g == m `bindP` (\x -> f x `bindP` g)
(id x) `bindF` f == f x m `bindF` id == m (m `bindF` f) `bindF` g == m `bindF` (\x -> f x `bindF` g)
一般に次の性質を満たす>>=とreturnを持った構造をモナドという。なので、[a]型やParser a型は(定義を書き換えれば)モナドになっている。
(>>=) :: m a -> (a -> m b) -> m b return :: a -> m a (return x) >>= f == f x m >>= return == m (m >>= f) >>= g == m >>= (\x -> f x >>= g)
入出力
遅延評価関数型言語で入出力を扱いたい場合、
- 参照透明性
- 入出力の実行順序
にどう対処するかが問題になる。
たいていの言語にあるような入力関数は、引数の値が同じでも帰ってくる値は(ユーザからの入力によって)違ってくるので参照透明性を満たさない。また参照透明性には目をつぶり参照透明性をやぶる関数を導入しても問題は残る。遅延評価では次のようなプログラムを書いた場合に、入出力関数がどの順番でいつ呼び出されるのか判らない。
let x = getchar() y = getchar() z = putchar()
この二つの問題を解決したい。
まず参照透明性については、次のような解決策がある。
普通の入出力関数が同じ引数に対して同じ値を返さないのならば、引数を増やしてやれば良い。
たとえば参照透明性を破る入力関数getchar
getchar :: Char
ではなく
getChar :: World -> (Char, World)
という関数にする。ここでWorld型は世界の状態を表している。こうしてやれば「引数である世界状態が違うのだから、戻ってくる値が異なっていても参照透明性を破ることにはならない」ことになる。より一般に
type IO a = World -> (a, World)
という型を定義して、入出力関数はこの型を利用することにすればよい。
ただしいくつか注意がいる。
まず、World型の値というのはコンピュータ上の何らかのデータではなく、単なる概念上のものにすぎない。なぜならコンピュータの全状態がまったく同じであっても、外界からコンピュータへの入力が異なれば、関数から戻ってくる値は異なる。だから、World型をコンピュータ上の何らかのデータと考えることはできず、コンピュータ外のインタラクションも含んだ概念上の世界状態だと考える必要がある。
でもこれはたいした問題ではない。World型は参照透明性を確保するために導入されただけで、具体的な値は別に必要ないから。
問題は別のところにある。次のようなプログラムを書いたとする。ここでは、World型のデータw0を2回使ってしまっている。
let (c1, w1) = getChar w0 (c2, w2) = getChar w0
このプログラムで参照透明性が満たされるためには、c1とc2が等しくないといけない。そうすると、二回の入力で必ず同じ文字を入力しないかぎり参照透明性が破られることになる。したがって、そもそもこのようなプログラムを書いてはいけない。そしてこのようなプログラムにならないためには、World型の値は常に一度だけ使うようにしないといけない。
これを保証するために、World変数を明示的に扱わなくてすむ統制された方法を使いたい。
ここでモナドが活用できる。モナドの形式でパーザを合成する場合、パーズ途中の文字列はプログラム上には登場しなくなった。同じようにモナドの形になるように入出力関数の合成をおこなうようにする。そこで
bindIO :: IO a -> (a -> IO b) -> IO b bindIO m k w = case (m w) of (a,w1) -> k a w1
のような関数を定義する。これを使って入出力関数を合成して望みの入出力関数を構築することにすれば、プログラムの途中で同じWorld型変数を繰り返し使うことはなくなるし、そもそもWorld型のことを意識する必要もなくなる。
ただしこの関数を使ったとしても、プログラム中のどこかにWorld型の値が登場するかぎり、World型の値を複数回使ってしまう可能性は残る。万全を期すためにはWorld型を隠蔽してプログラム中に表立っては一切出てこないようにする必要がある。そして入出力動作を駆動するための方法もプログラム中には登場させない(その結果そもそもWorld型なんてものが実装に導入されているのかも判らなくなる。別のやり方でIO型を実装しているかもしれない)。
これで参照透明性の問題は解決した。
もうひとつの問題だった実行順序の問題も解決できる。
たとえば
…… `bindIO` f1 `bindIO` f2 `bindIO` f3 `bindIO` f4 `bindIO` ……
とあった場合、f1、f2、f3、f4の順に入出力をおこなうように指定されている。このプログラムはどんな動作をするかを指定しているだけで、それだけでは実際の動作はおこなわれない(関数を合成しても引数を与えないと計算がおこなわれないのと同様)。これにWorld型の値を与えることではじめて入出力動作が始まる。
ここで一見すると、遅延評価の元ではf1、f2、f3、f4……のうちどの動作から実行されるか保証されないように見える。しかしパターンマッチに関する動作をうまく利用すると、bindIOで並んでいる順番に実行するように実装することができる(bindIOの右側の実行にはパターンマッチの結果が必要で、そのパターンマッチをするためにはbindIOの左側の計算結果が必要、となるように実装を工夫する)。
ここでもモナドを利用したことが役に立っている。モナドを使うと具体的な合成のメカニズムを気にしないで合成がおこなえた。ここでも実行順序を制御するテクニックはIO型データと関数のなかに隠されているので、そんなことは気にしないで入出力プログラムを書くことができる。
「どうしてモナドを使うと参照透明性が守られたり入出力の実行順序が保証されるのか全然判らない」という話がある。
でも、参照透明性を守るためのメカニズムや実行される順序の制御するための具体的なメカニズムを隠して気にしないで良いようにするためにモナドを利用しているのだから、メカニズムが全然判らないというのはあたりまえだとも言える。
