Haskell a-t-il besoin d'un garbage collector?

Je suis curieux de savoir pourquoi les implémentations Haskell utilisent un GC.

Je ne peux pas penser à un cas où GC serait nécessaire dans un langage pur. S'agit-il simplement d'une optimisation pour réduire la copie ou est-ce vraiment nécessaire?

Je recherche un exemple de code qui fuirait si un GC n'était pas présent.

Comme d'autres l'ont déjà souligné, Haskell nécessite une gestion automatique et dynamique de la mémoire: la gestion automatique de la mémoire est nécessaire car la gestion manuelle de la mémoire n'est pas sûre; la gestion dynamique de la mémoire est nécessaire car pour certains programmes, la durée de vie d'un objet ne peut être déterminée qu'au moment de l'exécution.

Par exemple, considérez le programme suivant:

main = loop (Just [1..1000]) where
  loop :: Maybe [Int] -> IO ()
  loop obj = do
    print obj
    resp <- getLine
    if resp == "clear"
     then loop Nothing
     else loop obj

Dans ce programme, la liste [1..1000]doit être conservée en mémoire jusqu'à ce que l'utilisateur tape "clear"; donc la durée de vie de celui-ci doit être déterminée dynamiquement, et c'est pourquoi une gestion dynamique de la mémoire est nécessaire.

Donc, dans ce sens, l'allocation de mémoire dynamique automatisée est nécessaire, et en pratique cela signifie: oui , Haskell nécessite un garbage collector, puisque garbage collection est le gestionnaire de mémoire dynamique automatique le plus performant.

Toutefois...

Bien qu'un garbage collector soit nécessaire, nous pourrions essayer de trouver des cas particuliers où le compilateur peut utiliser un schéma de gestion de mémoire moins cher que le garbage collection. Par exemple, étant donné

f :: Integer -> Integer
f x = let x2 = x*x in x2*x2

nous pourrions espérer que le compilateur détecte ce qui x2peut être libéré en toute sécurité lors du fretour (plutôt que d'attendre que le ramasse-miettes se désalloue x2). Essentiellement, nous demandons au compilateur d'effectuer une analyse d'échappement pour convertir les allocations en tas récupéré en mémoire en allocations sur la pile dans la mesure du possible.

Ce n'est pas trop déraisonnable de demander: le compilateur jhc haskell fait cela, bien que GHC ne le fasse pas. Simon Marlow dit que le ramasse-miettes générationnel de GHC rend l'analyse des évasions pratiquement inutile.

jhc utilise en fait une forme sophistiquée d'analyse d'échappement connue sous le nom d' inférence de région . Considérer

f :: Integer -> (Integer, Integer)
f x = let x2 = x * x in (x2, x2+1)

g :: Integer -> Integer
g x = case f x of (y, z) -> y + z

Dans ce cas, une analyse d'échappement simpliste conclurait que x2s'échappe de f(car il est retourné dans le tuple), et x2doit donc être alloué sur le tas récupéré. L'inférence de région, d'autre part, est capable de détecter ce qui x2peut être désalloué lors du gretour; l'idée ici est que cela x2devrait être attribué dans gla région de s plutôt que dans fla région de s.

Au-delà de Haskell

Bien que l'inférence de région soit utile dans certains cas comme discuté ci-dessus, elle semble difficile à concilier efficacement avec une évaluation paresseuse (voir les commentaires d'Edward Kmett et Simon Peyton Jones ). Par exemple, considérez

f :: Integer -> Integer
f n = product [1..n]

On pourrait être tenté d'allouer la liste [1..n]sur la pile et de la désallouer après les fretours, mais ce serait catastrophique: cela passerait fde l'utilisation de la mémoire O (1) (sous garbage collection) à la mémoire O (n).

Un travail approfondi a été effectué dans les années 1990 et au début des années 2000 sur l'inférence de région pour le langage fonctionnel strict ML. Mads Tofte, Lars Birkedal, Martin Elsman, Niels Hallenberg ont écrit une rétrospective assez lisible sur leur travail sur l'inférence de région, dont une grande partie a été intégrée au compilateur MLKit . Ils ont expérimenté la gestion de la mémoire purement basée sur la région (c'est-à-dire pas de ramasse-miettes) ainsi que la gestion hybride de la mémoire basée sur la région / ramasse-miettes, et ont signalé que leurs programmes de test fonctionnaient «entre 10 fois plus vite et 4 fois plus lentement» que le pur garbage- versions collectées.

Prenons un exemple trivial. Compte tenu de cela

f (x, y)

vous devez allouer la paire (x, y)quelque part avant d'appeler f. Quand pouvez-vous désallouer cette paire? Tu n'as aucune idée. Il ne peut pas être désalloué lors d'un fretour, car il faurait pu placer la paire dans une structure de données (par exemple, f p = [p]), de sorte que la durée de vie de la paire pourrait devoir être plus longue que celle du retour f. Maintenant, disons que la paire a été mise dans une liste, celui qui démonte la liste peut-il désallouer la paire? Non, car la paire peut être partagée (par exemple let p = (x, y) in (f p, p)). Il est donc vraiment difficile de dire quand la paire peut être désallouée.

Il en va de même pour presque toutes les allocations dans Haskell. Cela dit, il est possible d'avoir une analyse (analyse de région) qui donne une limite supérieure sur la durée de vie. Cela fonctionne assez bien dans les langages stricts, mais moins dans les langages paresseux (les langages paresseux ont tendance à faire beaucoup plus de mutation que les langages stricts dans l'implémentation).

J'aimerais donc renverser la question. Pourquoi pensez-vous que Haskell n'a pas besoin de GC. Comment suggéreriez-vous que l'allocation de mémoire soit effectuée?

Votre intuition que cela a quelque chose à voir avec la pureté a une part de vérité.

Haskell est considéré comme pur en partie parce que les effets secondaires des fonctions sont pris en compte dans la signature de type. Donc, si une fonction a pour effet secondaire d'imprimer quelque chose, il doit y avoir un IOquelque part dans son type de retour.

Mais il y a une fonction qui est utilisée implicitement partout dans Haskell et dont la signature de type ne tient pas compte, en un certain sens, d'un effet secondaire. À savoir la fonction qui copie certaines données et vous redonne deux versions. Sous le capot, cela peut fonctionner soit littéralement, en dupliquant les données en mémoire, soit «virtuellement» en augmentant une dette qui doit être remboursée plus tard.

Il est possible de concevoir des langages avec des systèmes de types encore plus restrictifs (des systèmes purement "linéaires") qui interdisent la fonction de copie. Du point de vue d'un programmeur dans un tel langage, Haskell a l'air un peu impur.

En fait, Clean , un parent de Haskell, a des types linéaires (plus strictement: uniques), et cela peut donner une idée de ce que serait d'interdire la copie. Mais Clean permet toujours la copie pour les types "non uniques".

Il y a beaucoup de recherche dans ce domaine et si vous cherchez assez sur Google, vous trouverez des exemples de code purement linéaire qui ne nécessite aucun ramasse-miettes. Vous trouverez toutes sortes de systèmes de types qui peuvent signaler au compilateur quelle mémoire peut être utilisée, ce qui permet au compilateur d'éliminer une partie du GC.

Il y a un sens dans lequel les algorithmes quantiques sont également purement linéaires. Chaque opération est réversible et donc aucune donnée ne peut être créée, copiée ou détruite. (Ils sont également linéaires au sens mathématique habituel.)

Il est également intéressant de comparer avec Forth (ou d'autres langages basés sur la pile) qui ont des opérations DUP explicites qui indiquent clairement quand la duplication se produit.

Une autre façon (plus abstraite) de penser à ce sujet est de noter que Haskell est construit à partir d'un calcul lambda simplement typé qui est basé sur la théorie des catégories fermées cartésiennes et que ces catégories sont équipées d'une fonction diagonale diag :: X -> (X, X). Une langue basée sur une autre classe de catégorie pourrait ne pas avoir une telle chose.

Mais en général, la programmation purement linéaire est trop difficile pour être utile, nous nous contentons donc de GC.

Les techniques d'implémentation standard appliquées à Haskell nécessitent en fait un GC plus que la plupart des autres langages, puisqu'elles ne mutent jamais les valeurs précédentes, créant à la place de nouvelles valeurs modifiées basées sur les précédentes. Puisque cela signifie que le programme alloue et utilise constamment plus de mémoire, un grand nombre de valeurs seront supprimées au fil du temps.

C'est pourquoi les programmes GHC ont tendance à avoir des chiffres d'allocation totale aussi élevés (de gigaoctets à téraoctets): ils allouent constamment de la mémoire, et ce n'est que grâce au GC efficace qu'ils la récupèrent avant de s'épuiser.

Si un langage (n'importe quel langage) vous permet d'allouer des objets de manière dynamique, il existe trois façons pratiques de gérer la gestion de la mémoire:

1. Le langage ne peut vous permettre d'allouer de la mémoire que sur la pile, ou au démarrage. Mais ces restrictions limitent considérablement les types de calculs qu'un programme peut effectuer. (En pratique. En théorie, vous pouvez émuler des structures de données dynamiques dans (par exemple) Fortran en les représentant dans un grand tableau. C'est HORRIBLE ... et sans rapport avec cette discussion.)

2. Le langage peut fournir un explicite freeou un disposemécanisme. Mais cela dépend du programmeur pour bien faire les choses. Toute erreur dans la gestion du stockage peut entraîner une fuite de mémoire ... ou pire.

3. Le langage (ou plus strictement l'implémentation du langage) peut fournir un gestionnaire de stockage automatique pour le stockage alloué dynamiquement; c'est à dire une forme de ramasse-miettes.

La seule autre option consiste à ne jamais récupérer le stockage alloué dynamiquement. Ce n'est pas une solution pratique, sauf pour les petits programmes effectuant de petits calculs.

En appliquant cela à Haskell, le langage n'a pas la limitation de 1., et il n'y a pas d'opération de désallocation manuelle selon 2. Par conséquent, pour être utilisable pour des choses non triviales, une implémentation Haskell doit inclure un garbage collector .

Je ne peux pas penser à un cas où GC serait nécessaire dans un langage pur.

Vraisemblablement, vous entendez un langage fonctionnel pur.

La réponse est qu'un GC est nécessaire sous le capot pour récupérer les objets de tas que le langage DOIT créer. Par exemple.

• Une fonction pure a besoin de créer des objets de tas car dans certains cas, elle doit les renvoyer. Cela signifie qu'ils ne peuvent pas être alloués sur la pile.

• Le fait qu'il puisse y avoir des cycles (résultant d'un let recpar exemple) signifie qu'une approche de comptage de références ne fonctionnera pas pour les objets de tas.

• Ensuite, il y a les fermetures de fonctions ... qui ne peuvent pas non plus être allouées sur la pile car elles ont une durée de vie qui est (généralement) indépendante de la trame de pile dans laquelle elles ont été créées.

Je recherche un exemple de code qui fuirait si un GC n'était pas présent.

À peu près n'importe quel exemple impliquant des fermetures ou des structures de données en forme de graphique fuirait dans ces conditions.

Un garbage collector n'est jamais nécessaire, à condition que vous ayez suffisamment de mémoire. Cependant, en réalité, nous n'avons pas de mémoire infinie, et nous avons donc besoin d'une méthode pour récupérer de la mémoire qui n'est plus nécessaire. Dans des langages impurs comme C, vous pouvez explicitement déclarer que vous avez terminé avec de la mémoire pour la libérer - mais il s'agit d'une opération de mutation (la mémoire que vous venez de libérer n'est plus sûre à lire), vous ne pouvez donc pas utiliser cette approche dans une langue pure. Il s'agit donc soit d'analyser statiquement où vous pouvez libérer la mémoire (probablement impossible dans le cas général), de perdre de la mémoire comme un tamis (fonctionne très bien jusqu'à ce que vous soyez à court de mémoire), ou d'utiliser un GC.

GC est "indispensable" dans les langages FP purs. Pourquoi? Les opérations allouées et gratuites sont impures! Et la deuxième raison est que les structures de données récursives immuables ont besoin de GC pour l'existence parce que le backlinking crée des structures abstruses et impossibles à maintenir pour l'esprit humain. Bien sûr, le backlinking est une bénédiction, car la copie de structures qui l'utilise est très bon marché.

Quoi qu'il en soit, si vous ne me croyez pas, essayez simplement d'implémenter le langage FP et vous verrez que j'ai raison.

EDIT: j'ai oublié. La paresse est ENFER sans GC. Tu ne me crois pas? Essayez-le simplement sans GC, par exemple en C ++. Vous verrez ... des choses

Haskell est un langage de programmation non strict, mais la plupart des implémentations utilisent l'appel par besoin (paresse) pour implémenter la non-rigueur. Dans Call-by-Need, vous n'évaluez les choses que lorsqu'elles sont atteintes pendant l'exécution en utilisant la machinerie des "thunks" (expressions qui attendent d'être évaluées puis se réécrivent, restant visibles pour que leur valeur soit réutilisée si nécessaire).

Donc, si vous implémentez votre langage paresseusement à l'aide de thunks, vous avez reporté tout raisonnement sur la durée de vie des objets jusqu'au dernier moment, qui est l'exécution. Puisque vous ne savez plus rien sur les durées de vie, la seule chose que vous pouvez raisonnablement faire est de ramasser les ordures ...