第12章 遅延評価 #1

12.1 導入

一般的な命令型言語は、同じ式に対する評価順序が違うと結果が変わることがあるが、Haskellではどのような順序で評価しても(停止するのでない限り)同じ結果が得られる。

ぐぐってみたら、「チャーチ・ロッサー性」というのかな?

12.2 評価戦略

簡約可能式の簡約方法。

最内簡約
最も内側で最も左の簡約可能式から簡約する。λ式の内部を除いた最内簡約が値渡し。
最外簡約
最も外側で最も左の簡約可能式から簡約する。λ式の内部を除いた最外簡約が名前渡し。

最外簡約を選んだとしても、関数が正格だと、引数を評価してからでないと値が決まらない。

(追記)なにか違和感があると思って落ち着いて考えた。よくある値渡しと名前渡しの比較は、変数をどう渡すかの違いを見ている。ここでいう値渡しと名前渡しは、変数だけじゃなくて、式を渡すときの扱い方だ。

12.3 停止性

inf :: Int
inf =  1 + inf

このような関数は、値渡しでも名前渡しでも停止しない。 しかし、fst (0, inf)を評価する場合は、値渡しでは停止しないが名前渡しなら停止する。

一般的に言うと、名前渡しには次のような重要な性質がある。すなわち、ある式に対し停止する評価の手順が存在するなら、名前渡しはこの式の評価を必ず停止させ、同じ結果を返す。 とのこと。まあここでは証明とかは考えずに、とりあえずすんなり受け入れて次に進むか。

12.4 簡約の回数

square   :: Int -> Int
square n =  n * n

このような関数について、square (1 + 2)を考える。値渡しと名前渡しを比べると、名前渡しのほうが簡約の回数が増える。しかし、名前渡しであっても、引数をポインター(参照)で共有すれば、簡約結果も共有できる。このような、ポインター(参照)による共有を用いた名前渡しを遅延評価と呼んでいる。