¿Qué es la fusión en Haskell?
optimization ghc (1)
En general, la fusión se refiere a las transformaciones cuyo propósito es deshacerse de las estructuras de datos intermedios. Fusiona llamadas de funciones que resultan en asignaciones de memoria derrochadoras en algo más eficiente. Esto es en realidad IMO una de las aplicaciones más grandes de Haskell siendo puro. Y prácticamente no necesita hacer nada para obtenerlo, se trata de forma gratuita a través del compilador de GHC.
Haskell es puro
Como Haskell es puro, obtenemos esta cosa llamada transparencia referencial , que (del enlace) significa que "la expresión siempre evalúa el mismo resultado en cualquier contexto" 1 . Eso significa que puedo hacer manipulaciones de nivel de programa muy generales sin cambiar lo que el programa realmente generará. Por ejemplo, incluso sin saber qué son x , y , z y w , siempre sé que
((x ++ y) ++ z) ++ w
evaluará a la misma cosa que
x ++ (y ++ (z ++ w))
sin embargo, el segundo implicará en la práctica menos asignaciones de memoria (ya que x ++ y requiere la reasignación del prefijo completo de la lista de salida).
Reescribir las reglas
De hecho, hay un montón de este tipo de optimización que podemos hacer, y, como Haskell es puro, básicamente podemos simplemente mover expresiones completas (reemplazando x , y , z o w por listas reales o expresiones que evalúan a las listas en el ejemplo anterior no cambian nada). Esto se convierte en un proceso bastante mecánico.
Además, resulta que puedes obtener muchas equivalencias para funciones de orden superior (¡ Teoremas gratis! ). Por ejemplo,
map f (map g xs) = map (f . g) xs
no importa qué f , g y xs sean (los dos lados son semánticamente iguales). Sin embargo, mientras que los dos lados de esta ecuación producen el mismo valor de salida, el lado izquierdo siempre es peor en eficiencia: termina asignando espacio para un map g xs lista intermedio map g xs , que es inmediatamente desechado. Nos gustaría decirle al compilador que cada vez que encuentre algo como map f (map g xs) , reemplácelo con map (f . g) xs . Y, para GHC, eso es a través de reglas de reescritura :
{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}
Los f , g y xs se pueden comparar con cualquier expresión, no solo variables (por lo que algo como map (+1) (map (*2) ([1,2] ++ [3,4])) se transforma en map ((+1) . (*2)) ([1,2] ++ [3,4]) . ( No parece haber una buena manera de buscar reglas de reescritura , así que compilé una lista ) Este artículo explica la motivación y el funcionamiento de las reglas de reescritura de GHC.
Entonces, ¿cómo es que GHC optimiza el map ?
En realidad, no del todo. Lo de arriba es la fusión de atajo . El nombre del tipo implica el inconveniente: no se escala demasiado bien y es molesto depurar. Usted termina teniendo que escribir una tonelada de reglas ad hoc para todos los arreglos de las mismas funciones comunes. Entonces, esperas que la aplicación repetida de las reglas de reescritura simplifique tus expresiones muy bien.
Resulta que podemos hacerlo incluso mejor en algunos casos organizando nuestras reglas de re-escritura para que construyamos alguna forma normal intermedia y luego tengamos reglas que se dirijan a esa forma intermedia. De esta manera, comenzamos a obtener rutas "calientes" de reglas de reescritura.
Probablemente el más avanzado de estos sistemas es la fusión de secuencias que apuntan a secuencias coinductivas (básicamente secuencias perezosas como listas). Vea esta tesis y este documento (que en realidad es más o menos cómo se implementa el paquete de vector ). Por ejemplo, en el vector , su código se transforma primero en una forma intermedia que involucra a Stream y Bundle s, se optimiza en esa forma y luego se transforma de nuevo en vectores.
Y ... ¿ Data.Text ?
Data.Text utiliza fusión de flujo para minimizar el número de asignaciones de memoria que se producen (creo que esto es especialmente importante para la variante estricta). Si revisas la fuente , verás que las funciones "sujetas a fusión" realmente manipulan Stream s en su mayor parte (son de la forma general unstream . (stuff manipulating stream) . stream ) y hay un montón de RULES pragmas para transformar Stream s. Al final, se supone que cualquier combinación de estas funciones se fusionará para que solo se produzca una asignación.
Entonces, ¿qué debo llevar para mi codificación diaria?
La única manera real de saber cuándo su código está sujeto a fusión es tener una buena comprensión de las reglas de reescritura involucradas y comprender bien cómo funciona GHC. Dicho eso, hay una cosa que debes hacer: tratar de usar funciones de orden superior no recursivas cuando sea posible, ya que estas pueden (al menos por ahora, pero en general siempre se fusionarán más fácilmente).
Complicaciones
Debido a que la fusión en Haskell ocurre mediante la aplicación repetida de reglas de reescritura, basta con convencerse de la corrección de cada regla de reescritura para saber que todo el programa "fusionado" hace lo mismo que su programa original. Excepto que hay casos extremos relacionados con la terminación de programas. Por ejemplo, uno podría pensar que
reverse (reverse xs) = xs
pero eso claramente no es cierto, ya que head $ reverse (reverse [1..]) no terminará pero head [1..] will. Más información de Haskell Wiki .
1 Esto es realmente verdadero solo a condición de que en estos contextos la expresión mantenga el mismo tipo.
De vez en cuando he notado lo siguiente en la documentación de Haskell: (por ejemplo, en Data.Text ):
Sujeto a fusión
¿Qué es fusión y cómo la uso?