看過的計算機書中，scheme相關的那幾本，好比SICP，the essence of program都很讓我愛不釋手。而the little schemer更加獨特，編程的本質，在這本書小人書上體現得淋漓盡致。竊以為，scheme是語法形式上最為完美的編程語言了，沒有之一。少即是多，這樣的贊美之言，唯有scheme當之無愧，并且它的確是精簡得不能再精簡了。至于那個自吹自擂的什么狗語言，不提也罷。當然，完美并不一定代表實用，也并不一定必須流行，曲高一向都是和寡的，但是，完美卻一定可以帶來賞心悅目般的感受。
the little schemer全書行云流水，逐漸顯露遞歸的威力，做足了鋪墊，到了第8章，真命天子lambda出現，一切變得很有意思了，讀完之后，意猶未盡。第9章，難度陡增，突然變得理論性起來，那是自然的。因為，這一章的主題是停機問題和Y組合算子。不引入任何形式化的方法，但是作者舉重若輕，依然闡釋得如此直白易懂，可以說，只要能看完前面的內容，就一定能看懂這一章。而前八章，據說6歲以上的兒童都能看得明白。
scheme中的函數是first class，可以作為參數傳遞給其他函數，也可以作為值從函數中返回。比如，廣為流傳的一道程序，用以考察語言的表達能力，“編寫一個函數，其入參數為n，返回值為新的函數，該函數的參數為x，返回值為之前的n與現在的x的和。”用scheme來表達，牛刀小試。
(define (addn n) (lambda (x) (+ x n)))然后，對于((addn 20) 30)，scheme解釋器上顯示其結果為50，很好。相比于那個lisp的版本，這里顯得多么的干凈。
函數式的語言對副作用（side effect）很敏感，特別是haskell，更加對副作用趕盡殺絕，壓根就不讓寫出有副作用的函數。因此，正常情況下，函數執行完畢，都有返回值。好比，……，總之很多就是，正常的函數，都可稱之為total functions，意思就是對所有的參數，都會有返回結果。但是，也還存在一些病態函數，它們不會返回，一旦調用它，那么將陷入與其中，永遠都不會返回了，顯然，里面出現死循環了，但是，scheme中沒有循環語句，所以不能這么說，總之，這一類是不會有返回值的。很輕易就能寫出一個例子。
(define eternity (lambda (x) (eternity x)))eternity為不朽的意思。
自然就有這樣的問題，能否實現這樣的函數，它能判斷函數是否終將返回，或者說，判斷函數會不會停止。這個函數作用可大了，當然不會那么容易實現。不過，可以先假設它存在，就叫它will-stop?（別驚訝，scheme中，標識符中可以有+-*等特殊符號）。因此，對于任何函數，(will-stop? afunction)表達式的值，要么為#t，表示函數afunction終將停止返回；要么為#f，則函數不會停止，好比eternity。顯然，讓will-stop?判斷自己，(will-stop? will-stop?)的結果一定是#t了。
但是，will-stop?是不可能存在的，這不是廢話嗎，地球人都知道。因為計算機學家精心構造了一個反例，此反例實在巧妙，真難以想象當初是如何構造出來，我等小民只需理解即可。請看代碼
(define (last-try x)
(and (will-stop? last-try) (eternity x)))
last-try，好名字，就叫它最后一擊吧。(will-stop? last-try)的結果不外乎#t或#f。
假如為#f，說明last-try不會返回，意味著有死循環，不會停止。但是，一考察last-try的內部實現，卻很容易就知道它馬上就返回了。表達式(and (will-stop? last-try) (eternity '()))中，由假設可知(will-stop? last-try)為#f，進而馬上可知，(and (will-stop? last-try) (eternity '()))馬上必將返回#f，也就是說，雖然一開始假設last-try不會停止，但實際運行中last-try一下子就返回了，矛盾。
看樣子，(will-stop? last-try)只好為#t了。可是，(and (will-stop? last-try) (eternity '()))，and表達式的兩個分支中，既然(will-stop? last-try)為#t，那么，勢必要進一步調用(eternity '())，而eternity老爺，一早就知道他乃不朽之身了，因此，last-try也沾光，一樣不朽了。與假設中(will-stop? last-try)為#t為終將停止，又是矛盾。
因此，will-stop?接受不了last-try的挑戰，失敗。也就是說，will-stop?這樣的函數，不存在。這道反例的高明之處，或者說耍賴吧，就是以will-stop?為基礎構造了一個will-stop?無法判斷的函數。假如規定，所有被檢測函數都不得直接間接的調用will-stop?，免得will-stop?難堪，那么這樣的will-stop?能否存在呢？存不存在，我就不知道了，但享受此待遇的Y組合子卻是存在的。
函數直接或間接調用到它自己，遞歸就產生了。問題來了，函數你自己都還沒實現完畢，怎么就可以自己拿來調用呢？這個過程中，編譯器解釋器肯定做了某些語義上處理，讓遞歸得以實現。邏輯學中，對于下定義的要求是“不得循環”，好比，白色就是一種白色的顏色，這種廢話定義就不符合下定義的基本要求了。
下面來將一條經典的遞歸函數整成非遞歸的版本。the little schemer的推導思路非常淺顯易懂，我不能做的更好的了，因此借用。
(define length
(lambda (l)
(cond ((null? l) 0)
(else (+ 1 (length (cdr l)))))))
函數length中，雖然調用到了自己，實際上，其實只是調用了一個同樣名字的函數而已。意味著，length的實際上的lambda表達式，背地里帶多了一個參數，此參數為函數，用以當入參l不為空時來進行使用。因此，可以將整個函數的定義改寫成下面的lambda表達式。
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (+ 1 (length (cdr l)))))))
lambda表達式的返回值為一個函數，當然沒有名字了。它的入參為一函數，返回一個新的函數，此新函數的入參是列表，返回列表的長度。為了便于后文敘述引用，就用define給它起個名字，叫mk-length。什么，連用define起名字都不會，沒救了。
mk-length不是需要函數入參嗎？剛好手頭有一個，就用它自己本身，((mk-length mk-length) '())，解釋器返回0，太好了。然后，我滿懷希望的用((mk-length mk-length) '(a))來測試，結果，解釋器報錯了，為什么？稍微一想，就明白了。(mk-length mk-length)的確返回計算列表長度的函數，但是，當列表不為空時，只好用表達式(+ 1 (length (cdr l)))做進一步處理，里面的length就是mk-length，而mk-length的入參是函數，不是列表，于是解釋器就報錯了。怎么辦？
當然，要計算長度為不大于1的列表的長度，還是有辦法的。就是，((mk-length (mk-length mk-length)) '(a))，這樣就好了。自然，當列表大于1時，解釋器必然又將報錯了。按照此法，為此，為了求得不大于N個元素的列表長度，必須將mk-length寫N次，好比，
((mk-length
(mk-length
(mk-length (...))))
'(a b c d ...))
并且，辛辛苦苦的重復寫N遍mk-length，只能計算個數不大于N的列表的長度。這，無論如何都不能讓程序猿接受。
那么，為何要寫那么多(mk-length (mk-length (mk-length...)))，皆因mk-length中(+ 1 (length (cdr l)))的length函數接收的函數參數是列表l。先暫時讓它適應環境，就讓它知道它接收的length參數是一個跟它自己本身的lambda表達一樣，是入參為函數，然后返回一個計算list長度的函數。將mk-length改寫成這樣。
(define mk-length
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (+ 1 ((length length) (cdr l))))))))
請注意，代碼里面已經不存在遞歸形式了，因為，mk-length的lambda表達式中，沒有用到mk-length這個名字了，當然，它還要用到入參length以計算當l不為空時的長度。再次抱著試試看的態度，驗證，((mk-length mk-length) '(a))，返回1，真的可以了。拿更長的列表丟進去，長度為2，為3，為N+1，都OK了，真是神奇。
它的工作原理是，故事一開始，(mk-length mk-length)生成一個計算列表長度的函數，在其內部中，假如列表l為空，就返回長度為0；否則，就計算l的尾部長度，并加上頭結點的長度1，而計算l的尾部的函數，是通過(length length)來生成，其中length就是mk-length，故事就回到原點(mk-length mk-length)了，只是，其返回值在外圍中要加1了，然后，在更外圍中繼續加1，加1，……。
但是，工作還沒有完成，因為，mk-length中，((length length) (cdr l))很刺眼，它應該是(length (cdr l))這樣的形式。重構，必須重構。必須在將其提煉成一個函數，因此，mk-length就變成
(define mk-length
(lambda (length-mk)
((lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (+ 1 (length (cdr l)))))))
(lambda (x)
((length-mk length-mk) x)))))
代碼似乎變得復雜些了，但效果是一樣，并且，語法結構上基本保持一致。但是代碼好像的確變得更長了，這也沒辦發，為了保持最內部length的純潔性。但是，它也太深了，作為重點，應該放在外面，嗯，應該將兩個lambda對調一下。
(define mk-length
(lambda (length-mk)
((lambda (length)
(length (lambda (x)
((length-mk length-mk) x))))
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (+ 1 (length (cdr l))))))))))
面對著這么多的lambda，實在難以淡定。但必須接收洗禮，方可體會到函數作為一等公民，所帶來的強悍的表達能力，簡直能撞破習慣命令式編程的眼球。里面的lambda(length)又變回原來的樣子，但是，mk-length的主體已經不再是它了，而是一個以的lambda(length)為參數的lambda了。為了保持mk-length的純潔，繼續努力，這一次，是在兩個(mk-length mk-length)上做文章，每次都要寫兩個相同的函數，不如把它做成函數。事情到了這一步，Y組合子已呼之欲出。
(define Y
(lambda (f)
(f f)))
((Y mk-length) '(a b c d e)) ;返回5
然后將mk-length中的第一條length的lambda搬過來，并且作為兩個f的入參
(define Y
(lambda (length)
((lambda (f)
(f f))
(lambda (length-mk)
(length (lambda (x)
((length-mk length-mk) x)))))))
最后，將Y整得更加好看一點，也看來更加的通用，不僅僅是針對length，而是全部的需要遞歸的函數。
(define (Y f)
((lambda (g) (g g))
(lambda (g)
(f
(lambda (x) ((g g) x))))))
再送上一道求和
((Y
(lambda (sum)
(lambda (n)
(cond ((= n 1) 1)
(else (+ n (sum (- n 1))))))))
10)
文章已經很長了，打住。以后再發揮吧。