Je suis curieux de savoir pourquoi les implémentations de Haskell utilisent un GC.
Je ne peux imaginer un cas où GC serait nécessaire dans une langue pure. Est-ce juste une optimisation pour réduire la copie, ou est-ce réellement nécessaire ?
Je suis à la recherche par exemple code qui pourrait s’écouler si un GC n’était pas présent.
Comme d'autres l'ont déjà souligné, Haskell nécessite automatique, dynamique de gestion de la mémoire: gestion automatique de la mémoire est nécessaire parce que le manuel de gestion de la mémoire est dangereux; gestion dynamique de la mémoire est nécessaire parce que, 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érons 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] doivent être conservés en mémoire jusqu'à ce que l'utilisateur tape "clair"; de sorte que la durée de vie de ce doit être déterminé de façon dynamique, et c'est pourquoi la gestion dynamique de la mémoire est nécessaire.
Ainsi, dans ce sens, automatisé allocation dynamique de la mémoire est nécessaire, dans la pratique, cela signifie: oui, Haskell nécessite un garbage collector, depuis la collecte des ordures est de la plus haute performance dynamique et automatique du gestionnaire de mémoire.
Bien qu'un garbage collector est nécessaire, nous pourrions essayer de trouver des cas particuliers dans lesquels le compilateur peut utiliser un meilleur gestion de la mémoire système de collecte des ordures. Par exemple, étant donné
f :: Integer -> Integer
f x = let x2 = x*x in x2*x2
on peut espérer pour le compilateur de détecter qu' x2 peuvent en toute sécurité être libéré lorsque f rendements (plutôt que d'attendre que le garbage collector pour désallouer x2). En fait, nous demandons que le compilateur d'effectuer échapper à l'analyse de convertir des allocations dans les déchets collectés sur le segment de mémoire à allouer sur la pile dans la mesure du possible.
Ce n'est pas trop déraisonnable de demander: le jhc compilateur haskell cela, bien que GHC ne le fait pas. Simon Marlow dit que GHC est générationnel garbage collector fait échapper à l'analyse de la plupart inutiles.
jhc utilise en fait une forme sophistiquée de s'échapper de l'analyse connu comme la région de l'inférence. Envisager
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 simple échapper à l'analyse de conclure que l' x2 s'en échappe f (parce qu'il est retourné dans le tuple), et par conséquent x2 doit être réparti sur les déchets collectés sur le tas. Région d'inférence, d'autre part, est capable de détecter x2 peut être libéré lors de l' g rendements; l'idée est qu' x2 devraient être alloués g's de la région plutôt que d' f's de la région.
Alors que la région de l'inférence est utile, dans certains cas, comme discuté ci-dessus, il apparaît difficile de concilier efficacement avec d'évaluation différée (voir Edward Kmett de et Simon Peyton Jones commentaires). Par exemple, considérons
f :: Integer -> Integer
f n = product [1..n]
On pourrait être tenté d'attribuer le liste [1..n] sur la pile et le désallouer après f de rendement, mais cela serait catastrophique: il changerait f de l'aide O(1) de la mémoire (en vertu de la collecte des ordures) à O(n) de la mémoire.
Travail considérable a été fait dans les années 1990 et au début des années 2000 sur la région de l'inférence pour la stricte langage fonctionnel ML. Mads Tofte, Lars Birkedal, Martin Elsman, Niels Hallenberg ont écrit un assez lisible rétrospective de leurs travaux sur la région de l'inférence, beaucoup de qui ils intégrés dans les MLKit compilateur. Ils ont expérimenté avec purement la région de base de la gestion de la mémoire (c'est à dire pas de garbage collector) ainsi que des hybrides de la région/le garbage collector de gestion de la mémoire, et ont indiqué que leurs programmes de test couru "entre 10 fois plus rapide, et 4 fois plus lent" que de purs déchets collectés versions.
Prenons un exemple trivial. Compte tenu de cette
f (x, y)
vous avez besoin d'allouer de la paire (x, y) quelque part avant d'appeler f. Quand pouvez-vous libérer cette paire? Vous n'avez aucune idée. Il ne peut pas être libéré lorsque f retours, car f est peut-être la paire dans une structure de données (e.g, f p = [p]), de sorte que la durée de vie de la paire pourrait être plus longue que le retour de f. Maintenant, dire que la paire a été mis dans une liste, pouvez-celui qui prend la liste, en dehors de désallouer la paire? Non, parce que la paire pourrait être partagé (par exemple, let p = (x, y) in (f p, p)). Donc, c'est vraiment difficile de dire quand la paire peut être libéré.
La même chose vaut pour presque toutes les attributions en Haskell. Cela dit, il est possible de disposer d'une analyse de la région (analyse) qui donne une limite supérieure sur la durée de vie. Cela fonctionne raisonnablement bien dans le strict langues, mais moins chez les paresseux langues (paresseux langues ont tendance à faire beaucoup plus de mutations que le strict langues dans la mise en œuvre).
J'aimerais donc tourner autour de la question. Pourquoi pensez-vous Haskell n'a pas besoin de GC. Comment voulez-vous suggérer d'allocation de mémoire à faire?
Votre intuition que cela a quelque chose à voir avec la pureté a une certaine vérité à cela.
Haskell est considérée comme pure en partie parce que les effets secondaires de fonctions sont prises en compte dans le type de signature. Donc, si une fonction a pour effet de bord de l'impression de quelque chose, il doit y avoir un IO quelque part dans son type de retour.
Mais il y a une fonction qui est implicitement utilisé partout dans Haskell et dont le type de signature ne tient pas compte, qu'est-ce que, dans un certain sens, un effet de bord. À savoir la fonction qui copie des données et vous donne deux versions de retour. Sous le capot, cela peut fonctionner soit littéralement, en dupliquant les données dans la mémoire, ou "virtuellement" par l'augmentation d'une dette qui doit être payée de retour plus tard.
Il est possible de concevoir des langues avec encore plus restrictive des systèmes de type (purement "linéaire") qui ne permettent pas la fonction de copie. Du point de vue d'un programmeur dans une telle langue, Haskell est un peu impur.
En fait, Propre, proche de Haskell, a linéaire (plus strictement: unique), et que peut donner une idée de ce que ce serait comme interdire la copie. Mais Propre encore permet la copie de la "non-unique".
Il y a beaucoup de recherche dans ce domaine et si vous Google assez, vous trouverez des exemples de pure linéaire de code qui ne nécessite pas de collecte des ordures. Vous trouverez toutes sortes de systèmes de type qui peut signaler au compilateur que la mémoire peut être utilisé permettant au compilateur pour éliminer certains de la GC.
Il y a un sens dans lequel les algorithmes quantiques sont également purement linéaire. Chaque opération est réversible et donc pas de données peuvent être créés, copié, ou détruits. (Ils sont aussi linéaires habituelles dans le sens mathématique.)
Il est également intéressant de comparer avec avant (ou autre pile en fonction des langues) qui ont explicites DUP opérations de préciser lors de la duplication qui se passe.
L'autre (plus abstrait) façon de penser à ce sujet est à noter que Haskell est construite à partir de lambda calcul simplement typé qui est basée sur la théorie cartésienne des catégories fermées et que ces catégories sont équipées avec une diagonale de la fonction diag :: X -> (X, X). Un langage basé sur une autre catégorie de la catégorie peut avoir aucune une telle chose.
Mais en général, purement programmation linéaire est trop difficile d'être utile, de sorte que nous nous installons pour la GC.
La mise en application des normes techniques applicables aux Haskell réellement besoin d'un GC moreso que la plupart des autres langues, puisqu'ils n'ont jamais muter valeurs précédentes, au lieu de créer de nouvelles, les valeurs modifiées basé sur les précédents. Car cela signifie que le programme est constamment une répartition et une utilisation de plus de mémoire, un grand nombre de valeurs sera rejeté comme le temps passe.
C'est pourquoi GHC programmes ont tendance à avoir de tels taux de l'allocation totale des chiffres (à partir de gigaoctets à des téraoctets): ils sont constamment en allouant de la mémoire, et c'est seulement grâce à l'efficacité de GC qu'ils le récupérer avant de ressortir.
Un garbage collector n'est jamais nécessaire, à condition de disposer de suffisamment de mémoire. Cependant, dans la réalité, nous n'avons pas infinie de la mémoire, et nous avons donc besoin d'une méthode pour récupérer de la mémoire qui ne sont plus nécessaires. Dans impur langages tels que le C, vous pouvez le mentionner explicitement que vous avez terminé avec un peu de mémoire pour libérer de l'il - mais c'est une mutation de l'opération (le mémoire que vous avez tout juste libérée, n'est plus sûr de lire), de sorte que vous ne pouvez pas utiliser cette approche dans une langue pure. Donc c'est soit en quelque sorte analyser statiquement où vous pouvez libérer de la mémoire (probablement impossible dans le cas général), une fuite de mémoire comme une passoire (fonctionne très bien jusqu'au bout), ou d'utiliser un GC.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
