読者です 読者をやめる 読者になる 読者になる

My Favorite Things - Coding or die.

とある技術者の経験記録、的な。

関数プログラミング実践入門 メモ - 第4章 評価戦略

関数プログラミング実践入門の4章「評価戦略」を読んだので簡単にメモ。

遅延評価(lazy evaluation)

  • 実際に使うまで計算しないという計算順序の規則
  • たらい回し関数(竹内関数)は、積極評価だと実行に時間がかかり、遅延評価だとすぐ完了する関数(の例)
  • メジャーなプログラミング言語の殆どは「積極評価」。正確評価(strict evaluation)や先行評価、厳密評価とも。
  • 遅延評価では「無限」を定義できる(実際に使われるまでは評価されないので)
  • 人間にとって自然な(無限な)「数列」の定義と、その数列から値を取り出す、というのを分離できる

評価戦略(evaluation strategy)

  • 評価(evaluation)を行うときの計算順の決め方
  • ラムダ計算では「簡約(reduction)」という変換操作を行うことで評価を進める。
    • (\x -> 変数xを含むかもしれない式A) 式B
    • 式A中の変数xをすべて式Bに置き換えた式にするような変換規則。
  • 式中のどの部分も簡約できない式を「正規形(normal form)」と呼ぶ。
  • ラムダ計算が基礎となっている関数型言語において、評価戦略とは「簡約を行う順序の決め方」といえる。

積極評価(eagar evaluation)

  • 関数型言語でも積極評価を採用している言語は多い。
    • Haskell使いでも”Haskellが積極評価だったら良かったのに”という意見を述べる人も。

最左最外簡約(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」まで簡約されている

パフォーマンスチューニング

他の言語とチューニング方法は一緒。

  • パフォーマンスを計測する
  • 問題箇所を潰す
  • 積極評価の言語でも、ラムダ式などを利用することで「関数呼び出しを行うことで評価される」仕組みを作れる。