本文借助阶乘函数，在lisp中推导了Y combinator。
原始的fact定义
(define fact
(lambda (n)
(if (= n 0)
1
(* n (fact (- n 1))))))
定义下文中用到的两个函数high-fact与fact-proto
(define high-fact
(lambda (f)
(lambda (n)
(if (= n 0)
1
(* n ((f f) (- n 1)))
)
)
)
)
(define fact-proto
(lambda (h)
(lambda (x)
(if (= x 0)
1
(* x (h (- x 1)))
)
)
)
)
fact就是high-fact对自身的调用
fact<=>
(high-fact high-fact)
使用一个辅助函数消除重复出现的两个high-fact
fact<=>
(
(lambda (g) (g g))
high-fact
)
代入high-fact的定义
fact<=>
(
(lambda (g) (g g))
(lambda (f)
(lambda (n)
;;;; 变换前
(if (= n 0)
1
(* n
((f f) (- n 1)))
)
)
)
)
将局部表达式变换为对fact-proto的调用
fact<=>
(
(lambda (g) (g g))
(lambda (f)
(lambda (n)
;;;; 变换后
(
(fact-proto (f f))
n
)
)
)
)
将fact-proto变成形参
fact<=>
(
(lambda (k)
(
(lambda (g) (g g))
(lambda (f)
(lambda (n)
(
(k (f f))
n
)
)
)
)
)
fact-proto
)
得到Y combinator
fact<=>
(
y-combinator
fact-proto
)
(define y-combinator
(lambda (k)
(
(lambda (g) (g g))
(lambda (f)
(lambda (n)
(
(k (f f))
n
)
)
)
)
)
)
紧凑一点
(define y-combinator
(lambda (k)
((lambda (g) (g g))
(lambda (f)
(lambda (n)
((k (f f))
n))))))
扩展为多参数形式
(define y-combinator
(lambda (k)
((lambda (g) (g g))
(lambda (f)
(lambda ns
(apply (k (f f)) ns))))))