Qu'est-ce qu'un combinateur Y? [fermé]

Un combinateur Y est un concept informatique du côté «fonctionnel» des choses. La plupart des programmeurs ne connaissent pas grand-chose aux combinateurs, s'ils en ont même entendu parler.

• Qu'est-ce qu'un combinateur Y?
• Comment fonctionnent les combinateurs?
• À quoi servent-ils?
• Sont-ils utiles dans les langages procéduraux?

Si vous êtes prêt pour une longue lecture, Mike Vanier a une excellente explication . Pour faire court, il vous permet d'implémenter la récursivité dans un langage qui ne le supporte pas nécessairement nativement.

Un combinateur Y est une "fonctionnelle" (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 de l'intérieur. Dans la théorie de l'informatique, il généralise la récursivité , en faisant abstraction de sa mise en œuvre, et en la séparant ainsi du travail réel de la fonction en question. L'avantage de ne pas avoir besoin d'un nom au moment de 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 affectant 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éaffectée, ce qui rompt l'auto-référence.

Les combinateurs Y sont lourds à implémenter et souvent à utiliser dans les langages de type statique (ce qui est souvent le cas des langages procéduraux ), car généralement les restrictions de frappe nécessitent que le nombre d'arguments pour la fonction en question soit connu au moment de la compilation. Cela signifie qu'un combinateur y doit être écrit pour tout nombre d'arguments que l'on doit utiliser.

Voici un exemple de la façon dont l'utilisation et le fonctionnement d'un Y-Combinator, en C #.

L'utilisation d'un combinateur Y implique une manière "inhabituelle" de construire une fonction récursive. Vous devez d'abord écrire votre fonction comme un morceau de code qui appelle une fonction préexistante, plutôt que lui-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 prend une fonction à appeler et renvoie une fonction qui le fait. C'est ce qu'on appelle une fonction, car elle prend une fonction et effectue une opération avec elle qui se traduit par 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<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

Vous avez maintenant 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 factoriel? Passez la fonction intérieure à 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<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> 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 lui-même, ce qui se passe est que le factoriel appelle le générateur factoriel (renvoyé par l'appel récursif à Y-Combinator). Et selon la valeur actuelle de t, la fonction renvoyée par le générateur appellera à nouveau le générateur, avec t - 1, ou retournera simplement 1, mettant fin à la récursivité.

C'est compliqué et cryptique, mais tout secoue 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 s'étendre sur deux fonctions. Le F interne est passé en argument , à appeler lors de l'itération suivante, uniquement si nécessaire .

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

J'utiliserai JavaScript dans cet exemple, mais de nombreuses autres langues fonctionneront également.

Notre objectif est de pouvoir écrire une fonction récursive de 1 variable en utilisant uniquement les fonctions de 1 variable et aucune affectation, en définissant les choses par leur nom, etc. sont donnés.) Semble impossible, hein? Par exemple, implémentons factorielle.

Eh bien, l'étape 1 est de dire que nous pourrions le faire facilement si nous trichions un peu. En utilisant les fonctions de 2 variables et l'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 moins tricher. Eh bien tout d'abord, 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 du nom de 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 celle-ci:

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

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

où ... reste exactement le même. (Cette astuce est appelée "currying" d'après son inventeur. Le langage Haskell est également nommé pour Haskell Curry. Fichier que sous trivia inutile.) Maintenant, appliquez simplement 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 reviennent, attachez-le à un bouton, peu importe. Ce code calcule les factorielles, récursivement, sans utiliser d'affectation, de déclarations ou de fonctions de 2 variables. (Mais essayer de tracer comment cela fonctionne est susceptible de faire tourner la tête. Et le remettre, sans dérivation, juste légèrement reformaté se traduira par un code qui est sûr de dérouter et de confondre.)

Vous pouvez remplacer les 4 lignes qui définissent récursivement factorielle par toute autre fonction récursive que vous souhaitez.

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 factqui renvoie une fonction de calcul factoriel anonyme au lieu d'effectuer le calcul lui-même:

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 juste une nouvelle fonction factorielle à chaque étape.

La récursivité à ce stade est encore assez explicite. La factfonction 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 super, mais recurseril faut quand même 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)directement, créons une fonction wrapper qui retourne son résultat:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

Nous pouvons maintenant nous débarrasser recursercomplètement du nom; c'est juste un argument pour la fonction interne de Y, qui peut être remplacée 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 fact, mais il devrait être clair maintenant que cela est également facilement paramétrable, 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 que le Y-Combinator est , mais pas ce qu'elle est pour .

Des combinateurs à point fixe sont utilisés pour montrer que le calcul lambda est complet . C'est un résultat très important dans la théorie du calcul et fournit une base théorique pour la programmation fonctionnelle .

L'étude des combinateurs à virgule fixe m'a également aidé à vraiment comprendre la programmation fonctionnelle. Je n'ai cependant jamais trouvé d'utilité pour eux dans la programmation réelle.

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 arrière-plan - désolé. 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 "combinateur y". Jetez maintenant un œil à la var factorialligne 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 combinateur y effectue la magie d'associer la fonction interne autrement anonyme au nom de paramètre de la 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 d'ailleurs).

Pour les programmeurs qui n'ont pas rencontré de programmation fonctionnelle en profondeur, et ne se soucient pas de commencer maintenant, mais 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 comme arguments, utilisées comme valeurs de retour et définies dans d'autres fonctions.

Il fonctionne en se passant la fonction en tant qu'argument, afin de pouvoir s'appeler.

Cela fait partie du calcul lambda, qui est vraiment des mathématiques mais est en fait un langage de programmation, et est assez fondamental pour l'informatique et surtout pour la programmation fonctionnelle.

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

Au cas où vous auriez besoin de l'identifier dans une composition policière, cela ressemble à ceci:

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

Vous pouvez généralement le repérer à cause des répétitions (λx.f (x x)).

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

Récursivité anonyme

Un combinateur à virgule fixe est une fonction d'ordre supérieur fixqui, par définition, satisfait l'équivalence

forall f.  fix f  =  f (fix f)

fix freprésente une solution xà l'équation à virgule fixe

               x  =  f x

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

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

L'utilisation de fixpreuves constructives arbitraires sur des fonctions générales / μ-récursives peut être dérivée sans auto-référentialité non-homogène.

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 à virgule fixe pour les réécritures

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

Calcul lambda

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

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

où vs'étend sur les variables, ainsi que 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 remplace toutes les occurrences libres de la variable xdans le corps d'abstraction («fonction») Bpar l'expression («argument») E. La réduction Eta élimine l'abstraction redondante. Il est parfois omis du formalisme. Une expression irréductible , à laquelle aucune règle de réduction ne s'applique, est sous forme normale ou canonique .

λ x y. E

est un raccourci pour

λ x. λ y. E

(abstraction multiarité),

E F G

est un raccourci pour

(E F) G

(application associative gauche),

λ x. x

et

λ y. y

sont équivalents alpha .

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

Les chiffres de l'Église sont un codage des nombres naturels similaires aux naturels peano-axiomatiques.

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) 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
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       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 d'identité

id x = x

De tels combinateurs sont les opérateurs primitifs des calculs de combinateurs comme le système SKI.

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

La réduction bêta ne normalise pas fortement ; toutes les expressions réductibles, «redexes», convergent vers la forme normale sous réduction bêta. Un exemple simple est l'application divergente du ωcombinateur oméga

λ x. x x

à lui-même:

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

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

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

diverge sous la réduction bêta de l'ordre d'application

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

car en sémantique stricte

forall f.  f _|_  =  _|_

mais converge sous une réduction bêta paresseuse d'ordre normal

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

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

Oui

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

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

est donné par

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

L'équivalence

Y g  =  g (Y g)

est isomorphe à

fix f  =  f (fix f)

Le calcul lambda non typé peut coder 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 l'Église, il a été démontré qu'il existe en outre une infinité récursivement énumérable de combinateurs à virgule fixe Y.

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

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

À Haskell, le combinateur à virgule 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 à une fin 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 programmation fonctionnelle
• Église Alonzo: un problème insoluble de la théorie des nombres élémentaires
• Calcul lambda
• Théorème de Church – Rosser

D'autres réponses fournissent une réponse assez concise à cela, sans un fait important: vous n'avez pas besoin d'implémenter un combinateur à point fixe dans un langage pratique de cette manière compliquée et cela ne sert à rien (sauf "regardez, je sais ce que le combinateur Y") est"). C'est un concept théorique important, mais de peu de valeur pratique.

Voici une implémentation JavaScript du Y-Combinator et de la fonction factorielle (de l'article de Douglas Crockford, disponible à: 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);

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

J'ai écrit une sorte de "guide idiots" sur le Y-Combinator à la fois dans Clojure et Scheme afin de m'aider à y faire face. Ils sont influencés par le matériel de "The Little Schemer"

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

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

Les deux tutoriels sont du code entrecoupé de commentaires et doivent être coupés et collables dans votre éditeur préféré.

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

De Crappy à Less Crappy

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

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

Dans le pseudo-code ci-dessus, almost-factorialprend la fonction fet le nombre x( almost-factorialest curry, il peut donc être considéré comme prenant la fonction fet renvoyant une fonction à 1 entité).

Lors du almost-factorialcalcul de la factorielle pour x, il délègue le calcul de la factorielle pour x - 1fonctionner fet accumule ce résultat avec x(dans ce cas, il multiplie le résultat de (x - 1) par x).

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

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

Si nous passons à plusieurs reprises la version moins merdique de factorielle à almost-factorial, nous obtiendrons finalement notre fonction factorielle souhaitée f. Où il peut être considéré comme:

almost-factorial f = f

Fix-point

Le fait que cela almost-factorial f = fsignifie fest le point fixe de la fonction almost-factorial.

C'était une façon vraiment intéressante de voir les relations des fonctions ci-dessus et c'était un moment aha pour moi. (veuillez lire le post de Mike sur fix-point si vous ne l'avez pas fait)

Trois fonctions

Pour généraliser, nous avons un non récursif fonction fn(comme notre presque factoriel), nous avons le point fixe fonction fr(comme notre f), alors qu'est - ce qu'il Yfait est quand on donne Y fn, Yretourne la fonction point fixe de fn.

Donc en résumé (simplifié en supposant frne prend qu'un seul paramètre; xdégénère en x - 1, x - 2... en récursivité):

• Nous définissons les calculs de base comme suitfn : def fn fr x = ...accumulate x with result from (fr (- x 1))c'est la fonction presque utile - bien que nous ne puissions pas l'utiliser fndirectement x, elle sera utile très bientôt. Ce non récursif fnutilise une fonction frpour calculer son résultat
• fn fr = fr, frEst le point fixe de fn, frest l' utile funciton, nous pouvons utiliser frsur xpour obtenir notre résultat
• Y fn = fr, YRetourne le point fixe d'une fonction, Y transforme notre presque utile fonction fndans utile fr

Dérivation Y(non inclus)

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

La forme de Y

Yest défini comme (au format lambda calcul ):

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

Si nous remplaçons la variable sà gauche des fonctions, nous obtenons

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

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

Pourquoi ça (Y f)marche?

Selon la signature de f, (Y f)peut être une fonction de n'importe quelle arité, pour simplifier, supposons (Y f)que ne prend qu'un paramètre, comme notre fonction factorielle.

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

depuis fn fr = fr, nous continuons

=> 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 interne (fn fr 1)est le cas de base et fnne l'utilise pas frdans le calcul.

En regardant à Ynouveau:

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

Donc

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

Pour moi, les parties magiques de cette configuration sont:

• fnet frinterdépendants les uns des autres: fr«s'enroule» fnà l' intérieur, chaque fois qu'il frest utilisé pour calculer x, il «apparaît» («se soulève»?) an fnet délègue le calcul à cela fn(en passant en lui fr- même et x); d'autre part, fndépend fret utilise frpour calculer le résultat d'un problème plus petit x-1.
• A l'époque fron utilise pour définir fn(quand on l' fnutilise frdans ses opérations), le réel frn'est pas encore défini.
• C'est ce fnqui définit la véritable logique métier. Sur la base fn, Ycrée fr- une fonction d'assistance sous une forme spécifique - pour faciliter le calcul pour fnune récursif manière.

Cela m'a aidé à comprendre Ycette façon pour le moment, j'espère que cela aide.

BTW, j'ai également trouvé le livre An Introduction to Functional Programming Through Lambda Calculus très bon, je ne suis que partiellement à travers et le fait que je n'ai pas pu me mettre la tête Ydans le livre m'a conduit à ce poste.

Voici les réponses aux questions originales , compilées à partir de l'article (qui vaut TOTALEMENT 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 Y-combinator est une "fonctionnelle" (ou une fonction d'ordre supérieur - une fonction qui opère sur d'autres fonctions) qui prend un seul argument, qui est une fonction qui n'est pas récursive, et renvoie une version de la fonction qui est récursif.

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

Un combinateur - est juste une expression lambda sans variable libre.
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 comme l'un de 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 avec sa définition partout où il se trouve et que tout fonctionne toujours (vous entrerez dans une boucle infinie si le combinateur contiennent une référence à lui-même, à l'intérieur du corps lambda).

Le combinateur Y est un combinateur à virgule fixe.

Le point fixe d'une fonction est un élément du domaine de la fonction qui est mappé sur lui-même par la fonction.
C'est-à-dire, cest un point fixe de la fonction f(x)si f(c) = c
cela signifief(f(...f(c)...)) = fn(c) = c

Comment fonctionnent les combinateurs?

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

Combinateur Y paresseux (ordre normal):
Cette définition s'applique aux langues 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(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))

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

Combinateur Y strict (ordre applicatif):
Cette définition s'applique aux langues avec une évaluation stricte (aussi: avide, gourmande) - 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.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) y)))

Il est identique à un paresseux dans sa nature, il a juste un λemballage supplémentaire pour retarder l'évaluation du corps du 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 en faisant abstraction, et en la séparant 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 typés statiquement, mais (au moins dans les exemples que j'ai vus), de telles définitions nécessitent généralement un piratage de type non évident, car le combinateur Y lui-même ne fait pas '' t ont un type statique simple. Cela dépasse le cadre de cet article, donc je ne le mentionnerai pas plus loin

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

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

Le combinateur y 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 sûr, le combinateur y ne fonctionne que dans les langues appelées par nom. Si vous souhaitez utiliser ceci dans n'importe quel langage d'appel normal, alors vous aurez besoin du combinateur z associé (le combinateur y divergent / boucle infinie).

Un combinateur à virgule fixe (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 du langage de programmation car elle permet l'implémentation de la récursivité sous la forme d'une règle de réécriture, sans prise en charge explicite du moteur d'exécution du langage. (src Wikipedia)

Cet opérateur peut vous simplifier la 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).

Je pense que la meilleure façon d'y 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 à l'intérieur de la fonction, mais l'appelle toujours récursivement.

Le seul endroit où le nom de la fonction factorialdoit être vu est sur le site de l'appel.

Astuce: vous ne pouvez pas utiliser de noms de fonctions, mais vous pouvez utiliser des noms de paramètres.

Travaillez le problème. Ne cherchez pas. Une fois que vous l'aurez résolu, vous comprendrez quel problème le combinateur y résout.