Exemple pratique de Y-Combinator

Question

J'ai été lire un peu ces derniers temps sur la programmation fonctionnelle, et je suis en train d'analyser le Y Combinator. Je comprends que vous pouvez utiliser le Y Combinator pour mettre en œuvre efficacement la récursivité dans une langue qui ne supporte pas la récursivité directement. Cependant, de toutes les langues que je suis susceptible d'utiliser prend déjà en charge de la récursivité donc je ne suis pas sûr de savoir comment il serait utile d'utiliser le Y Combinator pour que.

Est-il un meilleur exemple pratique de Y Combinator l'utilisation que je suis absent? Quelqu'un a effectivement utilisé dans la production réelle de code? Ou est l'utilisation de l'Y-Combinator vraiment juste un esprit de flexion exercice académique (quoique assez cool).

Answer 1

Je ne suis pas daccord avec les autres réponses: Le point fixe (Y) combinator ne avoir des applications pratiques, mais il faut un esprit très imaginatif pour les trouver. Comme Bruce McAdam. Voici le résumé de son livre Que Sur l'enveloppe en Haut:

Le Y combinator pour le calcul de points fixes peuvent être exprimés en Standard ML. Il est fréquemment utilisé comme un exemple de la puissance des fonctions d'ordre supérieur, mais n'est généralement pas considérée comme une programmation utile de la construction. Ici, nous examinons comment une technique de programmation basé sur le Y combinator et de l'encapsulation peut donner des programmeurs un niveau de contrôle sur le fonctionnement interne de fonctions pas possible autrement sans réécriture et de recompiler le code. Comme une expérience, l'inférence de type algorithme W est mis en œuvre à l'aide de cette technique, de sorte que les messages d'erreur sont produits avec un minimum d'interférences de l'algorithme. Le code de cet exemple de programme illustre la véritable utilité des concepts et de 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 discutés, y compris l'utilisation de fonctions d'ordre supérieur pour simuler l'utilisation des exceptions et des prolongements.

C'est une grande feuille de papier; quiconque s'intéresse à la programmation fonctionnelle sera probablement profiter de la lecture.

Answer 2

Vous pouvez vérifier cette chouette post sur la mise en œuvre du Y Combinator en C#: Récursive des Expressions Lambda, il peut vous aider à comprendre l'idée de mieux.

Vous voudrez peut-être vérifier quelques bons articles sur Wikipédia: point Fixe combinator et théorèmes de point Fixe

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

Answer 3

Vous pouvez considérer le combinateur comme la machine virtuelle qui exécute votre fonction, que vous décrivez par une fonction non-récursive (= fonction d'ordre supérieur).

Parfois, il serait bien d’avoir ce combinateur sous contrôle de programme, de faire des choses similaires à la programmation orientée aspect (mémorisation, traçage, ...), mais aucun langage de programmation que je connaisse ne le permet. Ce serait probablement trop lourd et / ou trop difficile à apprendre.

Answer 4

Les autres peuvent me corriger si je me trompe, mais je suis sûr que le Y combinator est strictement académique. Pensez-y: pour mettre en œuvre la langue de votre besoin à l'appui de fonctions d'ordre supérieur, mais pas la récursivité. Il n'y a qu'une seule langue, je sais comme ça: lambda calcul.

Donc, jusqu'à ce que nos machines commutateur de machines de Turing à l'exécution sur le lambda calcul, le Y combinator sera strictement académique.

Remarque: d'autres techniques fonctionnelles liées à la Y combinator sont utiles, afin de garder à elle. Comprendre le Y combinator va vous aider à comprendre les continuations, évaluation différée, etc.