尽管扯淡-Y-Combinator不同语言实现方案

递归和定点

纯λ演算的一大特色是可以通过使用一种自应用技巧来书写递归函数。

f(n) = if n = 0 then 1 else n*f(n-1) 
f = λn.if n = 0 then 1 else n*f(n-1)

把f移到等式的后面，得到函数G

G = λf.λn.if n = 0 then 1 else n*f(n-1)

很显然有：

f = G(f)

这表明递归声明涉及找出定点。函数G的定点是指满足f=G(f)的f的值。在λ演算中，定点由定点操作符Y来定义。具体的推导过程可以参考我的上一篇文章Y-Combinator的推导。

Y = λf.(λx.f(x x))(λx.f(x x))

Ruby 版本

def y(&gen)
    lambda {|g| g[g] }.call(lambda{|f| lambda {|*args| gen[f[f]][*args] }})
end

factorial = y do |recurse|
    lambda do |x|
        x.zero? ? 1 : x * recurse[x-1]
    end
end
puts factorial.call(10)

Python 版本

def y_combinator(gen):    
    return (lambda g: g(g))(lambda f: (lambda *args: (gen(f(f)))(*args)))

ret = y_combinator(lambda fab: lambda n: 1 if n < 2 else n * fab(n - 1))(10)
print(ret)

JavaScript 版本

function y(gen) {
    return (function(g) {
        return g(g);
    })(function(f) {
        return function(args){
            return gen(f(f))(args);
        };
    });
}

var fact = y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});
console.log(fac(5));

Clojure 版本

(defn Y [gen]
  ((fn [g] (g g))
    (fn [f]
      (fn [n] ((gen (f f)) n)))))
      
(defn fac-gen [f] (fn [n] (if (<= n 0) 1 (* n (f (dec n))))))
(assert (= ((Y fac-gen) 5) 120))