探索匿名递归函数

原创
09/06 03:36
阅读数 1W

匿名递归

在 C# 里递归可以这么定义吗?

Func<int, int> fac = (x) => (x <= 1) ? 1 : x * fac(x - 1);

目前不行。因为 C# 只认识下面这种写法:

Func<int, int> fac = null;
fac = (x) => (x <= 1) ? 1 : x * fac(x - 1);

但这实际上并未使该函数匿名化,而是把变量 fac 的引用绑定到了匿名函数的上下文中。这在变量 fac 被修改后存在失效的风险。

将自己传给自己

为了使匿名递归可行,必须将自身作为参数传给自己。

这么写可行吗?

var fac = (f, x) => (x <= 1) ? 1 : f(f, x - 1);
fac(fac, 5);

在 C# 里不行。因为 fac 的类型签名无法被自动推断,需要人工提供。

delegate int SelfFactorial(SelfFactorial f, int x);

写成泛型,提高通用性:

delegate TResult SelfApplicable<T, TResult>(SelfApplicable<T, TResult> self, T arg);
SelfApplicable<int, int> fac = (f, x) => (x <= 1) ? 1 : f(f, x - 1);
fac(fac, 5);

更进一步,为 fac 构建函数闭包,得到我们想要的函数形式:

Func<int, int> Fac = (x) => fac(fac, x);

综合以上过程,给出一个通用形式的帮助函数,简化类型推断:

static Func<T, TR> Make<T, TR>(SelfApplicable<T, TR> self)
{
    return (x) => self(self, x);
}

var fac = Make<int, int>((f, x) => (x <= 1) ? 1 : x * f(f, x - 1));

推广到两个参数的情形:

delegate TR SelfApplicable<T1, T2, TR>(SelfApplicable<T1, T2, TR> self, T1 arg1, T2 arg2);

static Func<T1, T2, TR> Make<T1, T2, TR>(SelfApplicable<T1, T2, TR> self)
{
    return (x, y) => self(self, x, y);
}

var gcd = Make<int, int, int>((f, x, y) => (y == 0) ? x : f(f, y, x % y));

但类型推断并不是什么大问题,下文如因类型推断而无法写出,大可手动补上。

柯里化

柯里化即将多参数的函数转化为多个单参数函数的嵌套。

你可能会想到这种写法:

var fac = Make2<int, int>((f) => (x) => (x <= 1) ? 1 : x * f(x - 1));

这需要配套怎样的 Make2 呢?

static Func<T, TR> Make2<T, TR>(Func<Func<T, TR>, Func<T, TR>> g)
{
    // 建立一个新的上下文,在里面用上 g 就能把 g 保存起来。
    var wrapped_k = (x) => {
        // 先跳过这行分析下面的,因为 h 是为了传给 g 做参数的。
        // 这个操作必须在子函数体内,不然就死循环了。
        var h = Make2(g);
        // k 才是想要的那个功能函数,但获得这个 k 之前没法传给 g 做其参数 f,陷入了鸡生蛋蛋生鸡的矛盾。
        // g 的参数 f 无法是 k,但 Make2 能构造 k 的转发函数,且转发函数使用时才会计算,不会死循环。
        var k = g(h);
        k(x);
    };
    // 这是一个 k 的转发函数,用起来就跟 k 没什么区别。而且它的上下文里有 g 的引用。
    return wrapped_k;
}

这是一个不动点组合子(将在下文中解释其含义),让我们先将其重命名为 Fix

static Func<T, TR> Fix<T, TR>(Func<Func<T, TR>, Func<T, TR>> g)
{
    return (x) => g(Fix(g))(x);
}

Fix 要配合一种两层的匿名函数写法。其中递归函数自身作为外层函数的参数,Fix 将其转化为了可以直接使用的函数对象。

两个参数的 Fix 函数也可以顺利写出来了:


static Func<T1, T2, TR> Fix<T1, T2, TR>(Func<Func<T1, T2, TR>, Func<T1, T2, TR>> g)
{
    return (x, y) => g(Fix(g))(x, y);
}
// g0 也可称为单步函数
var g0 = (f) => (x) => (x <= 1) ? 1 : x * f(x - 1);
var fac = Fix<int, int>(g0);
fac(5);

var g1 = (f) => (x, y) => (y == 0) ? x : f(y, x % y);
var gcd = Fix<int, int, int>(g1);
gcd(10, 15);

先把单步函数抽象一下:

// use(x) 产生当次执行的计算结果
// next(f, x) 递归地产生 f(x),或是在没有下一个 x 时及时终止
// reduce(a, b) 将当次与递归的结果合并为最终结果
var g = (f) => (x) => reduce(use(x), next(f, x));

以一个参数的 Fix 函数为例分析其过程。

先分析这个两层匿名函数 g,并将内层函数单独称为 k:

// 注意:这是方便理解而拆开的伪代码,因为不可能使 k 在没有 f 的上下文中绑定到 f。类型推断也是个问题。
var k = (x) => reduce(use(x), next(f, x));
var g = (f) => k;

var f0 = Fix(g) = (x) => g(Fix(g))(x);

这里的参数 x 被直接转发给了内部函数 h(Fix(g)),因此我们可以在分析时简化。

var f0 = (x) => k(x), f=Fix(g);

虽然每次 f=Fix(g) 计算得到一个新的函数对象而不是复用已得到的 f0,但二者的效果是相同的。

这里有一个等式:

g(Fix(g)) == Fix(g)

一般地,我们称值 x 是函数 f 的一个不动点,当且仅当 f(x) = x

那么根据上文中的两个等式,值 Fix(g) 是函数 g 的一个不动点。

Y-组合子

Y-组合子定义为:

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

注意:根据 α-变换,两个 λx 是不同的变元,互不影响。即上式与下式等价:

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

但只要表达式相同,自由变元的名字无关紧要,所以在两个不同的地方都用 λx 是没问题的。

拆分一下,方便理解:

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

写成 C# 是:

var Y = (f) => {
    // 这虽然写得出代码,但执行起来会死循环
    var H = (x) => f(x(x));
    return H(H);
};

因此这里需要多一层转发函数的嵌套,使 x(x) 被推迟执行。推迟执行最重要的目的是在递归到头的时候不再计算从而能够退出。

增加一层转发函数,这对应于 λ-演算,即可以使用 η-变换。有两个做法:

  • x x 展开为 λv.(x x) v
  • f (x x) 展开为 λv.(f (x x)) v

第二种变换对应的 C# 是:

var Y = (g) => {
    var H = (h) => {
        var wrapped_k = (x) => {
            // 每次 h(h) 都得到一个新的 wrapped_k
            var new_wrapped_k = h(h);
            // 在 wrapped_k 中使用了 g
            // 换取真正的功能函数,而 new_wrapped_k(next(x)) 是能递归下去的
            var k = g(new_wrapped_k);
            return k(x);
        };
        return wrapped_k;
    };
    // 巧妙的 H(H), h(h) 组合,创建对 g 的闭包
    return H(H);
};

简写为:

var Y = (g) => {
    var H = (h) => (x) => g(h(h))(x);
    return H(H);
};

Θ-组合子

var H = (h) => (g) => (x) => g(h(h)(g))(x);
var Θ = H(H);

Θ-组合子 与 Y-组合子 的唯一区别就是变量 g 在多层函数的位置,以及因此而需要的一个重复传参的步骤。

这两个组合子的对比同时说明了以下等式:

λx.λy.((f x y) y0 x0) == λy.λx.((f x y) x0 y0)
展开阅读全文
打赏
0
5 收藏
分享
加载中
public static readonly Action<object> ShowMessage = EventAggregator<object>.CreateEvent(() => ShowMessage);
09/19 20:51
回复
举报
看标题就猜到会提Y组合子,就是不知道在编程领域有什么作用
09/11 21:54
回复
举报
神乎其技
09/11 10:24
回复
举报
更多评论
打赏
3 评论
5 收藏
0
分享
在线直播报名
返回顶部
顶部