本篇是我對 SICP 第 1.6 題的試解。這一題同樣屬於理解題,核心在於弄清 Scheme 中特殊形式 if 與使用者自訂 procedure 之間的本質差異。
; ====================================================================== ; Structure and Interpretation of Computer Programs ; (trial answer to excercises) ; 電腦程式的構造與解釋(習題試解) ; created: code17 02/24/05 ; modifIed: ;(在保持內容完整不變的前提下,可以任意轉載) ; ====================================================================== ;; SICP No.1.6 ;; 本題為理解題 ;; 若把 special form "if" 看作普通 procedure,把子句(clause)看作參數(operands), ;; 那麼它與使用者可定義的 "new-if" 的區別在於:if 的參數 <predicate> <then-clause> ;; 和 <else-clause> 不需要在代入前 evaluate,這相當於採用了 normal-order evaluation, ;; 而不是 scheme 普通 procedure 採用的 applicative-order evaluation。then 子句與 else ;; 子句中的一個,只有在被需要時才會 evaluate,而另一個根本不會被 evaluate。但使用者定義 ;; 的 procedure "new-if" 的三個參數表達式,則都必須在代入前 evaluate。 ;; ;; 因此,我們可以很容易推斷出 new-if 的問題 ;; 1. 小的問題是效率上不如 if,它的 then 和 else 子句都要 evaluate,無論最後是否用得上。 ;; 2. 大的問題在於,如果遞歸函式出現於其子句裡,整個 evaluation 無法終止。 ;; 這是因為非無窮遞歸的終止依靠條件判斷,而在 new-if 中,無論條件子句結果如何, ;; 都必須先進行底層遞歸獲取結果。這樣,在任何第 n 次 procedure 的呼叫中,永遠需要 ;; 第 n+1 次 procedure 的結果先返回,才能決定本層是否終止,這樣就是一個無限遞歸。 ;; ;; 所以,可以知道,如果使用 new-if 替代 if,結果是無限遞歸,程式無法終止,交互式直譯器 ;; 失去反應。 ;; ;; 我們可以猜測,在遞歸函式存在的情況下,語言中一定需要有 normal-order evaluation ;; 的成分存在。否則,考慮遞歸函式 f 的最一般形式 ;; (define (f x) ;; (g x ;; (f (h x)))) ;; 可以看到 (f x) 的 evaluation 需要等待函式 g 裡的某個參數 (f x) 先返回值,無限遞歸。
這一題的關鍵,在於理解 if 作為 special form 的特殊之處:它的子句並非在代入前一律求值,而是採用 normal-order,只有真正被需要的那個子句才會被計算。若改用使用者自訂的 new-if,由於函式的所有參數都必須先求值,then 與 else 兩個子句都會被計算——這不僅浪費效率,更致命的是,當遞歸出現在子句中時,會導致永無止境的遞歸,使程式再也無法終止。由此可見,只要語言裡存在遞歸,就必然需要具備 normal-order 求值特性的成分,if 正是這樣的關鍵存在。