Pourquoi les langages de programmation fonctionnels nécessitent-ils un garbage collection?

14

Qu'est-ce qui empêche ghc de traduire Haskell en un langage de programmation concaténatif tel que la logique combinatoire, puis d'utiliser simplement l'allocation de pile pour tout? Selon Wikipedia, la traduction du calcul lambda à la logique combinatoire est triviale, et les langages de programmation concaténatifs peuvent compter uniquement sur une pile pour l'allocation de mémoire. Est-il possible de faire cette traduction et donc d'éliminer le ramasse-miettes pour des langues comme Haskell et ocaml? Y a-t-il des inconvénients à faire cela?

EDIT: déplacé ici /programming/39440412/why-do-functional-programming-languages-require-garbage-collection

Nicholas Grasevski
la source
Le langage de programmation Cat ressemble à un exemple de langage fonctionnel basé sur la pile.
Petr Pudlák
1
Ce n'est pas une question au niveau de la recherche, car la collecte des ordures est couverte dans les cours de premier cycle sur les langages de programmation (ainsi que la nécessité de celui-ci). Veuillez passer à cs.stackexchange.com
Andrej Bauer
Mon erreur. Connaissez-vous la réponse à ma question?
Nicholas Grasevski
5
Je pense qu'il y a une réponse au niveau de la recherche à donner à cette question, car je me souviens avoir eu du mal avec elle pendant mes années d'études: tout dans un langage comme Haskell ressemble à une application de fonction, qui vit sur la pile. Je pense qu'expliquer pourquoi les fermetures sont nécessaires, pourquoi elles vivent sur le tas, et peut-être ce que les "données échappant à la portée de la fonction" ont à voir avec cela ferait une réponse très informative (que je ne suis pas sûr d'être qualifié pour donner, malheureusement).
cody
2
λ

Réponses:

16

Tous les commentaires suivants reposent sur le choix d'une stratégie d'implémentation standard utilisant des fermetures pour représenter les valeurs de fonction et un ordre d'évaluation appel par valeur:

  1. Pour le calcul lambda pur, la collecte des ordures n'est pas nécessaire. Cela est dû au fait qu'il n'est pas possible de former des cycles dans le tas: chaque valeur nouvellement allouée ne peut contenir que des références aux valeurs précédemment allouées, et donc le graphique de la mémoire forme un DAG - donc le comptage des références suffit pour gérer la mémoire.

  2. La plupart des implémentations n'utilisent pas le comptage de références pour deux raisons.

    1. Ils prennent en charge une forme de type pointeur (par exemple, le refconstructeur de type en ML), et ainsi de vrais cycles dans le tas peuvent être formés.
    2. Le comptage des références est beaucoup moins efficace que la récupération de place, car
      • il nécessite beaucoup d'espace supplémentaire pour conserver les comptes de référence, et
      • la mise à jour des décomptes est généralement un travail inutile, et
      • les mises à jour des comptes créent un tas de conflits d'écriture qui détruit les performances parallèles.
  3. Les langages de type linéaire peuvent éliminer le nombre de références (essentiellement parce que les nombres sont 0-1: soit la valeur a une seule référence, soit elle est morte et peut être libérée).

  4. Cependant, l'allocation de pile ne suffit toujours pas. En effet, il est possible de former des valeurs de fonction qui se réfèrent à des variables libres (c'est-à-dire que nous devons implémenter des fermetures de fonction), si vous allouez des choses sur la pile, les valeurs en direct peuvent être entrelacées avec des valeurs mortes, ce qui entraînera une asymptotique incorrecte l'utilisation de l'espace.

  5. Vous pouvez obtenir la bonne asymptotique en remplaçant une pile par une "pile de spaghetti" (c'est-à-dire implémenter la pile en tant que liste chaînée dans le tas, afin de pouvoir découper les cadres morts selon les besoins).

  6. Si vous voulez une vraie discipline de pile, vous pouvez utiliser des systèmes de types basés sur une "logique ordonnée" (essentiellement des types linéaires sans échange).

Neel Krishnaswami
la source
2
N'est-ce pas la raison la plus fondamentale pour (2) que - même sans effets secondaires observables - les implémentations veulent avoir un opérateur efficace pour la récursion (mutuelle), c'est-à-dire un opérateur qui forme réellement un cycle dans le tas?
Andreas Rossberg
@andreasrossberg: J'ai pensé à le mentionner, mais je l'ai laissé de côté car vous pouvez utiliser le combinateur y pour la récursivité.
Neel Krishnaswami