Skip to content

Instantly share code, notes, and snippets.

@HeGanjie
Last active August 29, 2015 13:56
Show Gist options
  • Save HeGanjie/9000189 to your computer and use it in GitHub Desktop.
Save HeGanjie/9000189 to your computer and use it in GitHub Desktop.

在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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment