(define(factorialn)(if(zero?n)1(*n(factorial(-n1)))))Scheme中(define(fn-name))是(definefn-name(lambda))的简写,就像JS中,functionfoo(){}等价于varfoo=function(){}。把上面的定义展开成Lambda的定义:
(definefactorial(lambda(n)(if(zero?n)1(*n(factorial(-n1))))))2绑定函数名想要递归地调用一个函数,就必须给这个函数取一个名字。匿名函数想要实现递归,就得取一个临时的名字。所谓临时,指这个名字只在此函数体内有效,函数执行完成后,这个名字就伴随函数一起消失。为解决这个问题,第一篇文章中[1]强制规定匿名函数有一个隐藏的名字this指向自己,这导致this这个变量名被强行占用,并不优雅,因此第二篇文章[2]借鉴Clojure的方法,允许自定义一个名字。但在Lambda演算中,只有最普通的Lambda,没有赋值语句,如何绑定一个名字呢?答案是使用Lambda的参数列表!
(lambda(factorial)(lambda(n)(if(zero?n)1(*n(factorial(-n1))))))3生成阶乘函数的函数虽然通过参数列表,即使用闭包技术给匿名函数取了一个名字,但此函数并不是我们想要的阶乘函数,而是阶乘函数的元函数(meta-factorial),即生成阶乘函数的函数。因此需要执行这个元函数,获得想要的阶乘函数:
((lambda(factorial)(lambda(n)(if(zero?n)1(*n(factorial(-n1))))))xxx)此时又出现另一个问题:实参xxx,即形参factorial该取什么值?从定义来看,factorial就是函数自身,既然是“自身”,首先想到的就是复制一份一模一样的代码:
((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就能清晰地看出它是阶乘的元函数,而不是阶乘函数本身。4去除重复以上代码已经实现了lambda的自我调用,但其中包含重复的代码,meta-factorial即做函数又做参数,即(metameta):
((lambda(meta)(metameta))(lambda(meta-factorial)(lambda(n)(if(zero?n)1(*n((meta-factorialmeta-factorial)(-n1)))))))5提取阶乘函数因为我们想要的是阶乘函数,所以用factorial取代(meta-factorialmeta-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)原来是在求阶乘的过程中才被执行,现在提取出来后执行的时间被提前,于是陷入无限循环。解决方法是把它包装在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组合子(Y-Combinator),即:
(define(y-