sicp 習題1.5 正則序和應用序求值疑問?

SICP 1.5 習題：

(define p (p))
(define test (lambda (x y) (if (= x 0) 0 y)))


(test 0 (p))

問正則序和應用序的求值結果是什麼？

如果是正則序，代換形參之後，得到

(if (= 0 0) 0 (p))


，應用if的語法，求值0

如果是應用序，代換形參之後，得到

(if (= 0 0) 0 (p))


，之後會繼續代換p，無限遞歸下去，解釋器掛掉。

疑問：

對於求n!得遞歸函數

(define fact (n) (if (= n 1) 1 (* n (fact (- n 1)))))


(fact 10)
(if (= 10 1) 1 (* 10 (fact 9)))


接下來是直接應用if的語法，還是代換

(fact 9)


?為什麼？

---

對lambda表達式不熟，改寫問題中表述的SICP 1.5習題為：

(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))


求

(test 0 (p))


第一步替換成

(if (= 0 0) 0 (p))


如果對if進行應用序解釋，注意到if有3個參數，應用序對每一個參數求值，然而(p)是無限遞歸，進入死循環。

如果對if進行正則序解釋，可以理解為對if的參數lazy求值，用到哪個參數才對這個參數求值。

那麼階乘函數 (fact n) 呢？

如果 if 是應用序，有以下代換過程，

(fact 10)
(if (= 10 1) 1 (* 10 (fact 9)))
(if (= 10 1) 1 (* 10 (if (= 9 1) 1 (* 9 (fact 8)))))
(if (= 10 1) 1 (* 10 (if (= 9 1) 1 (* 9 (if (= 8 1) 1 (* 8 (fact 7)))))))
...
...
(if (= 10 1) 1 (* 10 (if (= 9 1) 1 (* 9 (if (= 8 1) 1 (* 8 5040)))))) ;;7!=5040
(if (= 10 1) 1 (* 10 (if (= 9 1) 1 (* 9 40320)))) ;;8!=40320
(if (= 10 1) 1 (* 10 362880)) ;;9!=362880
(if (= 10 1) 1 3628800) ;;自此對所有的參數求值
(3628800) ;;以後舉例子請用小一點的參數


如果 if 是正則序 （Scheme解釋器用正則序解釋 if ），有以下代換過程，

(fact 10)
(if (= 10 1) 1 (* 10 (fact 9)))
(* 10 (fact 9)) ;;應用 if 規則之後
(* 10 (if (= 9 1) 1 (* 9 (fact 8))))
(* 10 (* 9 (fact 8))) ;;應用 if 規則之後
...
...
(* 10 (* 9 (* 8 (* 7 (* 6 (* 5 (* 4 (* 3 (* 2 (1))))))))))
...
...
(3628800)


我們平時描述遞歸代換過程時，為了簡潔清晰，將 if 的正則序解釋步驟省略，就是這樣，

(fact 10)
(* 10 (fact 9))
(* 10 (* 9 (fact 8)))
...
...
(* 10 (* 9 (* 8 (* 7 (* 6 (* 5 (* 4 (* 3 (* 2 (1))))))))))
...
...
(3628800)


我想細心的同學看到區別了，在 (fact n) 這樣的函數中，把 if 解釋成正則序和應用序不會對結果產生影響，只是複雜度（時間 or 空間）不同。但是在有一些函數中，把 if 解釋成應用序就會出現問題，具體請看SICP，開平方函數中用 new-if(應用序) 代替 if(正則序) 出現的不可預期的結果。因為自己也是初學，先不寫了。

---

; 首先讓我們認真地看一下何謂應用序, 何謂正則序.

; 應用序 (applicative-order) 以類似 depth-first 的方式展開, 即

; To evaluate a combination, do the following:

; 1. Evaluate the subexpressions of the combination.

; 2. Apply the procedure that is the value of the leftmost subexpression

; (the operator) to the arguments that are the values of the other

; subexpressions (the operands).

; 即先求子表達式的值, 然後應用 leftmost element / operator / procedure 到 arguments 上(為了方便理解, 可以認為總是先展開 argument, 再展開 procedure).

; 注意書上(1.1.3 Evaluating Combinations)說:

; Even this simple rule illustrates some important points about processes in general. First, observe that the first step dictates that in order to accomplish the evaluation process for a combination we must first perform the evaluation process on each element of the combination. Thus, the evaluation rule is recursive in nature; that is, it includes, as one of its steps, the need to invoke the rule itself.

; 這段話的意思是說, evaluation 這個動作自身是一個遞歸的過程, 這個遞歸過程包含求值(evaluate)和應用(apply)兩步. 如果對一個複合表達式(combination) 進行求值的話, 首先要對其子表達式求值, 而對子表達式求值很顯然又包含對子表達式的子表達式求值和應用子表達式的 leftmost element. 這個求值遞歸當然會結束, 結束條件就是子表達式為基本表達式的時候, 也即遞歸樹的葉子節點. 這裡要注意, leftmost element 一般是一個 procedure.

; on the oppsite, 正則序 (normal-order) 以類似 breadth-first 的方式展開, 即總是先展開 leftmost element / procedure, 而展開 procedure 的方式是不斷使用實際參數 actual-arguments 去替換(substitute / replace) procedure & 中的形式參數 formal-parameters.

; (注意過程定義的上下文無關語法, context-free grammar 之一是:

; (define (& &) &)

; 其中 &<&> 及其內的是非終結符/變元, 其它的字元是終結符)

; 當然不論 applicative-order 還是 normal-order, 調用一個 procedure 時的語義就是將此 procedure 的 & 替換為 actual-arguments.

; OK, 回到這個問題,

; (define (p) (p))

; (define (test x y)

; (if (= x 0)

; 0

; y))

; (test 0 (p))

; 1. applicative-order:

; --&> 用 actual-arguments 替換 formal-parameters:

; (test 0 (p))

; 現在開始為各個子表達式求值, test 的值就是 (if (= x 0) 0 y), 接下來 0 的值當然就是 0 自己, 當 eval (p) 的值時, 根據 (define (p) (p)), 這很顯然會陷入無限遞歸.

; 2. normal-order:

; --&> 用 actual-arguments 替換 formal-parameters:

; (test 0 (p))

; 接下來將 test 求值(eval), test 的值是:

; (if (= x 0) 0 y)

; 接下來是 apply(將實際參數替換 procedure &, 注意, 不需要 eval arguments):

; ((if (= x 0) 0 y) 0 (p))

; 替換為

; (if (= 0 0) 0 (p))

; 由於 if 是特殊規則, 它的求值順序總是一樣的:

; (if #t 0 (p))

; 0

; 所以 applicative-order 是, 先 eval 每一個 sub-expression, 然後再 apply;

; on the other side, normal-order 則是, 先只 eval leftmost element, 然後直接apply/subsitute left(剩下的, rest remaining) elements 到 leftmost element 的 &.

; 由於 SICP 已經提及 scheme (基本上)是 applicative-order 的

; 1.1.5 The Substitution Model for Procedure Application

; Applicative order versus normal order

; Lisp uses applicative-order evaluation, partly because of the additional efficiency obtained from avoiding multiple evaluations of expressions such as those illustrated with (+ 5 1) and (* 5 2) above and, more significantly, because normal-order evaluation becomes much more complicated to deal with when we leave the realm of procedures that can be modeled by substitution.

; On the other hand, normal-order evaluation can be an extremely valuable tool, and we will investigate some of its implications in chapters 3 and 4.

; 實際上, normal-order 就是所謂的惰性求值(這個需要高手再確認一下). 書中已經說過, normal-order 會導致重複計算. 分別用 applicative-order 和 normal-order 展開遞歸樹就可以看到這一點. 不過, 裡面的重複計算是可以被優化掉的, 優化的方式是將遞歸樹中, 調用重複子樹的節點全部 share 到一顆子樹上, 這樣遞歸樹就會成為有向無環圖(某個子結點有多個父結點). 一般當解釋器做惰性求值的時候, 會做這種 share 優化.

; 所以, 如果你使用 DrScheme, 現名 DrRacket, 就有下面的 test:

; 如果使用 #lang racket / scheme 則會陷入無限遞歸
; 如果使用 #lang lazy 則會得到 0
; now test the procedure...

#lang racket

(define (p) (p))

(define (test x y)
(if (= x 0)
0
y))

(display "this procedure will cause dead loop.")
(newline)
(test 0 (p))


; 至於 LZ 問的 fib, 我認為只要認真理解我上面說的東西, 則根本不是問題. 注意 if 是特殊形式, 也就是它的求值是有順序的, 不會對每個子表達式都求值. 實際上 SICP 的 ex1.6, 那個 new-if 已經非常明確地指出了這一點.

---

這個是直接使用if的語法的, if作為一個內置的元素沒有交給使用者自己實現就是因為它的求值方式不一樣, if的兩個分支不能被首先求值而要先進行判斷,再對相應分支進行求值.如果對此還有什麼疑問,可以參考後面的習題1.6, 那個new-if的問題.

---

題目描述中，(test 0 (p))的正則序求值沒有問題，問題在於應用序求值時是先對(p)進行代換導致無限遞歸，而不是先對test進行代換，題主可能是在這裡沒有搞明白所以認為是表達式(if (= 0 0) 0 (p))出現無限遞歸。其實按照if表達式的求值方式，表達式(if (= 0 0) 0 (p))的值在應用序下也是0。

---

推薦閱讀：