用Clojure演示Y combinator

先来看Wikipedia中的Y combinator.

 
λf.(λx.f(x x)) (λx.f(x x))
 

方便起见, 先换几个符号, f用r代替, x用f代替, 然后翻译为Clojure

 
;; λr.((λf.r(f f)) (λf.r(f f)))
(defn YL [r] ( (fn [f] (r (f f)))
               (fn [f] (r (f f)))
             )
)
 

之所以叫做YL, 因为这种形式只适用lazy evaluation的语言, 例如Haskell. 这个版本是无法在Clojure当中使用的. 先来看一个例子, 来找出问题的原因. 比如阶乘函数

 
(defn fact [n]
  (if (= n 0) 1 (* n (fact (- n 1))))
)
 

因为不能使用命名函数, 只能用他的lambda形式

 
  (fn [self]
    (fn [n]
      (if (= n 0) 1 (* n (self (- n 1))))
    )
  )
 

这个函数将会作为参数来调用Y combinator, 返回的函数就是可以递归的版本.

 
user=>(YL 
    (fn [self]
      (fn [n]
        (if (= n 0) 1 (* n (self (- n 1))))
      )
    )
  )
StackOverflowError   user/YL/fn--112 (NO_SOURCE_FILE:153)
 

栈溢出了, 因为有一个无限循环的递归调用.

为了看清楚, 用A来表示lambda

 
A = (fn [f] (r (f f)))
 
(defn YL [r] ( A
               A
             )
)
 

假设传参给YL

 
(YL foo)
 
->
 
(foo (A A))
 
->
 
(foo (foo (A A)))
 
...
 

因为eager evaluation, (A A)必须先计算然后传参, 而计算的结果是再次展开为包含(A A)的表达式, 这样无限展开下去导致栈溢出.

所以根本原因就是self application的eager evaluation. 可以用简单的办法来将lazy等价的变换为eager. 即用lambda表达式将其包裹起来

 
(f f)
 
->
 
(fn [x] ((f f) x))
 

这样凡是(f f)出现的地方都用lambda wrapper代替了, 可以安全的传参, 但对语义没有影响, 当实际调用lambda的时候self application才会执行. 这种变换实质上是模拟了lazy evaluation.

那么新的Y combinator 如下

 
(defn YE [r]
  ( (fn [f] (r (fn [x] ((f f) x))))
    (fn [f] (r (fn [x] ((f f) x))))
  )
)
 

YE可以用在Clojure这样的语言当中了

 
user=>(  
  (YE 
    (fn [self]
      (fn [n]
        (if (= n 0) 1 (* n (self (- n 1))))
      )
    )
  )
5)
120
 

实际常用的是简化的形式. 注意到

 
(A A) = λs.(s s) A
 
;; simplified
 
(defn YL [r]
 
  ( (fn [f] (f f))
    (fn [f] (r (fn [x] ((f f) x))))
  )
 
)
 

参考

1. Introduction to Functional Programming through Lambda Calculus. Greg Michaelson

2. Recursive Definitions, Fixed Points and the Y Combinator. Greg Lavender

3. 1287-rubyconf2012-y-not-adventures-in-functional-programming. Jim Weirich