学習の素材は、
関数プログラミング実践入門
この表記は、私見・感想です。
評価戦略と遅延評価
遅延評価は、評価戦略( evaluation strategy ) の一種である。評価戦略とは、与えられた式を計算し結果を得る、つまり 評価( evaluation )を行う時の計算順の決め方のことである。
どう順番で評価をすすめていき、どういう状態になったら評価が停止 / 終了するのかによって、評価戦略が決まる。特に、関数や手続き( 数学的な意味の関数ではなく、命令型言語におけるいわゆる関数 )の引数に対し、評価済み状態にしてから渡すかどうかが着目される。
評価 とは、与えられた式を計算して結果を得ることをいう。
簡約
関数型言語の理論的背景は ラムダ計算 であり、ラムダ計算では 簡約 ( reduction )という変換操作を行うことで評価を進める。簡約とは、ラムダ計算における関数適用の規則であり、
(\x -> 変数xを含むかもしれない式A) 式B を 式A中の変数xをすべて式Bに変えた式 とするような変換規則のことである。
(\x -> x + 2) 3
-- => 2 + 3 -- \x -> x + 2 を簡約
-- => 5
正規形
式に対して簡約を進めていくと、これ以上、式中のどの部分についても簡約できない式になることがある。つまり、関数がないか、関数があるが適用される値がないような形である。ここまで簡約された式を、特に 正規形 (normal form) と呼ぶ。
簡約
簡約の実行方法は一つではない。
(\x -> x + x) ((\x -> x * x) 1)
のような式があるとき、
(\x -> x + x) ((\x -> x * x) 1)
-- => (\x -> x + x) (1 * 1)
-- => (\x -> x + x) 1
-- => (1 + 1)
-- => 2
という順番で実行する簡約もあるし、
(\x -> x + x) ((\x -> x * x) 1)
-- => ((\x -> x * x) 1) + ((\x -> x * x) 1)
-- => (1 * 1) + ((\x -> x * x) 1)
-- => 1 + ((\x -> x * x) 1)
-- => 1 + (1 * 1)
-- => 1 + 1
-- => 2
という簡約もあり得る。
評価戦略とは、「簡約を行う順番の決め方」と言える。
順番による結果の違い
(\x -> x x) (\x -> x x)
この式を簡約すると、
(\x -> x x) (\x -> x x)
-- => (\x -> x x) (\x -> x x)
-- => (\x -> x x) (\x -> x x)
-- ...
といった具合に、同じ形の式になり続ける。つまり無限ループに陥ることになる。
ここで、もう一つのラムダ式 \x -> (\y -> x) を用意する。この式は、引数xを取ると、何を取ってもxとなるラムダ式である。このラムダ式を上記の無限ループになるラムダ式と一緒に使うと、次のようになる。
((\x -> (\y -> x))1) ((\x -> x x) (\x -> x x))
この時、引数となる ((\x -> x x) (\x -> x x)) を簡約すると、同じように無限ループとなる。
一方、((\x -> (\y -> x))1) から簡約を始める形だと、
((\x -> (\y -> x))1) ((\x -> x x) (\x -> x x))
-- => (\y -> 1) ((\x -> x x) (\x -> x x)) -- (\y -> 1) はどのような引数を取っても 1 になる関数なので
-- => 1
となる。
個人的には、この考え方が非常に重要（理解のための考え方の転換点）と感じた。
積極評価
積極評価 (eagar evaluation) は、評価できる箇所をさっさと評価してしまい、できるだけすでに評価済みで、それ以上評価する必要のない値に落とし込もうとする評価戦略である。正格評価(strict evaluation)、先行評価 、厳密評価 とも呼ばれる。
既存のメジャーな命令型言語はほぼ積極評価になっていて、例えばC言語でf( g1(), g2(), g3() ) のような呼び出しがった時、手続きf の呼び出し時には３つの引数がすでに「値になっている」はずである。ただし、引数の手続きg1() g2() g3() が「どの順で実行されるか」は不定である。
- 手続きの呼び出しの際には、引数は値になっている
- 各引数が値になる順番は決めない( コンパイラ依存 )
上記がC言語の評価戦略と言える。
命令型言語に慣れている我々にとっては馴染みやすい評価方法である。
遅延評価
遅延評価( lazy evaluation )は、実際に評価が必要とされるまで評価を行わない評価戦略である。 非正格評価 ( non-strict evaluation )と呼ぶ。
最左最外簡約
- 外側にあるものから
- 左側にあるものから
を優先的に簡約していくという順序の選び方があり、最左最外簡約( leftost-outermost reduction )と呼ぶ。
((\x -> (\y -> x))1) ((\x -> x x) (\x -> x x))
-- => (\y -> 1) ((\x -> x x) (\x -> x x)) -- どのような引数を取っても 1 になる関数なので
-- => 1
これは最左最外簡約である。このような簡約順を、正規順序( normal order )と呼ぶ。
弱冠頭正規形( WHNF )
Haskell の遅延評価では、式を評価するときに、
- これ以上適用する値がない関数
- 式の先頭にコンストラクタが出た状態の値
というところまで評価を行う。これは、弱冠頭正規形( weak head normal form )呼ばれる。
この規則では、例えば、Maybe 型の ( Just 式 ) という式があるときには、Just の中身である式の部分が、たとえまだ評価できる形をしているとしても、その必要がなければ評価されずに残される。
isJust :: Maybe a -> Bool
isJust Nothing = False
isJust (Just _) = True
この関数に、Just (1+2) を適用しても、(1+2) の計算は実行されることなくTrue が得られる。
「 a の値がプレースホルダの状況で、右辺の先頭に
Trueというコンストラクタが出た。この段階で特定の値( True )を返すことができるようになったので、a については評価しなかった」、ということか。
弱冠頭正規形は、データ構造の評価タイミングと、そのデータ構造の中身に入っている値の評価タイミングを分離している。
たとえばリストの長さを求めるためには、リストのデータ構造が必要になる。(:) によりデータ構造としてまだ先があるのか、それとも[] によりデータ構造としてここで終わりなのかが重要になる。その一方で、リストの中身であるひとつひとつの要素については長さを求めるだけなら不要になる。
データ構造だけわかれば望む結果が得られるのであれば、データ構造の中身に入っている値の評価はしない規則なので、データ構造の中身が実行時エラーとなる原因を含んでいたとしてもこの場合は発現しない。このように、目的に対して不必要でかつエラーを出すかもしれない計算が行われないということは良いことである。
サンク
Haskell の遅延評価では、必要とされるまで評価を行わないが、代わりに 評価が行われないまま放置されている計算予定 オブジェクトが作られる。このオブジェクトのことを サンク(thunk) と呼ぶ。サンクは、Haskell の遅延評価を実現しているしくみのひとつである。サンクの結果が必要とされて計算が発生する、あるいは計算を発生させて値を得ることを「サンクを潰す」ということがある。
サンクは、評価され、評価結果の値を残したらお役御免となり、ガーベジコレクションの対象となる。不必要だったサンクは、そのままガーベジコレクションの対象となり消えていく。
この文脈でいう「オブジェクト」は、OOPでいうオブジェクト（クラスのインスタンス）と同じような概念で捉えるとややこしくなる。単純に、ヒープ領域に確保された、動的にメモリを利用する要素 くらいに思っておく。
積極評価と遅延評価の、利点と欠点
| 評価戦略 | メリット | デメリット |
|---|---|---|
| 積極評価 | 現在の計算機アーキテクチャとの相性の良さ |
無限列を生成できない（無限列を定義し使ったら、実際に無限個作ってしまう） 必要ないかもしれない計算を行うことによるコスト |
| 遅延評価 | 必要のない計算は行わないことによる計算量の低減 無限列を生成し、そこから指定個取り出せる |
使われないかもしれない計算予定を作るコスト 作った計算予定を破棄するコスト サンクがメモリを圧迫することがある パフォーマンスチューニングの難しさ |
積極評価と遅延評価にはそれぞれにメリット・デメリットが存在していて、真に決着することはしばらくない、とした上で、遅延評価なら、定義と実行が同時に行われないことにより、人間の感覚では無限に再帰させるような定義が自然な定義であるような部品に対して、言語の都合に合わせて定義の仕方を歪める必要がない と記述されている。このようなコードを書ける点に多くの人が魅力を感じるのではないか。