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

StackOverflow https://stackoverflow.com/questions/93526

Question

Un Y-combinator est un concept informatique issu de la & # 8220; fonctionnel & # 8221; côté des choses. La plupart des programmeurs ne savent pas grand chose des combinateurs, s’ils en ont même entendu parler.

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

La solution

Si vous êtes prêt pour une longue lecture, Mike Vanier a un excellent explication . En résumé, il vous permet d’implémenter la récursivité dans un langage qui ne la prend pas nécessairement en charge de manière native.

Autres conseils

Un Y-combinator est un "fonctionnel" (une fonction qui opère sur d'autres fonctions) qui active la récursivité, lorsque vous ne pouvez pas vous référer à la fonction de l'intérieur. Dans la théorie informatique, elle généralise la récursivité , en en abstenant la 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 s'applique aux langues qui prennent en charge les fonctions lambda . La nature exprimée des lambdas signifie généralement qu'ils ne peuvent pas se désigner eux-mêmes par leur nom. Et contourner ce problème en déclarant la variable, y faisant référence, 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éattribuée, ce qui casse l'auto-référence.

Les combineurs Y sont lourds à mettre en œuvre et souvent à utiliser dans à saisie statique langues (ce qui est souvent le cas de langages procéduraux ), car les restrictions de frappe exigent généralement le nombre d'arguments du la fonction en question doit être connue au moment de la compilation. Cela signifie qu'un y-combinator doit être écrit pour tout nombre d'arguments qu'il faut utiliser.

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

L'utilisation d'un combinateur en Y implique un comportement "inhabituel". manière de construire une fonction récursive. Vous devez d’abord écrire votre fonction sous forme de code appelant 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 fonctionnelle, car elle prend une fonction et effectue avec elle une opération qui aboutit à 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 transmis à la fonction externe. Comment faites-vous cela la factorielle? Passez la fonction interne à elle-même. 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, c’est que la factorielle appelle le générateur factoriel (renvoyé par l’appel récursif de Y-Combinator). Et en fonction de la valeur actuelle de t, la fonction renvoyée par le générateur appelle le générateur à nouveau, avec t-1, ou renvoie simplement 1, mettant fin à la récursivité.

C'est compliqué et cryptique, mais tout bouge au moment de l'exécution, et la clé de son fonctionnement est une "exécution différée" et la rupture de la récursivité pour couvrir deux fonctions. Le F interne est passé en tant qu'argument , à appeler lors de la prochaine itération, uniquement si nécessaire .

J'ai soulevé cette question de http: //www.mail-archive .com / boston-pm @ mail.pm.org / msg02716.html , une explication que j’ai écrite il ya plusieurs années.

J'utiliserai JavaScript dans cet exemple, mais de nombreux autres langages fonctionneront également.

Notre objectif est de pouvoir écrire une fonction récursive de 1 variable utilisant uniquement des fonctions de 1 variables et non missions, définir les choses par leur nom, etc. (Pourquoi est-ce notre objectif est une autre question, prenons cela comme la défi qui nous est donné.) semble impossible, hein? Comme un exemple, implémentons factoriel.

La première étape consiste à dire que nous pourrions le faire facilement si nous triché un peu. Utilisation de fonctions de 2 variables et affectation, nous pouvons au moins éviter d'avoir à utiliser 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 tricher moins. Eh bien, premièrement, nous utilisons cession, mais nous n'en avons pas besoin. On peut juste é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 un bon ordre supérieur fonctions alors vous avez seulement besoin de fonctions de 1 variable. le la preuve est que vous pouvez obtenir des fonctions de 2 (ou plus dans le cas général) variables à 1 variable avec un pur transformation de texte mécanique comme ceci: 

// 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 s'appelle "currying" d'après son inventeur. La langue Haskell est aussi nommé pour Haskell Curry. Fichier que sous trivia inutile.) Maintenant, appliquez 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 retourne, liez-le à un bouton, peu importe. Ce code calcule les factorielles, récursivement, sans utiliser affectation, déclarations ou fonctions de 2 variables. (Mais essayer de retracer son fonctionnement est susceptible de vous faire tourner la tête. Et le remettre, sans la dérivation, juste légèrement reformaté vous obtiendrez un code qui ne manquera pas de dérouter et de confondre.)

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

Je me demande s’il est utile de tenter de construire cela à partir de la base. 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 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 simplement une nouvelle fonction factorielle à chaque étape.

La récursion à ce stade est encore assez explicite. La fonction 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 récurseur doit toujours 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 directement recurser (recurser) , 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 du nom de récurseur ; c'est juste un argument de 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 fact , mais il devrait être clair à présent qu'il est facile à paramétrer, ce qui crée également 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 combinateur Y est mais pas ce qu'il est pour .

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

L’étude des combinateurs à point fixe m’a également aidé à comprendre vraiment la programmation fonctionnelle. Je n'ai cependant jamais trouvé d'utilisation dans la programmation.

Y-combinator dans 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

Modifier : J'ai beaucoup appris en regardant le code, mais celui-ci est un peu difficile à avaler sans arrière-plan - désolé pour cela. Avec certaines 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". Examinez maintenant la ligne var factorial où Y est utilisé. Notez que vous lui transmettez une fonction ayant un paramètre (dans cet exemple, recurse ) qui sera également utilisé ultérieurement dans la fonction interne. Le nom du paramètre devient fondamentalement le nom de la fonction interne lui permettant d'effectuer un appel récursif (puisqu'il utilise recurse () dans sa définition). Le y-combinator effectue la magie d'associer les fonctions internes autrement anonymes. fonction avec le nom de paramètre de la fonction passé à Y.

Pour une explication complète de la manière dont Y fait la magie, consultez la article lié (pas par moi d'ailleurs.)

Pour les programmeurs qui ne connaissent pas la programmation fonctionnelle en profondeur et se moquent de commencer maintenant, mais sont plutôt curieux:

Le combinateur Y est une formule qui vous permet d'implémenter la récursion dans une situation où les fonctions ne peuvent pas avoir de nom mais peuvent être transmises comme 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, afin qu'elle puisse s'appeler elle-même.

Cela fait partie du lambda calcul, qui est en réalité un calcul mais est en réalité un langage de programmation et est assez fondamental pour l’informatique et en particulier pour la programmation fonctionnelle.

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

Au cas où vous auriez besoin de l'identifier dans un alignement de police, il se présente comme suit:

  

Y = ?f. (?x.f (x x)) (?x.f (x x))

Vous pouvez généralement le repérer à cause du (?x.f (x x)) répété.

Les symboles ? sont la lettre grecque lambda, qui donne son nom au calcul lambda. Il existe de nombreux termes de style (?x.t) car c’est ce que lambda calcul ressemble.

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

Voici une implémentation JavaScript de Y-Combinator et de la fonction Factorial (extrait de l'article de Douglas Crockford, disponible à l'adresse suivante: 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 des idiots". Y-Combinator dans Clojure et Scheme pour m'aider à la maîtriser. Ils sont influencés par le contenu de "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 entrecoupés de commentaires et doivent être découpés avec & amp; coller dans votre éditeur préféré.

Récursion anonyme

Un combinateur de points fixes est une fonction correct de niveau supérieur qui, par définition, satisfait à l'équivalence 

forall f.  fix f  =  f (fix f)

correctif f repré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)

En utilisant correct , des preuves constructives arbitraires sur les fonctions générales / & # 956; - récursives peuvent être dérivées sans autoréférentialité non-identique. 

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 réécrire 

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

Calcul lambda

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

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

où v s'étend sur les variables, ainsi que les règles beta et eta réduction 

(λ 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 x dans l'abstraction (& # 8220; fonction & # 8221;) du corps B par l'expression (& # 8220; argument & # 8221;) E . Eta réduction é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 sous la forme normale ou forme canonique . 

λ x y. E

est un raccourci pour 

λ x. λ y. E

(multiarité d'abstraction), 

E F G

est un raccourci pour 

(E F) G

(associativité à gauche de l'application), 

λ x. x

et 

λ y. y

sont équivalents alpha .

L'abstraction et l'application sont les deux seules & # 8220; primitives de langage & # 8221; lambda calcul, mais ils 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. 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

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

Combinators

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

id x = x

isomorphe à la fonction d'identité 

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

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

λ x. x x
La

réduction bêta n’est pas normalisée fortement ; toutes les expressions réductibles, & # 8220; redexes & # 8221;, ne convergent pas vers la forme normale sous réduction bêta. Un exemple simple est l’application divergente du combinateur omega & # 969; 

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

à lui-même: 

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

La priorité est donnée à la réduction des sous-expressions les plus à gauche (& têtes & # 8220; & # 8221;). Ordre applicatif normalise les arguments avant la substitution, contrairement à ordre normal . Les deux stratégies sont analogues à une évaluation rapide, par ex. C et évaluation paresseuse, par exemple Haskell. 

=  (λ 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))
. . .
=  _|_

diverge sous une réduction bêta d’ordre d’ordre applicatif 

forall f.  f _|_  =  _|_

depuis dans la sémantique strict 

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

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

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

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

Y

Propriété essentielle du Y combinateur à virgule fixe 

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

est donné par 

Y g  =  g (Y g)

L'équivalence 

fix f  =  f (fix f)

est isomorphe à 

 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

Le calcul lambda non typé peut coder des preuves constructives arbitraires sur des fonctions générales / & # 956; -recursive. 

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

(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 . 

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

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

En Haskell, le combinateur en virgule fixe peut être implémenté avec élégance 

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

La paresse de Haskell se normalise avant l’évaluation de toutes les sous-expressions.

<*>

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

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

vous pouvez 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 cela dans n’importe quel langage appel par valeur normal, vous aurez besoin du combinateur z associé (le combinateur y diverge / boucle infinie).

As a newbie to combinators, I found Mike Vanier's article (thanks Nicholas Mancuso) to be really helpful. I would like to write a summary, besides documenting my understanding, if it could be of help to some others I would be very glad.

From Crappy to Less Crappy

Using factorial as an example, we use the following almost-factorial function to calculate factorial of number x:

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

In the pseudo-code above, almost-factorial takes in function f and number x (almost-factorial is curried, so it can be seen as taking in function f and returning a 1-arity function).

When almost-factorial calculates factorial for x, it delegates the calculation of factorial for x - 1 to function f and accumulates that result with x (in this case, it multiplies the result of (x - 1) with x).

It can be seen as almost-factorial takes in a crappy version of factorial function (which can only calculate till number x - 1) and returns a less-crappy version of factorial (which calculates till number x). As in this form:

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

If we repeatedly pass the less-crappy version of factorial to almost-factorial, we will eventually get our desired factorial function f. Where it can be considered as:

almost-factorial f = f

Fix-point

The fact that almost-factorial f = f means f is the fix-point of function almost-factorial.

This was a really interesting way of seeing the relationships of the functions above and it was an aha moment for me. (please read Mike's post on fix-point if you haven't)

Three functions

To generalize, we have a non-recursive function fn (like our almost-factorial), we have its fix-point function fr (like our f), then what Y does is when you give Y fn, Y returns the fix-point function of fn.

So in summary (simplified by assuming fr takes only one parameter; x degenerates to x - 1, x - 2... in recursion):

  • We define the core calculations as fn: def fn fr x = ...accumulate x with result from (fr (- x 1)), this is the almost-useful function - although we cannot use fn directly on x, it will be useful very soon. This non-recursive fn uses a function fr to calculate its result
  • fn fr = fr, fr is the fix-point of fn, fr is the useful funciton, we can use fr on x to get our result
  • Y fn = fr, Y returns the fix-point of a function, Y turns our almost-useful function fn into useful fr

Deriving Y (not included)

I will skip the derivation of Y and go to understanding Y. Mike Vainer's post has a lot of details.

The form of Y

Y is defined as (in lambda calculus format):

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

If we replace the variable s in the left of the functions, we get

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

So indeed, the result of (Y f) is the fix-point of f.

Why does (Y f) work?

Depending the signature of f, (Y f) can be a function of any arity, to simplify, let's assume (Y f) only takes one parameter, like our factorial function.

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

since fn fr = fr, we 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)))

the recursive calculation terminates when the inner-most (fn fr 1) is the base case and fn doesn't use fr in the calculation.

Looking at Y again:

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

So

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

To me, the magical parts of this setup are:

  • fn and fr interdepend on each other: fr 'wraps' fn inside, every time fr is used to calculate x, it 'spawns' ('lifts'?) an fn and delegates the calculation to that fn (passing in itself fr and x); on the other hand, fn depends on fr and uses fr to calculate result of a smaller problem x-1.
  • At the time fr is used to define fn (when fn uses fr in its operations), the real fr is not yet defined.
  • It's fn which defines the real business logic. Based on fn, Y creates fr - a helper function in a specific form - to facilitate the calculation for fn in a recursive manner.

It helped me understanding Y this way at the moment, hope it helps.

BTW, I also found the book An Introduction to Functional Programming Through Lambda Calculus very good, I'm only part through it and the fact that I couldn't get my head around Y in the book led me to this post.

Here are answers to the original questions, compiled from the article (which is TOTALY worth reading) mentioned in the answer by Nicholas Mancuso, as well as other answers:

What is a Y-combinator?

An Y-combinator is a "functional" (or a higher-order function — a function that operates on other functions) that takes a single argument, which is a function that isn't recursive, and returns a version of the function which is recursive.

Somewhat recursive =), but more in-depth definition:

A combinator — is just a lambda expression with no free variables.
Free variable — is a variable that is not a bound variable.
Bound variable — variable which is contained inside the body of a lambda expression that has that variable name as one of its arguments.

Another way to think about this is that combinator is such a lambda expression, in which you are able to replace the name of a combinator with its definition everywhere it is found and have everything still work (you will get into an infinite loop if combinator would contain reference to itself, inside the lambda body).

Y-combinator is a fixed-point combinator.

Fixed point of a function is an element of the function's domain that is mapped to itself by the function.
That is to say, c is a fixed point of the function f(x) if f(c) = c
This means f(f(...f(c)...)) = fn(c) = c

How do combinators work?

Examples below assume strong + dynamic typing:

Lazy (normal-order) Y-combinator:
This definition applies to languages with lazy (also: deferred, call-by-need) evaluation — evaluation strategy which delays the evaluation of an expression until its value is needed.

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

What this means is that, for a given function f (which is a non-recursive function), the corresponding recursive function can be obtained first by computing λx.f(x x), and then applying this lambda expression to itself.

Strict (applicative-order) Y-combinator:
This definition applies to languages with strict (also: eager, greedy) evaluation — evaluation strategy in which an expression is evaluated as soon as it is bound to a 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)))

It is same as lazy one in it's nature, it just has an extra λ wrappers to delay the lambda's body evaluation. I've asked another question, somewhat related to this topic.

What are they good for?

Stolen borrowed from answer by Chris Ammerman: Y-combinator generalizes recursion, abstracting its implementation, and thereby separating it from the actual work of the function in question.

Even though, Y-combinator has some practical applications, it is mainly a theoretical concept, understanding of which will expand your overall vision and will, likely, increase your analytical and developer skills.

Are they useful in procedural languages?

As stated by Mike Vanier: it is possible to define a Y combinator in many statically typed languages, but (at least in the examples I've seen) such definitions usually require some non-obvious type hackery, because the Y combinator itself doesn't have a straightforward static type. That's beyond the scope of this article, so I won't mention it further

And as mentioned by Chris Ammerman: most procedural languages has static-typing.

So answer to this one — not really.

A fixed point combinator (or fixed-point operator) is a higher-order function that computes a fixed point of other functions. This operation is relevant in programming language theory because it allows the implementation of recursion in the form of a rewrite rule, without explicit support from the language's runtime engine. (src Wikipedia)

The this-operator can simplify your life:

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

Then you avoid the extra function:

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

Finally, you call fac(5).

I think the best way to answer this is to pick a language, like 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));
    }
}

Now rewrite it so that it doesn't use the name of the function inside the function, but still calls it recursively.

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.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top