Definición de función Haskell y matrices de almacenamiento en caché

Question

Tengo una pregunta acerca de cómo implementar el almacenamiento en caché (memoialización) usando matrices en Haskell. El siguiente patrón funciona:

f = (fA !) 
    where fA = listArray... 

Pero esto no lo hace (la velocidad del programa sugiere que la matriz se está recreada cada llamada o algo así):

f n = (fA ! n) 
    where fA = listArray... 

Definición fA exterior de una cláusula where (en "alcance global") también funciona con cualquiera de los patrones.

Tenía la esperanza de que alguien pudiera indicarme una explicación técnica de cuál es la diferencia entre los dos patrones anteriores.

Tenga en cuenta que estoy usando el último GHC, y no estoy seguro de si esto es solo una peculiaridad del compilador o parte del lenguaje en sí.

EDIT:! se utiliza para el acceso a la matriz, entonces fA! 5 significa fA [5] en sintaxis de C++. Mi comprensión de Haskell es que (fA!) N sería lo mismo que (fA! N) ... también hubiera sido más convencional para mí haber escrito "f n = fA! N" (sin los paréntesis). De todos modos, obtengo el mismo comportamiento sin importar cómo hago entre paréntesis.

Answer 1

La mejor manera de encontrar lo que está sucediendo es decirle al compilador que muestre su representación intermedia con -v4. El resultado es voluminoso y un poco difícil de leer, pero debería permitirle saber exactamente cuál es la diferencia en el código generado y cómo llegó el compilador allí.

Probablemente notará que fA se está moviendo fuera de la función (al "alcance global") en su primer ejemplo. En su segundo ejemplo, probablemente no lo es (lo que significa que se recreará en cada llamada).

Una posible razón para que no se mueva fuera de la función sería porque el compilador cree que depende del valor de n. En su ejemplo de trabajo, no hay n para fA de los que depender.

Pero la razón por la que creo que el compilador está evitando mover fA afuera en su segundo ejemplo es porque está tratando de evitar una fuga de espacio. Considere lo que sucedería si fA, en lugar de su matriz, fuera una lista infinita (en la que utilizó el operador !!). Imagine que lo llamó una vez con un número grande (por ejemplo, f 10000) y luego solo lo llamó con números pequeños (f 2, f 3, f 12 ...). Los 10000 elementos de la llamada anterior todavía están en la memoria, desperdiciando espacio. Entonces, para evitar esto, el compilador crea fA nuevamente cada vez que llame a su función.

La fuga de espacio probablemente no suceda en su primer ejemplo porque en ese caso f solo se llama una vez, devolviendo un cierre (estamos ahora en la frontera de los mundos imperativos y funcionales puros, para que las cosas se pongan un poco más sutil). Este cierre sustituye a la función original, que nunca volverá a llamarse, por lo que fA solo se llama una vez (y, por lo tanto, el optimizador puede moverlo libremente fuera de la función). En su segundo ejemplo, f no se reemplaza por un cierre (ya que su valor depende del argumento) y, por lo tanto, se volverá a llamar.

Si quiere saber más de esto (lo que ayudará a leer la salida -v4), puede echar un vistazo al documento Spineless Tagless G-Machine (citeseer link).

En cuanto a su pregunta final, creo que es una peculiaridad del compilador (pero podría estar equivocado). Sin embargo, no me sorprendería si todos los compiladores hicieran lo mismo, incluso si no fuera parte del lenguaje.

Answer 2

La diferencia de comportamiento no está especificada por el estándar Haskell. Todo lo que tiene que decir es que las funciones son las mismas (dará como resultado el mismo resultado con la misma entrada).

Sin embargo, en este caso hay una manera simple de predecir el rendimiento de tiempo y memoria que la mayoría de los compiladores cumplen. Insisto en que esto no es esencial, solo que la mayoría de los compiladores lo hacen.

Primera reescribir sus dos ejemplos como expresiones lambda puros, la ampliación de la sección:

f = let fA = listArray ... in \n -> fA ! n 
f' = \n -> let fA = listArray ... in fA ! n 

compiladores usar le permiten vinculante para indicar compartir. La garantía es que en un entorno dado (conjunto de variables locales, cuerpo lambda, algo así), el lado derecho de un enlace let sin parámetros se evaluará a lo sumo una vez. El entorno de fA en el primero es el programa completo, ya que no está bajo ninguna lambda, pero el entorno de este último es más pequeño ya que está bajo una lambda.

Lo que esto significa es que en el último, fA puede evaluarse una vez por cada n diferente, mientras que en el primero esto está prohibido.

Podemos ver este patrón, en efecto, incluso con funciones multi argumento:

g x y = (a ! y) where a = [ x^y' | y' <- [0..] ] 
g' x = (\y -> a ! y) where a = [ x^y' | y' <- [0..] ] 

Luego, en:

let k = g 2 in k 100 + k 100 

Podríamos calcular 2^100 más de una vez, pero en:

let k = g' 2 in k 100 + k 100 

Solo lo calcularemos una vez.

Si está trabajando con memoria, recomiendo datacommandators en Hackage, que es una biblioteca de tablas memo de diferentes formas, por lo que no tiene que rodar la suya.

Answer 3

Genial, gracias por sus respuestas que ayudaron mucho, y definitivamente revisaré los memocombinators de datos en Hackage. Viniendo de un entorno pesado en C++, he estado luchando por comprender exactamente lo que hará Haskell (principalmente en términos de complejidad) con un programa determinado, que los tutoriales no parecen tener.