haskell - por - tipos de evaluacion

Estrategia de evaluación

Question

¿Cómo debería uno razonar acerca de la evaluación de funciones en ejemplos como los siguientes en Haskell:

let f x = ...
    x = ...
in map (g (f x)) xs

En GHC, a veces (fx) se evalúa solo una vez, y otras veces para cada elemento en xs , dependiendo de qué son exactamente f y g . Esto puede ser importante cuando fx es un cálculo costoso. Acabo de hacer tropezar a un principiante de Haskell al que estaba ayudando y no sabía qué decirle, aparte de que todo depende del compilador. ¿Hay alguna historia mejor?

Actualizar

En el siguiente ejemplo (fx) será evaluado 4 veces:

let f x = trace "!" $ zip x x
    x = "abc"
in map (/i -> lookup i (f x)) "abcd" 

Answer 1

Con las extensiones de lenguaje, podemos crear situaciones donde fx debe ser evaluado repetidamente:

{-# LANGUAGE GADTs, Rank2Types #-}
module MultiEvG where

data BI where
    B :: (Bounded b, Integral b) => b -> BI

foo :: [BI] -> [Integer]
foo xs = let f :: (Integral c, Bounded c) => c -> c
             f x = maxBound - x
             g :: (forall a. (Integral a, Bounded a) => a) -> BI -> Integer
             g m (B y) = toInteger (m + y)
             x :: (Integral i) => i
             x = 3
         in map (g (f x)) xs

El quid es tener fx polimórfico incluso como el argumento de g , y debemos crear una situación en la que no se pueda predecir el tipo (s) en el que se necesita (mi primera puñalada usó un Either ab lugar de BI , pero cuando optimizando, eso por supuesto llevó a solo dos evaluaciones de fx como máximo).

Una expresión polimórfica se debe evaluar al menos una vez para cada tipo en que se usa. Esa es una de las razones de la restricción de monomorfismo. Sin embargo, cuando el rango de tipos en los que se puede necesitar está restringido, es posible memorizar los valores en cada tipo, y en algunas circunstancias GHC hace eso (necesita optimización, y espero que la cantidad de tipos involucrados no sea demasiado) grande). Aquí lo confrontamos con lo que es básicamente una lista no homogénea, por lo que en cada invocación de g (fx) , puede ser necesaria en un tipo arbitrario que satisfaga las restricciones, por lo que el cálculo no puede levantarse fuera del map (técnicamente, el compilador aún podría cree un caché de los valores en cada tipo utilizado, de modo que se evalúe solo una vez por tipo, pero GHC no, con toda probabilidad no valdría la pena).

• Las expresiones monomórficas solo necesitan evaluarse una vez, se pueden compartir. Si están o no depende de la implementación; Por pureza, no cambia la semántica del programa. Si la expresión está vinculada a un nombre, en la práctica puede confiar en que se comparta, ya que es fácil y obviamente lo que quiere el programador. Si no está vinculado a un nombre, es una cuestión de optimización. Con el generador de código de bytes o sin optimizaciones, la expresión a menudo se evaluará repetidamente, pero con optimizaciones, la evaluación repetida indicaría un error de compilación.
• Las expresiones polimórficas se deben evaluar al menos una vez para cada tipo en el que se usan, pero con optimizaciones, cuando GHC puede ver que se pueden usar varias veces en el mismo tipo, (por lo general) todavía se compartirá para ese tipo durante una computación más grande.

En pocas palabras: compile siempre con optimizaciones, ayude al compilador mediante el enlace de las expresiones que desea compartir con un nombre, y dé firmas de tipo monomórfico siempre que sea posible.

Answer 2

En GHC sin optimizaciones, el cuerpo de una función se evalúa cada vez que se llama a la función. (Una "llamada" significa que la función se aplica a los argumentos y el resultado se evalúa). En el siguiente ejemplo, fx está dentro de una función, por lo que se ejecutará cada vez que se llame a la función. (GHC puede optimizar esta expresión como se explica en las preguntas frecuentes [1].)

let f x = trace "!" $ zip x x
    x = "abc"
in map (/i -> lookup i (f x)) "abcd" 

Sin embargo, si sacamos fx de la función, se ejecutará solo una vez.

let f x = trace "!" $ zip x x
    x = "abc"
in map ((/f_x i -> lookup i f_x) (f x)) "abcd" 

Esto puede ser reescrito más fácilmente como

let f x = trace "!" $ zip x x
    x = "abc"
    g f_x i = lookup i f_x
in map (g (f x)) "abcd" 

La regla general es que, cada vez que se aplica una función a un argumento, se crea una nueva "copia" del cuerpo de la función. La aplicación de función es lo único que puede hacer que una expresión se vuelva a ejecutar. Sin embargo, tenga en cuenta que algunas funciones y llamadas a funciones no se parecen a las funciones sintácticamente.

[1] http://www.haskell.org/haskellwiki/GHC/FAQ#Subexpression_Elimination

Answer 3

Esto depende realmente de las optimizaciones de GHC, como usted ha podido decir.

Lo mejor que puedes hacer es estudiar el núcleo de GHC que obtienes después de optimizar el programa. Miraría el Core generado y examinaría si fx tenía su propia declaración de let fuera del map o no.

Si desea estar seguro, entonces debe factorizar fx en su propia variable asignada en un let , pero realmente no hay una forma garantizada de averiguarlo más que leer a través de Core.

Dicho todo esto, con la excepción de elementos como el trace que utiliza unsafePerformIO , esto nunca cambiará la semántica de su programa: cómo se comporta realmente.

Answer 4

Tus ejemplos son bastante diferentes.

En el primer ejemplo, el argumento a mapear es g (fx) y se pasa una vez para map muy probablemente como función parcialmente aplicada. Si g (fx) , cuando se aplica a un argumento dentro del map evalúa su primer argumento, entonces esto se hará solo una vez y luego el procesador (fx) se actualizará con el resultado.

Por lo tanto, en su primer ejemplo, fx se evaluará como máximo 1 vez.

Su segundo ejemplo requiere un análisis más profundo antes de que el compilador pueda llegar a la conclusión de que (fx) siempre es constante en la expresión lambda. Tal vez nunca lo optimizará en absoluto, porque puede tener conocimiento de que el rastreo no es muy kosher . Por lo tanto, esto se puede evaluar 4 veces cuando se realiza el seguimiento y 4 veces o 1 vez cuando no se realiza el seguimiento.