第8回　遅延評価の仕組み

ITpro

2007.03.07

　これまでの回で，何度か遅延評価の持つ性質について語ってきました。皆さんの頭の中には，すでに遅延評価に対して「なんとなくこういうものだ」という漠然としたイメージができていると思います。

　多くの場合にはそうした漠然としたイメージだけでも十分なのですが，それでは困る場合もあります。例えば，プログラム全体の最適化（optimization）のために関数やデータ構造の効率化（efficiency improvement）を図ろうとする場合，遅延評価に対する理解がなければ完全に手探りで行うしかありません。

　残念ながら，前回のIOモナドと同様に，遅延評価を実現するための仕組みもまた，Haskell標準ではほとんど触れられていません。実装のための余地を残しておくためです。ただ，IOモナドの場合と同様に，「このようなモデルで，このような性質を持つ」という仕様外でのだいたいの合意は存在します。

　そこで今回は，こうしたモデルを中心にHaskellの遅延評価について説明していきたいと思います。

正格と非正格

　前回，正格・非正格という言葉について少しだけ触れました。まずは，この言葉の意味について説明しましょう。

　iterate関数を使ったプログラムや第4回で取り上げた素数を列挙するプログラムなど，無限の長さを持ち得る値を扱う場合，その値を使用する式によってはいつまでたっても計算が終了しない可能性があります。このように計算が停止しないことと，エラーが生じることの区別はHaskellプログラムにはできません。そのため，これらをまとめて⊥（底要素，bottomあるいは省略してbot）と表現します（参考リンク）。

　Preludeにはこうしたエラーを直接引き起こすための関数として，errorと「未定義であることを示す」undefinedの二つが用意されています。値が⊥であるときにその答えも⊥となるような式のことを正格であるといい，そのような関数を正格関数と呼びます。逆にそうでないものを非正格であるといい非正格関数と呼びます。

Prelude> undefined
*** Exception: Prelude.undefined
Prelude> id undefined
*** Exception: Prelude.undefined
Prelude> let twelve x = 4 + 8
Prelude> twelve undefined
12
Prelude> error "error occur"
*** Exception: error occur
Prelude> id $ error "error occur"
*** Exception: error occur
Prelude> twelve $ error "error occur"
12

　この例から，idが正格であるのに対し，let式で定義したtwelveは非正格であるのがわかると思います。

　さて，標準Haskellにおける遅延評価の意味論（semantics，セマンティクス）は，非正格関数を可能とするための⊥という値の定義とその扱いにもっぱら充てられています。どのような仕組みの下であっても遅延評価が達成できればよいという立場からすれば，このやり方は合理的です。しかし，遅延評価を学ぼうとする立場からすれば，詳細ばかり記述していてざっくりとしたモデルを紹介してくれない標準は不便です。そこで，ここでは標準の仕様はひとまず脇において，遅延評価のモデルについて説明したいと思います。

名前呼び出しと必要呼び出し

　遅延評価のための評価戦略としてよく説明されるのが，「名前呼び出し（call-by-name，名前渡し）」または「必要呼び出し（call-by-need，必要渡し）」です。実際のHaskellの処理系では必要呼び出しがよく使わます。ただ，必要呼び出しは名前呼び出しに機能を追加したものなので，名前呼び出しについて先に説明することにします。

　名前呼び出しとは何でしょうか？先ほどのtwelve関数について考えて見ましょう。遅延評価を持たない一般的なプログラミング言語では，その値が必要かどうかにかかわらず関数を適用する値を先に評価してから関数を評価する「値呼び出し（call-by-value，値渡し）」という戦略を採用しています。このため，遅延評価とは異なり，twelveを⊥に適用した結果として⊥が返ることになります。

　プログラムの効率化のために，Preludeには$!という値呼び出しでの関数適用（正格適用）を行うための演算子が用意されています。なので，これを用いて値呼び出しについて見ることにしましょう（演算子$!は上でも使用している非正格適用演算子$の親戚にあたるものです。参考リンク）。

Prelude> :t ($)
($) :: (a -> b) -> a -> b
Prelude> :t ($!)
($!) :: (a -> b) -> a -> b
Prelude> twelve $! undefined
*** Exception: Prelude.undefined
Prelude> twelve $! error "error occur"
*** Exception: error occur

　先に説明したように，値を先に評価した結果⊥が返っていることがわかりますね。

　これに対して名前呼び出しでは，twelveの答えを求めるのにxは本質的に必要ではないため，xを評価せずに12という答えを返しています。このように名前呼び出しでは，式の内側で使われている変数からではなく外側の式から先に評価を始め，その評価に必要な変数だけを評価することになります。

　さて，それでは名前呼び出しと必要呼び出しはどう違うのでしょうか？それについて知るには，簡約（reduction）モデルについて見てみるのがよいでしょう。簡約（あるいは簡約化）とは，式の関数を定義に置き換えていくことで「最も単純な等価な形」に書き換えることです。

　それではtwelve undefinedがどのように簡約されるか見てみましょう。twelve関数を値に適用することはラムダ抽象化してから適用することと等価なので，ここではわかりやすさのためにラムダ抽象化してから簡約することにします。

   twelve undefined
= (\x -> twelve x) undefined
=> (\x -> 4 + 8) undefined
=> (\x -> 12) undefined
=> 12

（正確には，名前呼び出しではラムダ抽象の内部を簡約させる必要はありません。ラムダ抽象内部の式の簡約は値に適用するまで遅延され，(\x -> twelve x) undefined => twelve undefined => 4+8 => 12のような形で簡約することになります。ただ，それではラムダ抽象化させた意味がないので，ここではラムダ抽象内部の式を先に簡約させることにしています）

　次にtwelve xの結果を2乗する計算，(twelve x)^2を簡約してみましょう。標準Haskellでは，演算子(^)は以下のように定義されています（参考リンク）。

(^)              :: (Num a, Integral b) => a -> b -> a
x ^ 0            =  1
x ^ n | n > 0    =  f x (n-1) x
                    where f _ 0 y = y
                          f x n y = g x n  where
                                    g x n | even n  = g (x*x) (n `quot` 2)
                                          | otherwise = f x (n-1) (x*y)
_ ^ _            = error "Prelude.^: negative exponent"

　第5回で説明したように，パターン照合はcase式の構文糖衣です。また，|の後ろに記述されている「ガード（guard）」も，case式の意味論の下で（if文を使った）条件式に置き換えることが可能です（参考リンク）。したがって，だいたい以下のような感じで簡約できます。

   (twelve undefined)^2
=> case 2 of
     0 -> 1
     n -> if n > 0 then f (twelve undefined) (2-1) (twelve undefined)
                   else error "Prelude.^: negative exponent"

=> if 2 > 0 then f (twelve undefined) (2-1) (twelve undefined)
            else error "Prelude.^: negative exponent"

=> f (twelve undefined) (2-1) (twelve undefined)

=> case (2-1) of
     0 -> (twelve undefined)
     n -> (g (twelve undefined) n (twelve undefined)) (twelve undefined)

=> case 1 of
     0 -> (twelve undefined)
     n -> (g (twelve undefined) n (twelve undefined)) (twelve undefined)

=> (g (twelve undefined) 1 (twelve undefined)) (twelve undefined)

=> if even 1 then g ((twelve undefined)*(twelve undefined)) (1 `quot` 2)
    else f (twelve undefined) (1-1) ((twelve undefined)*(twelve undefined))

=> f (twelve undefined) 0 ((twelve undefined)*(twelve undefined))

=> (twelve undefined)*(twelve undefined)
=> (4 + 8) * (twelve undefined)
=> 12 * (twelve undefined)
=> 12 * (4 + 8)
=> 12 * 12
=> 144

　簡約段階（reduction step）の最後のほうで，twelve undefinedが項ごとに別々に計算されていることに気づいたでしょうか？名前呼び出しでは，このように項が重複して登場する度に，それぞれの項を別々に簡約しなければなりません。(twelve undefined)*(twelve undefined)ぐらいならどうということはありませんが，項の数が増えたり項を簡約するのに必要なステップ（段数）が増えるにつれて，こうした無駄は大きな負担になってきます。どうにかならないでしょうか？

　この問題を解決するのが必要呼び出しです。必要呼び出しでは，同じ変数から束縛された項はポインタによって共有され，一度簡約された項をもう一度使用する場合には最初の計算によってキャッシュされた解を利用します。項を共有することにより，構文はもはや通常の木構造ではなくグラフ（graph）構造を取ることになります。そのため，このような簡約方法を「グラフ簡約（あるいはグラフ簡約法，graph reduction）」と呼びます。また，同じ式の評価のために，キャッシュされた解を使う手法のことを「メモ化（memoization）」といいます。