Optimiseur de combinateur Y et d'appel de queue

La définition d'un combinateur Y en F # est

let rec y f x = f (y f) x

f s'attend à avoir comme premier argument une continuation pour les sous-problèmes récursifs. En utilisant le yf comme suite, nous voyons que f sera appliqué aux appels successifs au fur et à mesure que nous développerons

let y f x = f (y f) x = f (f (y f)) x = f (f (f (y f))) x etc...

Le problème est que, a priori, ce schéma empêche d'utiliser toute optimisation d'appel de queue: en effet, il pourrait y avoir une opération en attente dans les f, auquel cas nous ne pouvons pas simplement muter la trame de pile locale associée à f.

Donc :

• d'une part, l'utilisation du combinateur Y nécessite une continuation explicitement différente de la fonction elle-même.
• sur l'othe pour appliquer le TCO, nous aimerions n'avoir aucune opération en attente dans f et n'appeler que f lui-même.

Connaissez-vous un moyen de réconcilier ces deux-là? Comme un Y avec astuce accumulateur, ou un Y avec astuce CPS? Ou un argument prouvant qu'il n'y a aucun moyen de le faire?

Connaissez-vous un moyen de réconcilier ces deux-là?

Non, et pour cause, à mon humble avis.

Le combinateur Y est une construction théorique et n'est nécessaire que pour compléter le calcul lambda (rappelez-vous, il n'y a pas de boucles dans le calcul lambda, et les lambdas n'ont pas de noms que nous pourrions utiliser pour la récursivité).

En tant que tel, le combinateur Y est vraiment fascinant.

Mais : Personne n'utilise réellement le combinateur Y pour une récursivité réelle! (Sauf peut-être pour le plaisir, pour montrer que cela fonctionne vraiment.)

L'optimisation des appels de queue, OTOH, est, comme son nom l'indique, une optimisation. Il n'ajoute rien à l'expressivité d'un langage, c'est uniquement à cause de considérations pratiques comme l'espace de pile et les performances du code récursif que nous nous en soucions.

Votre question est donc la suivante: existe-t-il une prise en charge matérielle pour la réduction bêta? (La réduction bêta est la façon dont les expressions lambda sont réduites, vous savez.) Mais aucun langage fonctionnel (à ma connaissance) ne compile son code source en une représentation des expressions lambda qui seront bêta réduites lors de l'exécution.

Je ne suis pas complètement sûr de cette réponse, mais c'est le mieux que j'ai pu trouver.

Le combinateur y est intrinsèquement paresseux, dans les langages stricts, la paresse doit être ajoutée manuellement via des lambdas supplémentaires.

let rec y f x = f (y f) x

Votre définition semble nécessiter de la paresse pour se terminer, sinon l' (y f)argument ne finirait jamais d'être évalué et devrait évaluer s'il l'a futilisé ou non . Le COT dans un contexte paresseux est plus compliqué et, de plus, le résultat (y f)est une composition de fonctions répétée sans application avec le x. Je ne suis pas sûr que ce besoin prenne de la mémoire O (n) où n est la profondeur de la récursivité, mais je doute que vous puissiez obtenir le même type de table des matières que possible avec quelque chose comme (passer à Haskell parce que je ne sais pas réellement F#)

length acc []    = acc
length acc (a:b) = length (acc+1) b 

Si vous ne le savez pas déjà, la différence entre foldlet foldl'à Haskell peut éclairer la situation. foldlest écrit comme on le ferait dans une langue avide. Mais au lieu d'être COT, c'est en fait pire que foldrparce que l'accélérateur stocke un thunk potentiellement énorme qui ne peut pas être partiellement évalué. (Cela est lié à la raison pour laquelle foldl et foldl 'ne fonctionnent pas sur des listes infinies.) Ainsi, dans les versions plus récentes de Haskell, a foldl'été ajouté, ce qui force l'évaluation de l'accumulateur à chaque fois que la fonction se reproduit pour garantir qu'aucun énorme thunk n'est créé. Je suis sûr que http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 peut expliquer cela mieux que moi.