haskell - what - lazy programacion
¿Cuáles son los puntos de rigor de Haskell? (7)
Todos sabemos (o deberíamos saber) que Haskell es flojo por defecto. Nada se evalúa hasta que se debe evaluar. Entonces, ¿cuándo debe evaluarse algo? Hay puntos donde Haskell debe ser estricto. Yo llamo a estos "puntos de rigor", aunque este término en particular no es tan amplio como había pensado. Según yo:
La reducción (o evaluación) en Haskell solo ocurre en puntos de rigor.
Entonces la pregunta es: ¿cuáles son, precisamente , los puntos de rigor de Haskell? Mi intuición dice que los main patrones de seq / bang, la coincidencia de patrones y cualquier acción de IO realizada a través de main son los principales puntos de rigor, pero realmente no sé por qué lo sé.
(Además, si no se les llama "puntos de rigor", ¿cómo se llaman?)
Imagino que una buena respuesta incluirá alguna discusión sobre WHNF y demás. También me imagino que podría tocar el cálculo lambda.
Editar: pensamientos adicionales sobre esta pregunta.
Al reflexionar sobre esta cuestión, creo que sería más claro agregar algo a la definición de un punto de rigor. Los puntos de rigor pueden tener contextos variables y profundidad (o rigor) variable. Volviendo a mi definición de que "la reducción en Haskell solo ocurre en puntos de rigor", agreguemos a esta definición esta cláusula: "un punto de rigor solo se activa cuando se evalúa o reduce su contexto circundante".
Por lo tanto, permítanme intentar comenzar con el tipo de respuesta que quiero. main es un punto de rigor. Está especialmente designado como el principal punto de rigor de su contexto: el programa. Cuando se evalúa el programa (contexto de main), se activa el punto de rigor de main. La profundidad de Main es máxima: debe evaluarse por completo. Principal generalmente se compone de acciones IO, que también son puntos de rigor, cuyo contexto es main .
Ahora intenta: discutir seq y coincidencia de patrones en estos términos. Explicar los matices de la aplicación de la función: ¿cómo es estricto? ¿Cómo no es? ¿Qué hay de deepseq ? let y declaraciones de case ? unsafePerformIO ? Debug.Trace ? Definiciones de nivel superior? ¿Tipos de datos estrictos? Patrones de explosión? Etc. ¿Cuántos de estos elementos se pueden describir en términos de solo seq o coincidencia de patrones?
C tiene el concepto de puntos de secuencia , que son garantías para operaciones particulares que un operando se evaluará antes que el otro. Creo que ese es el concepto existente más cercano, pero el término de rigor de término esencialmente equivalente (o posiblemente punto de fuerza ) está más en línea con el pensamiento de Haskell.
En la práctica, Haskell no es un lenguaje puramente perezoso: por ejemplo, la coincidencia de patrones suele ser estricta (por lo que probar una coincidencia de patrones obliga a que la evaluación suceda al menos lo suficiente como para aceptar o rechazar la coincidencia).
...
Los programadores también pueden usar la primitiva
seqpara forzar a una expresión a evaluar independientemente de si alguna vez se usará el resultado.
$!se define en términos deseq.
¡Entonces estás pensando ! / $! y seq es esencialmente correcto, pero la coincidencia de patrones está sujeta a reglas más sutiles. Siempre puedes usar ~ para forzar la coincidencia de patrones perezosos, por supuesto. Un punto interesante de ese mismo artículo:
El analizador de rigor también busca casos en los que las expresiones secundarias siempre son requeridas por la expresión externa y las convierte en una evaluación entusiasta. Puede hacerlo porque la semántica (en términos de "fondo") no cambia.
Sigamos por el agujero del conejo y miremos los documentos para las optimizaciones realizadas por GHC:
El análisis de estricción es un proceso mediante el cual GHC intenta determinar, en tiempo de compilación, qué datos definitivamente ''siempre serán necesarios''. GHC puede construir código para simplemente calcular dicha información, en lugar del proceso normal (mayor sobrecarga) para almacenar el cálculo y ejecutarlo más tarde.
En otras palabras, el código estricto se puede generar en cualquier lugar como una optimización, porque la creación de thunk es innecesariamente costosa cuando los datos siempre serán necesarios (y / o solo se pueden usar una vez).
... no se puede realizar más evaluación sobre el valor; se dice que está en forma normal . Si estamos en alguno de los pasos intermedios, de modo que hemos realizado al menos alguna evaluación sobre un valor, está en forma normal de cabeza débil (WHNF). (También hay una ''forma normal de cabeza'', pero no se usa en Haskell.) Evaluar completamente algo en WHNF lo reduce a algo en forma normal ...
(Un término está en la forma normal de la cabeza si no hay beta-redex en la posición 1 cabeza. Una redex es una redexión de la cabeza si está precedida solo por abstractores lambda de no-redexos 2 ). Así que cuando comienzas a forzar un thunk, estás trabajando en WHNF; cuando ya no quedan más thunk para forzar, estás en forma normal. Otro punto interesante:
... si en algún momento necesitáramos, por ejemplo, imprimir z al usuario, tendríamos que evaluarlo por completo ...
Lo que naturalmente implica que, de hecho, cualquier acción de IO realizada desde la evaluación main fuerza, lo que debería ser obvio teniendo en cuenta que los programas de Haskell, de hecho, hacen cosas. Todo lo que necesite pasar por la secuencia definida en main debe estar en forma normal y, por lo tanto, está sujeto a una evaluación estricta.
Sin embargo, CA McCann lo entendió bien en los comentarios: lo único especial sobre main es que main se define como especial; la coincidencia de patrones en el constructor es suficiente para garantizar la secuencia impuesta por la mónada IO . En ese sentido, solo el seq y la coincidencia de patrones son fundamentales.
El compilador de Haskell de Glasgow traduce su código en un lenguaje Lambda similar a un cálculo llamado core . En este lenguaje, se evaluará algo, siempre que el patrón coincida con una declaración de case . Por lo tanto, si se llama a una función, se va a evaluar el constructor más externo y solo él (si no hay campos forzados). Cualquier otra cosa está enlatada en un thunk. (Los thunk son introducidos por let bindings).
Por supuesto, esto no es exactamente lo que sucede en el lenguaje real. El compilador convierte a Haskell en Core de una manera muy sofisticada, haciendo tantas cosas como posiblemente vagas y cualquier cosa que siempre se necesite vago. Además, hay valores y tuplas sin caja que son siempre estrictos.
Si intentas evaluar una función a mano, básicamente puedes pensar:
- Intenta evaluar el constructor más externo de la devolución.
- Si se necesita algo más para obtener el resultado (pero solo si realmente se necesita) también se evaluará. El orden no importa.
- En el caso de IO, debe evaluar los resultados de todas las declaraciones desde la primera hasta la última. Esto es un poco más complicado, ya que la mónada IO hace algunos trucos para forzar la evaluación en un orden específico.
Esta no es una respuesta completa que apunta al karma, sino solo una parte del rompecabezas: en la medida en que se trata de semántica, tenga en cuenta que existen múltiples estrategias de evaluación que proporcionan la misma semántica. Un buen ejemplo aquí, y el proyecto también habla de cómo pensamos normalmente en la semántica de Haskell, fue el proyecto Eager Haskell, que alteró radicalmente las estrategias de evaluación manteniendo la misma semántica: http://csg.csail.mit.edu/pubs/haskell.html
Haskell es AFAIK no un lenguaje perezoso puro, sino un lenguaje no estricto. Esto significa que no necesariamente evalúa los términos en el último momento posible.
Una buena fuente para el modelo de "pereza" de Haskell se puede encontrar aquí: http://en.wikibooks.org/wiki/Haskell/Lazadez
Básicamente, es importante entender la diferencia entre un thunk y el encabezado débil de la forma normal WHNF.
Según tengo entendido, haskell extrae los cálculos hacia atrás en comparación con los lenguajes imperativos. Lo que esto significa es que, en ausencia de patrones "seq" y bang, en última instancia, habrá algún tipo de efecto secundario que fuerce la evaluación de un thunk, lo que a su vez puede causar evaluaciones previas (verdadera lazyness).
Como esto llevaría a una fuga de espacio horrible, el compilador luego descubrirá cómo y cuándo evaluar los subprocesos antes de tiempo para ahorrar espacio. El programador puede entonces apoyar este proceso dando anotaciones de rigor (en.wikibooks.org/wiki/Haskell/Strictness, www.haskell.org/haskellwiki/Performance/Strictness) para reducir aún más el uso del espacio en forma de "thunks" anidados.
No soy un experto en la semántica operacional de haskell, así que simplemente dejaré el enlace como un recurso.
Algunos recursos más:
Lazy no significa no hacer nada. Cada vez que su patrón de programa coincide con una expresión de case , evalúa algo, lo suficiente como sea. De lo contrario, no puede averiguar qué RHS usar. ¿No ve ninguna expresión de caso en su código? No se preocupe, el compilador está traduciendo su código a una forma simplificada de Haskell, donde es difícil evitar su uso.
Para un principiante, una regla básica es let es flojo, el case es menos vago.
Probablemente volvería a plantear esta pregunta, ¿en qué circunstancias va a evaluar Haskell una expresión? (Tal vez virar en una "forma normal de cabeza débil")
Para una primera aproximación, podemos especificar esto de la siguiente manera:
- La ejecución de acciones IO evaluará cualquier expresión que "necesiten" (por lo que debe saber si la acción IO se ejecuta, por ejemplo, si su nombre es principal, o si se llama desde main Y necesita saber qué necesita la acción).
- Una expresión que se está evaluando (¡eh, esa es una definición recursiva!) Evaluará cualquier expresión que necesite.
Desde su lista intuitiva, las acciones principal e IO entran en la primera categoría, y la coincidencia de seq y patrones cae en la segunda categoría. Pero creo que la primera categoría está más en línea con su idea de "punto de rigor", porque de hecho es así como causamos que la evaluación en Haskell se convierta en efectos observables para los usuarios.
Dar todos los detalles específicamente es una gran tarea, ya que Haskell es un lenguaje extenso. También es bastante sutil, porque Concurrent Haskell puede evaluar las cosas de manera especulativa, aunque terminemos sin usar el resultado al final: esta es una tercera clase de cosas que causa evaluación. La segunda categoría está bastante bien estudiada: quiere ver el rigor de las funciones involucradas. También se puede pensar que la primera categoría es una especie de "rigor", aunque esto es un poco dudoso porque evaluate x y seq x $ return () realidad son cosas diferentes! Puede tratarlo adecuadamente si le da algún tipo de semántica a la mónada IO (pasar explícitamente un token RealWorld# funciona para casos simples), pero no sé si hay un nombre para este tipo de análisis de rigor estratificado en general.
Un buen lugar para comenzar es entendiendo este artículo: Una semántica natural para la evaluación diferida (Launchbury). Eso te dirá cuándo se evalúan las expresiones para un lenguaje pequeño similar al Core de GHC. Luego, la pregunta restante es cómo asignar Haskell completo a Core, y la mayor parte de esa traducción está dada por el informe Haskell mismo. En GHC llamamos a este proceso "desugaring", porque elimina el azúcar sintáctico.
Bueno, esa no es la historia completa, porque GHC incluye una gran cantidad de optimizaciones entre desugaring y generación de código, y muchas de estas transformaciones reorganizarán el Core para que las cosas se evalúen en diferentes momentos (el análisis de rigor en particular hará que las cosas sean evaluadas más temprano). Entonces, para comprender realmente cómo se evaluará su programa, debe ver el núcleo producido por GHC.
Quizás esta respuesta te parezca un poco abstracta (no mencioné específicamente los patrones de bang o seq), pero pediste algo preciso , y esto es lo mejor que podemos hacer.