haskell - videos - un día siendo recolector de basura

¿Haskell requiere un recolector de basura? (8)

Como ya han señalado otros, Haskell requiere administración de memoria dinámica y automática: la administración automática de la memoria es necesaria porque la administración manual de la memoria no es segura; La gestión dinámica de la memoria es necesaria porque, para algunos programas, la duración de un objeto solo puede determinarse 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 [1..1000] "borrar"; por lo tanto, el tiempo de vida de esto se debe determinar dinámicamente, y esta es la razón por la cual la gestión dinámica de la memoria es necesaria.

Por lo tanto, en este sentido, la asignación automática de memoria dinámica 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 de memoria dinámica automática de más alto rendimiento.

Sin embargo...

Aunque es necesario un recolector de basura, podríamos tratar de 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

podemos esperar que el compilador detecte que x2 puede ser desasignado con seguridad cuando devuelve f (en lugar de esperar a que el recolector de basura desasigne x2 ). Básicamente, estamos pidiendo que el compilador realice un análisis de escape para convertir las asignaciones en el montón recogido de basura a las asignaciones en la pila siempre que sea posible.

No es demasiado irrazonable pedir esto: el compilador jhc haskell hace esto, aunque GHC no lo hace. Simon Marlow says que el recolector de basura generacional de GHC hace que el análisis de escape sea innecesario.

jhc en realidad usa una forma sofisticada de análisis de escape conocida como inferencia regional . 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 x2 escapa de f (porque se devuelve en la tupla) y, por lo tanto, x2 debe asignarse en el montón recogido de basura. La inferencia de región, por otro lado, es capaz de detectar que x2 puede ser desasignado cuando g regresa; la idea aquí es que x2 debería asignarse en la región de g en lugar de en la región de f .

Más allá de Haskell

Si bien la inferencia regional es útil en ciertos casos como se discutió anteriormente, parece ser difícil conciliar de manera efectiva 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 estar tentado de asignar la lista [1..n] en la pila y desasignarla después de que f regrese, pero esto sería catastrófico: cambiaría f de usar memoria O (1) (bajo recolección de basura) a O (n ) memoria.

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

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

No puedo pensar en un caso donde GC sería necesario en un lenguaje puro. ¿Es solo una optimización para reducir la copia, o es realmente necesario?

Estoy buscando un código de ejemplo que se filtre si un GC no está presente.

GC es "imprescindible" en los lenguajes PF 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 la existencia porque la vinculación posterior crea estructuras abstrusas e inmanejables para la mente humana. Por supuesto, el backlinking es una bendición, porque copiar estructuras que lo usan es muy barato.

De todos modos, si no me crees, simplemente intenta implementar el lenguaje FP y verás que estoy en lo correcto.

EDITAR: lo olvidé. La pereza es INFIERNO sin GC. No me creas? Pruébelo sin GC, por ejemplo, C ++. Verás ... cosas

Haskell es un lenguaje de programación no estricto, pero la mayoría de las implementaciones usan call-by-need (pereza) para implementar no severidad. En call-by-need solo evalúa las cosas cuando se llega 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 sea reutilizado cuando sea necesario).

Entonces, si implementa su lenguaje de forma perezosa usando thunk, ha postergado todo razonamiento sobre la duración de los objetos hasta el último momento, que es el tiempo de ejecución. Como ahora no sabes nada sobre vidas, lo único que puedes hacer razonablemente es recolectar basura ...

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 cambian los valores anteriores, sino que crean valores nuevos y modificados basados en los anteriores. Como esto significa que el programa asigna y usa constantemente más memoria, una gran cantidad de valores se descartarán a medida que pase el tiempo.

Esta es la razón por la cual los programas de GHC tienden a tener cifras de asignación total tan altas (de gigabytes a terabytes): asignan constantemente memoria, y es solo gracias al GC eficiente que la reclaman antes de quedarse sin ella.

Si un idioma (cualquier idioma) le permite asignar objetos dinámicamente, existen tres formas prácticas de manejar la memoria:

El idioma solo puede permitirle asignar memoria en la pila o al inicio. Pero estas restricciones limitan severamente los tipos de cálculos que un programa puede realizar. (En la práctica. En teoría, puede emular las estructuras de datos dinámicas en (digamos) Fortran representándolas en una gran matriz. Es HORRIBLE ... y no es relevante para esta discusión).
El lenguaje puede proporcionar un mecanismo explícito de free o dispose . Pero esto depende del programador para hacerlo bien. Cualquier error en la administración del almacenamiento puede provocar una pérdida de memoria ... o algo peor.
El lenguaje (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 nunca reclamar 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 idioma no tiene la limitación de 1. y no hay una operación de desasignación manual de acuerdo con 2. Por lo tanto, para ser utilizable para cosas no triviales, una implementación de Haskell debe incluir un recolector de basura .

No puedo pensar en un caso donde GC sería 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 reclamar 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 (resultantes de un let rec por ejemplo) significa que un enfoque de recuento de referencia no funcionará para los objetos de montón.
Luego hay cierres de funciones ... que tampoco se pueden asignar en la pila porque tienen una vida que es (típicamente) independiente de ese marco de pila en el que se crearon.

Estoy buscando un código de ejemplo que se filtre si un GC no está presente.

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

Tomemos un ejemplo trivial. Dado este

f (x, y)

necesita asignar el par (x, y) algún lugar antes de llamar a f . ¿Cuándo puedes desasignar ese par? No tienes idea. No se puede desasignar cuando devuelve f , porque f podría haber puesto el par en una estructura de datos (por ejemplo, fp = [p] ), por lo que la duración del par podría tener que ser más larga que la vuelta desde f . Ahora, digamos que el par fue puesto en una lista, ¿puede quien se lleve la lista desasignar a la pareja? No, porque el par podría ser compartido (por ejemplo, let p = (x, y) in (fp, p) ). Entonces es realmente difícil saber cuándo se puede desasignar a la pareja.

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

Entonces me gustaría dar vuelta la pregunta. ¿Por qué crees que Haskell no necesita GC? ¿Cómo sugeriría que se hiciera una 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 del tipo. Entonces, si una función tiene el efecto secundario de imprimir algo, debe haber un IO en algún lugar de su tipo de devolución.

Pero hay una función que se usa implícitamente en todas partes en Haskell y cuya firma tipo no tiene en cuenta, lo que en cierto sentido es un efecto secundario. A saber, la función que copia algunos datos y le devuelve dos versiones. Bajo el capó esto puede funcionar ya sea literalmente, al duplicar los datos en la memoria, o "virtualmente" al aumentar 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 copiado. Desde el punto de vista de un programador en ese idioma, 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 aún permite copiar para tipos "no únicos".

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

Hay un sentido en el que los algoritmos cuánticos también son puramente lineales. Cada operación es reversible y, por lo tanto, no se pueden crear, copied 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 stack) que tienen operaciones DUP explícitas que dejan en claro cuándo ocurre la duplicación.

Otra forma (más abstracta) de pensar sobre esto es notar que Haskell se construye a partir del 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.

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 reclamar la memoria que ya no se necesita. En lenguajes impuros como C, puede declarar 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 de leer), por lo que no puede usar este enfoque en un lenguaje puro. Entonces, de alguna manera, se analiza de forma estática dónde se puede liberar la memoria (probablemente imposible en el caso general), se pierde la memoria como un tamiz (funciona muy bien hasta que se acaba), o se usa un GC.