我是否使用C＃动态实现了Y-combinator，如果没有，那是什么？ [英] Have I implemented Y-combinator using C# dynamic, and if I haven't, what is it?

问题描述

我的大脑似乎处于虐待模式，所以在被淹死之后，他被淹死了。这个，这个和这个，它想要搞乱一些DIY在C＃。

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

  Func&FunC ;动态，动态>，Func<动态，动态>> 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<动态，动态>事实= Y（事实）; 
 Func<动态，动态> Fib = Y（fib）; 
 
 Enumerable.Range（0，10）
 .ToList（）
 .ForEach（i => Console.WriteLine（Fact（{0}）= {1} ，我，事实（i）））; 
 
 Enumerable.Range（0，10）
 .ToList（）
 .ForEach（i => Console.WriteLine（Fib（{0}）= {1} ，我，Fib（i）））; 
  

解决方案

不，这不是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 第二个定义与第一个定义中的两个事件相反。

（编辑为添加:) BTW，由于您使用C＃通过调用模拟模拟lambda演算，价值评估，您想要的定点组合器是通常称为Z，而不是Y

（再次编辑以阐述:)描述 Y 的方程是这样的（参见维基百科页面的推导）：

  Y g = g（Y g）
  

但是在大​​多数实用的编程语言在调用函数之前，您需要评估函数的参数。在编程语言社区中，这被称为调用值评估（不要与C / C ++ / Fortran / etc程序员区分按值调用vs通过引用调用vs通过copy-restore调用的方式混淆） ，等）。

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

  Y g = g（Y g）= g（g（Y g））= g（g（g（Y g）））= ... 
  

也就是说，我们将花费我们所有的时间来构建递归函数，永远不要绕过应用它。

另外一方面，在按名称评估中，您应用一个函数，这里 g 没有评价的论据表达式，这里（Y g）。但是，如果 g 就像事实，那么在它做任何事情之前，它正在等待另一个参数。所以我们等待第二个参数 g ，然后再尝试评估（Y g）关于该函数的功能（即，如果它有一个基本情况），我们可能不需要评估（Y g）。这就是为什么 Y 可以用于按名称评估。

对值调用的修复是改变方程。而不是 Y g = g（Y g），我们需要像以下公式：

  Z g = g（λx。（Z g）x）
  

我想我的方程式是正确的，或者靠近右边，你可以计算出来，看看它是否符合 Z 的定义。）

想到这一点的一种方法不是计算整个递归函数，而是把它交给 g ，我们给它一个函数，一次计算递归函数---只有当我们实际需要更多的时候才可以将它应用于参数（ x ）。 / p>

My brain seems to be in masochistic mode, so after being drowned in this, this and this, it wanted to mess around with some DIY in C#.

I came up with the following, which I don't think is the Y-combinator, but it does seem to manage to make a non-recursive function recursive, without referring to itself:

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

So given these:

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

We can generate these:

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

解决方案

No, that's not the Y combinator; you're only halfway there. You still need to factor out the self-application within the "seed" functions you're applying it to. That is, instead of this:

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

you should have this:

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

Note the single occurrence of self in the second definition as opposed to the two occurrences in the first definition.

(edited to add:) BTW, since your use of C# simulates the lambda calculus with call-by-value evaluation, the fixed-point combinator you want is the one often called Z, not Y

(edited again to elaborate:) The equation that describes Y is this (see the wikipedia page for the derivation):

Y g = g (Y g)

But in most practical programming languages, you evaluate the argument of a function before you call the function. In the programming languages community, that's called call-by-value evaluation (not to be confused with the way C/C++/Fortran/etc programmers distinguish "call by value" vs "call by reference" vs "call by copy-restore", etc).

But if we did that, we'd get

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

That is, we'd spend all of our time constructing the recursive function and never get around to applying it.

In call-by-name evaluation, on the other hand, you apply a function, here g, to the unevaluated argument expression, here (Y g). But if g is like fact, it's waiting for another argument before it does anything. So we would wait for the second argument to g before trying to evaluate (Y g) further---and depending on what the function does (ie, if it has a base case), we might not need to evaluate (Y g) at all. That's why Y works for call-by-name evaluation.

The fix for call-by-value is to change the equation. Instead of Y g = g (Y g), we want something like the following equation instead:

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

(I think I got the equation right, or close to right. You can calculate it out and see if it fits with the definition of Z.)

One way to think of this is instead of computing "the whole recursive function" and handing it to g, we hand it a function that will compute the recursive function a little bit at a time---and only when we actually need a bit more of it so we can apply it to an argument (x).

这篇关于我是否使用C＃动态实现了Y-combinator，如果没有，那是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！