Lambda 表达式编写递归一：前言及基础

这是一个比较古老的话题，三年半之前，老赵就此写过一篇很文章《使用Lambda表达式编写递归函数》。其中提出了伪递归的概念，提出了自己的解决方式，也引出了装配脑袋 使用不动点组合子 的解决办法。此后好长一段时间，伪递归和不动点组合子成了两个园子里的两大热门话题。当年我也写了篇文章《反驳 老赵 之 “伪”递归》参与了争论，不过对老赵提出的解决方式及装配脑袋的不动点组合子思路，一直没弄清楚。中间一段时间，工作忙，忘却了。最近比较轻闲，静下心来学习了下相关的的一些理论，并深入思考，略有所悟，在此和大家分享下。本文及后续章节会用到相当复杂的泛型及 lambda 表达式，请做好相关技术和心理准备。使用 Lambda 表达式构建递归函数很多朋友认为这很容易，随手便可用 lambda 表达式写出一个阶乘递归：1Func<int, int> fact = x => x <= 1 ? 1 : x * fact(x - 1);不过，很抱歉，这行代码是无法通过编译的，VS 提示：使用了未赋值的变量 fact。有种简单的解决办法，把上面这行代码拆成两行：12Func<int, int> fact = null;fact = x => x <= 1 ? 1 : x * fact(x - 1);不过这种写法也有问题，老赵说得比较清楚，我就不在赘述了，请查看《使用Lambda表达式编写递归函数》一文中伪递归部分。那么如何解决 lambda 表达式构建递归函数的问题呢？根据函数式编程理论，我们可以使用不定点组合子。在学习不定点组合子之前，需要先了解更基础 λ 演算。λ 演算λ 演算的基础请大家参考维基百科：http://zh.wikipedia.org/wiki/Lambda_演算 http://en.wikipedia.org/wiki/Lambda_calculus 非形式化的描述请确保你已经理解了文中几个表达式的等价关系：12(λf. f 3)(λx. x + 2) == (λx. x + 2) 3 == 3 + 2 (λx. λy. x - y) 7 2 == (λy.7 - y) 2 == 7 - 2还清楚知道函数应用（application）的概念及其左结合性：1f x y == (f x) y还有它的各种等价变换1f x y == (f x) y = (f(x))y = (f(x))(y) = f(x)(y)归约并会运用三个常用的规约（Reduction）α-变换（α-conversion） β-归约（β-reduction） η-变换（η-conversion） 不动点组合子请参考：http://zh.wikipedia.org/wiki/不动点组合子 http://en.wikipedia.org/wiki/Fixed-point_combinator 定义不动点组合子（Fixed-point combinator，或不动点算子，使用 FIX 表示）是计算其他函数的一个不动点的高阶函数。不动点算子具有以下特性，对于任何函数 f 都有：1FIX f = f (FIX f)定义匿名的递归函数不动点组合子允许定义匿名的递归函数，具体来说是将一个非递归的单步函数（只执行递归中的一步，a single step of this recursion，使用 g 表示）转换为递归函数。如下是阶乘的单步函数定义：1g = λf. λn. (ISZERO n) 1 (MULT n (f (PRED n)))FIX g 可获取到匿名的递归函数：1FIX g = λn. (ISZERO n) 1 (MULT n ((FIX g) (PRED n)))向 FIX g 的参数 n 传入值 5，可最终得出：1FIX g 5 = 5 * (4 * (3 * (2 * (1 * 1)))) = 120常用的不定点组合子不动点组合子中最有名的（也可能是最简单的）是 Y 组合子：1Y = λf. (λx. f (x x)) (λx. f (x x))另一个常见不动点组合子是图灵不动点组合子（阿兰·图灵发现的）: 1Θ = (λx. λy. (y (x x y))) (λx.λy.(y (x x y)))传值调用（call-by-value）在 λ 演算中，每个表达式（lambda term）都代表一个只有单独参数的函数，这个函数的参数本身也是一个只有单一参数的函数，同时，函数的值是又一个只有单一参数的函数。根据此描述，可知 λ 演算中函数只有一个参数，这个参数是一个函数，而不是一个值。而对于我们常见的递归（阶乘、斐波那契数列求值），参数都是值（自然数）。两者是不匹配的。为了适当传值调用，需要将不动点组合子 η-展开：简单而言 η-变换 是说 λx. f x 和 f 可以互相转换。从 f 这种简单形式 η-变换 为 λx. f x 复杂形式，称为 η-展开。对于 Y 组合子，通常是将其中的 (x x) η-展开为  λy. x x y，由此得出传值调用版本的 Y组合子（也称为 Z 组合子）：1Y = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y)) 如果不展开呢？会怎样？如果使用不展开的不动点算子，也能写出可编译通过的代码，但最终执行会陷入死循环，直至堆栈溢出。小结后续章节将使用以下符号和名称，不再另行说明：FIX：不动点组合子 g：单步函数 n：表示递归函数的参数（在阶乘、斐波那契数列求值中是一个自然数） 对于 FIX、g、n：FIX g： 将会生成对应的递归函数 FIX g n： 将进行递归运算 λ 演算表达式与 c# lambda 表达式的对应关系λx. x + 2λx. x + 2 在 c#中的 lambda 表达式可表式为：x => x+ 2；假定 x 的 int 类型，可写作：1Func<int, int> f = x => x + 2;相应 (λx. x + 2) 1 可写为：1var result = f(1); // 结果为 3λx. λy. x + y复杂点，λx. λy. x + y 用 c# 的 lambda 表达式表示为：x => y => x + y；x, y 类型为均整数时，可写作：1Func<int, Func<int, int>> f = x => y => x + y;相应 (λx. λy. x + y) 1 2 便是：1var result = f(1)(2); // 结果为 3λx. λy. λz. x + y + z 再复杂些，λx. λy. λz. x + y + z 表示为：x => y=> z => x + y + z，三个参数都为 int 时 c# 代码：1Func<int, Func<int, Func<int, int>>> f = x => y => z => x + y + z;可如下调用：123456789// (λx. λy. λz. x + y + z) 1 2 3var result1 = f(1)(2)(3); //结果为 6// (λx. λy. λz. x + y + z) 1 → λy. λz. 1 + y + z Func<int, Func<int, int>> g = f(1); // (λy. λz. 1 + y + z) 2 → λz. 1 + 2 + z → λz. 3 + zFunc<int, int> h = g(2);// (λz. 3 + z) 3 → 3 + 3 → 6var result2 = h(3); // 结果为 6每 5 行，向 f 传入一个常量 1，返回一个新的方法 g；再经过第 7 行，向 g 传入常量 2，再次返回一个新方法 h。方法 h 只能接受一个参数，最后得出 h(3) = 6。为什么不是  (x, y, z) => x + y + z？也许你会有疑问，不就是 x、y、z 三个整数加起来嘛，为什么搞这么复杂，像下面这样不是更简单吗？12Func<int, int, int, int> f = (x, y, z) => x + y + z;var result = f(1, 2, 3);确实简单，不过：在 λ 演算中，每个表达式（lambda term）都代表一个只有单独参数的函数，这个函数的参数本身也是一个只有单一参数的函数，同时，函数的值是又一个只有单一参数的函数。注意都是只有一个参数，对应到 c# 的 lambda 表达式，也应是一个参数，所以是：x => y=> z => x + y + z。总结λ 演算表达式c# lambda 表达式λx. x + 2x => x+ 2λx. λy. x + yx => y => x + yλx. λy. λz. x + y + zx => y=> z => x + y + z好像有些规律：对于一个 Lambda terms，去掉“λ”并把“.”替换为”=>”便可变成对应 lambda 表达式。（注意，这个规律不严谨！）练习一下，看看下面这个如何转为 lambda 表达式： 1λx. λn. (g (x x) n)先对它进行一步演算得出：1λx. λn. (g (x(x)) (n)) 运用上的的规律，可以写出 lambda 表达式：x => n => g((x(x))(n)对于复杂点的如：λx. f ( λv. (x x) v)，这条规律就不适用了。文后续部分会通过演算绕开这种复杂的转换，不对此进行讨论。理解本文中的泛型和 lambda 表达式 对于上一部分使用的泛型和 lambda 表达式，尤其是下面这行代码，你需要花点时间去理理思路（因为后续章节中泛型要远比此复杂）：1Func<int, Func<int, Func<int, int>>> f = x => y => z => x + y + z;如果对你对泛型和 lambda 认识不是非常深刻的话，难度有点大，不妨先从下面这个简单点的开始：1Func<int, Func<int, int>> f = x => y => x + y;换种写法，或许有助于理解：1234Func<int, Func<int, int>> f = x => { Func<int, int> g = y => { return x + y ;}; return g;}; 本文简单阐述了 lambda 构建递归函数的问题，粗略提及 λ 演算及不动点组合子的知识，并总结了下 λ 演算表达式与 c# lambda 表达式的对应关系。下一篇文章 将推断 FIX、g 的参数及返回值类型。-------------------思想火花，照亮世界