Por que não puramente linguagens funcionais usar contagem de referência?

Question

Em linguagens puramente funcionais, os dados é imutável. Com a contagem de referência, criando um ciclo de referência requer a alteração de dados já criados. Parece que puramente linguagens funcionais poderia usar contagem de referência sem se preocupar com a possibilidade de ciclos. Am é certo? Se assim for, por que não?

Eu entendo que a contagem de referência é mais lento do GC, em muitos casos, mas pelo menos reduz os tempos de pausa. Seria bom ter a opção de contagem de referência utilização nos casos em que os tempos de pausa são ruins.

Answer 1

A sua questão é baseada em uma falsa verdade. É perfeitamente possível ter referências circulares e dados imutáveis. Considere o seguinte exemplo C # que utiliza dados imutáveis ??para criar uma referência circular.

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

Este tipo de truque pode ser feito de várias linguagens funcionais e, portanto, qualquer mecanismo de recolha tem de lidar com a possibilidade de referências circulares. Não estou dizendo que um mecanismo ref contagem é impossível com uma referência circular, apenas que ele deve ser tratado.

Editar por ephemient

Em resposta ao comentário ... este é trivial em Haskell

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

e mal qualquer um maior esforço no SML.

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

No mutação necessário.

Answer 2

Em relação a outros idiomas gerenciados como Java e C #, linguagens puramente funcionais alocar como um louco . Eles também alocar objetos de diferentes tamanhos. A estratégia de alocação de mais rápido conhecido é alocar a partir do espaço livre contíguo (às vezes chamado de "viveiro") e reservar um registo hardware para apontar para o próximo espaço livre disponível. Alocação da pilha torna-se tão rápido quanto a alocação de uma pilha.

Contagem de referência é fundamentalmente incompatível com esta estratégia de alocação. puts contagem Ref objetos em listas livres e leva-los novamente. contagem Ref também tem despesas gerais substanciais necessários para atualizar a contagem ref como novos objetos são criados (que, como mencionado acima, as linguagens funcionais puras fazer como um louco).

Contagem de referência tende a fazer muito bem em situações como estas:

• Quase toda a memória heap é usado para armazenar objetos vivos.
• reserva e atribuição de ponteiro são pouco frequentes em relação a outras operações.
• As referências podem ser gerenciados em outro processador ou computador.

Para entender como o melhor sistemas de alto desempenho ref de contagem de trabalho hoje, olhar para cima o trabalho de David Bacon e Erez Petrank .

Answer 3

Existem algumas coisas, eu acho.

• Não são ciclos : "vamos rec" em muitas línguas não permite estruturas "circular" a ser criado. Além disso, a imutabilidade que geralmente implicam nenhum ciclo, mas isso quebra a regra.
• Ref contagens são ruins em listas : Eu não sei que a coleta contou-referência funciona bem com por exemplo, longa estruturas muitas vezes você encontrar em FP isoladamente-linked-list (por exemplo lento, necessidade de garantir cauda-recursivo, ...)
• Outras estratégias têm benefícios : Como você aludem a, outras estratégias de GC ainda são geralmente melhor para localidade memória

(Era uma vez eu acho que talvez realmente 'sabia' isso, mas agora eu estou tentando lembrar / especular, portanto, não tome isso como qualquer autoridade.)

Answer 4

essa alegoria contou sobre David lua , um inventor do Lisp Máquina :

Um dia um estudante veio a Lua e disse: "Eu entendo como fazer um coletor de lixo melhor Devemos manter uma contagem de referência dos ponteiros a cada contras."

Moon pacientemente disse o estudante a seguinte história:

"Um dia um estudante veio a Lua e disse: 'Eu entendo como fazer um lixo melhor coletor ...

Answer 5

Am é certo?

Não é bem assim. É possível criar estruturas de dados cíclicos utilizando a programação puramente funcional simplesmente definindo valores mutuamente-recursiva ao mesmo tempo. Por exemplo, em OCaml:

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

No entanto, é possível definir idiomas que tornam impossível criar estruturas cíclicas por design. O resultado é conhecido como um unidirecional pilha e sua principal vantagem é que a coleta de lixo pode ser tão simples como a contagem de referência.

Se assim for, por que não?

Algumas línguas fazer proibir ciclos e contagem de referência utilização. Erlang e Mathematica são exemplos.

Por exemplo, em Mathematica quando você faz referência um valor de fazer uma cópia profunda do mesmo modo mutação do original não sofrer mutações a cópia:

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}

Answer 6

contagem

Referência é muito mais lento do que o GC, porque não é bom para a CPU. E GC na maioria das vezes pode esperar que o tempo ocioso e também GC pode ser concomitante (em outro segmento). Então, esse é o problema - GC é menos mal e muitas tentativas mostraram que

.