2012-03-11 12 views
27

Me he dado cuenta de que GHC manual dice "para una función de recitación automática, el interruptor de lazo solo puede ser la función en sí misma, por lo que siempre se ignora un pragma EN LÍNEA".¿Puede GHC realmente nunca alinear mapa, escanear, plegar, etc.?

¿No se dicen todas las aplicaciones de construcciones funcionales recursivas comunes como map, zip, scan*, fold*, sum, etc., pueden no ser inline?

Siempre podría volver a escribir todas estas funciones cuando las emplee, agregue las etiquetas de rigurosidad adecuadas, o tal vez emplee técnicas sofisticadas como la "fusión de secuencias" recomendada here.

Sin embargo, ¿no todo esto limita drásticamente nuestra capacidad para escribir código que sea simultáneamente rápido y elegante?

Respuesta

51

De hecho, GHC no puede en este momento funciones recursivas en línea. Sin embargo:

  • GHC todavía especializar las funciones recursivas. Por ejemplo, dada

    fac :: (Eq a, Num a) => a -> a 
    fac 0 = 1 
    fac n = n * fac (n-1) 
    
    f :: Int -> Int 
    f x = 1 + fac x 
    

    GHC se dará cuenta de que fac se utiliza en tipo Int -> Int y generar una versión especializada de fac para ese tipo, que utiliza aritmética de enteros rápido.

    Esta especialización se realiza automáticamente dentro de un módulo (por ejemplo, si fac y f se definen en el mismo módulo). Para especialización-módulo de cruz (por ejemplo, si f y fac se definen en diferentes módulos), marcar la función a-ser especializado-con an INLINABLE pragma:

    {-# INLINABLE faC#-} 
    fac :: (Eq a, Num a) => a -> a 
    ... 
    
  • Hay transformaciones manuales que hacen funciones no recursiva. La técnica de menor potencia es static argument transformation, que se aplica a las funciones recursivas con argumentos que no cambian en las llamadas recursivas (por ejemplo, muchas funciones de orden superior como map, filter, fold*). Mediante esta transformación,

    map f []  = [] 
    map f (x:xs) = f x : map f xs 
    

    en

    map f xs0 = go xs0 
        where 
        go []  = [] 
        go (x:xs) = f x : go xs 
    

    de manera que una llamada como

    g :: [Int] -> [Int] 
    g xs = map (2*) xs 
    

    tendrá map entre líneas y convertirse en

    g [] = [] 
    g (x:xs) = 2*x : g xs 
    

    este Transformati se ha aplicado a funciones de Preludio como foldr y foldl.

  • Las técnicas de fusión también hacen que muchas funciones no sean recursivas, y son más poderosas que la transformación de argumento estático. El enfoque principal para las listas, que está integrado en el Preludio, es shortcut fusion. El enfoque básico es escribir tantas funciones como sea posible como funciones no recursivas que usan foldr y/o build; entonces toda la recursividad se captura en foldr, y hay REGLAS especiales para tratar con foldr.

    Tomando ventaja de esta fusión es en principio fácil: evitar la recursión manual, prefiriendo funciones de biblioteca tales como foldr, map, filter, y cualquier función en this list.En particular, escribir código en este estilo produce un código que es "simultáneamente rápido y elegante".

  • Las bibliotecas modernas como text y vector usan stream fusion detrás de escena. Don Stewart escribió un par de publicaciones en el blog (1, 2) demostrando esto en acción en la ahora obsoleta biblioteca uvector, pero los mismos principios se aplican al texto y al vector.

    Al igual que con la fusión de atajos, aprovechar la fusión de flujo en texto y vector es, en principio, fácil: evite la recursión manual, prefiriendo funciones de biblioteca que han sido marcadas como "sujetas a fusión".

  • Se está trabajando en la mejora de GHC para admitir la creación de funciones recursivas. Esto cae bajo el título general de supercompilation, y el trabajo reciente en este parece haber sido dirigido por Max Bolingbroke y Neil Mitchell.

+2

He editado en los enlaces por usted y votado en alza. ¡Gran respuesta! – ehird

+1

Ahh, maravilloso, esto pinta una imagen mucho más clara, ¡gracias! –

+0

Quizás quiso decir 'g (x: xs) = 2 * x: g xs'? – pat

2

Para una función recursiva, el interruptor de lazo solo puede ser la función en sí misma, por lo que siempre se ignora un pragma INLINE.

Si algo es recursivo, para alinearlo, debería saber cuántas veces se ejecuta en tiempo de compilación. Teniendo en cuenta que será una entrada de longitud variable, eso no es posible.

Sin embargo, ¿no todo esto limita drásticamente nuestra capacidad para escribir código que sea a la vez rápido y elegante?

Sin embargo, existen ciertas técnicas que pueden hacer llamadas recursivas mucho, mucho más rápido que en su situación normal. Por ejemplo, optimización de la cola de llamada SOWiki

+0

Imagine Tengo código como 'let {a = map f (cycle foo); b = escaneo g 0 a; c = zipCon h a b; d = takeWhile (> = 0) b} in (fst $ last $ zip c d, maximum d) '. Idealmente, deberíamos reescribir esto para que se convierta en un simple bucle o recursión de cola usando solo unos pocos registros, uno para el último valor de 'a',' b', 'c',' d', el máximo actual de ' d', y un índice en 'foo', pero eso destruirá la expresividad. No puedo ver cómo se evita este conflicto sin delimitar todo el ciclo que resulta de una repetición de cola. –

8

En resumen, no tan a menudo como se podría pensar. La razón es que las "técnicas sofisticadas" como la fusión de secuencias se emplean cuando se implementan las bibliotecas, y los usuarios de la biblioteca no tienen que preocuparse por ellas.

Considere Data.List.map. El paquete de base define map como

map :: (a -> b) -> [a] -> [b] 
map _ []  = [] 
map f (x:xs) = f x : map f xs 

Este map es auto-recursivo, por lo GHC no inline ella.

Sin embargo, base define también los siguientes reglas de reescritura:

{-# RULES 
"map"  [~1] forall f xs. map f xs    = build (\c n -> foldr (mapFB c f) n xs) 
"mapList" [1] forall f.  foldr (mapFB (:) f) [] = map f 
"mapFB"  forall c f g.  mapFB (mapFB c f) g  = mapFB c (f.g) 
    #-} 

Esto reemplaza usos de map través foldr/build fusion, entonces, si la función no se puede fusionar, lo reemplaza con el original map. Debido a que la fusión ocurre automáticamente, no depende de que el usuario lo sepa.

Como prueba de que todo esto funciona, puede examinar lo que GHC produce para entradas específicas. Para esta función:

proc1 = sum . take 10 . map (+1) . map (*2) 

eval1 = proc1 [1..5] 
eval2 = proc1 [1..] 

cuando se compila con -O2, GHC fusiona todos proc1 en una sola forma recursiva (como se ve en la salida de núcleo con -ddump-simpl).

Por supuesto que estas técnicas tienen sus límites.Por ejemplo, la función de promedio ingenuo, mean xs = sum xs/length xs, se puede transformar fácilmente manualmente en un solo pliegue, y frameworks exist that can do so automatically, sin embargo, en la actualidad no hay forma conocida de traducir automáticamente entre las funciones estándar y el marco de fusión. Entonces, en este caso, el usuario debe ser consciente de las limitaciones del código producido por el compilador.

Por lo tanto, en muchos casos los compiladores son lo suficientemente avanzados para crear código que es rápido y elegante. Sabiendo cuándo lo harán, y cuándo es probable que el compilador se caiga, en mi humilde opinión, una gran parte de aprender a escribir un código Haskell eficiente.

Cuestiones relacionadas