非原创文章。算是某些文章的翻译。加上一点自己的理解。 ```scheme (define (f n) (if (= n 0) 1 (* n (f (- n 1))))) (f 5) ``` 不用到自己定义自己，把 f 当作参数 ```scheme (define (p0 self n) (if (= n 0) 1 (* n (self self (- n 1))))) (p0 p0 5) ``` 柯里化，两个参数变一个 ```scheme (define (p1 self) (lambda (n) (if (= n 0) 1 (* n ((self self) (- n 1)))))) ((p1 p1) 5) ``` 提升 (self self) ， racket 不是 lazy 的，总是看到啥执行啥。如下定义会无限执行下去。尝试移除 (self self) ```scheme (define (p2-wrong self) (let ((f (self self))) (lambda (n) (if (= n 0) 1 (* n (f (- n 1))))))) ((p2-wrong p2-wrong) 5) ``` lambda make it lazy to eval let ((f (self self)) 是即时计算 let ((f (lambda (x) ((self self) x)) 延迟计算, 先定义了一个函数。 (self self) 和 (lambda (x) ((self self) x) 在使用的时候是等价的。再次尝试去掉 (self self) ```scheme (define (p2 self) (let ((f (lambda (x) ((self self) x)))) (lambda (n) (if (= n 0) 1 (* n (f (- n 1))))))) ((p2 p2) 5) ``` let expression can be converted into an equivalent lambda expression using this equation: (let ((x )) ) ==> ((lambda (x) ) ) 就是说把 x 变量当作参数处理。 ```scheme (define (p3 self) ((lambda (f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1)))))) (lambda (x) ((self self) x)) )) ((p3 p3) 5) ``` ;; 抽出一个函数处理，简化推导 ```scheme (define g (lambda (f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1))))))) (define (p4 self) (g (lambda (x) ((self self) x)) )) ((p4 p4) 5) ``` 继续简化 (p4 p4) 这样可以直接传入变量 n (define p5 (p4 p4)) (p5 5) 展开 p5 的定义, 定义一个本地变量 ```scheme (define p6 (let ((p4-local (lambda (self) (g (lambda (x) ((self self) x)))))) (p4-local p4-local))) (p6 5) ``` make the name short，p4-local is just a name ```scheme (define p7 (let ((f (lambda (self) (g (lambda (x) ((self self) x)))))) (f f))) ``` 再次使用 (let ((x )) ) ==> ((lambda (x) ) ) ```scheme (define p8 ((lambda (f) (f f)) (lambda (self) (g (lambda (x) ((self self) x)) )))) (p8 5) ``` make the name short， self is just a name ```scheme (define p9 ((lambda (f) (f f)) (lambda (h) (g (lambda (x) ((h h) x)) )))) (p9 5) ``` g 在这里是全局变量。可被化简为参数。而不是特定的 g，变 p9 为 Y ```scheme (define Y (lambda (g) ((lambda (f) (f f)) (lambda (h) (g (lambda (x) ((h h) x)))) ))) ( (Y g) 5) ``` 把 (lambda (h) (g (lambda () ((h h) y)))) 应用在 f 上 ```scheme (define Y1 (lambda (g) ((lambda (h) (g (lambda (x) ((h h) x)))) (lambda (h) (g (lambda (x) ((h h) x)))) ))) ``` 再进一步可以把之前即时求值的替换简化公式，但 racket 不能使用。 (lambda (y) ((h h) y)) is just mean (h h) haskell / lazy-racket can do it ```scheme (define Y2 (lambda (g) ((lambda (h) (g (h h))) (lambda (h) (g (h h)))))) ``` * * * Y 参数化的作用使得求解更加通用 ```scheme (define g1 (lambda (f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1))))))) (define f1 (lambda (n) (if (= n 0) 1 (* n (f1 (- n 1)))))) ``` g1 和 f1 可以应用； ((g f1) 5) ; 不同的函数 ```scheme (define g2 (lambda (f) (lambda (n) (if (= n 0) 1 (* 2 (f (- n 1))))))) (define (f2 n) (if (= n 0) 1 (* 2 (f2 (- n 1))))) ;; wrong ((g2 f2) 5) ((g2 f2) 5) ``` 不同的版本的 g 确实可以运行/但只能应用特定版本的 f，而且 g f 大量重复 ((g1 f2) 5) ((g2 f1) 5) 都是错误的结论。 * * * 参考文章： 1\. 2\.

Y-combinator 的推导