Y-combinator

* Y-combinator

[http://www.catonmat.net/blog/derivation-of-ycombinator]
解决在函数中应用匿名函数的问题。

1. 使用???替换函名函数，如果执行不到，这代码是可以执行的。

: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (
:
: (lambda (list) ; the
: (cond ;
: ((null? list) 0) ; function
: (else ;
: (add1 (??? (cdr list)))))) ; itself
:
: (cdr list))))))

2. 以length为参数以后，下面这段代码需要修正后执行，否则报错 "reference to undefined identifier: ???"

: ((lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (length (cdr list)))))))
: ???)

??? 被改为 length 后可执行。
??? 被改为 '(???) 也可以被执行。
??? 被改为 '() 也可以被执行。
看起来，只要???是个可以被引用的东西就行，但是不能是未定义的。
事实上，lambda (length)的参数不管是什么，都会返回 (lambda (list) 这个函数。

如下实验：

: (((lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (willnot_run_here (cdr list)))))))
: 'place_holer) '() )

下面的代码

: ((lambda (f)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (f (cdr list)))))))
: ((lambda (g)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (g (cdr list)))))))
: ((lambda (h)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (h (cdr list)))))))
: ???)))

"ince the argument names f, g,h in (lambda (f) ...), (lambda (g) ...),
(lambda (h) ...) are independent, we can rename all of them to length,
to make it look more similar to the length function:"

以上并非可以替换名字的原因。
真正的原因是，lamda(f)中的参数f，是lamda(g);
lamda(g)中的参数g，是lambda(h);
而h只是占位符，对程序的求值没有任何作用。
以下代码是上面代码的变形，帮助理解。

: (((lambda (lambda_lambda_place_holder)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (lambda_lambda_place_holder (cdr list)))))))
: ((lambda (lambda_place_holder)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (lambda_place_holder (cdr list)))))))
: ((lambda (place_holder)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (willnot_run_here (cdr list)))))))
: 'place_holder))) '(a b))

下面的代码中，
把lambda(length)作为参数传给lambda (mk-length)
lambda (mk-length) 的执行是以参数作为函数，给这个函数的参数是占位符???；
这个参数此时是 lambda (length)。
lambda (length)的占位符参数没有被求值，函数就结束了。
所以，以下代码能求 '()

: ((lambda (mk-length)
: (mk-length ???))
: (lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (length (cdr list))))))))

下面的代码中
lambda (mk-length)的执行是，
向mk-length传递参数 (mk-length ???)。
这一参数的解释上面已经提到，执行一次lambda (length)。
执行lambda (length)，最后返回的是 length (cdr list)。
即，以lambda (length)作为lambda (length)的参数。
一共执行两次。

: ((lambda (mk-length)
: (mk-length
: (mk-length ???)))
: (lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (length (cdr list))))))))

既然???是占位符，不会被求值，所以可以

: ((lambda (mk-length)
: (mk-length mk-length))
: (lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (length (cdr list))))))))

所有的length改在mk-length。
传进来的参数确实是它。
代码略去。

然后，length (cdr list) 换成 (mk-length mk-length) (cdr list)。
这样，(mk-length mk-length) 递归地返回 原来的lambda (length) 应用在 (cdr list) 上

: ((lambda (mk-length)
: (mk-length mk-length))
: (lambda (mk-length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 ((mk-length mk-length) (cdr list))))))))

其实mk-lenth只执行了一次，然后mk-length参数就是占位符了。
但是，"The function works because it keeps adding recursive uses by passing
mk-length to itself, just as it is about to expire."

递归的跳出条件是(null? list)。

把(lambda (length)移出作为lambda (le)的参数，
(lambda (x)作为le的参数。
代码如下。

: ((lambda (le)
: ((lambda (mk-length)
: (mk-length mk-length))
: (lambda (mk-length)
: (le (lambda (x)
: ((mk-length mk-length) x))))))
: (lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (length (cdr list))))))))

Y-combinator如下。

: (define Y
: (lambda (le)
: ((lambda (f) (f f))
: (lambda (f)
: (le (lambda (x) ((f f) x)))))))

匿名函数的应用如下。

: ((Y (lambda (length)
: (lambda (list)
: (cond
: ((null? list) 0)
: (else
: (add1 (length (cdr list))))))))
: '(a b c d e f g h i j))

另一种Y-combinator的写法,
[http://www.mactech.com/articles/mactech/Vol.07/07.05/LambdaCalculus/]
and [http://www.stanford.edu/class/cs242/readings/vocabulary.html]
"When applied to a function, returns its fixed point."
: (define y
: (lambda (f)
: ((lambda (x) (f (x x)))
: (lambda (x) (f (x x))))))

参见TLS书(非pdf页码)pp.171，
如何把lambda (length)移出，从而形成了Y-combinatior的框架。

*关键：applying arguemnt lambda on precedure lambda, and eval the
augument lambda in precedure lambda.*

另，参考[http://blog.vazexqi.com/2006/07/13/y-combinator]

原来看不懂的一个原因是，这本电子书有缺页。
[The Little Schemer - 4th Edition.pdf]是个更完整的版本。