1.1
10,12,8,3,10 6,a,b,19,#f,4,16,6,16
1.2
(/(+ 5 4 (- 2 (- 3 (+ 6(/ 4 5)))))(* 3 (- 6 2)(- 2 7)))
or
(/(+ 5 4 (- 2 (- 3 (+ 6 4/5))))(* 3 (- 6 2)(- 2 7)))
1.3
這個問題中文版的翻譯是錯的，參看原文是求平方和而不是“和”。
(define (square(x)(* x x)))
(define (max x y)(if (< x y) y x))
(define (func x y z)
(+ (square (max x y))
(square (max (min x y) z))))
1.4
a+|b|
<=>
1 # in python
2 def a_plus_abs_b(a,b):
3 if b>0 :
4 x = a + b
5 else:
6 x = a - b
7 return x
1.5
在網(wǎng)上看了很多答案，都認(rèn)為“應(yīng)用序”的實現(xiàn)會導(dǎo)致死循環(huán)，我非常困惑。反復(fù)看了中文版和英文版，覺得大家這樣認(rèn)為可能是書中說lisp的實現(xiàn)是“應(yīng)用序”，而在scheme中跑這段代碼會死循環(huán)，就先入為主的認(rèn)為“應(yīng)用序”的實現(xiàn)會死循環(huán)。其實對照正文，我們可以看到“正則序”停止展開的條件是“只包含基本運算符的表達(dá)式”，而對于
(define (p) (p))
是無論如何也沒法完全展開的，因為它會不斷遞歸，所以“正則序”才會死循環(huán)。
而對于“應(yīng)用序”的實現(xiàn)，則會這樣展開
(test 0 (p))
(if (= 0 0) 0 (p))
(if #t 0 (p))
; 0
解決這個問題主要是“正則序”（Normal order）以及“應(yīng)用序”（Applicative order）展開一個組合式的規(guī)則，仔細(xì)研究了MIT 6.001課程講義，網(wǎng)上的各種答案，以及中英文版。我認(rèn)為，正則序以類似廣度優(yōu)先的方式進(jìn)行展開。而應(yīng)用序優(yōu)先計算子表達(dá)式，類似與深度優(yōu)先。那么對于這個問題，正則序會展開為
=> (if (= 0 0) 0 (p))
=> (if #t 0 (p))
接著，由于這是一個if的special form（特殊形式），就會被展開為
0
而應(yīng)用序，由于(p)一直可以遞歸代換，從一開始就會進(jìn)入一個無限遞歸中去。
簡言之，由于應(yīng)用序的原因，在 test 表達(dá)式 還沒有展開為 if 特殊形式（special forms）時， (p)已經(jīng)陷入了無限遞歸。