應用序 or 正則序？

2023-06-07 14:54:30

這是《計算機程式的構造與解釋》中的一道習題，如何去判斷一個scheme解釋器是采用什麼方式進行求值的？應用序 or 正則序。應用序是先對參數求值而後應用，而正則序則相反——完全展開而後歸約求值。正則序相比于應用序，會部分存在重複求值的情況。習題是這樣的：

Ben Bitdiddle發明了一種檢測方法，能夠确定解釋器究竟采用的哪種序求值，是采用正則序，還是采用應用序，他定義了下面兩個過程：

(define (p) (p))

(define (test x y)

( if ( = x 0 )

y)) 而後他求值下列的表達式：

(test 0 (p)) 如果解釋器采用的是應用序求值，ben将會看到什麼情況？如果是正則序呢？

分别分析下這兩種情況下解釋器的求值過程：

1.如果解釋器是應用序，将先對過程test的參數求值，0仍然是0，(p)傳回的仍然是(p)，并且将無窮遞歸下去直到棧溢出，顯然，在這種情況下，解釋器将進入假死狀态沒有輸出。

2.如果解釋器是正則序，完全展開test過程：

(define (test 0 (p))

( if ( = 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)) 遞歸調用自身，導緻無限循環直到棧溢出。