本篇是我對 SICP 第 1.5 題的試解。這一題屬於理解題,核心在於釐清 Scheme 的求值順序,以及括號在語意上的關鍵作用。
; ====================================================================== ; Structure and Interpretation of Computer Programs ; (trial answer to excercises) ; 電腦程式的構造與解釋(習題試解) ; created: code17 02/24/05 ; modifIed: ;(在保持內容完整不變的前提下,可以任意轉載) ; ====================================================================== ;; SICP No.1.5 ;; 本題為理解題 ;; (define (p) (p)) ;; ;; 相當於定義了一個無限遞迴函式 p,p 作為 operator,以 0 個 operand 為參數。依定義 ;; 可知,(p) 會被 evaluate 為 (p),而 (p) 再 evaluate 為 (p)……如此無窮盡。 ;; p 自身作為一個 procedure 並沒有問題,我們允許定義遞迴函式;但當 p 作用於 operand ;; 時,(p) 就有問題了,因為它的 evaluation 是無限遞迴的。所以可知,在 scheme 中, ;; () 的作用絕不只是優先級的控制工具,而是不可忽略的語意控制工具。p 是一個函式, ;; 而 (p) 是函式 p 作用於其參數(0 個)後的回傳值。 ;; ;; Test-it: ;; Welcome to MzScheme version 209, Copyright (c) 2004 PLT Scheme, Inc. ;; > (define (p) (p)) ;; > p ;; #<procedure:p> ;; > (p) ;; 交互式直譯器在此失去反應 ;; (define (test x y) ;; (if (= x 0) ;; 0 ;; y)) ;; (test 0 (p)) ;; ;; 因此,測試函式在不同原則的 evaluation 順序下的結果就很容易推測了。在 ;; normal-order evaluation 原則下,只有當一個表達式的值被需要時才會 evaluation, ;; (test 0 (p)) 將被 evaluate 為 (if (= 0 0) 0 (p)),因為判斷條件成立,最後表達式 ;; evaluate 為 0,不需要計算 (p) 的值,從而避免了無限遞迴的發生;而在 ;; applicative-order 的原則下,所有的 operands 必須在代入前 evaluate,因此 (p) 的計算 ;; 無法避免,結果是無限遞迴。 ;; ;; Test-it: ;; > (test 0 (p)) ;; 交互式直譯器在此失去反應,因為 scheme 使用 applicative-order evaluation ;; 如果我們定義 ;; (define (p) p) ;; 則是另外一個意思,它定義了一個有 0 個 operand 的函式 p,當它作用於其 operand ;; 時,回傳值為其自身,這樣我們有 (p) 被 evaluate 為 p,那麼 ((p)) 被 evaluate 為 ;; (p) 然後再 evaluate 為 p,那麼 (((...(((p)))...))) ;; ;; Test-it: ;; > (define (p) p) ;; > p ;; #<procedure:p> ;; > (p) ;; #<procedure:p> ;; > ((p)) ;; #<procedure:p> ;; > (((((((((((((((((((((((p))))))))))))))))))))))) ;; #<procedure:p>
這一題的精髓,在於對比 normal-order 與 applicative-order 兩種求值策略的差異。在 normal-order(正規序)下,表達式只有在真正需要其值時才會被求值,因此像 (test 0 (p)) 這樣的呼叫可以避開對 (p) 的計算,安然回傳 0;而在 Scheme 實際採用的 applicative-order(應用序)下,所有參數都必須在代入前求值,於是 (p) 的無限遞迴無可迴避,直譯器便陷入死循環、失去反應。這也提醒我們:括號不只是控制優先級的工具,更是決定求值語意的關鍵。