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

问题描述

我的大脑似乎处于自虐模式，所以在被淹没在this, this 和 this，它想弄乱在 C# 中进行一些 DIY.

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#.

我想出了以下内容，我不认为是 Y 组合器，但它确实似乎设法使非递归函数递归, 不指代自身:

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

鉴于这些:

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

推荐答案

不，那不是 Y 组合子；你只是成功了一半.您仍然需要在您应用它的种子"功能中分解出自我应用程序.也就是说，而不是这样:

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

你应该有这个:

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

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

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

(编辑添加:)顺便说一句，由于您使用 C# 模拟了具有按值调用评估的 lambda 演算，因此您想要的定点组合器是 通常称为 Z 而非 Y 的那个

(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

(再次编辑以详细说明:)描述 Y 的等式是这样的(参见 维基百科页面 用于推导):

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

Y g = g (Y g)

但在大多数实际编程语言中，您在调用函数之前评估函数的参数.在编程语言社区中，这称为按值调用(不要与 C/C++/Fortran/etc 程序员区分按值调用"、按引用调用"和按复制恢复调用"的方式混淆)等).

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.

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

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.

按价值调用的解决方法是改变等式.我们想要的不是 Y g = g (Y g)，而是类似于以下等式:

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)

(我觉得我的方程是对的，或者说接近对.你可以计算出来看看它是否符合Z的定义.)

(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.)

一种思考方式是，不是计算整个递归函数"并将其交给g，而是将其交给一个函数，该函数将一次计算一点递归函数--- 并且只有在我们确实需要更多的时候才能将它应用到参数 (x) 上.

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# dynamic 实现了 Y-combinator，如果没有，它是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！