乐趣区

关于java:10种编程语言实现Y组合子

简介:Y 组合子是 Lambda 演算的一部分,也是函数式编程的实践根底。它是一种办法 / 技巧,在没有赋值语句的前提下定义递归的匿名函数,即仅仅通过 Lambda 表达式这个最根本的“原子”实现循环 / 迭代。本文将用 10 种不同的编程语言实现 Y 组合子,以及 Y 版的递归阶乘函数。

作者 | 技师
起源 | 阿里技术公众号

一 Y-Combinator
Y 组合子是 Lambda 演算的一部分,也是函数式编程的实践根底。它是一种办法 / 技巧,在没有赋值语句的前提下定义递归的匿名函数。即仅仅通过 Lambda 表达式这个最根本的“原子”实现循环 / 迭代,颇有道生一、毕生二、二生三、三生万物的感觉。

1 从递归的阶乘函数开始

先不思考效率等其余因素,写一个最简略的递归阶乘函数。此处采纳 Scheme,你能够抉择本人相熟的编程语言跟着我一步一步实现 Y -Combinator 版的阶乘函数。

(define (factorial n)
(if (zero? n)

1
(* n (factorial (- n 1)))))

Scheme 中 (define (fn-name)) 是 (define fn-name (lambda)) 的简写,就像 JS 中,function foo() {} 等价于 var foo = function() {}。把下面的定义开展成 Lambda 的定义:

(define factorial
(lambda (n)

(if (zero? n)
  1
  (* n (factorial (- n 1))))))

2 绑定函数名
想要递归地调用一个函数,就必须给这个函数取一个名字。匿名函数想要实现递归,就得取一个长期的名字。所谓长期,指这个名字只在此函数体内无效,函数执行实现后,这个名字就随同函数一起隐没。为解决这个问题,第一篇文章中 [1] 强制规定匿名函数有一个暗藏的名字 this 指向本人,这导致 this 这个变量名被强行占用,并不优雅,因而第二篇文章 [2] 借鉴 Clojure 的办法,容许自定义一个名字。

但在 Lambda 演算中,只有最一般的 Lambda,没有赋值语句,如何绑定一个名字呢?答案是应用 Lambda 的参数列表!

(lambda (factorial)
(lambda (n)

(if (zero? n)
  1
  (* n (factorial (- n 1))))))

3 生成阶乘函数的函数
尽管通过参数列表,即应用闭包技术给匿名函数取了一个名字,但此函数并不是咱们想要的阶乘函数,而是阶乘函数的元函数(meta-factorial),即生成阶乘函数的函数。因而须要执行这个元函数,取得想要的阶乘函数:

((lambda (factorial)
(lambda (n)

 (if (zero? n)
   1
   (* n (factorial (- n 1))))))

xxx)
此时又呈现另一个问题:实参 xxx,即形参 factorial 该取什么值?从定义来看,factorial 就是函数本身,既然是“本身”,首先想到的就是复制一份截然不同的代码:

((lambda (factorial)
(lambda (n)

 (if (zero? n)
   1
   (* n (factorial (- n 1))))))

(lambda (factorial)
(lambda (n)

 (if (zero? n)
   1
   (* n (factorial (- n 1)))))))

看起来曾经把本人传递给了本人,但马上发现 (factorial (- n 1)) 会失败,因为此时的 factorial 不是一个阶乘函数,而是一个蕴含阶乘函数的函数,即要获取蕴含在外部的函数,因而调用形式要改成 ((meta-factorial meta-factorial) (- n 1)):

((lambda (meta-factorial)
(lambda (n)

 (if (zero? n)
   1
   (* n ((meta-factorial meta-factorial) (- n 1))))))

(lambda (meta-factorial)
(lambda (n)

 (if (zero? n)
   1
   (* n ((meta-factorial meta-factorial) (- n 1)))))))

把名字改成 meta-factorial 就能清晰地看出它是阶乘的元函数,而不是阶乘函数自身。

4 去除反复
以上代码曾经实现了 lambda 的自我调用,但其中蕴含反复的代码,meta-factorial 即做函数又做参数,即 (meta meta):

((lambda (meta)
(meta meta))
(lambda (meta-factorial)
(lambda (n)

 (if (zero? n)
   1
   (* n ((meta-factorial meta-factorial) (- n 1)))))))

5 提取阶乘函数
因为咱们想要的是阶乘函数,所以用 factorial 取代 (meta-factorial meta-factorial),办法同样是应用参数列表命名:

((lambda (meta)
(meta meta))
(lambda (meta-factorial)
((lambda (factorial)

  (lambda (n)
    (if (zero? n)
      1
      (* n (factorial (- n 1))))))
(meta-factorial meta-factorial))))

这段代码还不能失常运行,因为 Scheme 以及其余支流的编程语言实现都采纳“利用序”,即执行函数时先计算参数的值,因而 (meta-factorial meta-factorial) 原来是在求阶乘的过程中才被执行,当初提取进去后执行的工夫被提前,于是陷入有限循环。解决办法是把它包装在 Lambda 中(你学到了 Lambda 的另一个用途:提早执行)。

((lambda (meta)
(meta meta))
(lambda (meta-factorial)
((lambda (factorial)

  (lambda (n)
    (if (zero? n)
      1
      (* n (factorial (- n 1))))))
(lambda args
  (apply (meta-factorial meta-factorial) args)))))

此时,代码中第 4 行到第 8 行正是最后定义的匿名递归阶乘函数,咱们终于失去了阶乘函数自身!

6 造成模式

如果把其中的阶乘函数作为一个整体提取进去,那就是失去一种“模式”,即能生成任意匿名递归函数的模式:

((lambda (fn)
((lambda (meta)

  (meta meta))
(lambda (meta-fn)
  (fn
    (lambda args
      (apply (meta-fn meta-fn) args))))))

(lambda (factorial)
(lambda (n)

 (if (zero? n)
   1
   (* n (factorial (- n 1)))))))

Lambda 演算中称这个模式为 Y 组合子(Y-Combinator),即:

(define (y-combinator fn)
((lambda (meta)

 (meta meta))

(lambda (meta-fn)

 (fn
   (lambda args
     (apply (meta-fn meta-fn) args))))))

有了 Y 组合子,咱们就能定义任意的匿名递归函数。前文中定义的是递归求阶乘,再定义一个递归求斐波那契数:

(y-combinator
(lambda (fib)

(lambda (n)
  (if (< n 3)
    1
  (+ (fib (- n 1))
     (fib (- n 2)))))))

二 10 种实现

上面用 10 种不同的编程语言实现 Y 组合子,以及 Y 版的递归阶乘函数。理论开发中可能不会用上这样的技巧,但这些代码别离展现了这 10 种语言的诸多语法个性,能帮忙你理解如何在这些语言中实现以下性能:

如何定义匿名函数;
如何就地调用一个匿名函数;
如何将函数作为参数传递给其余函数;
如何定义参数数目不定的函数;
如何把函数作为值返回;
如何将数组里的元素平坦开来传递给函数;
三元表达式的应用办法。
这 10 种编程语言,有 Python、PHP、Perl、Ruby 等大家耳熟能详的脚本语言,预计最让大家诧异的应该是其中有 Java!

1 Scheme
我始终感觉 Scheme 版是这么多种实现中最优雅的!它没有“刻意”的简洁,读起来很天然。

(define (y-combinator f)
((lambda (u)

 (u u))

(lambda (x)

 (f (lambda args
      (apply (x x) args))))))

((y-combinator
(lambda (factorial)

(lambda (n)
  (if (zero? n)
      1
      (* n (factorial (- n 1)))))))

10) ; => 3628800
2 Clojure
其实 Clojure 不须要借助 Y -Combinator 就能实现匿名递归函数,它的 lambda——fn——反对传递一个函数名,为这个长期函数命名。兴许 Clojure 的 fn 不应该叫匿名函数,应该叫长期函数更贴切。

同样是 Lisp,Clojure 版本比 Scheme 版本更简短,却让我感觉是一种刻意的简洁。我喜爱用 fn 取代 lambda,但用稀奇古怪的符号来缩减代码量会让代码的可读性变差(我最近如同变得不太喜爱用符号,哈哈)。

(defn y-combinator [f]
(#(% %) (fn [x] (f #(apply (x x) %&)))))

((y-combinator
(fn [factorial]

#(if (zero? %) 1 (* % (factorial (dec %))))))

10)

3 Common Lisp

Common Lisp 版和 Scheme 版其实差不多,只不过 Common Lisp 属于 Lisp-2,即函数命名空间与变量命名空间不同,因而调用匿名函数时须要额定的 funcall。我集体不喜爱这个额定的调用,感觉它是冗余信息,地位信息曾经蕴含了角色信息,就像命令行的第一个参数永远是命令。

(defun y-combinator (f)
((lambda (u)

 (funcall u u))

(lambda (x)

 (funcall f (lambda (&rest args)
              (apply (funcall x x) args))))))

(funcall (y-combinator

      (lambda (factorial)
        (lambda (n)
          (if (zerop n)
            1
            (* n (funcall factorial (1- n)))))))
     10)
     

4 Ruby

Ruby 从 Lisp 那儿借鉴了许多,包含它的毛病。和 Common Lisp 一样,Ruby 中执行一个匿名函数也须要额定的“.call”,或者应用中括号“[]”而不是和一般函数一样的小括号“()”,总之在 Ruby 中匿名函数与一般函数不一样!还有繁冗的符号也影响我在 Ruby 中应用匿名函数的情绪,因而我会把 Ruby 看作语法更灵便、更简洁的 Java,而不会思考写函数式格调的代码。

def y_combinator(&f)
lambda {|&u| u[&u]}.call do |&x|

f[&lambda {|*a| x[&x][*a]}]

end
end

y_combinator do |&factorial|
lambda {|n| n.zero? ? 1: n*factorial[n-1]}
end[10]

5 Python

Python 中匿名函数的应用形式与一般函数一样,就这段代码而言,Python 之于 Ruby 就像 Scheme 之于 Common Lisp。但 Python 对 Lambda 的反对几乎弱爆了,函数体只容许有一条语句!我决定我的工具箱中用 Python 取代 C 语言,尽管 Python 对匿名函数的反对只比 C 语言好一点点。

def y_combinator(f):

return (lambda u: u(u))(lambda x: f(lambda *args: x(x)(*args)))

y_combinator(lambda factorial: lambda n: 1 if n < 2 else n * factorial(n-1))(10)

6 Perl

我集体对 Perl 函数不能申明参数的埋怨更甚于繁冗的符号!

sub y_combinator {

my $f = shift;
sub {$_[0]->($_[0]); }->(sub {
    my $x = shift;
    $f->(sub { $x->($x)->(@_); });
});

}

print y_combinator(sub {

my $factorial = shift;
sub {$_[0] < 2? 1: $_[0] * $factorial->($_[0] - 1); };

})->(10);
假如 Perl 能像其余语言一样申明参数列表,代码会更简洁直观:

sub y_combinator($f) {
sub($u) {$u->($u); }->(sub($x) {

$f->(sub { $x->($x)->(@_); });

});
}

print y_combinator(sub($factorial) {
sub($n) {$n < 2? 1: $n * $factorial->($n – 1); };
})->(10);

7 JavaScript

JavaScript 无疑是脚本语言中最风行的!但简短的 function、return 等关键字总是刺痛我的神经:

var y_combinator = function(fn) {

return (function(u) {return u(u);
})(function(x) {return fn(function() {return x(x).apply(null, arguments);
    });
});

};

y_combinator(function(factorial) {

return function(n) {return n <= 1? 1: n * factorial(n - 1);
};

})(10);
ES6 提供了 => 语法,能够更加简洁:

const y_combinator = fn => (u => u(u))(x => fn((…args) => x(x)(…args)));
y_combinator(factorial => n => n <= 1? 1: n * factorial(n – 1))(10);

8 Lua

Lua 和 JavaScript 有雷同的故障,最让我意外的是它没有三元运算符!不过没有应用花括号让代码看起来清新不少~

function y_combinator(f)

return (function(u)
    return u(u)
end)(function(x)
    return f(function(...)
        return x(x)(...)
    end)
end)

end

print(y_combinator(function(factorial)

return function(n)
    return n < 2 and 1 or n * factorial(n-1)
end

end)(10))
留神:Lua 版本为 5.2。5.1 的语法不同,需将 x(x)(…) 换成 x(x)(unpack(arg))。

9 PHP

PHP 也是 JavaScript 的难兄难弟,function、return……

此外,PHP 版本是脚本语言中符号($、_、()、{})用的最多的!是的,比 Perl 还多。

function y_combinator($f) {

return call_user_func(function($u) {return $u($u);
}, function($x) use ($f) {return $f(function() use ($x) {return call_user_func_array($x($x), func_get_args());
    });
});

}

echo call_user_func(y_combinator(function($factorial) {

return function($n) use ($factorial) {return ($n < 2)? 1: ($n * $factorial($n-1));
};

}), 10);

10 Java

最初,Java 退场。我说的不是 Java 8,即不是用 Lambda 表达式,而是匿名类!匿名函数的意义是把代码块作为参数传递,这正是匿名类所做得事件。


原文链接
本文为阿里云原创内容,未经容许不得转载。

退出移动版