¿Por qué la función "no hacer nada" de Haskell, id, consume toneladas de memoria?

112

Haskell tiene una función de identidad que devuelve la entrada sin cambios. La definición es simple:

id :: a -> a
id x = x

Entonces, para divertirse, esto debería generar 8:

f = id id id id id id id id id id id id id id id id id id id id id id id id id id id
main = print $ f 8

Después de unos segundos (y aproximadamente 2 gb de memoria según el Administrador de tareas), la compilación falla con ghc: out of memory. Del mismo modo, dice el intérprete ghci: out of memory.

Dado que ides una función bastante simple, no esperaría que sea una carga de memoria en tiempo de ejecución o tiempo de compilación. ¿Para qué se utiliza toda la memoria?

haskell ghc Ryan
fuente
11
Quieres componer esos ids. En VIM, con el cursor en la definición de f, hacer esto: :s/id id/id . id ./g.
Tobias Brandt

Respuestas:

135

Sabemos el tipo de id,

id :: a -> a

Y cuando nos especializamos en esto id id, la copia izquierda de idtiene el tipo:

id :: (a -> a) -> (a -> a)

Y luego, cuando usted se especializa esto de nuevo para el extremo izquierdo iden id id id, se obtiene:

id :: ((a -> a) -> (a -> a)) -> ((a -> a) -> (a -> a))

Para que vea cada uno idque agrega, la firma de tipo del extremo izquierdo ides dos veces más grande.

Tenga en cuenta que los tipos se eliminan durante la compilación, por lo que esto solo ocupará memoria en GHC. No ocupará memoria en su programa.

Dietrich Epp
fuente
Recuerdo que Okasaki tuvo un problema similar cuando escribió una calculadora RPN incrustada en Haskell.
partir
3
La pregunta, tal vez, es si GHC debería encontrar una manera de manejar este tipo de cosas con más gracia. En particular, el tipo es muy grande cuando está escrito en su totalidad, pero hay una enorme cantidad de duplicación. ¿Podría usarse el uso compartido para comprimir tales cosas? ¿Existe una forma eficaz de procesarlos?
partir
5
@dfeuer Intente preguntar por el tipo en ghci. Verá por la velocidad de la respuesta que debe estar compartiendo adecuadamente. Sospecho que este intercambio se pierde, por razones obvias, una vez que se traduce a otra representación intermedia (por ejemplo, núcleo).
Daniel Wagner
4
Esto significa que si idse repite nveces, el espacio de su tipo es proporcional a 2^n. El tipo inferido en el código de Ryan necesitaría 2^27referencias a su variable de tipo además de la otra estructura necesaria para representar el tipo, que probablemente sea mucho más grande de lo que esperaría que fueran la mayoría de los tipos.
David
58
Hacer inferencia de tipo ingenuamente es doble exponencial, al usar inteligentemente el uso compartido en las expresiones de tipo, puede reducirlo a exponencial. Pero no importa lo que hagas, habrá algunas expresiones bastante simples que harán explotar el verificador de tipos. Afortunadamente, estos no ocurren en la programación práctica.
2014