関数プログラミング実践入門 メモ - 第4章 評価戦略
関数プログラミング実践入門の4章「評価戦略」を読んだので簡単にメモ。
遅延評価(lazy evaluation)
- 実際に使うまで計算しないという計算順序の規則
- たらい回し関数(竹内関数)は、積極評価だと実行に時間がかかり、遅延評価だとすぐ完了する関数(の例)
- メジャーなプログラミング言語の殆どは「積極評価」。正確評価(strict evaluation)や先行評価、厳密評価とも。
- 遅延評価では「無限」を定義できる(実際に使われるまでは評価されないので)
- 人間にとって自然な(無限な)「数列」の定義と、その数列から値を取り出す、というのを分離できる。
評価戦略(evaluation strategy)
- 評価(evaluation)を行うときの計算順の決め方
- ラムダ計算では「簡約(reduction)」という変換操作を行うことで評価を進める。
(\x -> 変数xを含むかもしれない式A) 式B
を式A中の変数xをすべて式Bに置き換えた式
にするような変換規則。
- 式中のどの部分も簡約できない式を「正規形(normal form)」と呼ぶ。
- ラムダ計算が基礎となっている関数型言語において、評価戦略とは「簡約を行う順序の決め方」といえる。
積極評価(eagar evaluation)
最左最外簡約(leftmost-outermost reduction)
- 外側にあるものから
- 左側にあるものから
- を、優先的に簡約していく順序。
- 評価戦略としては「遅延評価」になる
- 最左最外簡約で停止しないラムダ式であれば、他のどのような簡約順を選んでも停止しない。(正規順序)
弱冠頭正規形(WHNF) - weak head normal form
- これ以上適用する値がない関数
- 式の先頭にコンストラクタが出た状態の値
- というところまで評価する、Haskellでの評価戦略。
isJust (Just (1 + 2))
という式では、(1 + 2)
の計算は実行されずにTrue
が得られる。(中身の値は関係ないので)
サンク(thunk)
- 「評価が行われないまま放置されている計算予定」オブジェクト
- 他の言語では「ラムダ式(関数)」を利用することで、同じようなことを実現できる。(関数を呼び出した時に、はじめて計算)
- サンクに予定されていた計算を発生させて値を得ることを「サンクを潰す」と表現する。
- Haskellでは「グラフ簡約(graph reduction)という仕組みで、同じ式が複数回登場する場合に最初の1回だけ評価される。
積極評価 vs 遅延評価
- 「積極評価」の方が、現在の計算機アーキテクチャと相性が良い。
- 「遅延評価」では、
- 必要のない計算を本当に行わないことで計算量を低減できる。(が、実際には稀)
- 「計算の定義」と「その実行」を区別できるため、モジュラリティが高い。(数列定義と取り出し操作など)
評価の制御
seq(seq :: a -> b -> b)
という関数を利用することで、サンクを潰せる。- 1つ目の値を「WHNFまで評価してから」2つめの値になる関数
- let xs = map (+1) [0, 1, 2] in xs
seq
xs ++ xs では、++
する段階でxs
が「WHNF」まで簡約されている
パフォーマンスチューニング
他の言語とチューニング方法は一緒。