我是否使用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组合者; 你只有一半在那里.您仍然需要在应用它的"种子"函数中分解自我应用程序.也就是说,而不是这个:

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,它会在它做任何事之前等待另一个论点.因此,g在尝试(Y g)进一步评估之前,我们会等待第二个参数- 并且取决于函数的作用(即,如果它具有基本情况),我们可能根本不需要进行评估(Y g).这就是为什么Y适用于名称评估的原因.

按值调用的修正方法是更改​​等式.而不是Y g = g (Y g),我们想要类似下面的等式:

Z g = g (?x. (Z g) x)

(我想我的方程是正确的,或者接近正确.你可以计算出它,看它是否符合定义Z.)

想到这一点的一种方法是不是计算"整个递归函数"并将其交给它g,我们将它交给一个函数,它将一次一点地计算递归函数 - 并且只有当我们实际需要更多时才因此我们可以将它应用于参数(x).