関数プログラミング実践入門 メモ - 第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
seqxs ++ xs では、++する段階でxsが「WHNF」まで簡約されている
パフォーマンスチューニング
他の言語とチューニング方法は一緒。
