我是否使用 C# 动态实现了 Y-combinator，如果没有，那是什么？

Question

我的大脑似乎处于受虐模式，所以在被 此 和 这个，它想用 C# 进行一些 DIY。

我想出了以下内容，我不认为它是 Y 组合器，但它似乎设法使非递归函数递归，而无需引用给它自己：

Func<Func<dynamic, dynamic>, Func<dynamic, dynamic>> Y = x => x(x);

所以给定这些：

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(self)(n - 1);
Func<dynamic, Func<dynamic, dynamic>> fib = 
                  self => n => n < 2 ? n : self(self)(n-1) + self(self)(n-2);

我们可以生成这些：

Func<dynamic, dynamic> Fact = Y(fact);
Func<dynamic, dynamic> Fib = Y(fib);

Enumerable.Range(0, 10)
          .ToList()
          .ForEach(i => Console.WriteLine("Fact({0})={1}", i, Fact(i)));

Enumerable.Range(0, 10)
          .ToList()
          .ForEach(i => Console.WriteLine("Fib({0})={1}", i, Fib(i)));

Answer 1

不，那不是 Y 组合器；而是 Y 组合器。你只完成了一半。您仍然需要在要应用它的“种子”函数中分解出自我应用程序。也就是说，

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(self)(n - 1);

您应该这样：

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(n - 1);

注意第二个定义中仅出现一次 self，而不是第一个定义中出现两次。

（编辑添加：）顺便说一句，由于您使用 C# 通过按值调用评估来模拟 lambda 演算，因此您想要的定点组合器是 通常称为 Z，而不是 Y

（再次编辑以详细说明：）描述 Y 的方程是这样的（请参阅维基百科页面了解推导）：

Y g = g (Y g)

但在大多数实用的编程语言中，在调用函数之前评估函数的参数。在编程语言社区中，这称为按值调用评估（不要与 C/C++/Fortran/etc 程序员区分“按值调用”与“按引用调用”与“通过复制恢复调用”的方式混淆） ， ETC）。

但如果我们这样做，我们就会得到

Y g = g (Y g) = g (g (Y g)) = g (g (g (Y g))) = ...

也就是说，我们将花费所有时间构建递归函数，而永远不会应用它。

另一方面，在按名称调用求值中，您将函数（此处为 g）应用于未求值的参数表达式（此处为 (Y g)）。但如果 g 就像 fact 一样，它会在执行任何操作之前等待另一个参数。因此，在尝试进一步评估 (Y g) 之前，我们会等待 g 的第二个参数——并且取决于函数的作用（即，如果它有一个基本情况），我们可能根本不需要评估(Y g)。这就是 Y 适用于按名称调用评估的原因。

按值调用的解决方法是更改​​方程式。我们想要的不是 Y g = g (Y g)，而是类似下面的方程：（

Z g = g (λx. (Z g) x)

我认为我得到的方程是正确的，或者接近正确的。你可以计算出来，看看它是否符合 Z 的定义。）

一种思考方式是，我们不计算“整个递归函数”并将其交给 g，而是将其交给一个函数：将一次一点地计算递归函数——并且仅当我们确实需要更多时，我们才能将其应用于参数 (x)。