我是否使用c#动态实现了y组合子，如果我没有，它是什么?

本文关键字：如果 它是什么 组合 是否 实现 动态 | 更新日期: 2023-09-27 18:10:32

我的大脑似乎处于受虐模式，所以在被这个，这个和这个淹没之后，它想在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)));

我是否使用c#动态实现了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程序员区分"按值调用"、"按引用调用"、"按复制恢复调用"等的方式混淆)。

但是如果我们那样做了，我们会得到

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)。

相关文章：