遅延パターン

 ここまでの話はすべて標準外のことでした。標準仕様の中にも,理解しておかなければならない話題が一つあります。「パターン束縛(pattern binding)」に関するものです。

 パターン束縛とは,左辺がfun x ... のような関数ではなく,Just xや(x,y)などのようなパターンになる等式のことです。パターン束縛はトップレベルで定義するよりもlet式などで利用することのほうが多いと思うので,以下の部分ではlet式でのパターン束縛を例に説明していくことにしましょう。

 head $ zip [11,12] ["Number","Number"]のようなタプルを作り出す式から,それぞれの値を変数に束縛するときのことを考えてみましょう。zipは二つのリスト綴じ合わせてペアのリストを作成する関数です。

Prelude> zip [11,12] ["Number","Number"]
[(11,"Number"),(12,"Number")]
Prelude> head $ zip [11,12] ["Number","Number"]
(11,"Number")
Prelude> let (x,y) = head $ zip [11,12] ["Number","Number"]
Prelude> x
11
Prelude> y
"Number"

 このとき,ペアの値のどちらかではなく,ペアそのものが⊥ならどうなるでしょうか? パターン束縛が普通の変数束縛同様にcase式に変換されるなら,その後の式でペアが全く使われなくても⊥になってしまう可能性があります。パターン照合が早すぎるのです。

Prelude> (\ (x,y) -> twelve y) (11,undefined)
12
Prelude> (\ (x,y) -> twelve y) undefined
*** Exception: Prelude.undefined
Prelude> (\ v@(x,y) -> twelve v) undefined
*** Exception: Prelude.undefined

 @は「アズパターン(as-pattern)」といって,上の例のように(x,y)のようなデータ型全体に照合させる場合に使えます。

 この問題を改善するには,「先にとりあえず変数の束縛に成功させておき,その後改めて評価を行う」ように,パターン照合に「非正格な意味論」を持たせる必要があります。これを可能にするのが,「遅延パターン(lazy pattern)」あるいは「不可反駁パターン(irrefutable pattern)」と呼ばれるものです。

Prelude> (\ ~(x,y) -> twelve y) undefined
12
Prelude> (\ ~v@(x,y) -> twelve v) undefined
12

 ほかには,変数やワイルドカード・パターンが不可反駁になっています(参考リンク)。

Prelude> (\ v -> twelve v) undefined
12
Prelude> (\ _ -> twelve ()) undefined
12

 もちろん,パターン束縛も暗黙の遅延照合になっており,その結果が⊥であっても問題なく使用できます(参考リンク1参考リンク2)。

Prelude> let (x,y) = undefined in twelve y
12
Prelude> let v@(x,y) = undefined in twelve v
12

 また,パターン束縛が遅延照合になっていなければ,ここまで述べてきた問題のほかに,パターン束縛で定義されている関数が再帰になっているときに問題が発生する可能性があります。

 第1回にコラムで紹介した「The Haskell School of Expression: Learning Functional Programming through Multimedia」や,あまりやさしくはないことで有名な「やさしいHaskell入門」(原文はA Gentle Introduction to Haskell, Version 98)で使われているプログラムを例に説明しましょう。サーバー・プロセスserverとクライアント・プロセスclientとの間のやり取りをシミュレートするプログラムです。

 clientが一連の要求(request)を送り,serverがそれぞれの要求に対して応答(response)を返す動きは,次のように相互再帰(mutually recursive)的に定義できます。

reqs = client 1 resps
resps = server reqs

 clientとserverは,それぞれ以下のように定義されているとしましょう。

client init ys = init:ys
server xs = map (+1) xs

 変数は不可反駁なので,この場合には問題なく使用できます。

*Main> take 10 reqs
[1,2,3,4,5,6,7,8,9,10]
*Main> take 10 resps
[2,3,4,5,6,7,8,9,10,11]

 しかし,client関数の第2引数を,以下のように変数から型構成子を使うパターンに書き換えた瞬間,問題が発生するようになってしまいます。

client init (y:ys) = if True then init:y:ys
                     else error "faulty server"

 clientがreqsとresps双方の再帰的な環境下で使われているので,最初の要求が発行されるよりも前に応答リストを照合しようとしてしまうのです。この結果,いつまでたってもプログラムは結果を返しません。

*Main> take 10 reqs
(応答なし)

 これを改善するには,以下のように不可反駁パターンを使うか変数を使用するよう書き換える必要があります。

client init ~(y:ys) = if True then init:y:ys
                      else error "faulty server"

client' init ys = if True then init:(head ys):(tail ys)
                  else error "faulty server"

 いずれにせよ,このような問題が発生したところで定義を書き換えるよりは,パターン束縛がデフォルトで遅延照合してくれるほうがプログラムは遥かに書きやすくなります。

 では,以上のプログラムをlet式のパターン束縛を使って書き直して見ましょう。

main =
  let init = 1
      req:reqs = if True then init:resps
                 else error "faulty server"
      resps = map (+1) (req:reqs)
      {-
      -- あるいは、以下のように書くこともできます。
      req:reqs = if True then init:(map (+1) (y:ys))
                 else error "faulty server"
      resps = drop 1 (req:reqs)
       -}
  in print $ take 10 resps

 「req:reqsに対する束縛を,req:reqsなしには定義できない」形になっているのがわかりますね。

$ runhaskell Lazy.hs
[2,3,4,5,6,7,8,9,10,11]

 最後に,プログラム全体を再度掲載しておきます。

main' = print $ take 10 resps
main'' = print $ take 10 reqs

reqs = client 1 resps
resps = server reqs

client init ~(y:ys) = if True then init:y:ys
                      else error "faulty server"

client' init ys = if True then init:(head ys):(tail ys)
                  else error "faulty server"

server xs = map (+1) xs


main =
  let init = 1
      req:reqs = if True then init:resps
                 else error "faulty server"
      resps = map (+1) (req:reqs)
      {-
      -- あるいは、以下のように書くこともできます。
      req:reqs = if True then init:(map (+1) (y:ys))
                 else error "faulty server"
      resps = drop 1 (req:reqs)
       -}
  in print $ take 10 resps

seq関数とpseq関数

 $!演算子について紹介している部分で参考リンク先を見に行った方はすでにおわかりだと思いますが,$!演算子はseq関数を使って定義されています(参考リンク)。

seq :: a -> b -> b
seq = ...       -- Primitive

($), ($!) :: (a -> b) -> a -> b
f $! x    =  x `seq` f x

 seqは与えられた引数を評価して,第2引数を返す関数です。上のPrimitiveという記述からわかるように,seq自身は処理系で定義される組み込みの関数になっています。このような関数は,本文中で紹介した遅延評価の仕組みからは(少なくとも容易には)導き出せません。あまり深くは考えずに「処理系への指示の一種で,関数的なインタフェースを持たせたもの」ととらえてしまってよいと思います。

Prelude> seq ('r', "xy") 11
11
Prelude> seq undefined 11
*** Exception: Prelude.undefined
Prelude> seq ('r', "xy") undefined
*** Exception: Prelude.undefined
Prelude> twelve $ seq ('r', "xy") undefined
12
Prelude> twelve $! seq ('r', "xy") undefined
*** Exception: Prelude.undefined
Prelude> ('r', "xy") `seq` 11 `seq` "r"
"r"

 seqは,$!演算子の意味やsequenceの省略形を連想させる名前のイメージとは異なり,左側の項を評価してから右側の項を評価するという意味はありません。正格評価を行いたいだけであれば,項を正規形にするよう簡約を促せば十分だからです。

 評価の順序が問題になるのは,I/Oのように並列に行われうる計算を一つにまとめる場合だけです。このため,左側を評価してから右側を評価するというやり方で評価できる関数pseqは,標準Haskellの範囲内ではなく,並列計算を行わせるためのライブラリであるGHCのControl.Parallelモジュールに用意されています(参考リンク1参考リンク2)。ただし,Control.Parallelモジュールから利用できるようになるのはGHC6.8以降の話です。実のところ現行のGHC6.6では,GHC.Concモジュールから利用しなければなりません(参考リンク1参考リンク2)。

 pseqの使い方については,並列計算について説明する回に別途紹介しようと思います。今は,seqとpseqの間にこのような意味的な違いがあることがわかれば十分です。


著者紹介 shelarcy

 察しのよい方なら,今回の話で「なぜ遅延評価だと処理が速くなる場合と遅くなる場合があるのか」がわかるでしょう。遅延評価は簡約段数を減らす可能性がある一方で,簡約段数の同じ正格な式に対しては,遅延評価を実現するための仕組みを入れる分だけ様々な負荷が増えるからです。このあたりの話は込み入っているので,今回は詳しくは触れませんでした。次回以降,改めて説明していきたいと思います。