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