Pourquoi les langages purement fonctionnels n'utilisent-ils pas le comptage de références?

Question

Sur le plan purement fonctionnel langues, les données sont immuables. Avec le comptage de référence, la création d'un cycle de référence nécessite un changement déjà créé de données. Il semble que purement fonctionnelle des langues peut utiliser le comptage de référence sans vous soucier de la possibilité de cycles. Suis est de droite? Si oui, pourquoi n'ont-ils pas?

Je comprends que le comptage de référence est plus lente que la GC dans de nombreux cas, mais au moins il réduit les temps de pause. Il serait agréable d'avoir la possibilité d'utiliser le comptage de référence dans les cas où des temps de pause sont mauvais.

Answer 1

Par rapport à d'autres langages comme Java et C#, purement fonctionnelle langues allouer comme un fou. Ils ont également allouer des objets de différentes tailles. Le plus rapide stratégie de répartition est d'allouer d'espace libre contiguë (parfois appelé une "pépinière") et à la réserve d'un matériel inscrire à point pour le prochain espace libre disponible. L'Allocation dans le tas devient aussi rapide que l'allocation d'une pile.

Comptage de référence est fondamentalement incompatible avec cette stratégie de répartition. Ref comptage met des objets sur les listes libres et les enlève à nouveau. Ref comptage a aussi substantielle des frais généraux requis pour la mise à jour réf compte comme la création de nouveaux objets (qui, comme mentionné ci-dessus, fonctionnels purs langues comme des fous).

Comptage de référence tend à faire vraiment bien dans des situations comme celles-ci:

• Presque tous de segment de mémoire est utilisé pour organiser les objets vivants.
• L'Allocation et le pointeur de la cession sont rares par rapport à d'autres opérations.
• Les références peuvent être gérés sur un autre processeur ou de l'ordinateur.

Pour comprendre comment la meilleure de haute performance ref-systèmes de comptage de travail aujourd'hui, de rechercher le travail de David Bacon et Erez Petrank.

Answer 2

Votre question est basée sur une mauvaise hypothèse. Il est parfaitement possible d'avoir les références circulaires et des données immuables. Considérez les points suivants exemple en C# qui utilise des données immuables de créer une référence circulaire.

class Node { 
  public readonly Node other;
  public Node() { 
    other = new Node(this);
  }
  public Node(Node node) {
    other = node;
  }
}

Ce type de truc qui peut être fait dans de nombreux langages fonctionnels, et donc aucun mécanisme de collecte doit faire face à la possibilité de références circulaires. Je ne dis pas une ref mécanisme de comptage est impossible avec une référence circulaire, juste qu'elle doit être traitée.

Edit par ephemient

En réponse au commentaire... c'est trivial en Haskell

data Node a = Node { other :: Node a }
recursiveNode = Node { other = recursiveNode }

et à peine plus d'efforts dans le SML.

datatype 'a node = NODE of unit -> 'a node
val recursiveNode : unit node =
    let fun mkRecursiveNode () = NODE mkRecursiveNode
    in mkRecursiveNode () end

Aucune mutation nécessaire.

Answer 3

Il y a quelques choses, je pense.

• Il y sont des cycles: "let rec" dans de nombreuses langues ne permettent de "circulaire" créer des structures. En dehors de cela, l'immutabilité ne requièrent généralement pas de cycles, mais cela rompt la règle.
• Ref-chiffres sont mauvais pour les listes: je ne sais pas qui font référence à compté de la collection fonctionne bien avec, par exemple, longtemps liée individuellement-structures de liste que vous trouverez souvent dans FP (par exemple, lent, besoin de s'assurer de la queue-récursive, ...)
• D'autres stratégies ont des avantages: Comme vous faites allusion, les autres GC stratégies sont encore mieux à la localité de mémoire

(Une fois, je pense que j'ai peut-être vraiment "savait", mais maintenant, je suis en train d'essayer de se rappeler/spéculer, alors ne prenez pas cela comme une autorité quelconque.)

Answer 4

Considérer cette allégorie a dit à propos de David Lune, l'inventeur de la Machine Lisp:

Un jour, un étudiant est venu à la Lune et dit: "je comprends comment faire un meilleur garbage collector. Nous devons garder un nombre de références de la des pointeurs vers chaque contre."

Lune patiemment dit à l'étudiant l'histoire suivante:

"Un jour, un étudiant est venu à la Lune et dit:" je comprends comment faire un meilleur garbage collector...

Answer 5

Suis est de droite?

Pas tout à fait. Vous pouvez créer cyclique des structures de données à l'aide purement fonctionnelle programmation en définissant simplement mutuellement récursives valeurs en même temps. Par exemple, dans le cas d'OCaml:

let rec xs = 0::ys and ys = 1::xs

Toutefois, il est possible de définir les langues qui font qu'il est impossible de créer des structures cycliques de par sa conception. Le résultat est connu comme un unidirectionnelle tas , et son principal avantage est que la collecte des ordures peut être aussi simple que de comptage de référence.

Si oui, pourquoi n'ont-ils pas?

Certaines langues ne interdire les cycles et l'utilisation de comptage de référence. Erlang et Mathematica sont des exemples.

Par exemple, dans Mathematica, lorsque vous faites référence à une valeur de vous faire une copie afin de la mutation de l'original n'est pas muter la copie:

In[1] := xs = {1, 2, 3}
Out[1] = {1, 2, 3}

In[2] := ys = xs
Out[2] = {1, 2, 3}

In[3] := xs[[1]] = 5
Out[3] = 5

In[4] := xs
Out[4] = {5, 2, 3}

In[5] := ys
Out[5] = {1, 2, 3}