¿Por qué las lenguas no puramente funcional utilizan el recuento de referencias?

StackOverflow https://stackoverflow.com/questions/791437

Pregunta

En los lenguajes puramente funcionales, los datos son inmutables. Con el recuento de referencias, creando un ciclo de referencia requiere cambiar los datos ya creadas. Parece que puramente lenguajes funcionales podrían utilizar el conteo de referencia sin tener que preocuparse por la posibilidad de ciclos. Am es correcto? Si es así, ¿por qué no lo hacen?

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

¿Fue útil?

Solución

Su pregunta se basa en una suposición errónea. Es perfectamente posible tener referencias circulares y datos inmutables. Considere el siguiente ejemplo C # que utiliza 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 de muchas lenguajes funcionales y por lo tanto cualquier mecanismo de recolección debe hacer frente a la posibilidad de referencias circulares. No estoy diciendo que un mecanismo de conteo ref es imposible con una referencia circular, sólo que debe ser tratado.

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 el SML. 

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

No se requiere la mutación.

Otros consejos

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

El conteo de referencias es fundamentalmente incompatible con esta estrategia de asignación. Ref conteo pone objetos en las listas libres y los lleva de nuevo. Ref conteo también tiene gastos sustanciales requeridos para la actualización de los recuentos árbitro medida que se crean nuevos objetos (que, como se señaló anteriormente, los lenguajes funcionales puros hacen como locos).

El conteo de referencias tiende a hacer muy bien en situaciones como las siguientes:

  • Casi toda la pila de memoria se utiliza para sostener objetos vivos.
  • Asignación y asignación de puntero son poco frecuentes en relación con otras operaciones.
  • Referencias pueden ser gestionados en otro procesador o un ordenador.

Para entender cómo los mejores sistemas de conteo de ref alto rendimiento en el trabajo actual, buscar el trabajo de David bacon y Erez Petrank .

Hay algunas cosas, creo.

  • No son ciclos : "dejar que rec" en muchos idiomas sí permite estructuras "circulares" que se creará. Aparte de esto, por lo general implica la inmutabilidad no hay ciclos, pero esto rompe la regla.
  • Ref recuentos son malos en las listas : No sé que la recolección de referencia contado funciona bien con, por ejemplo, larga estructuras a menudo se encuentran en FP de enlace simple-lista (por ejemplo, lento, necesitará asegurarse recursiva de cola, ...)
  • Otras estrategias tener beneficios : Como usted alude a otras estrategias de GC siguen siendo generalmente mejor para la localidad de memoria

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

esta alegoría habló de David luna , un inventor de la máquina Lisp :

  

Un día, un estudiante vino a Luna y dijo: "Yo entiendo cómo hacer un mejor recolector de basura Debemos mantener un contador de referencia de los punteros a cada uno de los contras."

     

Luna pacientemente le dijo al estudiante la siguiente historia:

     
    

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

  
  

Am es verdad?

No del todo. Se pueden crear estructuras cíclicas de datos utilizando la programación puramente funcional, simplemente mediante la definición de los valores mutuamente recursivas al mismo tiempo. Por ejemplo, en OCaml: 

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

Sin embargo, es posible definir lenguajes que hacen que sea 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 recuento de referencias.

  

Si es así, ¿por qué no lo hacen?

Algunos idiomas prohíben ciclos y utilizan el recuento de referencias. Erlang y Mathematica son ejemplos.

Por ejemplo, en Mathematica cuando hace referencia a un valor que haga una copia profunda de ella para mutar el original no mutar 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}

El conteo de referencias es mucho más lento que GC porque no es bueno para la CPU. Y GC mayor parte del tiempo podemos esperar a que el tiempo de inactividad y también GC puede ser concurrente (en otro hilo). Así que ese es el problema -. GC es menos mal y las porciones de intentos que se muestra

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top