Qu'est-ce qu'un combinateur en Y?

un combinateur en Y est une fonction" fonctionnelle " (une fonction qui fonctionne sur d'autres fonctions) qui permet la récursion, lorsque vous ne pouvez pas vous référer à la fonction de l'intérieur. Dans la théorie informatique, il généralise la récursion , en faisant l'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 de compilation pour la fonction récursive est en quelque sorte un bonus. = )

c'est applicable dans les langues qui supportent fonctions lambda . L'expression basée sur signifie généralement que les lambdas ne peuvent pas se référer à eux-mêmes par leur nom. Et travailler autour de cela en déclarant la variable, en s'y référant, puis en lui assignant la lambda, pour compléter la boucle d'auto-référence, est fragile. La variable lambda peut être copiée, et la variable originale réattribuée, ce qui casse l'auto-référence.

Y-combinators sont lourdes à mettre en œuvre, et souvent à utiliser, dans statique tapé langues ( les langages procéduraux le 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'utilisation d'un combinateur en Y implique une façon" inhabituelle " de construire une fonction récursive. Tout d'abord, vous devez é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);

Alors vous transformer en une fonction qui prend une fonction à appeler, et retourne une fonction qui le fait. Ceci est appelé un fonctionnel, parce qu'il prend une fonction, et effectue une opération avec elle qui résulte 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 renvoie une autre fonction qui ressemble un peu à un factoriel, mais au lieu de s'appeler elle-même, elle appelle l'argument passé dans la fonction externe. Comment voulez-vous faire de cette factoriel? Passer la fonction intérieure à elle-même. Le combinateur Y fait cela, en étant une fonction avec un nom permanent, qui peut introduire la récursion.

// 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 le appel factoriel lui-même, ce qui se produit est que le factoriel appelle le générateur factoriel (retourné 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 appellera de nouveau le générateur, avec t - 1, ou retournera tout simplement 1, mettant fin à la récursion.

C'est compliqué et cryptique, 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é pour couvrir deux fonctions. L'intérieur de F est passé comme argument , d'être appelé dans la prochaine itération, seulement si nécessaire .

j'ai levé ceci de http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html qui est une explication que j'ai écrite il y a plusieurs années.

J'utiliserai JavaScript dans cet exemple, mais beaucoup d'autres langues fonctionneront aussi.

notre objectif est de pouvoir écrire une fonction récursive de 1 variable utilisant uniquement les fonctions de 1 variables et no tâches, définition des choses par leur nom, etc. (Pourquoi c'est notre le but est un autre question, prenons juste ceci comme le le défi que nous nous sommes donnée. Ça semble impossible, hein? Comme un exemple, mettons en œuvre factoriel.

Eh bien la première étape est de dire que nous pourrions le faire facilement si nous triché un peu. En utilisant les 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
);

voyons maintenant si nous pouvons tricher moins. Eh bien tout d'abord que nous utilisons d'affectation, mais nous n'avons pas besoin de. Nous 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? Un type intelligent du nom de Le Curry d'Haskell a une astuce soignée, si vous avez un bon ordre supérieur fonctions alors vous n'avez besoin que 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 une transformation mécanique de 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. La langue Haskell est aussi du nom de Haskell Curry. Classez ça sous futilités inutiles.) 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 renvoient, de la lier à un bouton, que ce soit. Ce code calcule factoriels, récursivement, sans utiliser attribution, déclarations ou fonctions de 2 variables. (Mais essayer de tracer comment cela fonctionne est susceptible de faire tourner votre tête. Et le remettre, sans la dérivation, légèrement reformaté résultera en un code qui est sûr de déconcerter et de confondre.)

vous pouvez remplacer les 4 lignes qui définissent factoriellement factoriel avec toute autre fonction récursive qui vous voulez.

je me demande s'il y a une utilité à essayer de construire ceci à partir de la base. Voyons voir. Voici une fonction factorielle de base récursive:

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

Let's 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 à ça. Nous produisons juste un nouveau factoriel la fonction à 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 génial, mais recurser a encore besoin de connaître son propre nom. Paramétrons ça 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 renvoie son résultat:

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

var factorial = Y();

nous pouvons maintenant nous débarrasser complètement du nom recurser ; c'est juste un argument à 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 c'est facilement paramétré, aussi, créant la solution complète, 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 est mais pas ce qu'il est pour .

les combinateurs à points fixes sont utilisés pour montrer que lambda calculus est turing complete . Il s'agit d'un résultat très important dans la théorie du calcul et fournit une base théorique pour programmation fonctionnelle .

L'étude des combinateurs à points fixes m'a également aidé à comprendre vraiment la programmation fonctionnelle. Je n'ai jamais trouvé d'aucune utilité dans la programmation.

y combinator 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'apprends beaucoup en regardant le code, mais celui-ci est un peu difficile à avaler sans quelques arrière-plan - désolé à ce sujet. 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"combinateur y". Maintenant, regardez la ligne var factorial où Y est utilisé. Avis 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 (puisqu'il utilise recurse() dans sa définition.) Le combinateur y effectue la magie d'associer la fonction interne par ailleurs anonyme avec le nom de paramètre de la fonction passée à Y.

pour l'explication complète de comment Y fait la magie, vérifié les lié à l'article (pas par moi btw.)

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écursion dans une situation où les fonctions ne peuvent pas avoir de noms mais peuvent être passées comme arguments, utilisées comme valeurs de retour, et définies dans d'autres fonctions.

il fonctionne en passant la fonction à lui-même comme un argument, de sorte qu'il peut s'appeler elle-même.

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

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

dans le cas où vous devez l'identifier dans une identification de police, il ressemble à ceci:

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

vous pouvez habituellement le repérer à cause de la répétition (λx.f (x x)) .

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

D'autres réponses fournissent une réponse assez concise à cela, sans un fait important: vous n'avez pas besoin de mettre en œuvre point combinator fixe dans n'importe quel langage pratique de cette manière alambiquée et le faire ne sert aucun but 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 du combinateur Y 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 combinateur en Y est un autre nom pour un condensateur de flux.

j'ai écrit une sorte de" guide des idiots " pour le combinateur en Y, à la fois dans le style et dans le style, afin de m'aider à le maîtriser. Ils sont influencés par article dans "Le Petit Intrigant"

Dans Le Régime: https://gist.github.com/z5h/238891

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

les deux tutoriels sont des codes entrecoupés de commentaires et devraient être coupez et collez dans votre éditeur préféré.

Le y combinator met en œuvre anonyme de la récursivité. Donc au lieu de

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

vous pouvez le 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 qu'en langage d'appel. Si vous voulez utiliser ceci dans n'importe quel langage d'appel-par-valeur, alors vous aurez besoin du combinateur z correspondant (le combinateur y divergera/boucle infinie).

un combinateur de points fixes (ou opérateur de point 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 la mise en œuvre de la récursion sous la forme d'une règle de réécriture, sans support explicite du moteur d'exécution du langage. (src Wikipedia)

l'opérateur ceci peut simplifier votre vie:

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

alors vous évitez la fonction supplémentaire:

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

enfin, vous appelez fac(5) .

Recursion anonyme

un combinateur à point fixe est une fonction d'ordre supérieur fix qui, par définition, satisfait à l'équivalence

forall f.  fix f  =  f (fix f)

fix f représente une solution x à l'équation à point fixe

               x  =  f x

le factoriel d'un nombre naturel peut être prouvé par

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

en utilisant fix , preuves constructives arbitraires sur les fonctions générales / μ-récursives peuvent être dérivées sans auto-référentialité non nulle.

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 de combinateur à point fixe pour rewrites

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

Lambda calcul

le lambda calcul non typé formalisme consiste dans un contexte de libre-grammaire

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

où v s'étend sur les variables, avec le bêta et réduction eta règles

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

Beta reduction remplace 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 l'abstraction redondante. Elle est parfois omise du formalisme. Une expression irréductible , à laquelle aucune règle de réduction ne s'applique, est normale ou sous forme canonique .

λ x y. E

est la abréviation de

λ x. λ y. E

(abstraction multiarity),

E F G

est la abréviation de

(E F) G

(application de la gauche-associativité),

λ x. x

et

λ y. y

sont alpha-équivalent .

Abstraction et application sont les deux seules " primitives langagières "du calcul lambda, mais elles permettent encodage de données et d'opérations complexes arbitraires.

les chiffres de L'Église sont un encodage de la 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

à l'aide de la règle de réécriture de la bêta de réduction:

   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, combinators sont des abstractions qui ne contiennent pas de variables libres. 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 de combinator calculi comme le système de SKI.

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

Bêta de réduction n'est pas fortement normalisant ; non pas réductible expressions, "redexes", de converger vers une forme normale en vertu de la bêta de réduction. Un exemple simple est l'application divergente du combinateur omega ω

λ x. x x

à lui-même:

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

réduction des sous-expressions à gauche ("têtes") est prioritaire. Applicative "ordre de 1519660920" normalise les arguments avant de substitution, normal ne fonctionne pas. Les deux stratégies sont analogues à l'évaluation impatiente, par exemple C, et à l'évaluation paresseuse, par exemple Haskell.

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

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

forall f.  f _|_  =  _|_

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

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

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

Y g  =  g (Y g)

fix f  =  f (fix f)

 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

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

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

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

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

Il peut être considéré comme almost-factorial prend un de merde version de la fonction factorielle (qui ne peut calculer jusqu'au numéro x - 1 ) et renvoie un "15191050920 moins" de merde version de factorielle (qui calcule jusqu'au numéro x ). Comme sous cette forme:

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

si nous à plusieurs reprises passer le moins-merdique version de factoriel à almost-factorial , nous obtiendrons finalement notre fonction factorielle désirée f . Où elle peut être considérée comme:

almost-factorial f = f

point de repère

le fait que almost-factorial f = f signifie f est le point de repère de la fonction almost-factorial .

C'était une façon très intéressante de voir le les relations des fonctions ci-dessus et ce fut un moment aha pour moi. (s'il vous plaît lire le post de Mike sur fix-point si vous n'avez pas)

trois fonctions

pour généraliser, nous avons un non-récursive fonction fn (comme notre presque-factorielle), nous avons son point fixe fonction fr (comme notre f), alors ce que Y fait est quand vous donnez "1519310920 fn " , Y renvoie la fonction de point de repère de fn .

donc en résumé (simplifié en supposant fr ne prend qu'un paramètre; x dégénère en x - 1 , x - 2 ... en récursion):

• nous définissons le calculs de base comme fn : def fn fr x = ...accumulate x with result from (fr (- x 1)) , c'est le presque utile fonction-bien que nous ne puissions pas utiliser fn directement sur x , il sera utile très bientôt. Ce fn non récursif utilise une fonction fr pour calculer son résultat
• fn fr = fr , fr est le point de repère de fn , fr est le utile funciton, nous pouvons utiliser fr sur x pour obtenir notre résultat
• Y fn = fr , Y renvoie le point de repère d'une fonction, Y transforme notre presque utile fonction fn en utile fr

dérivant Y (non inclus)

je vais sauter la dérivation de Y et aller à comprendre Y . Mike Vainer post a beaucoup de détails.

la forme de Y

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

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

si nous remplaçons la variable s dans la 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)

en effet, le résultat de (Y f) est le point de repère de f .

pourquoi (Y f) fonctionne?

en fonction de la signature de f , (Y f) peut être une fonction de n'importe quelle arité, pour simplifier, supposons que (Y f) 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 (fn fr 1) est le cas de base et le fn n'utilise pas fr dans le calcul.

en regardant Y encore:

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:

• fn et fr interdepend les uns les autres: fr des "emballages" de fn à l'intérieur, à chaque fois fr est utilisée pour calculer les x , il engendre' ("soulève"?) un fn et délègue le calcul à celui fn (en lui-même fr et x ); d'autre part, fn dépend de fr et utilise fr pour calculer le résultat d'un plus petit problème x-1 .
• À l'époque fr est utilisé pour définir fn (quand fn utilise fr dans ses opérations), le véritable fr n'est pas encore défini.
• c'est fn qui définit la véritable logique commerciale. Basé sur fn , Y crée fr - une fonction d'aide dans une forme spécifique - pour faciliter le calcul pour fn dans un récursive manière.

Il m'a aidé à comprendre Y de cette façon, pour le moment, espérons que cela aide.

BTW, j'ai également trouvé le livre une Introduction à la fonctionnelle Programmation par Lambda calcul très bon, je ne suis qu'une partie à travers elle et le fait que je ne pouvais pas obtenir ma tête autour Y dans le livre m'a conduit à ce poste.

Voici les réponses aux questions originales , compilées à partir de l'article (qui vaut 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 en Y?

Y combinator est un "fonctionnelle" (ou d'une fonction d'ordre supérieur - une fonction qui fonctionne sur d'autres fonctions) prend un seul argument, qui est une fonction n'est pas récursive, et renvoie une version de la fonction qui est récursive.

Somewhat recursive =), mais plus en profondeur définition:

un combinateur - est juste une expression lambda sans variables libres.

Libre variable 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 combinator est une telle expression lambda, dans laquelle vous êtes en mesure de remplacer le nom d'un combinateur avec sa définition partout où il se trouve et avoir tout fonctionne encore (vous obtiendrez dans une boucle infinie si combinator contiendrait une référence à lui-même, à l'intérieur du corps lambda).

Y-combinator est un combinateur à point fixe.

point fixe d'une fonction est un élément du domaine de la fonction qui est mappé à lui-même par la fonction.

, C'est-à-dire, c est un point fixe de la fonction f(x) si f(c) = c

cela signifie f(f(...f(c)...)) = fn(c) = c

comment fonctionnent les combinateurs?

exemples ci-dessous supposons fort + dynamique Dactylographie:

Paresseux (normal) Y-combinator:

cette définition s'applique aux langues dont l'évaluation est paresseuse (aussi: évaluation 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.

"1519510920 Strict" (applicative) Y-combinator:

cette définition s'applique aux langues ayant une stratégie d'évaluation stricte (également: avide, avide) 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)))

c'est comme un paresseux dans sa nature, il a juste un emballage supplémentaire λ pour retarder l'évaluation du corps de la lambda. J'ai demandé une autre question , quelque peu liée à ce sujet.

à quoi servent-ils?

volé emprunté à réponse de Chris Ammerman : Y-combinator généralise la récursion, en faisant l'abstraction de sa mise en œuvre, et en la séparant ainsi du travail réel de la fonction en question.

même si Y-combinator a quelques 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 d'analyse et de développement.

sont-ils utiles dans la procédure langues?

comme déclaré par Mike Vanier : il est possible de définir un combinateur de Y dans de nombreux langages statiquement dactylographiés, mais (au moins dans les exemples que j'ai vus) de telles définitions exigent généralement un certain hackery de type non évident, parce que le combinateur de Y lui-même n'a pas un type statique simple. C'est au-delà de la portée de cet article, donc je ne vais pas le mentionner plus loin

et comme mentionné par Chris Ammerman : la plupart des langues procédurales a static-typing.

donc réponse à celle - ci-pas vraiment.

je pense que la meilleure façon de répondre à cette question Est de choisir un langage, 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éécrire afin qu'il n'utilise pas le nom de la fonction à l'intérieur de la fonction, mais encore l'appelle récursivement.

le seul endroit où le nom de la fonction factorial devrait être affiché est le site d'appel.

indice: vous ne pouvez pas utiliser les noms de fonctions, mais vous pouvez utiliser les noms de paramètres.

travailler le problème. Ne pas le regarder. Une fois que vous le résolvez, vous comprendrez quel problème le combinateur y résout.