はじめに
2016/2/14 開催の hs.hs 勉強会で以下の発表をしてきました。
これから Haskell を書くにあたって
さて、この内言語拡張の 1 つである Bang Patterns の説明について、誤りが発覚したため、ここで訂正も込みで再度説明しようと思います。
Bang Pattern とは
関数の引数を正格評価させるためにデザインされた言語拡張です。
使い方
特に難しい書き方や考え方が必要なわけではなく、LANGUAGE プラグマに Bang Pattern を記述し、関数の引数の直前に ! を付け加えるだけで適用できます。よく書かれる階乗計算を例にとってみましょう。
階乗計算から考える値の評価の仕方とスタック
fact 0 = 1
fact n = n * fact (n - 1)
何の変哲もない計算に見えます。しかし、気をつけなければならないことがあります。
- 引数の中身はパターンマッチが始まるまで評価されない
- 末尾再帰ではないので、このままでは領域から溢れてしまう。
(2)については、大事なことではあるものの、今回は Bang Pattern の説明に終始するため省きます。気になる方は末尾再帰最適化で調べてみるといいかもしれません。
(1)についてです。
Haskell では引数の特定のパターンに応じて処理を切り替える構文を持っています。それはパターンマッチといいます。引数のパターンとして使えるのは基本的に以下の 4 パターンです。
- 実の値
- 名前だけ
- アンダーバー
- as パターン(別名パターン)
実際のリテラルをマッチさせる
先の例でいうところの、 fact 0 = 1 がそのパターンです。これは、引数(Int/Integer型)として 0 がわたってきた場合に 1 を返す。見たまんまの定義です。
引数の名前だけを書く
先の例でいうところの、 fact n = n * (n - 1) がそのパターンです。
アンダーバー
アンダーバーが置かれた部分に渡された引数は、 使いもしないし評価もしない ものとして扱われます。つまり、何が渡ってきても、値を受け取る側はそれを無視するわけです。
f _ = ...
上記のコードは、本来受け取るはずの第一引数について何の処理も行いません。計算に使い回すことができなくなるのはもちろん、仮に受け取ってもそれは評価せずに右から左に流します。
as パターン
引数に別の名前を割り当てます。
f xxs@(x:xs) g
| null xxs = []
| otherwise = g x : f xs
上記のコードは、以下の 2 通りの動きをします。
- 渡された引数が null(nil) である場合は
[]を返す - それ以外の場合は、
xに関数gを適用し、残りの要素を再帰呼び出しに回し、次の要素を生成していく。
通常と同じように見えるこのコードですが、 as パターンは以下の 2 通りの使い方ができます。
-
(x:xs)のマッチ失敗を防ぐ -
(x:xs)のパターンから得られる値が必要なかった場合、xxsの方を次の関数に回せる(もちろんそのまま返り値にしてしまってもよい)
このパターンが実際にどう使われているかは各自調べてもらうこととします。
本題
この内、注意が必要なのは名前だけのパターンです。どういうことかというと、 Haskell では関数に渡された引数というのはパターンマッチの瞬間まで評価されません。パターンマッチの式に当てはめられるまで、中身にはタッチしないということなのです。このようなパターンのことを遅延パターンといいます。では、何がまずくて注意が必要なのかを説明していきます。
未評価値の行方
いくら遅延評価されるといっても、コンパイラがコードを解析すればいずれは評価されるタイミングに行き着きます。当然ながら、遅延しっぱなしで 1 度もその中身を使わないというのは、コーディングの効率的にも、計算の効率的にも全く無意味なことです。 GHC では基本的にはパターンマッチが始まるその瞬間まで、評価されていない引数の情報を別などこか(スタック)に溜め込んでおきます。そしてそれは、関数呼び出しの都度行われます。
問題は、その溜め込まれた情報の方にあります。今日のメモリがいくら 64 bit で従来よりも遥かに大きい量を積めるからといっても、それは無限ではありません。スタックについても同様です。よって、関数呼び出しの回数が多くなればなるほど、パターンマッチされていない間に受け取る値はどんどんスタックに積もり、最終的には溢れてしまいます。この現象をスペースリークといいます。
遅延評価から正格評価へ
ここで、先の階乗の例を振り返ってみます。
fact 0 = 1
fact n = n * fact (n - 1)
問題ないように見えますが、大アリです。修正あり(2016/2/15時点)
この fact n のパターンは、 n については、0に達するその瞬間までは中身には触れないということに注意が必要です。これは呼び出し回数が少ない内は正常に動作します。例えば、 n = 5 とか n = 10 とかその近辺であれば、スタックに積まれる値もそれほど多くはありません。しかし、実際に Haskell で何かを書くといった時に、それよりも遥かに多い回数で呼び出したりしなきゃ実装できないものがあるかもしれません。そうなると、スタック領域としてはお手上げです。だからといって、先の階乗の例だと、これ以上細かくパターンを分けることができません。そこで役立つのが Bang Patterns です。
びっくり！
実際に書くとこのようになります。
{-# LANGUAGE BangPatterns #-}
fact 0 = 1
fact !n = n * fact (n - 1)
n の直前にびっくりマーク ! がついています。これが Bang Patterns です。これにより、 n の値は受け取った直後に正格評価され、未評価なままスタックに積もるという遅延パターンのデメリットはなくなりました。
マッチしているわけではない
さて、このパターンですが、パターンマッチするものではないということに注意が必要です。実際の値はそのままに、正格評価を適用して束縛するための拡張であるということに留意してください。
スライド中の誤情報と訂正
私はスライド中(当該スライドの 149 頁)で、以下のように記しました。
当然ながら遅延評価ではないので、部分適用はできない
太字部分に誤りがあります。 Bang Patterns は、該当の引数について正格評価を適用すると言っているだけで、関数や式のルールそのものには何ら変更を加えていないのです。つまり、部分適用ができるということになります。例えば、以下のコードは正常に動作します。
{-# LANGUAGE BangPatterns #-}
f !x y = x + y
g = flip f 1
終わりに
今回は階乗の数値引数を例にとりましたが、この Bang Patterns はもっと様々なパターンに適用できます。詳しくは参考文献リンクを辿ってください。
参考文献
7.16 びっくりパターン - kotha.net
seq - Prelude
修正
先の階乗の例について、訂正があります。
{-# LANGUAGE BangPatterns #-}
fact 0 = 1
fact !n = n * fact (n - 1)
このコードですが、その引数の内容自体は評価されていることがわかりました(ruiccさんのご指摘)(ありがとう！)
本文との相違点は ruicc さんのご指摘の通りですが、念の為ここにも要点をまとめておきます。
- リテラル(実の値)パターンを含め、変数(名前だけ)パターン以外のあらゆるパターンは、該当する引数の評価を強制するものである(指定されたパターンとの比較のために、中身を都度見る必要がある)。
- Bang Patterns が効力を発揮するのは、この記事に限ってはパターンマッチが一度も行われていない(変数パターンしか存在しない)コードに対してである。つまり、上記のコードサンプルでは何一つ効力を発揮していない。
このことについて、より詳細な記事を確認したため、以下にそのリンクを記します。
Haskell スペースリーク Advent Calendar - Qiita(多くが ruicc さんの記事ですね。すごい…)
正格評価と遅延評価(詳細編) - Qiita
正格フラグ、バンパターン、正格版関数・データ構造 - モナドとわたしとコモナド
スペースリークと代数的構造 - Qiita
今回の誤記は、私のパターンマッチに対する勉強不足から来たものでした。なので、近々 GHC の仕様を読み直そうかなと考えています。