Posted on 2007-05-08 15:11
dennis 閱讀(4387)
評論(6) 編輯 收藏 所屬分類:
計算機科學與基礎
這是《計算機程序的構造與解釋》中的一道習題，如何去判斷一個scheme解釋器是采用什么方式進行求值的？應用序 or 正則序。應用序是先對參數求值而后應用，而正則序則相反——完全展開而后歸約求值。正則序相比于應用序，會部分存在重復求值的情況。習題是這樣的：
Ben Bitdiddle發明了一種檢測方法，能夠確定解釋器究竟采用的哪種序求值，是采用正則序，還是采用應用序，他定義了下面兩個過程：
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
而后他求值下列的表達式：
(test 0 (p))
如果解釋器采用的是應用序求值，ben將會看到什么情況？如果是正則序呢？
分別分析下這兩種情況下解釋器的求值過程：
1.如果解釋器是
應用序，將先對過程test的參數求值，0仍然是0，(p)返回的仍然是(p)，并且將無窮遞歸下去直到棧溢出，顯然，在這種情況下，解釋器將進入假死狀態沒有輸出。
2.如果解釋器是
正則序，完全展開test過程：
(define (test 0 (p))
(if (= 0 0)
0
(p))
接下來再進行求值，顯然0=0，結果將返回0。
一般lisp的解釋器都是采用應用序進行求值。這個問題在習題1.6中再次出現。我們知道scheme已經有一個cond else的特殊形式，為什么還需要一個if else的特殊形式呢？那么我們改寫一個new-if看看：
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
寫幾個過程測試一下：
(new-if (< 1 0) 1 0)
結果一切正常，但是，當這3個參數是過程的時候會發生什么情況呢？在這3個參數如果存在遞歸調用等情況下，解釋器也將陷入無限循環導致棧溢出！比如書中的求平方根過程用new-if改寫：
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
(define (average x y)(/ (+ x y) 2))
(define (square x) (* x x))
(define (improve guess x)(average guess (/ x guess)))
(define (good_enough? guess x)
(< (abs (- (square guess) x)) 0.000001))
(define (sqrt_iter guess x)
(new-if (good_enough? guess x)
guess
(sqrt_iter (improve guess x) x)))
(define (simple_sqrt x)(sqrt_iter 1 x))
因為解釋器是應用序求值，將對new-if過程的3個參數求值，其中第三個參數也是一個過程(sqrt_iter (improve guess x) x)) 遞歸調用自身，導致無限循環直到棧溢出。