Qu’est-ce qu’un combinateur Y?

Si vous êtes prêt pour une longue lecture, Mike Vanier a une bonne explication . En bref, cela vous permet d’implémenter la récursivité dans un langage qui ne le supporte pas nécessairement nativement.

Un combinateur Y est un “fonctionnel” (une fonction qui opère sur d’autres fonctions) qui permet la récursivité, lorsque vous ne pouvez pas vous référer à la fonction depuis elle-même. En théorie de l’informatique, elle généralise la récursivité , en résume la mise en œuvre et la sépare ainsi du travail réel de la fonction en question. L’avantage de ne pas avoir besoin d’un nom à la compilation pour la fonction récursive est en quelque sorte un bonus. =)

Ceci est applicable dans les langues qui prennent en charge les fonctions lambda . La nature basée sur l’ expression des lambdas signifie généralement qu’ils ne peuvent pas se référer à eux-mêmes par leur nom. Et contourner cela en déclarant la variable, en s’y référant, puis en lui assignant le lambda, pour compléter la boucle d’auto-référence, est fragile. La variable lambda peut être copiée et la variable d’origine réatsortingbuée, ce qui rompt la référence automatique.

Les combinateurs Y sont lourds à mettre en œuvre et souvent à utiliser dans les langages de type statique (que sont souvent les langages procéduraux ), car les ressortingctions de typage exigent généralement que le nombre d’arguments de la fonction en question soient connus au moment de la compilation. Cela signifie qu’un combinateur y doit être écrit pour tout nombre d’arguments à utiliser.

Vous trouverez ci-dessous un exemple d’utilisation et de fonctionnement d’un combinateur Y, en C #.

L’utilisation d’un combinateur en Y implique une manière “inhabituelle” de construire une fonction récursive. Vous devez d’abord écrire votre fonction en tant que morceau de code qui appelle une fonction préexistante, plutôt qu’elle-même:

// Factorial, if func does the same thing as this bit of code... x == 0 ? 1: x * func(x - 1); 

Ensuite, vous transformez cela en une fonction qui appelle une fonction et retourne une fonction qui le fait. Cela s’appelle une fonction, car elle prend une fonction et effectue une opération qui entraîne une autre fonction.

 // A function that creates a factorial, but only if you pass in // a function that does what the inner function is doing. Func, Func> fact = (recurs) => (x) => x == 0 ? 1 : x * recurs(x - 1); 

Maintenant, vous avez une fonction qui prend une fonction et renvoie une autre fonction qui ressemble à une factorielle, mais au lieu de s’appeler elle-même, elle appelle l’argument passé dans la fonction externe. Comment faites-vous cela le factoriel? Passer la fonction interne à elle-même. Le Y-Combinator fait cela, en étant une fonction avec un nom permanent, qui peut introduire la récursivité.

 // One-argument Y-Combinator. public static Func Y(Func, Func> F) { return t => // A function that... F( // Calls the factorial creator, passing in... Y(F) // The result of this same Y-combinator function call... // (Here is where the recursion is introduced.) ) (t); // And passes the argument into the work function. } 

Plutôt que l’appel factoriel proprement dit, le factoriel appelle le générateur factoriel (renvoyé par l’appel récursif à Y-Combinator). Et en fonction de la valeur courante de t, la fonction renvoyée par le générateur appelle à nouveau le générateur, avec t-1, ou retourne simplement 1, mettant fin à la récursivité.

C’est compliqué et cryptique, mais tout se déroule au moment de l’exécution, et la clé de son fonctionnement est “l’exécution différée” et la rupture de la récursivité pour couvrir deux fonctions. Le F interne est passé en argument , pour être appelé dans la prochaine itération, seulement si nécessaire .

J’ai soulevé ceci de http://www.mail-archive.com/[email protected]/msg02716.html qui est une explication que j’ai écrite il y a plusieurs années.

Je vais utiliser JavaScript dans cet exemple, mais de nombreuses autres langues fonctionneront également.

Notre objective est d’être capable d’écrire une fonction récursive de 1 variable en utilisant uniquement les fonctions de 1 variable et sans affectation, en définissant les choses par leur nom, etc. (Pourquoi est-ce que notre objective est une autre question, est donné.) Semble impossible, hein? À titre d’exemple, implémentons factoriel.

Eh bien, l’étape 1 consiste à dire que nous pourrions le faire facilement si nous sortingchions un peu. En utilisant des fonctions de 2 variables et d’affectation, nous pouvons au moins éviter d’avoir à utiliser l’affectation pour configurer la récursivité.

 // Here's the function that we want to recurse. X = function (recurse, n) { if (0 == n) return 1; else return n * recurse(recurse, n - 1); }; // This will get X to recurse. Y = function (builder, n) { return builder(builder, n); }; // Here it is in action. Y( X, 5 ); 

Voyons maintenant si nous pouvons sortingcher moins. Premièrement, nous utilisons l’affectation, mais nous n’en avons pas besoin. Nous pouvons simplement écrire X et Y en ligne.

 // No assignment this time. function (builder, n) { return builder(builder, n); }( function (recurse, n) { if (0 == n) return 1; else return n * recurse(recurse, n - 1); }, 5 ); 

Mais nous utilisons des fonctions de 2 variables pour obtenir une fonction de 1 variable. Pouvons-nous résoudre ce problème? Eh bien, un gars intelligent nommé Haskell Curry a une astuce intéressante, si vous avez de bonnes fonctions d’ordre supérieur, vous n’avez besoin que de fonctions de 1 variable. La preuve est que vous pouvez passer de fonctions de 2 variables (ou plus dans le cas général) à 1 variable avec une transformation de texte purement mécanique comme ceci:

 // Original F = function (i, j) { ... }; F(i,j); // Transformed F = function (i) { return function (j) { ... }}; F(i)(j); 

où … rest exactement le même. (Cette astuce s’appelle “currying” après son inventeur. Le langage Haskell est également nommé pour Haskell Curry. Fichier que sous sortingvia inutile.) Maintenant, il suffit d’appliquer cette transformation partout et nous obtenons notre version finale.

 // The dreaded Y-combinator in action! function (builder) { return function (n) { return builder(builder)(n); }}( function (recurse) { return function (n) { if (0 == n) return 1; else return n * recurse(recurse)(n - 1); }})( 5 ); 

N’hésitez pas à l’essayer. alert () qui revient, liez-le à un bouton, peu importe. Ce code calcule les factorielles, récursivement, sans utiliser d’affectation, de déclaration ou de fonction de 2 variables. (Mais essayer de suivre son fonctionnement risque de faire tourner votre tête. Et le remettre, sans dérivation, légèrement reformaté, se traduira par un code qui ne manquera pas de dérouter.)

Vous pouvez remplacer les 4 lignes qui définissent récursivement le factoriel avec toute autre fonction récursive souhaitée.

Je me demande s’il est utile d’essayer de construire cela à partir de zéro. Voyons voir. Voici une fonction factorielle récursive de base:

 function factorial(n) { return n == 0 ? 1 : n * factorial(n - 1); } 

Refactorisons et créons une nouvelle fonction appelée fact qui renvoie une fonction de calcul factoriel anonyme au lieu d’effectuer elle-même le calcul:

 function fact() { return function(n) { return n == 0 ? 1 : n * fact()(n - 1); }; } var factorial = fact(); 

C’est un peu bizarre, mais il n’y a rien de mal à cela. Nous générons simplement une nouvelle fonction factorielle à chaque étape.

La récursivité à ce stade est encore assez explicite. La fonction de fact doit connaître son propre nom. Paramétrons l’appel récursif:

 function fact(recurse) { return function(n) { return n == 0 ? 1 : n * recurse(n - 1); }; } function recurser(x) { return fact(recurser)(x); } var factorial = fact(recurser); 

C’est bien, mais recurser doit encore connaître son propre nom. Paramétrons cela aussi:

 function recurser(f) { return fact(function(x) { return f(f)(x); }); } var factorial = recurser(recurser); 

Maintenant, au lieu d’appeler recurser(recurser) , créons une fonction wrapper qui renvoie son résultat:

 function Y() { return (function(f) { return f(f); })(recurser); } var factorial = Y(); 

Nous pouvons maintenant nous débarrasser recurser nom du recurser ; c’est juste un argument pour la fonction interne de Y, qui peut être remplacé par la fonction elle-même:

 function Y() { return (function(f) { return f(f); })(function(f) { return fact(function(x) { return f(f)(x); }); }); } var factorial = Y(); 

Le seul nom externe encore référencé est le fact , mais il devrait être clair maintenant que cela est facilement paramétrable, en créant la solution complète et générique:

 function Y(le) { return (function(f) { return f(f); })(function(f) { return le(function(x) { return f(f)(x); }); }); } var factorial = Y(function(recurse) { return function(n) { return n == 0 ? 1 : n * recurse(n - 1); }; }); 

La plupart des réponses ci-dessus décrivent ce qu’est le Y-combinator, mais pas à quoi il sert.

Les combinateurs de points fixes sont utilisés pour montrer que le calcul du lambda est complet . Ceci est un résultat très important dans la théorie du calcul et fournit une base théorique pour la functional programming .

L’étude des combinateurs de points fixes m’a également aidé à comprendre vraiment la functional programming. Je n’ai jamais trouvé aucune utilisation pour eux dans la programmation réelle cependant.

y-combinator en JavaScript :

 var Y = function(f) { return (function(g) { return g(g); })(function(h) { return function() { return f(h(h)).apply(null, arguments); }; }); }; var factorial = Y(function(recurse) { return function(x) { return x == 0 ? 1 : x * recurse(x-1); }; }); factorial(5) // -> 120 

Edit : J’apprends beaucoup en regardant le code, mais celui-ci est un peu difficile à avaler sans un peu de fond – désolé pour ça. Avec quelques connaissances générales présentées par d’autres réponses, vous pouvez commencer à distinguer ce qui se passe.

La fonction Y est le “y-combinator”. Regardez maintenant la ligne var factorial où Y est utilisé. Notez que vous lui passez une fonction qui a un paramètre (dans cet exemple, recurse ) qui est également utilisé plus tard dans la fonction interne. Le nom du paramètre devient essentiellement le nom de la fonction interne lui permettant d’effectuer un appel récursif (car il utilise recurse() dans sa définition). Le y-combinator associe la fonction interne par ailleurs anonyme au nom de paramètre du fonction passée à Y.

Pour l’explication complète de la façon dont Y fait la magie, consultez l’ article lié (pas par moi btw).

Pour les programmeurs qui n’ont pas rencontré de functional programming en profondeur et qui ne veulent pas démarrer maintenant, mais qui sont légèrement curieux:

Le combinateur Y est une formule qui vous permet d’implémenter la récursivité dans une situation où les fonctions ne peuvent pas avoir de noms mais peuvent être transmises sous forme d’arguments, utilisées comme valeurs de retour et définies dans d’autres fonctions.

Cela fonctionne en passant la fonction à elle-même en tant qu’argument, ainsi elle peut s’appeler elle-même.

Cela fait partie du calcul lambda, qui est vraiment un maths mais qui est effectivement un langage de programmation, et qui est fondamental pour l’informatique et en particulier pour la functional programming.

La valeur pratique quotidienne du combinateur Y est limitée, car les langages de programmation ont tendance à vous donner des noms.

Si vous avez besoin de l’identifier dans une ligne de police, cela ressemble à ceci:

Y = λf. (Λx.f (xx)) (λx.f (xx))

Vous pouvez généralement le repérer à cause de la répétition (λx.f (xx)) .

Les symboles λ sont la lettre grecque lambda, qui donne son nom au calcul lambda, et il y a beaucoup de termes de style (λx.t) car c’est à cela que ressemble le calcul lambda.

D’autres réponses apportent une réponse assez concise à cela, sans un fait important: vous n’avez pas besoin d’implémenter un combinateur de points fixes dans un langage pratique de cette manière compliquée et cela ne sert à rien (sauf “look, je sais ce que Y-combinator”) est”). C’est un concept théorique important, mais de peu de valeur pratique.

Un Y-Combinator est un autre nom pour un condensateur de stream.

Voici une implémentation JavaScript de la fonction Y-Combinator et de la fonction Factorial (d’après l’article de Douglas Crockford, disponible à l’ adresse : http://javascript.crockford.com/little.html ).

 function Y(le) { return (function (f) { return f(f); }(function (f) { return le(function (x) { return f(f)(x); }); })); } var factorial = Y(function (fac) { return function (n) { return n <= 2 ? n : n * fac(n - 1); }; }); var number120 = factorial(5); 

J’ai écrit une sorte de “guide des idiots” au Y-Combinator à la fois dans Clojure et dans Scheme afin de m’aider à le maîsortingser. Ils sont influencés par des matériaux dans “The Little Schemer”

Dans le schéma: https://gist.github.com/z5h/238891

ou Clojure: https://gist.github.com/z5h/5102747

Les deux didacticiels sont entrelacés avec des commentaires et doivent être copiés et collés dans votre éditeur préféré.

Le y-combinator implémente la récursivité anonyme. Donc au lieu de

 function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) } 

tu peux faire

 function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) } 

Bien entendu, le Y-combinator ne fonctionne que dans les langages appel par nom. Si vous souhaitez l'utiliser dans un langage appel par valeur normal, vous aurez besoin du combinateur z associé (le combinateur y sera différent / boucle infinie).

Un combinateur de points fixes (ou opérateur à virgule fixe) est une fonction d’ordre supérieur qui calcule un point fixe d’autres fonctions. Cette opération est pertinente dans la théorie des langages de programmation car elle permet l’implémentation de la récursion sous la forme d’une règle de réécriture, sans prise en charge explicite du moteur d’exécution du langage. (src Wikipedia)

L’opérateur peut simplifier votre vie:

 var Y = function(f) { return (function(g) { return g(g); })(function(h) { return function() { return f.apply(h(h), arguments); }; }); }; 

Ensuite, vous évitez la fonction supplémentaire:

 var fac = Y(function(n) { return n == 0 ? 1 : n * this(n - 1); }); 

Enfin, vous appelez fac(5) .

Récursivité anonyme

Un combinateur en virgule fixe est un fix fonction d’ordre supérieur qui, par définition, satisfait à l’équivalence

 forall f. fix f = f (fix f) 

fix f représente une solution x à l’équation à virgule fixe

  x = fx 

La factorielle d’un nombre naturel peut être prouvée par

 fact 0 = 1 fact n = n * fact (n - 1) 

En utilisant fix , des preuves de construction arbitraires sur des fonctions générales / μ-récursives peuvent être dérivées sans auto-référentialité asymésortingque.

 fact n = (fix fact') n 

où

 fact' rec n = if n == 0 then 1 else n * rec (n - 1) 

tel que

  fact 3 = (fix fact') 3 = fact' (fix fact') 3 = if 3 == 0 then 1 else 3 * (fix fact') (3 - 1) = 3 * (fix fact') 2 = 3 * fact' (fix fact') 2 = 3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1) = 3 * 2 * (fix fact') 1 = 3 * 2 * fact' (fix fact') 1 = 3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1) = 3 * 2 * 1 * (fix fact') 0 = 3 * 2 * 1 * fact' (fix fact') 0 = 3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1) = 3 * 2 * 1 * 1 = 6 

Cette preuve formelle que

 fact 3 = 6 

utilise méthodiquement l’équivalence du combinateur en virgule fixe pour les réécritures

 fix fact' -> fact' (fix fact') 

Calcul Lambda

Le formalisme de calcul lambda non typé consiste en une grammaire sans contexte

 E ::= v Variable | λ v. E Abstraction | EE Application 

où v situe sur les variables, avec les règles de réduction bêta et eta

 (λ x. B) E -> B[x := E] Beta λ x. E x -> E if x doesn't occur free in E Eta 

La réduction bêta substitue toutes les occurrences libres de la variable x dans le corps d’abstraction («fonction») B par l’expression («argument») E La réduction Eta élimine les abstractions redondantes. Il est parfois omis du formalisme. Une expression irréductible , à laquelle aucune règle de réduction ne s’applique, est la forme normale ou canonique .

 λ x y. E 

est sténographie pour

 λ x. λ y. E 

(multi-abstraction),

 EFG 

est sténographie pour

 (EF) G 

(associativité à gauche de l’application),

 λ x. x 

et

 λ y. y 

sont équivalents en alpha .

L’abstraction et l’application sont les deux «primitives de langage» du calcul lambda, mais elles permettent l’ encodage de données et d’opérations arbitrairement complexes.

Les chiffres de l’Église sont un encodage des nombres naturels similaires aux naturels Peano-axiomatiques.

  0 = λ f x. x No application 1 = λ f x. fx One application 2 = λ f x. f (fx) Twofold 3 = λ f x. f (f (fx)) Threefold . . . SUCC = λ nf x. f (nfx) Successor ADD = λ nmf x. nf (mfx) Addition MULT = λ nmf x. n (mf) x Multiplication . . . 

Une preuve formelle que

 1 + 2 = 3 

en utilisant la règle de réécriture de la réduction bêta:

  ADD 1 2 = (λ nmf x. nf (mfx)) (λ g y. gy) (λ h z. h (hz)) = (λ mf x. (λ g y. gy) f (mfx)) (λ h z. h (hz)) = (λ mf x. (λ y. fy) (mfx)) (λ h z. h (hz)) = (λ mf x. f (mfx)) (λ h z. h (hz)) = λ f x. f ((λ h z. h (hz)) fx) = λ f x. f ((λ z. f (fz)) x) = λ f x. f (f (fx)) Normal form = 3 

Combinateurs

Dans le calcul lambda, les combinateurs sont des abstractions qui ne contiennent aucune variable libre. Plus simplement: I , le combinateur d’identité

 λ x. x 

isomorphe à la fonction identité

 id x = x 

Ces combinateurs sont les opérateurs primitifs des calculs combinatoires tels que le système SKI.

 S = λ xy z. xz (yz) K = λ x y. x I = λ x. x 

La réduction bêta n’est pas fortement normalisante ; Toutes les expressions réductibles, «redexes», ne convergent pas vers la forme normale sous réduction bêta. Un exemple simple est l’application divergente du combinateur omega ω

 λ x. xx 

à elle-même:

  (λ x. xx) (λ y. yy) = (λ y. yy) (λ y. yy) . . . = _|_ Bottom 

La réduction des sous-expressions les plus à gauche («têtes») est prioritaire. L’ordre d’application normalise les arguments avant la substitution, mais pas l’ ordre normal . Les deux stratégies sont analogues à une évaluation enthousiaste, par exemple C, et l’évaluation paresseuse, par exemple Haskell.

  K (I a) (ω ω) = (λ k l. k) ((λ i. i) a) ((λ x. xx) (λ y. yy)) 

diverge sous la réduction bêta d’ordre d’application

 = (λ k l. k) a ((λ x. xx) (λ y. yy)) = (λ l. a) ((λ x. xx) (λ y. yy)) = (λ l. a) ((λ y. yy) (λ y. yy)) . . . = _|_ 

puisque en sémantique ssortingcte

 forall f. f _|_ = _|_ 

mais converge sous la réduction bêta de l’ordre normal paresseux

 = (λ l. ((λ i. i) a)) ((λ x. xx) (λ y. yy)) = (λ l. a) ((λ x. xx) (λ y. yy)) = a 

Si une expression a une forme normale, la réduction bêta d’ordre normal le trouvera.

Y

La propriété essentielle du combinateur à point fixe Y

 λ f. (λ x. f (xx)) (λ x. f (xx)) 

est donné par

  Y g = (λ f. (λ x. f (xx)) (λ x. f (xx))) g = (λ x. g (xx)) (λ x. g (xx)) = Y g = g ((λ x. g (xx)) (λ x. g (xx))) = g (Y g) = g (g ((λ x. g (xx)) (λ x. g (xx)))) = g (g (Y g)) . . . . . . 

L’équivalence

 Y g = g (Y g) 

est isomorphe à

 fix f = f (fix f) 

Le calcul lambda non typé peut encoder des preuves constructives arbitraires sur des fonctions générales / μ-récursives.

  FACT = λ n. Y FACT' n FACT' = λ rec n. if n == 0 then 1 else n * rec (n - 1) FACT 3 = (λ n. Y FACT' n) 3 = Y FACT' 3 = FACT' (Y FACT') 3 = if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1) = 3 * (Y FACT') (3 - 1) = 3 * FACT' (Y FACT') 2 = 3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1) = 3 * 2 * (Y FACT') 1 = 3 * 2 * FACT' (Y FACT') 1 = 3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1) = 3 * 2 * 1 * (Y FACT') 0 = 3 * 2 * 1 * FACT' (Y FACT') 0 = 3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1) = 3 * 2 * 1 * 1 = 6 

(Multiplication retardée, confluence)

Pour le calcul lambda non typé de Churchian, il a été démontré qu’il existe une infinité récursivement énumérable de combinateurs à virgule fixe en plus de Y

  X = λ f. (λ x. xx) (λ x. f (xx)) Y' = (λ x y. xyx) (λ y x. y (xyx)) Z = λ f. (λ x. f (λ v. xxv)) (λ x. f (λ v. xxv)) Θ = (λ x y. y (xxy)) (λ x y. y (xxy)) . . . 

La réduction bêta d’ordre normal fait du calcul lambda non typé non étendu un système de réécriture complet de Turing.

Dans Haskell, le combinateur à point fixe peut être mis en œuvre avec élégance

 fix :: forall t. (t -> t) -> t fix f = f (fix f) 

La paresse de Haskell se normalise avant que toutes les sous-expressions aient été évaluées.

 primes :: Integral t => [t] primes = sieve [2 ..] where sieve = fix (\ rec (p : ns) -> p : rec [n | n <- ns , n `rem` p /= 0]) 

---

• David Turner: thèse de l'Église et functional programming
• Alonzo Church: Un problème insoluble de la théorie des nombres élémentaires
• Calcul Lambda
• Théorème de l'Église – Rosser

En tant que débutant dans les combinateurs, j’ai trouvé que l’article de Mike Vanier (merci Nicholas Mancuso) était vraiment utile. J’aimerais écrire un résumé, en plus de documenter ma compréhension, si cela pouvait être utile à d’autres, je serais très heureux.

De la merde à la merde

En utilisant factorial comme exemple, nous utilisons la fonction almost-factorial suivante pour calculer la factorielle du nombre x :

 def almost-factorial fx = if iszero x then 1 else * x (f (- x 1)) 

Dans le pseudo-code ci-dessus, almost-factorial prend en compte la fonction f et le nombre x ( almost-factorial est curry, il peut donc être vu comme prenant la fonction f et renvoyant une fonction 1-arité).

Lorsque almost-factorial calcule factoriel pour x , il délègue le calcul de factoriel pour x - 1 à la fonction f et accumule ce résultat avec x (dans ce cas, il multiplie le résultat de (x – 1) avec x).

Il peut être vu comme almost-factorial sockets almost-factorial dans une version de la fonction factorielle (qui ne peut calculer que le nombre x - 1 ) et retourne une version moins factorielle de la factorielle (qui calcule le nombre x ). Comme sous cette forme:

 almost-factorial crappy-f = less-crappy-f 

Si nous passons à plusieurs resockets la version de craquage de factorial à almost-factorial , nous finirons par obtenir notre fonction factorielle désirée f . Où il peut être considéré comme:

 almost-factorial f = f 

Point fixe

Le fait que almost-factorial f = f signifie f est le point fixe de la fonction almost-factorial .

C’était une façon vraiment intéressante de voir les relations entre les fonctions ci-dessus et ce fut un moment pour moi. (s’il vous plaît lire le post de Mike sur le point fixe si vous ne l’avez pas)

Trois fonctions

Pour généraliser, nous avons une fonction non récursive fn (comme notre quasi-factorielle), nous avons sa fonction de point fixe fr (comme notre f), alors ce que fait Y est quand vous donnez Y fn , Y retourne le point fixe fonction de fn .

Donc en résumé (simplifié en supposant que fr prend un seul paramètre; x dégénère en x - 1 , x - 2 … en récursivité):

• Nous définissons les calculs de base comme étant fn : def fn fr x = ...accumulate x with result from (fr (- x 1)) , c’est la fonction presque utile – bien que nous ne puissions pas utiliser fn directement sur x , ce sera utile très bientôt. Cette fn non récursive utilise une fonction fr pour calculer son résultat
• fn fr = fr , fr est le point fixe de fn , fr est la fonction utile , on peut utiliser fr sur x pour obtenir notre résultat
• Y fn = fr , Y retourne le point fixe d’une fonction, Y transforme notre fonction presque utile fn en fr

Dériver Y (non inclus)

Je vais sauter la dérivation de Y et aller à la compréhension de Y Le message de Mike Vainer contient beaucoup de détails.

La forme de Y

Y est défini comme (au format calcul lambda ):

 Y f = λs.(f (ss)) λs.(f (ss)) 

Si on remplace la variable s à gauche des fonctions, on obtient

 Y f = λs.(f (ss)) λs.(f (ss)) => f (λs.(f (ss)) λs.(f (ss))) => f (Y f) 

En effet, le résultat de (Y f) est le point fixe de f .

Pourquoi (Y f) travaille-t-il?

Selon la signature de f , (Y f) peut être une fonction de toute arité, pour simplifier, supposons que (Y f) ne prenne qu’un seul paramètre, comme notre fonction factorielle.

 def fn fr x = accumulate x (fr (- x 1)) 

puisque fn fr = fr , on continue

 => accumulate x (fn fr (- x 1)) => accumulate x (accumulate (- x 1) (fr (- x 2))) => accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1))) 

le calcul récursif se termine lorsque le plus grand nombre (fn fr 1) est le cas de base et fn n’utilise pas fr dans le calcul.

En regardant à nouveau Y :

 fr = Y fn = λs.(fn (ss)) λs.(fn (ss)) => fn (λs.(fn (ss)) λs.(fn (ss))) 

Alors

 fr x = Y fn x = fn (λs.(fn (ss)) λs.(fn (ss))) x 

Pour moi, les parties magiques de cette configuration sont les suivantes:

• fn et fr interdépendants les uns sur les autres: fr ‘wraps’ fn dedans, chaque fois que fr est utilisé pour calculer x , il ‘engendre’ (‘lifts’?) fn et délègue le calcul à ce fn (passant lui-même fr et x ); Par contre, fn dépend de fr et utilise fr pour calculer le résultat d’un problème plus petit x-1 .
• Au moment où fr est utilisé pour définir fn (lorsque fn utilise fr dans ses opérations), le fr réel n’est pas encore défini.
• C’est fn qui définit la véritable logique métier. Sur la base de fn , Y crée une fonction auxiliaire dans une forme spécifique – pour faciliter le calcul de fn de manière récursive .

Cela m’a aidé à comprendre Y cette façon en ce moment, en espérant que ça aide.

BTW, j’ai également trouvé le livre Une introduction à la functional programming par Lambda Calculus très bien, je ne suis qu’un passage par-dessus et le fait que je ne pouvais pas comprendre Y dans le livre m’a conduit à ce poste.

Voici les réponses aux questions originales , compilées à partir de l’article (qui vaut vraiment la peine d’être lu) mentionné dans la réponse de Nicholas Mancuso , ainsi que d’autres réponses:

Qu’est-ce qu’un combinateur Y?

Un combinateur Y est une fonction “fonctionnelle” (ou une fonction d’ordre supérieur – une fonction opérant sur d’autres fonctions) qui prend un seul argument, qui est une fonction non récursive, et renvoie une version de la fonction qui est récursive.

---

Quelque peu récursif =), mais définition plus approfondie:

Un combinateur – est juste une expression lambda sans variables libres.
Variable libre – est une variable qui n’est pas une variable liée.
Variable liée – variable qui est contenue dans le corps d’une expression lambda qui a ce nom de variable parmi ses arguments.

Une autre façon de penser à cela est que le combinateur est une telle expression lambda, dans laquelle vous pouvez remplacer le nom d’un combinateur par sa définition partout où il se trouve et que tout fonctionne toujours (vous entrerez dans une boucle infinie si contient la référence à lui-même, à l’intérieur du corps lambda).

Y-combinator est un combinateur à points fixes.

Le point fixe d’une fonction est un élément du domaine de la fonction qui lui est mappé par la fonction.
C’est-à-dire que c est un point fixe de la fonction f(x) si f(c) = c
Cela signifie que f(f(...f(c)...)) = fn(c) = c

Comment fonctionnent les combinateurs?

Les exemples ci-dessous supposent un typage fort + dynamic :

Combinateur Y paresseux (d’ordre normal):
Cette définition s’applique aux langages avec évaluation paresseuse (également: différée, appel par besoin) – stratégie d’évaluation qui retarde l’évaluation d’une expression jusqu’à ce que sa valeur soit nécessaire.

 Y = λf.(λx.f(xx)) (λx.f(xx)) = λf.(λx.(xx)) (λx.f(xx)) 

Cela signifie que pour une fonction donnée f (qui est une fonction non récursive), la fonction récursive correspondante peut être obtenue en calculant d’abord λx.f(xx) , puis en appliquant cette expression lambda à elle-même.

Combinateur Y ssortingct (applicatif-ordre):
Cette définition s’applique aux langages ayant une évaluation ssortingcte (aussi: avide, gourmande) – une stratégie d’évaluation dans laquelle une expression est évaluée dès qu’elle est liée à une variable.

 Y = λf.(λx.f(λy.((xx) y))) (λx.f(λy.((xx) y))) = λf.(λx.(xx)) (λx.f(λy.((xx) y))) 

Il est identique à la paresseuse dans sa nature, il a juste un wrapper λ supplémentaire pour retarder l’évaluation du corps de lambda. J’ai posé une autre question , quelque peu liée à ce sujet.

À quoi servent-ils?

Volé emprunté à la réponse de Chris Ammerman : Y-combinator généralise la récursivité, en résume la mise en œuvre et la sépare ainsi du travail réel de la fonction en question.

Même si Y-combinator a des applications pratiques, il s’agit principalement d’un concept théorique, dont la compréhension élargira votre vision globale et augmentera probablement vos compétences analytiques et de développement.

Sont-ils utiles dans les langages procéduraux?

Comme l’a déclaré Mike Vanier : il est possible de définir un combinateur Y dans de nombreux langages statiquement typés, mais (du moins dans les exemples que j’ai vus), de telles définitions nécessitent généralement un type de piratage non évident, car le combinateur Y lui-même ne t avoir un type statique simple. C’est au-delà de la scope de cet article, donc je ne le mentionnerai plus

Et comme mentionné par Chris Ammerman : la plupart des langages procéduraux ont un typage statique.

Alors répondez à celui-ci – pas vraiment.

Je pense que la meilleure façon de répondre est de choisir une langue, comme JavaScript:

 function factorial(num) { // If the number is less than 0, reject it. if (num < 0) { return -1; } // If the number is 0, its factorial is 1. else if (num == 0) { return 1; } // Otherwise, call this recursive procedure again. else { return (num * factorial(num - 1)); } } 

Maintenant réécrivez-le pour qu'il n'utilise pas le nom de la fonction dans la fonction, mais l'appelle toujours de manière récursive.

The only place the function name factorial should be seen is at the call site.

Hint: you can't use names of functions, but you can use names of parameters.

Work the problem. Don't look it up. Once you solve it, you will understand what problem the y-combinator solves.