DIV CSS 佈局教程網

您现在的位置: DIV+CSS佈局教程網 >> 網頁腳本 >  >> JavaScript入門知識 >> AJAX入門 >> AJAX詳解
SICP 習題試解 (1.6)
編輯:AJAX詳解     

本篇是我對 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 正是這樣的關鍵存在。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved