10种编程语言实现Y组合子

简介：Y组合子是Lambda演算的一部分，是函数式编程的理论基础。定义一个没有赋值语句的递归匿名函数是一种方法/技巧，即只通过Lambda表达式最基本的“原子”来实现循环/迭代。本文将使用10种不同的编程语言实现Y组合器和递归阶乘函数的Y版本。作者|技术员来源|阿里科技公众号-Y-CombinatorY组合子是Lambda演算的一部分，是函数式编程的理论基础。这是一种在没有赋值语句的情况下定义递归匿名函数的方法/技巧。即只通过Lambda表达式最基本的“原子”实现循环/迭代，有道生一，一生二，二生三，三生万物的感觉。1从递归阶乘函数开始，写出最简单的递归阶乘函数，不考虑效率等其他因素。这里使用Scheme，大家可以选择自己熟悉的编程语言，跟着我一步步实现Y-Combinator版的阶乘函数。(define(factorialn)(if(zero?n)1(*n(factorial(-n1)))))(define(fn-name))在Scheme中是(definefn-name(lambda))的简写，就像在JS中一样，functionfoo(){}等同于varfoo=function(){}。把上面的定义展开成Lambda定义：(definefactorial(lambda(n)(if(zero?n)1(*n(factorial(-n1))))))2bindfunctionnamewanttorecursivetocalla函数，你必须给函数一个名字。如果一个匿名函数想要实现递归，它就不得不取一个临时的名字。所谓临时的，就是这个名字只在函数体内有效。函数执行后，名称随函数一起消失。为了解决这个问题，第一篇文章[1]中强制要求匿名函数有一个指向自身的隐藏名this，导致变量名this被强行占用，不优雅，所以第二篇文章[2]借鉴了允许自定义名称的Clojure方法。但是在Lambda演算中，只有最常见的Lambda，没有赋值语句，如何绑定一个名字？答案是使用Lambda的参数列表！(lambda(factorial)(lambda(n)(if(zero?n)1(*n(factorial(-n1))))))3通过参数列表生成阶乘函数的函数，即使用闭包技巧给匿名函数一个名字，但是这个函数并不是我们想要的阶乘函数，而是阶乘函数的元阶乘函数，也就是生成阶乘函数的函数。因此，您需要执行此元函数以获得所需的阶乘函数：((lambda(factorial)(lambda(n)(if(zero?n)1(*n(factorial(-n1))))))xxx)这时候又产生了一个问题：实参xxx，即形参阶乘应该取什么值呢？根据定义，阶乘就是函数本身。既然是“self”，首先想到的就是复制一模一样的代码：((lambda(factorial)(lambda(n)(if(zero?n)1(*n(factorial(-n1))))))(lambda(factorial)(lambda(n)(if(zero?n)1(*n(factorial(-n1)))))))看起来已经把它自己传递给了自己，但是马上发现(factorial(-n1))会失败，因为此时的factorial不是阶乘函数，而是包含阶乘函数的函数，也就是获取内部函数，所以调用方法为更改为((meta-factorialmeta-factorial)(-n1)):((lambda(meta-factorial)(lambda(n)(if(zero?n)1(*n((meta-factorialmeta-factorial)(-n1)))))(lambda(meta-factorial)(lambda(n)(if(zero?n)1(*n((meta-factorialmeta-factorial)(-n1)))))))将名称改为meta-factorial可以清楚地表明它是factorial的元函数，而不是factorial函数本身。4去除重复上面的代码已经实现了lambda的自调用，但是里面有重复的代码，meta-factorial既是函数又是参数，即(metameta):((lambda(meta)(metameta))(lambda(meta-factorial)(lambda(n)(if(zero?n)1(*n((meta-factorialmeta-factorial)(-n1)))))))5提取阶乘function因为我们要的是Factorialfunction，所以把(meta-factorialmeta-factorial)换成factorial，方法也用参数列表命名：((lambda(meta)(metameta))(lambda(meta-factorial)((lambda(factorial)(lambda(n)(if(zero?n)1(*n(factorial(-n1)))))(meta-factorialmeta-factorial))))此代码不起作用然而由于Scheme等世界上主要的编程语言实现都是采用“应用顺序”，即在函数执行时先计算参数的值，所以(meta-factorialmeta-factorial)本来是在执行期间执行的计算的过程atingthefactorial，现在提取后的执行时间被提前，从而陷入死循环。解决方案是将其包装在Lambda中（您了解了Lambda的另一种用途：延迟执行）。((lambda(meta)(metameta))(lambda(meta-factorial)((lambda(factorial)(lambda(n)(if(zero?n)1(*n(factorial(-n1))))))(lambdaargs(apply(meta-factorialmeta-factorial)args)))))此时，代码中的第4行到第8行正是最初定义的匿名递归阶乘函数，我们最终得到阶乘函数本身！6形成模式如果将阶乘函数作为一个整体抽取出来，就是一个“模式”，即可以生成任意匿名递归函数的模式：((lambda(fn)((lambda(meta)(metameta))(lambda(meta-fn)(fn(lambdaargs(apply(meta-fnmeta-fn)args)))))(lambda(factorial)(lambda(n)(if(zero?n)1(*n(factorial(-n1))))))在Lambda演算中，这种模式被称为Y-Combinator(Y-Combinator)，即：(define(y-combinatorfn)((lambda(meta)(metameta))(lambda(meta-fn)(fn(lambdaargs(apply(meta-fnmeta-fn)args))))))使用Y组合器，我们可以定义任意匿名递归函数。前面的定义是递归阶乘，然后定义一个递归斐波那契数：(y-combinator(lambda(fib)(lambda(n)(if(36288002Clojure实际上，Clojure可以实现匿名递归函数而不用Y-Combinator，其lambda—fn—支持传递一个函数名来命名临时函数。也许Clojure的fn不应该叫匿名函数，应该叫临时函数更合适。Lisp也是一样，Clojure版本比Scheme版本短，但是让我觉得是刻意的简洁。我喜欢用fn代替lambda，但是用怪异的符号来减小代码的大小会降低代码的可读性（我最近好像不太喜欢符号了，哈哈).(defny-combinator[f](#(%%)(fn[x](f#(apply(xx)%&))))((y-combinator(fn[factorial]#(if(零?%)1(*%(factorial(dec%))))))10)3CommonLispCommonLisp版本其实和toScheme版本，除了CommonLisp属于Lisp-2，即函数命名空间不同于变量命名空间，所以在调用匿名函数时需要额外的funcall。个人不喜欢这个额外的调用，我觉得是多余的信息，职位信息已经包含了角色信息，就像命令行的第一个参数永远是命令一样。(defuny-combinator(f)((lambda(u)(funcalluu))(lambda(x)(funcallf(lambda(&restargs)(apply(funcallxx)args))))(funcall(y-combinator(lambda(factorial)(lambda(n)(if(zeropn)1(*n(funcallfactorial(1-n)))))))10)4Ruby从Lisp中借鉴了很多，包括它的缺点。比如CommonLisp，在Ruby中执行匿名函数也需要额外的“.call”，或者用方括号“[]”代替普通函数一样的圆括号“()”。简而言之，Ruby中的匿名函数与普通的函数，函数不一样！还有一些复杂的符号，也影响了我在Ruby中使用匿名函数的心情，所以我会把Ruby当成Java，语法更灵活简洁，不会考虑写函数式的代码。defy_combinator(&f)lambda{|&u|u[&u]}.call做|&x|f[&lambda{|*a|x[&x][*a]}]endendy_combinator做|&factorial|lambda{|n|n。零？？1：n*factorial[n-1]}end[10]5P中的Python匿名函数ython的使用方式与普通函数相同。就这段代码而言，Python之于Ruby就像Scheme之于CommonLisp。但是Python对Lambda的支持简直弱到不行，函数体内只能有一条语句！我已经决定在我的工具箱中用Python替换C，尽管Python对匿名函数的支持只比C好一点点。defy_combinator(f):return(lambdau:u(u))(lambdax:f(lambda*args:x(x)(*args)))y_combinator(lambdafactorial:lambdan:1ifn<2elsen*factorial(n-1))(10)6Perl我个人对Perl函数无法声明参数的抱怨不仅仅是繁琐的符号！suby_combinator{my$f=shift;sub{$_[0]->($_[0]);}->(sub{my$x=shift;$f->(sub{$x->($x)->(@_);});});}printy_combinator(sub{my$factorial=shift;sub{$_[0]<2?1:$_[0]*$factorial->($_[0]-1);};})->(10);假设Perl可以像其他语言一样声明参数列表，代码会更加简洁直观：suby_combinator($f){sub($u){$u->($u);}->(sub($x){$f->(sub{$x->($x)->(@_);});});}printy_combinator(sub($factorial){sub($n){$n<2?1:$n*$factorial->($n-1);};})->(10);7JavaScriptJavaScript绝对是最流行的脚本语言！但是冗长的function、return等关键字总是刺痛我的神经：返回x(x).apply(null,arguments);});});};y_combinator(函数(阶乘){返回函数(n){返回n<=1?1:n*阶乘(n-1);};})(10);ES6提供了=>语法，可以更简洁：consty_combinator=fn=>(u=>u(u))(x=>fn((...args)=>x(x)(...args)));y_combinator(factorial=>n=>n<=1?1:n*factorial(n-1))(10);8LuaLua和JavaScript有同样的问题，最让我吃惊的是它没有三元运算符！但是不使用花括号让代码看起来干净很多~functiony_combinator(f)return(function(u)returnu(u)end)(function(x)returnf(function(...)returnx(x)(...)end)end)endprint(y_combinator(function(factorial)returnfunction(n)returnn<2and1orn*factorial(n-1)endend)(10))注：Lua版本为5.25。1的语法不一样，需要把x(x)(...)换成x(x)(unpack(arg))。9PHPPHP也是JavaScript的难兄难弟，function，return...另外，PHP版本是脚本语言中使用最多的符号($,_,(),{})！是的，超过Perl。函数y_combinator($f){returncall_user_func(function($u){return$u($u);},function($x)use($f){return$f(function()use($x){返回call_user_func_array($x($x),func_get_args());});});}echocall_user_func(y_combinator(function($factorial){returnfunction($n)use($factorial){return($n<2)?1:($n*$factorial($n-1));};}),10);10Java最后，Java登场了。我不是在谈论Java8，即不是Lambda表达式，而是匿名类！匿名函数的要点是将一段代码作为参数传递，这正是匿名类所做的。原文链接本文为阿里云原创内容，未经许可不得转载。