Acumuladores en haskell - haskell, cola-recursión

En Haskell, si escribo.

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

y compílalo con GHC, ¿el resultado será diferente al que usé?

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

Yo podría hacer fácilmente fac n = product [1..n] y evitar todo el asunto, pero estoy interesado enCómo funciona un intento de recursión de cola en un lenguaje perezoso. Entiendo que todavía puedo obtener un desbordamiento de pila porque se están acumulando Thunks, pero ¿sucede algo realmente diferente (en términos del programa compilado resultante) cuando uso un acumulador que cuando simplemente declaro la recursión ingenua? ¿Hay algún beneficio en dejar de lado la recursión de la cola que no sea una mejor legibilidad? ¿Cambia la respuesta en absoluto si estoy usando? runhaskell ¿Para ejecutar el cálculo en lugar de compilarlo primero?

Respuestas

Recursion de cola hace tiene sentido en (GHC) Haskell si su acumulador es estricto. Para demostrar el problema, aquí hay un "rastro" de su 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

El nivel de sangrado corresponde (aproximadamente) anivel de pila Tenga en cuenta que el acumulador solo se evalúa al final y eso puede causar un desbordamiento de pila. El truco, por supuesto, es hacer que el acumulador sea estricto. Teóricamente es posible demostrar que facRec es estricto si se llama en un contexto estricto, pero no conozco ningún compilador que haga eso, ATM. GHC hace Sin embargo, la optimización de llamadas de cola, por lo que la facRec Las llamadas utilizan un espacio de pila constante.

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

Respecto a tu segunda parte, runhaskell/runghc es solo una envoltura sobre GHCi. Si GHCi encuentra el código compilado, lo utilizará; de lo contrario, usará el intérprete de código de bytes que realiza algunas optimizaciones, por lo que no espere que se realicen optimizaciones extravagantes.

En haskell, solo ayuda escribir su programa de forma recursiva en la cola si su acumulador es estricto y necesita un resultado completo.

Con ghc "s runHaskell el programa ganó" t beoptimizado, por lo que no habrá un análisis de rigor, por lo que puede apilar el desbordamiento; 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 manera es inspeccionar el núcleo de la red generada. Una buena publicación en el blog de Don Stewart explica las cosas. . Muchas de sus publicaciones en el blog son interesantes si te interesa el rendimiento, por cierto.

Tu pregunta no está completa. Supongo que te refieres a GHC, y al menos sin optimizaciones, la respuesta es "sí" porque la función de trabajo (facRec en el primero o fac en el segundo) tiene una aridad 2 comparada con una y el ensamblaje reflejará esto. Con optimizaciones o con JHC, la respuesta es probablemente "no".