Ai-je implémenté Y-combinator en utilisant C# dynamic, et si non, qu'est-ce que c'est?

Question

Mon cerveau semble être en mode masochiste, donc après avoir été noyé dans this, this et this, il voulait déranger avec un peu de bricolage en C#.

je suis venu avec ce qui suit, que je ne pense est le Y-Combinator, mais il ne semblent réussir à faire une récursif de fonction non récurrente, sans se référer à lui-même:

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

donc, étant donné ces:

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

Nous pouvons générer ces:

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

Non, ce n'est pas le combinateur Y; vous n'êtes qu'à mi-chemin. Vous avez encore besoin de factoriser l'auto-application dans les fonctions de «graine» auxquelles vous l'appliquez. Autrement dit, au lieu de cela:

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

vous devriez avoir ceci:

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

Notez la seule occurrence de self dans la deuxième définition, par opposition aux deux événements dans la première définition.

(sous la direction d'ajouter :) BTW, depuis votre utilisation de C# simule le calcul lambda à l'évaluation appel par valeur, le point fixe Combinator que vous voulez est the one often called Z, not Y

(modifié à nouveau pour élaborer :) Le équation qui décrit Y est ce (voir the wikipedia page pour la dérivation):

Y g = g (Y g) 

Mais dans les langages de programmation les plus pratiques, vous évaluez l'argument d'une fonction avant d'appeler la fonction. Dans la communauté des langages de programmation, cela s'appelle l'évaluation call-by-value (à ne pas confondre avec la façon dont les programmeurs C/C++/Fortran/etc distinguent "call by value" vs "call by reference" vs "call by copy-restore" , etc).

Mais si nous faisions cela, nous obtiendrions

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

C'est, nous passerions tout notre temps construire la fonction récursive et ne jamais se déplacer à l'application il.

Dans l'évaluation call-by-name, d'autre part, vous appliquez une fonction, ici g, à l'expression d'argument non évaluée, ici (Y g). Mais si g est comme fact, il attend un autre argument avant de faire quoi que ce soit. Donc, nous attendrions le second argument à g avant d'essayer d'évaluer (Y g) plus loin --- et en fonction de ce que la fonction fait (c'est-à-dire, si elle a un cas de base), nous n'aurons pas besoin d'évaluer (Y g) du tout. C'est pourquoi Y fonctionne pour l'évaluation call-by-name.

Le correctif pour l'appel-par-valeur est de changer l'équation.Au lieu de Y g = g (Y g), nous voulons quelque chose comme l'équation suivante à la place.

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

(je pense que je suis l'équation à droite, ou à proximité de droite, vous pouvez calculer et voir si elle correspond à la définition de Z. Une façon de penser à ceci est de remplacer "la fonction récursive entière" par g, et de lui donner une fonction qui va calculer la fonction récursive un peu à la fois --- et seulement quand nous avons en fait besoin d'un peu plus pour que nous puissions l'appliquer à un argument (x).