非原创文章。
算是某些文章的翻译。加上一点自己的理解。
(define (f n)
(if (= n 0)
1
(* n (f (- n 1)))))
(f 5)
不用到自己定义自己，把 f 当作参数
(define (p0 self n)
(if (= n 0)
1
(* n (self self (- n 1)))))
(p0 p0 5)
柯里化， 两个参数变一个
(define (p1 self)
(lambda (n)
(if (= n 0)
1
(* n ((self self) (- n 1))))))
((p1 p1) 5)
提升 (self self) ， racket 不是 lazy 的，总是看到啥执行啥。
如下定义会 无限执行下去。 尝试移除 (self self)
(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)
(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 <expr1>)) <expr2>) ==> ((lambda (x) <expr2>) <expr1>)
就是说把 x 变量当作参数处理。
(define (p3 self)
((lambda (f)
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1))))))
(lambda (x) ((self self) x)) ))
((p3 p3) 5)
;; 抽出一个函数处理，简化推导
(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 的定义, 定义一个本地变量
(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
(define p7
(let ((f (lambda (self)
(g (lambda (x) ((self self) x))))))
(f f)))
再次使用 (let ((x <expr1>)) <expr2>) ==> ((lambda (x) <expr2>) <expr1>)
(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
(define p9
((lambda (f) (f f))
(lambda (h) (g (lambda (x) ((h h) x)) ))))
(p9 5)
g 在这里是全局变量。可被化简为参数。 而不是特定的 g， 变 p9 为 Y
(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 上
(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
(define Y2
(lambda (g)
((lambda (h) (g (h h)))
(lambda (h) (g (h h))))))
Y 参数化的作用使得求解更加通用
(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) ;
不同的函数
(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. https://mvanier.livejournal.com/2897.html
2. https://www.cs.toronto.edu/~david/courses/csc324_w15/extra/ycomb.html