c# - 我是否使用 C# 动态实现了 Y 组合器，如果没有，它是什么？

Question

我的大脑似乎处于自虐模式，所以在被this淹没之后, this和 this ，它想在 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 组合子；你只完成了一半。您仍然需要在您应用它的“种子”功能中分解出 self 应用程序。也就是说，不是这样的:

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 演算，因此您想要的定点组合器是 the one often called Z, not Y

(再次编辑以详细说明:)描述 Y 的等式是这样的(推导参见 the wikipedia page):

Y g = g (Y g)

但是在大​​多数实用的编程语言中，您在调用函数之前评估函数的参数。在编程语言社区中，这称为按值调用评估(不要与 C/C++/Fortran/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)。