Y-Combinator Exemple pratique

Question

J'ai lu un peu ces derniers temps sur la programmation fonctionnelle et je suis en train de assimilez le Y-Combinator. Je comprends que vous pouvez utiliser le Y-Combinator pour mettre en œuvre efficacement récursion dans une langue qui ne prend pas directement récursivité. Cependant, toutes les langues que je suis susceptible d'utiliser des supports déjà récursion donc je ne sais pas comment il serait utile d'utiliser le Y-Combinator pour cela.

Y at-il un exemple plus pratique d'utilisation Y-Combinator que je suis absent? Quelqu'un at-il réellement utilisé un dans le code de production réel? Ou utilise le Y-Combinator vraiment juste un exercice académique bending (mais un assez cool).

Answer 1

Je vais être en désaccord avec d'autres réponses: Le point fixe (Y) combinateur Finalité avoir des applications pratiques , mais il faut un esprit très imaginatif pour les trouver . Comme Bruce McAdam. Voici le résumé de son journal Qu'environ Wraps il :

  

Y combinateur pour le calcul de points fixes peut être exprimé en Standard ML. Il est souvent utilisé comme un exemple de la puissance des fonctions d'ordre supérieur, mais il est généralement pas considéré comme une construction de programmation utile. Ici, nous examinons comment une technique de programmation basée sur Y Combinator et emballages peut donner aux programmeurs un niveau de contrôle sur le fonctionnement interne des fonctions non autrement possible sans réécrire et recompiler le code. A titre d'expérience, l'algorithme de type inférence W est mis en œuvre en utilisant cette technique, de sorte que les messages d'erreur sont produits avec un minimum d'interférence à l'algorithme. Le code de ce programme d'exemple illustre l'utilité réelle des concepts et la facilité avec laquelle ils peuvent être appliqués. Un certain nombre d'autres techniques de mise en œuvre et les applications possibles sont également examinées, y compris l'utilisation des fonctions d'ordre supérieur pour simuler l'utilisation des exceptions et continuations.

Il est un grand papier; toute personne intéressée par la programmation fonctionnelle sera probablement une bonne lecture.

Answer 2

Vous pouvez consulter cet article sur la mise en œuvre du nifty Y Combinator en C #: récursives expressions Lambda , il pourrait vous aider à mieux comprendre l'idée.

Vous pouvez consulter quelques articles sur Wikipédia belle: Point fixe Combinator et < a href = "http://en.wikipedia.org/wiki/Fixed-point_theorem#Fixed_point_theorems_in_discrete_mathematics_and_theoretical_computer_science" rel = "nofollow noreferrer"> théorèmes de point fixe

Comme le dit Nathan, de nombreuses techniques fonctionnelles sont liées au Y Combinator et sont utiles, donc gardez à elle! Y est vraiment utile car il vous permet de mieux comprendre votre code, mais je ne pense pas que ce soit particulièrement utile pour décrire la façon dont il aide.

Answer 3

Vous pouvez penser Combinator comme la machine virtuelle qui exécute votre fonction, que vous décrivez par une fonction (= fonction d'ordre supérieur) non récurrent.

Parfois, il serait bien d'avoir cette combinateur sous le contrôle du programme, de faire des choses semblables que la programmation orientée aspect (memoizing, suivi, ...), mais pas le langage de programmation que je connaisse le permet. Sans doute, il serait trop lourd la plupart du temps et / ou trop difficile à apprendre.

Answer 4

D'autres peuvent me corriger si je me trompe, mais je suis sûr que le Y Combinator est strictement académique. Pensez-y: pour la mettre en œuvre votre langue doit prendre en charge les fonctions d'ordre supérieur mais pas récursivité. Il n'y a qu'une seule langue que je sais comme ça:. Lambda-calcul

Alors que nos machines passent de machines Turing fonctionnant sur le calcul lambda, le combinateur Y sera strictement académique.

Note: D'autres techniques fonctionnelles liées au Y Combinator sont utile, donc persévérez. Comprendre le combinateur Y vous aidera à comprendre continuations, évaluation paresseuse, etc.

Answer 5

let sprite = pipe4 sprite_start blanks (manyTill attribute newline) blanks (fun a b c _ -> Sprite(a,c))

let sprites = 
    let rec y f x = f (y f) x // The Y Combinator
    //let rec sprites_up = many1Indents sprite sprites_up |>> (fun x -> SubSprites x) // Does not work.
    let sprites_up = y (fun f -> many1Indents sprite f |>> (fun x -> SubSprites x))
    many1Indents sprite sprites_up

Voici un exemple du compilateur pour une bibliothèque de jeu assez petite, je fais en F #. Plus précisément, dans ce qui précède que je dois avoir le sprites_up appeler lui-même récursive sinon l'analyseur d'indentation ne fonctionne pas correctement.

Sans Y Combinator, je ne aurais pu faire l'analyseur correctement et aurait dû recourir à écrire quelque chose comme ceci:

let sprites_up4 = many1Indents sprite error |>> (fun x -> SubSprites x) 
let sprites_up3 = many1Indents sprite sprites_up4 |>> (fun x -> SubSprites x) 
let sprites_up2 = many1Indents sprite sprites_up3 |>> (fun x -> SubSprites x) 
let sprites_up1 = many1Indents sprite sprites_up2 |>> (fun x -> SubSprites x) 
let sprites_up = many1Indents sprite sprites_up1 |>> (fun x -> SubSprites x) 

n'aurait pas été une excellente solution, le Y Combinator m'a vraiment sauvé là. Ce fut certainement pas la première chose qui vient à l'esprit cependant.