看过的计算机书中，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)
文章已经很长了，打住。以后再发挥吧。