Я реализовал Y-комбинатор, используя C# динамический, и если я не сделал, что это?

Question

Мой мозг, кажется, находится в мазохистском режиме, поэтому после того, как он утонул в этом, этом и этом, он захотел возиться с каким-то DIY в C#.

Я придумал следующее: я не думаю, что это 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# имитирует лямбда-исчисление с оценкой по значению, вам нужен комбинатор с фиксированной точкой, который часто называется 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).