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

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

14 голосов
/ 05 октября 2011

Мой мозг, кажется, находится в мазохистском режиме, поэтому после того, как его утопили в этом , этом и этом , он захотел возиться с некоторыми своими руками в 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)));

1 Ответ

7 голосов
/ 06 октября 2011

Нет, это не 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).

...