LISP Scheme Part2

正規順序って要は遅延評価でしょ?

多分違う。

多分だが、遅延評価というのは、
いわゆるcall-by-needと言われる奴で、
正規順序というのは、
call-by-nameとか言われる奴だったと思うが。
自信無いんで適当に調べてくれ。

じゃあ、kawaはcall-by-needだな。

>>744
ちがうって。kawaはただのcall-by-valueだよ。

call-by-nameで生じる無駄な計算を避けるのがcall-by-need。

call-by-name (normal order):
((lambda (x) (+ x x)) (* 10 10))
-> (+ (* 10 10) (* 10 10))
-> (+ 100 (* 10 10))
-> (+ 100 100)
-> 200

call-by-need だと、(* 10 10)をコピーせずに、同じ式を
共有して
((lambda (x) (+ x x)) (* 10 10))
-> (+ (* 10 10) (* 10 10))　　　　;　2つの(* 10 10)は同一のセルで表す
-> (+ 100 100)
-> 200
みたいになる。

delayとforceを使った場合、forceするたびにdelayの引数を計算
しなおすとcall-by-name。一度forceされたら結果をキャッシュして
計算し直さないのがcall-by-need。(ふつうの実装は後者。)

>>740

normal formが存在するならば、正規順序の簡約で必ずnormal form
に到達できるという保証がある。つまり、止まるプログラムなら正
規順序で評価すれば必ず止まる。正規順序で止まらないプログラム
はどうやっても止まらない。

作用順序簡約にはその保証がない。正規順序なら止まるプログラム
も、作用順序だと止まらないかもしれない。そういうプログラムの
例が >>725

他にも、
(define infinite-list (cons 1 infinite-list))
(caddr infinite-list)
なんていうのは、正規順序の言語なら止まるが、Schemeのような作
用順序の言語では止まらない。

MLやSchemeのような作用順序の言語に比べて、正規順序で評価する
と >>745 のように無駄な評価が生じて桁違いに遅くなる。そこで
開発されたのがcall-by-need (graph reduction, fully lazy
reduction)。能力は正規順序と同じで、効率が良い。Haskellや
Cleanはfully lazyな言語。

昔、リストのアドレスに対してhash値を適用できないか質問した者です。
あれから、gc直後をフックする様にして、
hash-object毎にrehashする関数をフックに登録する方法で
なんとかできました。結果、物凄く速くなりました。
答えてくれた方、ありがとうございました。

かなり昔になんかで勉強したが、
一般に、実引数の評価時期（評価順序）は、3つに分けられるらしい。
1.eager-evaluate
2.lazy-evaluate
3.normal-order

んで、1.は、cとかpascalで一般に行われているようなものをいう。
これは、簡単なんだが、不必要な引数（！）まで評価してしまう。
2.は、必要な時に評価されるが、それは最初だけで、
次から同じ物が出てきた時には、どっかに取っておいた最初の評価結果を使う。
3.は、必要な時に評価されるのは同じだが、その評価結果は取っておかないで、
いつもいつも評価する。自明のことだが、これは不効率ということになる。

2.3は関数プログラミングでは、有効とされている方法らしい。今思い出した。

んで、1の不必要な評価って言うのが、例えば、次のような奴。多分。

int f(void){return f(void);}

void g(int a, int b){cout << "a has " << a << endl;}

ここで、g(1,f());とかやると、終了しなくなる。
これが、正規順序だと、f()は評価されないまま終了できる。

つーことらしい。

しかし、考えてみれば分かるが、C/C++とか使っている限りでは、
こんなプログラミングはしない。
そのことよりも、lazy-evaluationをやることのオーバーヘッドが気になってしまう。
まあしかし、最近はほとんど問題にならないということらしいが詳しいことは知らん。