¿Haskell requiere un recolector de basura?

Tengo curiosidad por saber por qué las implementaciones de Haskell usan un GC.

No puedo pensar en un caso en el que GC sea necesario en un lenguaje puro. ¿Es solo una optimización para reducir el copiado o es realmente necesario?

Estoy buscando un código de ejemplo que se filtraría si no estuviera presente un GC.

Como ya han señalado otros, Haskell requiere una gestión automática y dinámica de la memoria: la gestión automática de la memoria es necesaria porque la gestión manual de la memoria no es segura; La administración de memoria dinámica es necesaria porque para algunos programas, la vida útil de un objeto solo se puede determinar en tiempo de ejecución.

Por ejemplo, considere el siguiente programa:

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

En este programa, la lista [1..1000]debe mantenerse en la memoria hasta que el usuario escriba "borrar"; por lo que la vida útil de esto debe determinarse dinámicamente, y es por eso que la administración dinámica de la memoria es necesaria.

Entonces, en este sentido, la asignación de memoria dinámica automatizada es necesaria, y en la práctica esto significa: sí , Haskell requiere un recolector de basura, ya que la recolección de basura es el administrador automático de memoria dinámica de mayor rendimiento.

Sin embargo...

Aunque es necesario un recolector de basura, podríamos intentar encontrar algunos casos especiales en los que el compilador pueda usar un esquema de administración de memoria más económico que la recolección de basura. Por ejemplo, dado

f :: Integer -> Integer
f x = let x2 = x*x in x2*x2

podríamos esperar que el compilador detecte que x2se puede desasignar de forma segura cuando fregrese (en lugar de esperar a que el recolector de basura desasigne x2). Básicamente, le pedimos al compilador que realice un análisis de escape para convertir las asignaciones en un montón de basura recolectada en asignaciones en la pila siempre que sea posible.

No es descabellado pedirlo: el compilador jhc haskell hace esto, aunque GHC no. Simon Marlow dice que el recolector de basura generacional de GHC hace que el análisis de escape sea casi innecesario.

jhc en realidad utiliza una forma sofisticada de análisis de escape conocida como inferencia de región . Considerar

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

En este caso, un análisis de escape simplista concluiría que x2escapa de f(porque se devuelve en la tupla) y, por x2lo tanto, debe asignarse en el montón de recolección de basura. La inferencia de región, por otro lado, es capaz de detectar que x2se puede desasignar cuando gregresa; la idea aquí es que x2debería asignarse en gla región ' en lugar de fla región'.

Más allá de Haskell

Si bien la inferencia de región es útil en ciertos casos como se discutió anteriormente, parece ser difícil conciliar efectivamente con la evaluación perezosa (ver los comentarios de Edward Kmett y Simon Peyton Jones ). Por ejemplo, considere

f :: Integer -> Integer
f n = product [1..n]

Uno podría tener la tentación de asignar la lista [1..n]en la pila y desasignarla después de los fretornos, pero esto sería catastrófico: cambiaría fde usar memoria O (1) (bajo recolección de basura) a memoria O (n).

Se realizó un trabajo extenso en la década de 1990 y principios de la de 2000 en la inferencia de regiones para el lenguaje funcional estricto ML. Mads Tofte, Lars Birkedal, Martin Elsman, Niels Hallenberg han escrito una retrospectiva bastante legible sobre su trabajo sobre inferencia de regiones, gran parte del cual integraron en el compilador MLKit . Experimentaron con la administración de memoria puramente basada en regiones (es decir, sin recolector de basura), así como con la administración de memoria híbrida basada en regiones / recolectada de basura, e informaron que sus programas de prueba se ejecutaban "entre 10 veces más rápido y 4 veces más lento" que la basura pura. versiones recopiladas.

Tomemos un ejemplo trivial. Dado este

f (x, y)

debe asignar el par en (x, y)algún lugar antes de llamar f. ¿Cuándo puede desasignar ese par? No tienes idea. No se puede desasignar cuando fregresa, porque fpodría haber colocado el par en una estructura de datos (por ejemplo, f p = [p]), por lo que la vida útil del par podría tener que ser más larga que la del regreso f. Ahora, digamos que el par se puso en una lista, ¿quien separe la lista puede desasignar el par? No, porque el par podría compartirse (p let p = (x, y) in (f p, p). Ej., ). Por lo que es muy difícil saber cuándo se puede desasignar el par.

Lo mismo ocurre con casi todas las asignaciones en Haskell. Dicho esto, es posible tener un análisis (análisis de región) que proporcione un límite superior en la vida útil. Esto funciona razonablemente bien en lenguajes estrictos, pero menos en lenguajes perezosos (los lenguajes perezosos tienden a hacer muchas más mutaciones que los lenguajes estrictos en la implementación).

Así que me gustaría darle la vuelta a la pregunta. ¿Por qué crees que Haskell no necesita GC? ¿Cómo sugeriría que se haga la asignación de memoria?

Tu intuición de que esto tiene algo que ver con la pureza tiene algo de verdad.

Haskell se considera puro en parte porque los efectos secundarios de las funciones se tienen en cuenta en la firma de tipo. Entonces, si una función tiene el efecto secundario de imprimir algo, debe haber un IOen algún lugar de su tipo de retorno.

Pero hay una función que se usa implícitamente en todas partes en Haskell y cuya firma de tipo no tiene en cuenta lo que, en cierto sentido, es un efecto secundario. Es decir, la función que copia algunos datos y le devuelve dos versiones. Bajo el capó, esto puede funcionar literalmente, duplicando los datos en la memoria, o "virtualmente" aumentando una deuda que debe pagarse más tarde.

Es posible diseñar lenguajes con sistemas de tipos aún más restrictivos (puramente "lineales") que no permiten la función de copia. Desde el punto de vista de un programador en tal lenguaje, Haskell parece un poco impuro.

De hecho, Clean , un pariente de Haskell, tiene tipos lineales (más estrictamente: únicos), y eso puede dar una idea de cómo sería no permitir la copia. Pero Clean todavía permite copiar para tipos "no únicos".

Hay mucha investigación en esta área y si busca en Google lo suficiente, encontrará ejemplos de código lineal puro que no requiere recolección de basura. Encontrará todo tipo de sistemas de tipos que pueden indicar al compilador qué memoria se podría usar, lo que permite que el compilador elimine parte del GC.

En cierto sentido, los algoritmos cuánticos también son puramente lineales. Cada operación es reversible, por lo que no se pueden crear, copiar ni destruir datos. (También son lineales en el sentido matemático habitual).

También es interesante comparar con Forth (u otros lenguajes basados ​​en pilas) que tienen operaciones DUP explícitas que dejan en claro cuándo se está produciendo la duplicación.

Otra forma (más abstracta) de pensar sobre esto es notar que Haskell se construye a partir de un cálculo lambda simplemente tipado que se basa en la teoría de categorías cerradas cartesianas y que tales categorías vienen equipadas con una función diagonal diag :: X -> (X, X). Un lenguaje basado en otra clase de categoría podría no tener tal cosa.

Pero en general, la programación puramente lineal es demasiado difícil para ser útil, por lo que nos conformamos con GC.

Las técnicas de implementación estándar aplicadas a Haskell en realidad requieren un GC más que la mayoría de los otros lenguajes, ya que nunca mutan los valores anteriores, sino que crean valores nuevos y modificados basados ​​en los anteriores. Dado que esto significa que el programa asigna constantemente y utiliza más memoria, una gran cantidad de valores se descartarán a medida que pase el tiempo.

Esta es la razón por la que los programas GHC tienden a tener cifras de asignación total tan altas (de gigabytes a terabytes): están asignando memoria constantemente, y solo gracias a la GC eficiente la recuperan antes de agotarse.

Si un idioma (cualquier idioma) le permite asignar objetos de forma dinámica, existen tres formas prácticas de abordar la gestión de la memoria:

1. El idioma solo puede permitirle asignar memoria en la pila o al inicio. Pero estas restricciones limitan severamente los tipos de cálculos que puede realizar un programa. (En la práctica. En teoría, puede emular estructuras de datos dinámicas en (digamos) Fortran representándolas en una gran matriz. Es HORRIBLE ... y no es relevante para esta discusión).

2. El lenguaje puede proporcionar una explícita freeo disposemecanismo. Pero esto depende del programador para hacerlo bien. Cualquier error en la gestión del almacenamiento puede provocar una pérdida de memoria ... o algo peor.

3. El idioma (o más estrictamente, la implementación del idioma) puede proporcionar un administrador de almacenamiento automático para el almacenamiento asignado dinámicamente; es decir, alguna forma de recolector de basura.

La única otra opción es no recuperar nunca el almacenamiento asignado dinámicamente. Esta no es una solución práctica, excepto para pequeños programas que realizan pequeños cálculos.

Al aplicar esto a Haskell, el lenguaje no tiene la limitación de 1., y no hay una operación de desasignación manual según 2. Por lo tanto, para que sea utilizable para cosas no triviales, una implementación de Haskell debe incluir un recolector de basura. .

No puedo pensar en un caso en el que GC sea necesario en un lenguaje puro.

Presumiblemente te refieres a un lenguaje funcional puro.

La respuesta es que se requiere un GC bajo el capó para recuperar los objetos de montón que el lenguaje DEBE crear. Por ejemplo.

• Una función pura necesita crear objetos de montón porque en algunos casos tiene que devolverlos. Eso significa que no se pueden asignar en la pila.

• El hecho de que pueda haber ciclos (como resultado de, let recpor ejemplo) significa que un enfoque de recuento de referencias no funcionará para objetos de montón.

• Luego están los cierres de funciones ... que tampoco se pueden asignar en la pila porque tienen una vida útil que es (normalmente) independiente del marco de la pila en el que se crearon.

Estoy buscando un código de ejemplo que se filtraría si no estuviera presente un GC.

Casi cualquier ejemplo que involucre cierres o estructuras de datos en forma de gráfico se filtraría en esas condiciones.

Un recolector de basura nunca es necesario, siempre que tenga suficiente memoria. Sin embargo, en realidad, no tenemos memoria infinita, por lo que necesitamos algún método para recuperar la memoria que ya no se necesita. En lenguajes impuros como C, puede indicar explícitamente que ha terminado con algo de memoria para liberarlo, pero esta es una operación de mutación (la memoria que acaba de liberar ya no es segura para leer), por lo que no puede usar este enfoque en un lenguaje puro. Entonces, de alguna manera, es analizar estáticamente dónde puede liberar la memoria (probablemente imposible en el caso general), perder memoria como un tamiz (funciona muy bien hasta que se agota) o usar un GC.

GC es "imprescindible" en lenguajes FP puros. ¿Por qué? ¡Las operaciones alloc y free son impuras! Y la segunda razón es que las estructuras de datos recursivas inmutables necesitan GC para existir porque el backlinking crea estructuras abstrusas e imposibles de mantener para la mente humana. Por supuesto, el backlinking es una bendición, porque copiar las estructuras que lo usan es muy barato.

De todos modos, si no me cree, intente implementar el lenguaje FP y verá que tengo razón.

EDITAR: Lo olvidé. La pereza es el INFIERNO sin GC. ¿No me crees? Pruébelo sin GC en, por ejemplo, C ++. Verás ... cosas

Haskell es un lenguaje de programación no estricto, pero la mayoría de las implementaciones usan llamada por necesidad (pereza) para implementar la no estricción. En la llamada por necesidad, solo evalúa cosas cuando se alcanza durante el tiempo de ejecución utilizando la maquinaria de "thunks" (expresiones que esperan ser evaluadas y luego se sobrescriben, permaneciendo visibles para que su valor se reutilice cuando sea necesario).

Entonces, si implementa su lenguaje de manera perezosa usando thunks, ha pospuesto todo razonamiento sobre la vida útil de los objetos hasta el último momento, que es el tiempo de ejecución. Dado que ahora no sabe nada sobre vidas, lo único que puede hacer razonablemente es recolectar basura ...