第9章 … and Again, and Again, and Again, …
开场先介绍一个looking函数：
(define looking
(lambda (a lat)
(keep-looking a (pick 1 lat) lat)))
looking函数的使用举例，对于(looking 'caviar '(6 2 4 caviar 5 7 3))，第一个位置是6，以6作为下标找到的节点值是7；以7为下标找到的节点值为3；以3为下标找到的节点值为caviar，和目标匹配，然后返回#t。
如果是(looking 'caviar '(6 2 grits caviar 5 7 3))的话，找到的是grits，和目标不匹配，返回#f。但是如果是(looking 'caviar '(7 2 4 7 5 6 3))的话，那么就进入无限循环了。
下面给出keep-looking的定义：
(define keep-looking
(lambda (a sorn lat)
(cond
((number? sorn)
(keep-looking a (pick sorn lat) lat))
(else (eq? sorn a)))))
上面代码中的sorn是Symbol or Number的所写。
前面定义的looking叫做partial function，本章之前遇到的都是total function。partial function不会对每个输入都产生一个值。下面再举一个partial function的例子：
(define eternity
(lambda (x)
(eternity x)))
eternity会不断重复调用自己，永远不会结束。
在这个例子之前，书中例子中函数的递归都是基于对list的遍历，而list一般是有限长度的，所以递归是有底线的。上面的eternity例子所表明的意思是，递归可以是没有底线的。
下一个碰到的是shift：
(define shift
(lambda (pair)
(build (first (first pair))
(build (second (first pair))
(second pair)))))
书中对shift的描述：
The function shift takes a pair whose first component is a pair and build a pair by shifting the second part of the first component into the second component.
接下来是align函数：
(define align
(lambda (pora)
(cond
((atom? pora) pora)
((a-pair? (first pora)) (align (shift pora)))
(else (build (first pora) (align (second pora)))))))
可以猜测，上面的pora是pair or atom的缩写。align的主要功能是在一个嵌套的pair上反复执行shift操作。但是，shift并不会减少pair中atom的个数。align函数是total function。
接下来的是length*，用来统计align的参数pora中的atom的个数：
(define length*
(lambda (pora)
(cond
((atom? pora) 1)
(else
(+ (length* (first pora))
(length* (second pora)))))))
接下来是weight函数，和length相比，给pair的左成员更多权重，多达两倍：
(define weight*
(lambda (pora)
(cond
((atom? pora) 1)
(else
(+ (* (weight* (frist pora)) 2)
(weight* (second pora)))))))
接下来是shuffle:
(define shuffle
(lambda (pora)
(cond
((atom? pora) pora)
((a-pair? (first pora))
(shuffle (revpair pora)))
(else (build (first pora)
(shuffle (second pora)))))))
如果输入是((a b) (c d))，那么shuffle的执行将不会终止。所以shuffle是partial function。
接下来的函数是C：
(define C
(lambda (n)
(cond
((one? n) 1)
(else
(cond
((even? n) (C (/ n 2)))
(else (C (add1 (* 3 n)))))))))
C函数在输入为0的时候无法产生值。对于C函数，书中提到了一个人物Lothar Collatz (1910-1990)。
接下来的函数是A：
(define A
(lambda (n m)
(cond
((zero? n) (add1 m))
((zero? m) (A (sub1 n) 1))
(else (A (sub1 n)
(A n (sub1 m)))))))
对于A函数，书中提到的人物是Wilhelm Ackermann。A函数和shuft以及looking一样，对于某些输入参数，递归无法在有限时间内收敛。比如：(A 4 3)。
然后书中引用了一首诗：
But answer came there none – And this was scarcely odd, because They’d eaten every one.
The Walrus and The Carpenter - Lewis Carroll
接下来，书中举了一个will-stop?的例子，来看看是否能定义出一个函数，能够用来判断另一个函数是否能够返回值。
(define will-stop?
(lambda (f)
...))
然后又列举了一个last-try来扩展will-stop?，使其能应用在eternity上，使其能应用在eternity上：
(define last-try
(lambda (x)
(and (will-stop? last-try)
(eternity x))))
给出的结论是无法定义出这样一个will-stop?，书中给出的解释是：
We took a really close look at the two possible cases. If we can define will-stop?, then (will-stop? last-try) must yield either #t or #f. But it cannot – due to the very definition of what will-stop? is supposed to do. This must mean that will stop? cannot be defined.
last-try是一个反例，它是对will-stop?的一个悖论（只有(will-stop? last-try) 在false的情况下，last-try才会stop），表明有些递归函数，是无法用(define …)来命名的。
有很多函数是无法define的，也就是说不能有名字。对此，书中附带列举了两个人名： Alan M. Turing (1912-1954) 以及 Kurt Gödel (1906-1978) 。
那怎么办呢？很简单，没有名字，就不通过名字来使用函数，而是直接使用函数本身。就像一个人原本叫张三，但是后来名字被剥夺了，所以不能通过张三找到这个人，但是还是可以跟这个人打交道的。
下面是length函数的定义：
(define length
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
我们完全可以把其名字length去掉。先来看下面这个例子：
(lambda (l)
(cond
((null? l) 0)
(else (add1 (eternity (cdr l))))))
上面定义了一个lambda函数，但是因为没有名字，在定义之后再无法使用，因为无法通过名字来找到它。所以，要在定义的时候就使用这个函数，比如：
(lambda (l)
(cond
((null? l) 0)
(else
(add1
((lambda (l)
(cond
((null? l) 0)
(else (add1 eternity (cdr l)))))
(cdr l))))))
上面的嵌套代码有重复的部分，细心的人或许能够发现重复的部分有下面的模式：
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
eternity)
你可能会觉得上面函数又有了名字，叫length。可是这个名字是局部的临时的，跟用(define …)定义的名字在作用域上有所不同。
把重复的部分提取出来，用局部的mk-length加以表示，我们有：
((lambda (mk-length)
(mk-length
(mk-length eternity)))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
上面的lambda定义对'()返回0
只要嵌套mk-length，即可实现对模式的重复：
((lambda (mk-length)
(mk-length
(mk-length
(mk-length eternity)))）
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
如果高兴，我们可以把length也命名为mk-length，毕竟length也只是局部的名字：
((lambda (mk-length)
(mk-length
(mk-length eternity)))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (mk-length (cdr l))))))))
All names are equal, but some names are more equal than others. – George Orwell ( 1903- 1950)
进一步，eternity挪到里面
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 ((mk-length eternity) (cdr l))))))))
上面的lambda函数在'(apple)的时候返回1，但是如果list元素超过一个，就没有结果了。
更进一步，将eternity替换成mk-length:
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 ((mk-length mk-length) (cdr l))))))))
这样一改造，那么上面的lambda函数能够接受节点数为N的list了。这是一个把自己传给自己，让自己重复自己的游戏。
可以更加进一步，把(mk-length mk-length)提取出来，称为length：
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))
遗憾的是，上面的例子递归无法收敛。因为(mk-length mk-length)是一个函数调用，而我们需要的是返回一个length函数，所以需要让其返回一个lambda：
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(lambda (x)
((mk-length mk-length) x)))))
这样的话，中间的那个(lambda (length) ...其实和mk-length没有太大关系了，可以提取出一个单独的函数：
((lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x)
((mk-length mk-length) x))))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
也就是下面的部分其实是独立的：
(lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x)
((mk-length mk-length) x))))))
上面的这个函数叫做Y combinator，其常见形式是：
(define Y
(lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x)))))))
但是(Y Y)会返回什么结果呢？谁知道！
（本章完）