Haskellの言語仕様(ja)は式の評価順序を定めていないが、プログラムの計算量を見積もるには具体的な評価戦略を知っている必要がある。といっても事態は単純で、GHCを始めとする有名な処理系は全て「必要呼び(call by need)」という評価戦略を基本にしている。(「Haskellは遅延評価をする言語である」と言われるが、この「遅延評価」という語は必要呼びを指す)。そこで、必要呼びに従った評価を手動で再現することができれば、Haskellプログラムの計算量をおおざっぱに見積もることができる。以下ではその手順を紹介する。
普通の言語の評価戦略は値呼び(call by value)と呼ばれる。値呼びと対比したときの必要呼びの大きな特徴は、関数を呼ぶ際に、引数を未評価のまま渡すことである。次の関数を考える。
inc :: Int -> Int inc n = n + 1
これを使った「inc (7 + 8)」という式は、必要呼びに従うと以下のように評価される。
inc (7 + 8) -> (7 + 8) + 1 -> 15 + 1 -> 16
incの引数である式「7+8」は、incの適用の時点では評価されず、最終的に必要になって初めて計算される。比較のために、値呼びの場合は次のようになる。
inc (7 + 8) -> inc 15 -> 15 + 1 -> 16
ある引数が最終的に使われない場合、それは評価されないまま捨てられる。標準関数constは次のように定義できる。
const :: a -> b -> a const x _ = x
すると、式「const (1 + 2) (3 + 4)」は以下のように評価される。
const (1 + 2) (3 + 4) -> (1 + 2) -> 3
引数である「3 + 4」は評価されなかった。
必要呼び戦略のもう一つの特徴は引数の自動メモ化である。ある関数の仮引数が、その関数の本体に複数回出現したとしても、対応する実引数の評価は高々一回しか発生しない。例として次の関数を考える。
square :: Int -> Int square x = x * x
「square (4 + 2)」の評価は以下のように進行する。
square (4 + 2) -> (4 + 2) * (4 + 2) -> 6 * 6 -> 36
引数である式「4 + 2」の評価は一回だけである。実装としては、式「4 + 2」を表現するメモリ上のオブジェクトは一個だけで、それが二箇所から参照されており、評価が完了したときに破壊的に「6」に更新されると思えば良い。抽象的には、構文木を拡張して末端での共有を認めたグラフ構造を考え、それを操作していると言えるので、このテクニックをグラフ簡約という。
普通にテキストとして書くとこの共有構造が表現できないので、次のような記法を使うことにする。
square (4 + 2) -> x * x where x = 4 + 2 -> x * x where x = 6 -> 36
この「where」の使い方はHaskellの構文として正しくないが、言いたいことは分かると思う。
この評価戦略におけるlet式の評価は非常に単純で、次の一般形に従う。
let v = 式1 in 式2 -> 式2 where v = 式1
つまり、この時点では式1は全く評価されず、評価は必要になるまで遅延される。また、引数の場合と同様のメモ化が働くので、式1が複数回評価されることはない。
where節はlet式の構文糖衣とみなせるので、これと同様に評価できる。
ここまで見たように、必要呼びという戦略は、部分式をなるべく評価せずに済ませるものだと言える。では、部分式の評価が「必要」になるのはどういう時か。これは以下の場合である。
順に見ていこう。
Intの(+)や(*)が両辺の評価を強制する様子は、上のincやsquareの例で既に出ている。加算や乗算を行うためには両辺の式が評価済みでないといけない、というのは直感にも合致すると思う。なおGHCではIntも(+)も厳密な意味でのプリミティブではないが、ここでの議論には影響しないので無視する。
パターン照合では、照合するかどうかを決めるために対象の式を評価する。これに関して関数定義・case式・λ式のパターンは全て同じように振る舞う(実際、すべてcase式の構文糖とみなせる)。ただし、letやwhereにおけるパターン束縛は複雑なので後述する。
例のために、プレリュード関数nullとiterateを次のように定義する。
null :: [a] -> Bool null [] = True null _ = False iterate :: (a -> a) -> a -> [a] iterate f x = x : iterate f (f x)
「null (iterate negate 5)」を評価してみる。
null (iterate negate 5) -> null (5 : iterate negate (negate 5)) -- nullの定義の[]パターンに照合するためにiterateを展開 -> False -- []パターンに適合しないことが分かったのでnullの引数の評価は終了。nullを展開
なお、タプルのような構築子が一つしかないデータ型に対するパターン照合は、必ず成功するので評価の必要がないように思えるかもしれないが、実際には対象が⊥でないことを確認する必要があるので、構築子が明示される形になるまで評価しないといけない。
第三のケース、関数適用の場合。これは、適用する関数が不明では展開できないので、それが決まるまで評価する必要がある、というだけだ。
最後にseqの場合。弱頭部正規形とは次のものを指す。
例えば「44」や「Just (2 + 2)」や「\x -> 2 + 2」は弱頭部正規形である。データ構築子やλの中身は評価されている必要がない。一方、「2 + 2」や「not True」や「case Just 3 of Just n -> n; _ -> 3」は弱頭部正規形でない。
ここまで紹介した手順を手でなぞることで、コードの計算量をおおざっぱに見積もることができる。具体的には、評価完了までのステップ数で時間計算量を、最も長い途中式のトークン数で空間計算量を見積もる。例として、Haskellレポートにあるlength関数のリファレンス実装の時間・空間計算量を調べてみる。定義は以下の通り。
length :: [a] -> Int length [] = 0 length (_:l) = 1 + length l
これをreplicate 3 Trueというリストに適用することを考える。ここで使うreplicateの定義は以下。
replicate :: Int -> a -> [a] replicate 0 _ = [] replicate n x = x : replicate (n-1) x
length (replicate 3 True) -> length (True : replicate (3-1) True) -- lengthの[]と照合するためにreplicateを展開 -> 1 + length (replicate (3-1) True) -- lengthを展開 -> 1 + length (replicate 2 True) -- +の右辺を評価するためにlengthの[]と照合するためにreplicateを展開するために(3-1)を評価 -> 1 + length (True : replicate (2-1) True) -- replicateを展開 -> 1 + 1 + length (replicate (2-1) True) -- lengthを展開 -> 1 + 1 + length (replicate 1 True) -- 以下同様... -> 1 + 1 + length (True : replicate (1-1) True) -> 1 + 1 + 1 + length (replicate (1-1) True) -> 1 + 1 + 1 + length (replicate 0 True) -> 1 + 1 + 1 + length [] -> 1 + 1 + 1 + 0 -> 1 + 1 + 1 -> 1 + 2 -> 3
完了までに14ステップ掛かった。一般に、入力がreplicate N xならば必要ステップ数は4N+2になる。評価ステップの粒度を変えれば定数倍の違いは生まれるものの、この式の時間計算量をO(N)と見積もることができる。また、最大トークン数は2N+10なので、空間計算量もやはりO(N)であると推測できる。
lengthを効率化することを考える。時間がO(N)掛かるのは良いとして、空間計算量は改善の余地がありそうだ。「1 + 1 + 1 + ...」という、引数未確定の関数適用の長い列がメモリを大量に使っている。この手の振る舞いは、関数を末尾再帰形に変形できれば解消する。次のように。
length :: [a] -> Int length = len 0 where len n [] = n len n (_:l) = len (n+1) l
lenはlengthに「n」という蓄積引数を追加することで末尾再帰の形に変形したものであり、新しいlengthは単にlenに処理を移譲している。同様に評価を追跡してみる。
length (replicate 3 True) -> len 0 (replicate 3 True) -> len 0 (True : replicate (3-1) True) -> len (0 + 1) (replicate (3-1) True) -> len (0 + 1) (replicate 2 True) -> len (0 + 1) (True : replicate (2-1) True) -> len (0 + 1 + 1) (replicate (2-1) True) -> len (0 + 1 + 1) (replicate 1 True) -> len (0 + 1 + 1) (True : replicate (1-1) True) -> len (0 + 1 + 1 + 1) (replicate (1-1) True) -> len (0 + 1 + 1 + 1) (replicate 0 True) -> len (0 + 1 + 1 + 1) [] -> 0 + 1 + 1 + 1 -> 1 + 1 + 1 -> 2 + 1 -> 3
先程の問題は解消されたが、空間計算量はO(N)のままだ。lenの蓄積引数が未評価のまま大きくなっていくことが原因である。この引数はいずれ評価される運命だから、未評価の大きな式を持っておくことは完全な無駄である。このように未評価の式がメモリを圧迫する問題を空間リーク(space leak; スペースリーク)と言って、Haskellでありがちなパフォーマンスバグの一つだ。特にこのlenのような蓄積引数が空間リークを招くことが多い。幸いこのリークには簡単な解決策がある。seqを使って評価順を変えてやれば良い。
length :: [a] -> Int length = len 0 where len n [] = n len n (_:l) = seq n (len (n+1) l)
length (replicate 3 True) -> len 0 (replicate 3 True) -> len 0 (True : replicate (3-1) True) -> seq n (len (n + 1) (replicate (3-1) True)) where n = 0 -> len (0 + 1) (replicate (3-1) True) -> len (0 + 1) (replicate 2 True) -> len (0 + 1) (True : replicate (2-1) True) -> seq n (len (n + 1) (replicate (2-1) True)) where n = 0 + 1 -> seq n (len (n + 1) (replicate (2-1) True)) where n = 1 -> len (1 + 1) (replicate (2-1) True) -> len (1 + 1) (replicate 1 True) -> len (1 + 1) (True : replicate (1-1) True) -> seq n (len (n + 1) (replicate (1-1) True)) where n = 1 + 1 -> seq n (len (n + 1) (replicate (1-1) True)) where n = 2 -> len (2 + 1) (replicate (1-1) True) -> len (2 + 1) (replicate 0 True) -> len (2 + 1) [] -> 2 + 1 -> 3
これでO(1)空間で動作するようになった。
実際の処理系が上の必要呼び戦略を忠実に実行する保証はないし、事実GHCは最適化のために局所的に評価順を変更することがある。例えば、上記のseqを使わない末尾再帰版のlengthは、ghc -Oによって定数空間で動くコードにコンパイルされる。さらに一般にはseqの第一引数が第二引数より先に評価される保証すらない。
それでもこの素朴な必要呼びによる見積もりに意味があるのは、GHCがプログラマの心理モデルとしてこの評価戦略を想定しているからである。GHCはこの評価戦略を期待しているプログラマを落胆させないようなコードを生成しようとする。具体的には、最適化によって素朴な必要呼びより速くなることはあっても、顕著に遅くなることがないように努力が払われている。特に、必要呼びに比べてオーダーが違うほど非効率なケースはバグとして扱われている。直る見込みがないものもあるが。
上の必要呼びの追跡の応用で、IOを行うコードの計算量を見積もることができる。Haskellプログラムの実行の全体は次のように理解できる。
要するに、評価と実行を交互に繰り返していると考えることができる。なお例外や並行性の扱いは省いた。詳しくはTackling the awkward squadを参照。
これで、例えば「putStr (repeat '@')」というプログラムが定数空間で動作することが言える。まず必要な定義を用意する。
repeat :: a -> [a] repeat x = x : repeat x putStr :: [Char] -> IO () putStr [] = return () putStr (c:cs) = putChar c >>= \_ -> putStr cs -- putCharはプリミティブだと思っておく
実行は次のようになる。
main -> putStr (repeat '@') -> putStr ('@' : repeat '@') -> putChar '@' >>= \_ -> putStr (repeat '@') -> #<put-char-@> >>= \_ -> putStr (repeat '@') -- #<put-char-@>は「@を出力する」を意味するプリミティブなIO動作のつもり => (\_ -> putStr (repeat '@')) () -- ここで@を出力。結果()を得る -> putStr (repeat '@') -> 以下繰り返し...
Haskellの関数は同じ引数で呼ぶと同じ結果を返すので透過的にメモ化が可能だが、GHCはそれを行わない。局所的な最適化によってメモ化と同じ結果になることはあるが、一般には期待できない。メモ化が必要なら「引数->結果」の対応を保存するデータ構造(Map、Arrayなど)を明示的に用意する必要がある。
Haskellのリストは、遅延リストであることと変更不可(immutable)であることを除けば、普通の単方向リンクリストである。構文的に優遇されていて使いやすいデータ構造だが、用途によっては遅すぎることがある。
高速な添字アクセスが必要ならArrayが使える。ただしArrayは変更を加えるたびに完全なコピーが必要。頻繁な変更が必要なら、モナドを介してO(1)書き込みが可能なIOArray/STArrayか、添字アクセスと連結を含む幅広い操作が対数時間で可能なData.Sequenceを検討すると良い。
Data.Sequenceは先頭への追加/削除が償却定数時間で可能なのに加え、末尾への追加/削除も償却定数時間なので、キューあるいは両端キューとしても使える。
連想配列のような用途にはData.Mapが優秀。キーがIntで表現できるなら効率の良いData.IntMapが使える。キーがStringやByteStringなど、大小比較のコストが大きい型の場合はData.HashMapが良いようだ。
UArray、STUArray、IOUArrayは非ボックス化配列と呼ばれる。限られた型しか要素に持てず、さらに要素が遅延しない正格な配列で扱いにくいが、速度とメモリ使用の両面で通常のボックス化配列よりかなり効率が良い。これらは要するに生のメモリブロックをカプセル化したものである。
リストは末尾への追加が遅いが、単にリストを前から順番に構築していくだけなら、逆順で作っておいて最後にreverseするというシンプルな方法がある。
リストの各部分を構築してから任意の順序で連結したい場合、生のリスト[T]を使わずに、「後続のリスト」を受け取って最終結果を返す関数[T] -> [T]を使うというテクニックがある。リストの連結(++)は左側のリストの長さに比例する時間が掛かるのに対して、リスト関数の連結(.)は定数時間で終わることを利用する。これは標準のShowクラスでも使われていて、ShowS型がリスト関数に相当する。例として、次のように定義された二分木をリストに変換する問題を考える。
data Tree a = Bin (Tree a) (Tree a) | Tip a
次のように素朴に書くと、最悪で(たぶん平均でも)木の大きさの自乗に比例する時間が掛かる。
flatten :: Tree a -> [a] flatten (Tip x) = [x] flatten (Bin left right) = flatten left ++ flatten right
このテクニックを使うと次のようになる。これは線形時間で動作する。
flatten :: Tree a -> [a] flatten t = fla t [] fla :: Tree a -> [a] -> [a] fla (Tip x) = (x:) fla (Bin left right) = fla left . fla right
このような[T] -> [T]の関数は差分リストと呼ばれ、パッケージとしても用意されている。
Haskellの標準の文字列は[Char]だが、これが時間的にも空間的にも非効率すぎることが珍しくない。その場合は代替としてData.ByteString(バイト列)かData.Text(Unicodeテキスト)を検討すると良い。
パターン束縛を使った次の式を考える。
let (a, b) = f x in y a b
これは次のものの略記とみなせる。
let __tmp = f x a = case __tmp of (a, _) -> a b = case __tmp of (_, b) -> b in y a b
ちゃんと束縛が遅延することを保証するためにまわりくどい変換をしていて、相応の実行時コストがかかる。「f x」の評価を遅延させる必要がない場合は、letの代わりにcase式を直接使うことができる。
case f x of (a, b) -> y a b
これが美しくないと思うなら、びっくりパターン拡張(ja)(BangPatterns)を使って次のように書ける。
let !(a, b) = f x in y a b
なお、let式におけるパターン束縛の意味論はHaskellレポートに書いてあるが、letをcaseと遅延パターンで定義して、さらにcaseと遅延パターンを関数適用で定義するという形になっていて分かりにくい。
C++などに慣れていると戸惑うかもしれないが、GHCでは関数を細かく分けることによるオーバーヘッドは小さい。-Oオプションを渡せば適切にインライン化してくれる。関数が別モジュールにある場合でも、小さい関数についてはインタフェースファイルを介してインライン化が行われるので、実行時性能を犠牲にせずにデータ構造の実装を隠すことができる。インライン化はパッケージを跨いでも適用される(そうでなければIOモナドは今の100倍遅かっただろう)。($)や(.)を多用しても、それによって性能が悪影響を受ける心配は必要ない。
モジュールに分ける際、必要でない関数はエクスポートしないようにすると、GHCの最適化を阻害せずに済む。