YCombinator.md

在LISP之根源里面看到作者提到Y组合子，于是去了解了一下，但是看其他人的解释都很难完全弄懂。
最后通过 王垠的wiki 发现 Franco 教授的推演过程讲得最简单易懂，在看懂了之后我再用CoffeeScript推演了一次，加深理解。

LISP之根源 http://daiyuwen.freeshell.org/gb/rol/roots_of_lisp.html#foot108
王垠的wiki http://minus273.eu/mirrors/2001315450/wiki/SchemeYcombinator.html
Franco 教授的推演过程 http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
可以将代码贴在这里上面验证结果 http://coffeescript.org/

• 第一步

  #普通的递归
  fac = (n) ->
    return 1 if n is 0
    return n * fac(n - 1)
  
  alert fac(5)

• 第二步

  #假设事先不知道自己的名字，通过一个lambda包裹，传入自身
  fac0 = (fn) -> 
           (n) ->
             return 1 if n is 0
             return n * fn(n - 1)
  
  alert fac0(？)(5)
  
  #但是这样无法递归，因为必须要接受真正的fac作为参数，所以要变换一下
  
  fac1 = (fn) ->
           (n) ->
             return 1 if n is 0
             return n * fn(fn)(n - 1)
  
  alert fac1(fac1)(5)

• 第三步

  #由于 func(n) 等于 ((x) -> func(x))(n)
  #于是：func(func)(x) 等于 ((x) -> func(func)(x))(n) ，所以上一步可以变成：
  
  fac2 = (F) -> 
           ((fn) -> 
             (n) ->
               return 1 if n is 0
               return n * fn(n - 1)
           )((x) -> F(F)(x))
  
  alert fac2(fac2)(5)

• 第四步

  #现在可以从其中发现fac0了，其实上一步的目的就是为了得到fac0
  
  fac0 = (fn) -> 
           (n) ->
             return 1 if n is 0
             return n * fn(n - 1)
  
  fac3 = (F) -> 
           fac0((x) -> F(F)(x))
  
  alert fac3(fac3)(5)
  
  #于是让fac0从外面传入，那么Y组合子就能够应用于其他的递归了
  
  fac4 = (g) -> 
           (F) -> 
             g((x) -> F(F)(x))
  
  alert fac4(fac0)(fac4(fac0))(5)

• 第五步

  #总结出Y组合子和验证： Y(fac0) 等于 fac0( Y(fac0) )
  
  fac0 = (fn) -> (n) ->
    return 1 if n is 0
    return n * fn(n - 1)
  
  # 注意：在 coffeeScript 中 (func func) 等于 (func(func))
  
  Y = (g) -> 
        ((F) -> 
          g((x) -> (F F)(x))
        )((F) -> 
          g((x) -> (F F)(x))
        )
  
  alert Y(fac0)(5)
  
  alert fac0( Y(fac0) )(5)
  
  # 后记：其实我们总结出的是 Y组合子 的变体 Z组合子 ，因为Y组合子只能用于正则序演算
  #（在应用序尝试一下，会栈溢出），而经过变换后的Z组合子才能在应用序求值中使用
  # Y = λf.(λx.f (x x)) (λx.f (x x))
  # Z = λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))