Ce qui est un y-combinator ?

Question

Un y-combinator est un concept de maquette-sci du côté « fonctionnels » des choses. La plupart des programmeurs ne sais pas beaucoup du tout à leur sujet, si ils ont même entendu à leur sujet.

Ce qui est un y-combinator ? Comment ça marche ? Quels sont-ils bon pour ? Sont-ils utiles dans les langages procéduraux ?

Answer 1

Un Y combinator est un "fonctionnelle" (une fonction qui fonctionne sur d'autres fonctions) qui permet la récursivité, lorsque vous ne pouvez pas se référer à la fonction à partir de l'intérieur de lui-même. Dans la théorie des sciences, il généralise la récursivité, l'abstraction de sa mise en œuvre, et ce qui le sépare du travail réel de la fonction en question. L'avantage de ne pas avoir besoin d'un moment de la compilation du nom de la fonction récursive est une sorte de bonus. =)

Ceci est applicable dans les langues qui prennent en charge les lambda fonctions. L' expressionde la lambdas signifie généralement qu'ils ne peuvent pas se référer à eux-mêmes par leur nom. Et de travail autour de ce en déclarant la variable, qui est venu à elle, puis à attribuer le lambda, pour compléter l'auto-référence de la boucle, est fragile. Le lambda variable peut être copié, et la variable d'origine attribué à nouveau, ce qui rompt l'auto-référence.

Y-combinators sont lourdes à mettre en œuvre, et souvent à l'utilisation en statique de type de langues ( langues procédurales sont souvent), parce que d'habitude de taper des restrictions exigent le nombre d'arguments de la fonction en question à être connu au moment de la compilation. Cela signifie qu'un y combinator doit être écrit pour tout argument compter que l'on doit utiliser.

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

À l'aide d'un Y-combinator implique un "inhabituel" la construction d'une fonction récursive. D'abord, vous devez écrire votre fonction comme un morceau de code qui appelle une pré-existante de la fonction, plutôt que de lui-même:

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

Ensuite, vous transformer en une fonction qui prend une fonction à appeler, et retourne une fonction qui le fait. Cela s'appelle fonctionnel, car il faut une fonction, et effectue une opération avec elle que les résultats dans 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);

Maintenant, vous avez une fonction qui prend une fonction, et retourne une fonction qui donne l'impression d'être une factorielle, mais au lieu d'appeler lui-même, il appelle l'argument passé à la fonction externe. Comment voulez-vous faire de cette factoriel? Passer à la fonction interne à lui-même. Le Y Combinator fait que, en étant une fonction avec un nom définitif, ce qui peut introduire de 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 de la factorielle d'appel lui-même, ce qui se passe, c'est que la factorielle appelle la factorielle générateur (retourné par l'appel récursif à Y Combinator). Et en fonction de la valeur actuelle de t la fonction renvoyée à partir du générateur d'appeler le générateur encore, à t - 1, ou juste de retour de 1, la résiliation de la récursivité.

C'est complexe et énigmatique, mais tout s'équilibrera au moment de l'exécution, et la clé de son travail est "l'exécution différée", et la rupture de la récursivité à durée de deux fonctions. L'intérieur F est passé comme argument, pour être appelé dans la prochaine itération, seulement si nécessaire.

Answer 2

Si vous êtes prêt pour une longue lecture, Mike Vanier a une grande explication. Longue histoire courte, il permet d’implémenter de récursivité dans une langue qui nécessairement ne le supporte pas nativement.

Answer 3

J'ai soulevé ce à partir de http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html ce qui est une explication que j'ai écrit il y a plusieurs années.

Je vais utiliser JavaScript dans cet exemple, mais de nombreuses autres langues de travail.

Notre objectif est d'être capable d'écrire une fonction récursive de 1 variable en utilisant uniquement les fonctions de 1 variables et pas de d'affectations, de définir les choses par leur nom, etc. (Pourquoi c'est notre but est une autre question, nous allons juste prendre ce que l' le défi que nous nous sommes donnés). Semble impossible, hein? Comme un exemple, nous allons mettre en œuvre factorielle.

Étape 1 consiste à dire que l'on peut faire facilement si nous triché un peu. Utilisation des fonctions de 2 variables et affectation du moins pouvons-nous éviter d'avoir à utiliser cession 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
);

Maintenant, nous allons voir si nous pouvons tricher moins. Eh bien tout d'abord que nous utilisons d'affectation, mais nous n'avons pas besoin de. Il nous suffit d'é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 sommes à l'aide de fonctions de 2 variables pour obtenir une fonction de 1 variable. Pouvons-nous résoudre ce problème? Eh bien c'est un gars intelligent par le nom de Haskell Curry a une astuce, si vous avez de bons d'ordre supérieur fonctions vous avez seulement besoin de fonctions de 1 variable. L' la preuve est que vous pouvez obtenir à partir de fonctions de 2 (ou plus dans le cas général) des variables à 1 variable purement mécanique de transformation du texte comme ceci:

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

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

où ... reste exactement la même. (Cette astuce est appelé "nourrissage" d'après son inventeur. Le langage Haskell est également nommé pour Haskell Curry. Fichier sous inutile de trivia.) 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 à essayer. alert() qui renvoient, de la lier à un bouton, que ce soit. Ce code calcule factorielles, de manière récursive, sans l'aide de d'affectation, de déclarations, ou des fonctions de 2 variables. (Mais pour retrouver la trace de la façon dont il fonctionne est susceptible de vous faire tourner la tête. Et de remettre, sans la dérivation, juste un peu reformaté sera le résultat dans le code qui est sûr pour le déflecteur et les confondre.)

Vous pouvez remplacer les 4 lignes que de manière récursive définir factorielle avec toute autre fonction récursive qui vous voulez.

Answer 4

Je me demande si il n'y a aucune utilisation dans la tentative de construire ce à partir du sol. Voyons voir. Voici une base, la fonction factorielle récursive:

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

Nous allons refactoriser et de créer une nouvelle fonction appelée fact qui renvoie un anonyme factorielle-le calcul de la fonction au lieu d'effectuer le calcul en 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 en sommes seulement à la génération d'une nouvelle fonction factorielle à chaque étape.

La récursivité à ce stade est encore assez explicite. L' fact fonction doit être conscient de son propre nom. Nous allons paramétrer 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 génial, mais recurser faut quand même savoir son nom propre. Nous allons paramétrer qu', trop:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

Maintenant, au lieu d'appeler recurser(recurser) directement, nous allons créer une fonction wrapper qui renvoie son résultat:

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

var factorial = Y();

On peut maintenant se débarrasser de la recurser nom de tout; c'est juste un argument de Y sont à l'intérieur de la fonction, 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és est - fact, mais il devrait être clair maintenant que c'est facilement paramétrable, aussi, la création de la compléter, de génériques, de la solution:

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

Answer 5

La plupart des réponses ci-dessus décrivent ce que le Y combinator est mais pas ce qu'il en est pour.

Point fixe combinators sont utilisés pour montrer que le lambda calcul est turing complet. C'est un résultat très important dans la théorie du calcul et fournit un fondement théorique à la programmation fonctionnelle.

L'étude de point fixe combinators m'a aussi permis de vraiment comprendre la programmation fonctionnelle. Je n'ai jamais trouvé d'aucune utilité dans la programmation.