memory management - programacion - ¿Por qué los lenguajes puramente funcionales no usan el conteo de referencias?

recoleccion de basura en programacion

Question

En lenguajes puramente funcionales, los datos son inmutables. Con el recuento de referencias, la creación de un ciclo de referencia requiere cambiar los datos ya creados. Parece que los lenguajes puramente funcionales podrían usar el recuento de referencias sin preocuparse por la posibilidad de ciclos. ¿Estoy en lo cierto? Si es así, ¿por qué no?

Entiendo que el conteo de referencias es más lento que el GC en muchos casos, pero al menos reduce los tiempos de pausa. Sería bueno tener la opción de utilizar el recuento de referencias en los casos en que los tiempos de pausa son malos.

Answer 1

¿Estoy en lo cierto?

No exactamente. Puede crear estructuras de datos cíclicos usando programación puramente funcional simplemente definiendo valores mutuamente recursivos al mismo tiempo. Por ejemplo, en OCaml:

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

Sin embargo, es posible definir lenguajes que hacen imposible crear estructuras cíclicas por diseño. El resultado se conoce como un montón unidireccional y su principal ventaja es que la recolección de basura puede ser tan simple como el conteo de referencias.

Si es así, ¿por qué no?

Algunos idiomas prohiben los ciclos y usan el recuento de referencias. Erlang y Mathematica son ejemplos.

Por ejemplo, en Mathematica cuando haces referencia a un valor, haces una copia profunda del mismo para que la mutación del original no mute la copia:

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 2

Considere esta alegoría contada acerca de David Moon , un inventor de la Máquina Lisp :

Un día, un estudiante vino a Moon y dijo: "Entiendo cómo hacer un mejor recolector de basura. Debemos mantener un recuento de referencias de los indicadores para cada inconveniente".

Moon le dijo pacientemente al alumno la siguiente historia:

"Un día, un estudiante vino a Moon y dijo: ''Entiendo cómo hacer un mejor recolector de basura ...

Answer 3

El recuento de referencias es MUCHO más lento que el GC porque no es bueno para la CPU. Y la mayoría de las veces GC puede esperar tiempo de inactividad y también GC puede ser concurrente (en otro subproceso). Así que ese es el problema: GC es menos malvado y muchos intentos lo demuestran.

Answer 4

En relación con otros lenguajes administrados como Java y C #, los lenguajes puramente funcionales se asignan como locos . También asignan objetos de diferentes tamaños. La estrategia de asignación más rápida conocida es asignar desde el espacio libre contiguo (a veces llamado "guardería") y reservar un registro de hardware para apuntar al siguiente espacio libre disponible. La asignación del montón se vuelve tan rápido como la asignación de una pila.

El recuento de referencias es fundamentalmente incompatible con esta estrategia de asignación. Ref contar pone objetos en listas libres y los quita de nuevo. El recuento de reflectores también tiene importantes gastos generales necesarios para actualizar recuentos a medida que se crean nuevos objetos (que, como se señaló anteriormente, los lenguajes funcionales puros se vuelven locos).

El conteo de referencias tiende a funcionar muy bien en situaciones como estas:

• Casi toda la memoria del montón se utiliza para contener objetos en vivo.
• La asignación y la asignación del puntero son infrecuentes en relación con otras operaciones.
• Las referencias se pueden administrar en otro procesador o computadora.

Para comprender cómo funcionan los mejores sistemas de conteo de ref que funcionan hoy en día, consulte el trabajo de David Bacon y Erez Petrank .

Answer 5

Hay algunas cosas, creo.

• Hay ciclos : "let rec" en muchos idiomas permite crear estructuras "circulares". Aparte de esto, la inmutabilidad generalmente implica que no hay ciclos, pero esto rompe la regla.
• Los recuentos son malos en las listas : no sé si la colección contada por referencia funciona bien con, por ejemplo, las estructuras largas de listas individuales que a menudo se encuentran en FP (por ejemplo, lenta, necesidad de asegurar la cola recursiva, ...)
• Otras estrategias tienen beneficios : como usted alude, otras estrategias de GC son usualmente mejores para la localidad de memoria

(Érase una vez, creo que tal vez realmente ''sabía'' esto, pero ahora estoy tratando de recordar / especular, así que no lo tome como una autoridad).

Answer 6

Su pregunta se basa en una suposición errónea. Es perfectamente posible tener referencias circulares y datos inmutables. Considere el siguiente ejemplo de C # que usa datos inmutables para crear una referencia circular.

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

Este tipo de truco se puede hacer en muchos lenguajes funcionales y, por lo tanto, cualquier mecanismo de recolección debe abordar la posibilidad de referencias circulares. No estoy diciendo que un mecanismo de recuento de ref es imposible con una referencia circular, solo que debe tratarse.

Editar por ephemient

En respuesta al comentario ... esto es trivial en Haskell

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

y apenas más esfuerzo en SML.

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

No se requiere mutación.