Acumuladores en Haskell

en Haskell, si escriboAcumuladores en Haskell

fac n = facRec n 1 
    where facRec 0 acc = acc 
     facRec n acc = facRec (n-1) (acc*n)

y compilarlo con GHC, el resultado será diferente que si usara

fac 0 = 1 
fac n = n * fac (n-1)

que fácilmente podría hacer fac n = product [1..n] y evitar la Todo, pero estoy interesado en cómo funciona un intento de recursividad de cola en un lenguaje perezoso. Entiendo que todavía puedo tener un desbordamiento de la pila debido a que los thunk se están acumulando, pero ¿algo realmente sucede de manera diferente (en términos del programa compilado resultante) cuando uso un acumulador que cuando digo la recursividad ingenua? ¿Hay algún beneficio en dejar de lado la recursividad de la cola que no sea una legibilidad mejorada? ¿La respuesta cambia si uso runhaskell para ejecutar el cálculo en lugar de compilarlo primero?

Fuente

2010-11-26 Inaimathi

¿Cuál es su definición de "algo realmente sucede de manera diferente"? La respuesta trivial es "sí", porque "son diferentes", uno es recursivo de cola y el otro no. Pero no creo que sea eso lo que estás preguntando ... – lijie

¿no quieres decir facRec n acc = facRec (n-1) (acc * n) ???? –

@lijie - Principalmente estoy interesado en si GHC optimiza las llamadas finales (con o sin el acumulador), pero lo dejé en general porque honestamente no estoy seguro de cómo la recursividad de cola interactúa con los lenguajes perezosos, y puede hacer otras cosas diferentes cosas basadas en mi uso de una forma frente a otra. No sé cuáles son esas otras cosas. – Inaimathi

recursividad de cola hace tiene sentido en (GHC) Haskell si su acumulador es estricto. Para demostrar el problema, aquí hay una "huella" de la definición recursiva de cola de fac:

fac 4 
~> facRec 4 1 
~> facRec 3 (1*4) 
~> facRec 2 ((1*4)*3) 
~> facRec 1 (((1*4)*3)*2) 
~> facRec 0 ((((1*4)*3)*2)*1) 
~> (((1*4)*3)*2) * 1 
    ~> ((1*4)*3) * 2 
    ~> (1*4) * 3 
     ~> 1*4 
    ~> 4 * 3 
    ~> 12 * 2 
~> 24 * 1 
~> 24

Los corresponde nivel de sangrado (más o menos) en la pantalla normal. Tenga en cuenta que el acumulador solo se evalúa al final y puede causar un desbordamiento de la pila. El truco, por supuesto, es hacer que el acumulador sea estricto. Teóricamente es posible mostrar que facRec es estricto si se llama en un contexto estricto, pero no conozco ningún compilador que lo haga, ATM. GHC hace hacer la optimización de llamada de cola, sin embargo, por lo que las llamadas facRec usar espacio de pila constante.

Por la misma razón, generalmente se prefiere foldl' a foldl, ya que el primero es estricto en el acumulador.

En cuanto a su segunda parte, runhaskell/runghc es sólo un envoltorio sobre GHCi. Si GHCi encuentra el código compilado, lo usará, de lo contrario utilizará el intérprete de códigos de bytes que realiza pocas optimizaciones, por lo que no espere que ocurran optimizaciones sofisticadas.

Fuente

2010-11-26 14:54:37 nominolo

La sugerencia de 'foldl'' vs' fold' ayudó, creo; http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27. En otras palabras, si quisiera recurrencia de cola en el sentido que estoy acostumbrado de Scheme, tendría que decir algo como 'let acc '= acc * n en seq acc' $ facRec (n-1) acc'' en lugar de 'facRec (n-1) (acc * n)' en la última línea de 'facRec'. – Inaimathi

@Inaimathi: Sí; o, más simplemente, puede escribir 'fracRec (n-1) $! acc * n', donde '$!' es simplemente aplicación de función estricta ('f $! x = x \' seq \ 'f x'). –

La forma más fácil de agregar rigor es usar '{- # LANGUAGE BangPatterns # -}'. Entonces tienes coincidencias de patrones estrictas. Por ejemplo, 'let! X = ... in ...' o directamente en la definición de la función: 'facRec 0! N = ...' – nominolo

Su pregunta no es completa. Supongo que te refieres GHC, y al menos sin optimizaciones la respuesta es "sí", porque la función del trabajador (facRec en la primera o en la segunda fac) tiene una aridad 2 en comparación con uno y el conjunto reflejará esto. Con optimizaciones o con JHC la respuesta es probablemente "no".

Fuente

2010-11-26 03:54:26

Lo siento, sí, estoy hablando del GHC; enmendó la pregunta. – Inaimathi

en Haskell, que sólo ayuda a escribir el programa de una manera recursiva de cola si su acumulador es estricta y hay que resultado conjunto.

Con runHaskell de GHC el programa no será optimizado, por lo que no será un análisis de rigor, por lo que puede desbordamiento de pila; mientras que si compila con optimizaciones, el compilador puede detectar que el acumulador debe ser estricto y optimizar en consecuencia.

Para ver cómo suceden las cosas de manera diferente (o no) la mejor forma de hacerlo es inspeccionar el langage core generado, a good blog post from Don Stewart explains things. Muchas de las publicaciones de su blog son interesantes si está interesado en el rendimiento, por cierto.

Fuente

2010-11-26 10:55:08

Voy a tener que marcar eso. +1 – Inaimathi

También facRec probablemente debería estar en una cláusula where en lugar de una declaración de nivel superior. Esta es una transformación de envoltura de trabajador y es más probable que se note por el analizador de rigidez. –

@stephen - corregido en la pregunta. – Inaimathi

Respuesta

Cuestiones relacionadas