Problèmes d'implémentation de fermetures dans des paramètres non fonctionnels

18

Dans les langages de programmation, les fermetures sont une fonctionnalité populaire et souvent souhaitée. Wikipédia dit (c'est moi qui souligne):

En informatique, une fermeture (...) est une fonction associée à un environnement de référence pour les variables non locales de cette fonction. Une fermeture permet à une fonction d'accéder à des variables en dehors de sa portée lexicale immédiate.

Une fermeture est donc essentiellement une valeur de fonction (anonyme?) Qui peut utiliser des variables en dehors de sa propre portée. D'après mon expérience, cela signifie qu'il peut accéder aux variables qui sont dans la portée à son point de définition.

Dans la pratique, le concept semble cependant divergent, du moins en dehors de la programmation fonctionnelle. Différentes langues implémentent des sémantiques différentes, il semble même y avoir des guerres d'opinions sur. De nombreux programmeurs ne semblent pas savoir ce que sont les fermetures, les considérant comme un peu plus que des fonctions anonymes.

En outre, il semble exister des obstacles majeurs lors de la mise en œuvre des fermetures. Plus notable, Java 7 était censé les inclure, mais la fonctionnalité a été repoussée à une future version.

Pourquoi les fermetures sont-elles si difficiles (à comprendre et) à réaliser? C'est une question trop large et trop vague, alors permettez-moi de me concentrer davantage sur ces questions interconnectées:

  • Existe-t-il des problèmes d'expression des fermetures dans les formalismes sémantiques courants (petit pas, grand pas, ...)?
  • Les systèmes de type existants ne conviennent-ils pas aux fermetures et ne peuvent-ils pas être étendus facilement?
  • Est-il problématique d'aligner les fermetures sur une traduction de procédure traditionnelle basée sur la pile?

Notez que la question concerne principalement les langages procéduraux, orientés objet et de script en général. Pour autant que je sache, les langages fonctionnels n'ont aucun problème.

Raphael
la source
Bonne question. Des fermetures ont été implémentées dans Scala, et Martin Odersky a écrit le compilateur Java 1.5, donc on ne sait pas pourquoi ils ne sont pas dans Java 7. C # les a. (J'essaierai d'écrire une meilleure réponse plus tard.)
Dave Clarke
4
Les langages fonctionnels impurs comme Lisp et ML acceptent très bien les fermetures, il ne peut donc pas y avoir de raison sémantique intrinsèque pour qu'elles soient problématiques.
Gilles 'SO- arrête d'être méchant'
J'ai inclus l'élément parce que j'ai eu du mal à imaginer à quoi pourrait ressembler une sémantique à petite étape pour les fermetures. Il se peut très bien que les fermetures en elles-mêmes ne soient pas un problème, mais les inclure dans un langage qui n'est pas conçu en pensant à elles est difficile.
Raphael
1
Jetez un oeil à pdfs.semanticscholar.org/73a2/… - Les auteurs de Lua l'ont fait de manière très intelligente et discutent également des problèmes généraux de mise en œuvre des fermetures
Bulat

Réponses:

10

Puis-je vous diriger vers la page wikipedia du problème Funarg ? Au moins, c'est ainsi que les gens du compilateur faisaient référence au problème de mise en œuvre de la fermeture.

Une fermeture est donc essentiellement une valeur de fonction (anonyme?) Qui peut utiliser des variables en dehors de sa propre portée. D'après mon expérience, cela signifie qu'il peut accéder aux variables qui sont dans la portée à son point de définition.

Bien que cette définition soit logique, elle n'aide pas à décrire le problème de l'implémentation de fonctions de première classe dans un langage traditionnel basé sur la pile d'exécution. En ce qui concerne les problèmes d'implémentation, les fonctions de première classe peuvent être grossièrement divisées en deux classes:

  • Les variables locales dans les fonctions ne sont jamais utilisées après le retour de la fonction.
  • Les variables locales peuvent être utilisées après le retour de la fonction.

Le premier cas (funargs vers le bas) n'est pas si difficile à implémenter et peut être trouvé même sur les langages procéduraux plus anciens, comme Algol, C et Pascal. C contourne le problème, car il n'autorise pas les fonctions imbriquées, mais Algol et Pascal font la comptabilité nécessaire pour permettre aux fonctions internes de référencer les variables de pile de la fonction externe.

Le deuxième cas (funargs vers le haut), d'autre part, nécessite que les enregistrements d'activation soient enregistrés en dehors de la pile, dans le tas. Cela signifie qu'il est très facile de fuir des ressources de mémoire à moins que le runtime de langage ne comprenne un garbage collector. Bien que presque tout soit ramassé aujourd'hui, en exiger un est toujours une décision de conception importante et l'était encore plus il y a quelque temps.


Quant à l'exemple particulier de Java, si je me souviens bien, le problème principal n'était pas en fait de pouvoir implémenter des fermetures, mais comment les introduire dans le langage d'une manière qui n'était pas redondante avec les fonctionnalités existantes (comme les classes internes anonymes) et cela ne heurtait pas les fonctionnalités existantes (comme les exceptions vérifiées - un problème qui n'est pas trivial à résoudre et auquel la plupart des gens ne pensent pas au début).

Je peux également penser à d'autres choses qui rendent les fonctions de première classe moins triviales à implémenter, comme décider quoi faire avec des variables "magiques" comme celle- ci , self ou super et comment interagir avec les opérateurs de flux de contrôle existants, tels que break et return (voulons-nous autoriser les retours non locaux ou non?). Mais à la fin, la popularité récente des fonctions de première classe semble indiquer que les langues qui ne les ont pas le font principalement pour des raisons historiques ou en raison d'une décision de conception importante au début.

hugomg
la source
1
Connaissez-vous des langues qui distinguent les cas ascendants et descendants? Dans les langages .NET, une méthode générique qui s'attendait à recevoir une fonction vers le bas uniquement pouvait recevoir une structure de type générique avec un délégué qui recevrait une telle structure comme un byref (en C #, un " refparamètre"). Si l'appelant a encapsulé toutes les variables d'intérêt dans la structure, le délégué pourrait être entièrement statique, évitant ainsi d'avoir besoin d'une allocation de tas. Les compilateurs n'offrent aucune aide syntaxique intéressante pour de telles constructions, mais le Framework pourrait les prendre en charge.
supercat
2
@supercat: Rust a plusieurs types de fermetures qui vous permettent d'appliquer au moment de la compilation si une fonction interne devra utiliser le tas. Cependant, cela ne signifie pas qu'une implémentation ne peut pas essayer d'éviter les allocations de tas sans vous forcer à vous soucier de tous ces types supplémentaires. Un compilateur peut essayer d'inférer les durées de vie de la fonction ou il peut utiliser des vérifications d'exécution pour enregistrer paresseusement des variables dans le tas uniquement lorsque cela est strictement nécessaire (consultez la section "portée lexicale" du document Evolution of Lua pour plus de détails)
hugomg
5

Nous pouvons voir comment les fermetures sont implémentées en C #. L'ampleur des transformations effectuées par le compilateur C # montre clairement que leur façon d'implémenter les fermetures demande beaucoup de travail. Il existe peut-être des moyens plus faciles d'implémenter des fermetures, mais je pense que l'équipe du compilateur C # en serait conscient.

Considérez le pseudo-C # suivant (j'ai coupé un peu de choses spécifiques à C #):

int x = 1;
function f = function() { x++; };
for (int i = 1; i < 10; i++) {
    f();
}
print x; // Should print 9

Le compilateur transforme cela en quelque chose comme ceci:

class FunctionStuff {
   int x;
   void theFunction() {
       x++;
   }
}

FunctionStuff theClosureObject = new FunctionStuff();
theClosureObject.x = 1;
for (int i = 1; i < 10; i++) {
    theClosureObject.theFunction();
}
print theClosureObject.x; // Should print 9

(en réalité, la variable f sera toujours créée, où f est un «délégué» (= pointeur de fonction), mais ce délégué est toujours associé à l'objet theClosureObject - j'ai laissé cette partie pour plus de clarté pour ceux qui ne sont pas familiers avec C #)

Cette transformation est assez massive et délicate: considérez les fermetures à l'intérieur des fermetures et l'interaction des fermetures avec le reste des fonctionnalités du langage C #. Je peux imaginer que la fonctionnalité a été repoussée pour Java, car Java 7 a déjà beaucoup de nouvelles fonctionnalités.

Alex ten Brink
la source
Je peux voir où cela va; ayant plusieurs fermetures et l'accès à la portée principale, la même variable va être compliquée.
Raphael
Pour être honnête, cela est davantage dû à l'utilisation du cadre OO existant pour implémenter les fermetures, puis à tout problème réel avec elles. D'autres langues allouent simplement les variables dans une structure distincte et sans méthode, puis laissent plusieurs fermetures la partager si elles le souhaitent.
hugomg
@Raphael: que pensez-vous des fermetures à l'intérieur des fermetures? Attendez, permettez-moi d'ajouter cela.
Alex ten Brink
5

Pour répondre à une partie de votre question. Le formalisme décrit par Morrisett et Harper couvre la sémantique à grands et petits pas des langages polymorphes d'ordre supérieur contenant des fermetures. Il y a des articles avant ceux-ci fournissant le type de sémantique que vous recherchez. Regardez, par exemple, la machine SECD . L'ajout de références mutables ou de variables locales mutables dans ces sémantiques est simple. Je ne vois pas qu'il y ait de problèmes techniques à fournir une telle sémantique.

Dave Clarke
la source
Merci pour la référence! Cela ne semble pas permettre une lecture légère, mais cela est probablement à prévoir dans un article sémantique.
Raphael
1
@Raphael: Il y en a probablement plus simples. J'essaierai de trouver quelque chose et je te recontacterai. Dans tous les cas, la figure 8 a la sémantique que vous recherchez.
Dave Clarke
Vous pouvez peut-être donner un aperçu approximatif resp. les idées centrales dans votre réponse?
Raphael
2
@Raphael. Je pourrais peut-être vous référer à mes notes de cours que j'utilise pour un cours de langages de programmation, qui vous donne une introduction rapide. Veuillez consulter les documents 8 et 9.
Uday Reddy
1
Ce lien apparaît soit mort, soit derrière une authentification invisible. ( cs.cmu.edu/afs/cs/user/rwh/public/www/home/papers/gcpoly/tr.pdf ). J'ai 403 interdit.
Ben Fletcher