ordenar - pattern matching haskell

¿Está todo en Haskell almacenado en trozos, incluso en valores simples? (5)

¿A qué se parecen los thunk para el siguiente valor / expresión / función en el montón de Haskell?

val = 5 -- is `val` a pointer to a box containing 5? add x y = x + y result = add 2 val main = print $ result

Sería bueno tener una idea de cómo están representados en Haskell, dado su modo de evaluación perezosa.

Respuesta oficial

No es asunto tuyo. Estrictamente el detalle de implementación de tu compilador.

Respuesta corta

Sí.

Respuesta más larga

Para el programa Haskell en sí, la respuesta siempre es sí, pero el compilador puede y hará las cosas de manera diferente si descubre que puede salirse con la suya, por razones de rendimiento.

Por ejemplo, para '''' ''agregar xy = x + y'' '''', un compilador puede generar código que funcione con thunks para xey y construya un thunk como resultado. Pero considera lo siguiente:

foo :: Int -> Int -> Int foo x y = x * x + y * y

Aquí, un compilador de optimización generará un código que primero saca a xey de sus casilleros, luego hace toda la aritmética y luego almacena el resultado en un recuadro.

Respuesta avanzada

Este documento describe cómo GHC pasó de una forma de implementar thunks a otra que en realidad era más simple y más rápida: http://research.microsoft.com/en-us/um/people/simonpj/papers/eval-apply/

Creo que los demás respondieron a su pregunta muy bien, pero solo para completar, permítanme agregar que GHC también le ofrece la posibilidad de usar valores no compartidos directamente. Esto es lo que Haskell Wiki dice al respecto :

Cuando realmente está desesperado por la velocidad, y quiere llegar hasta las "partes en bruto". Consulte GHC Primitives para obtener información sobre el uso de tipos sin caja.
Sin embargo, este debería ser el último recurso, ya que los tipos y primitivas no compartidas no son portátiles. Afortunadamente, generalmente no es necesario recurrir al uso de tipos y primitivas explícitamente desempacados, ya que el optimizador de GHC puede hacer el trabajo por usted mediante operaciones de línea que conoce, y unboxing los argumentos de funciones estrictas. Los campos de constructor estrictos y desempaquetados también pueden ayudar mucho. A veces, GHC necesita un poco de ayuda para generar el código correcto, por lo que es posible que tenga que mirar el resultado del Core para ver si sus ajustes realmente están teniendo el efecto deseado.
Una cosa que puede decirse del uso de tipos y primitivas no compartidas es que usted sabe que está escribiendo un código eficiente, en lugar de confiar en que el optimizador de GHC haga lo correcto, y estar a merced de los cambios en el optimizador de GHC. Esto bien puede ser importante para ti, en cuyo caso apúntate.

Como se mencionó, no es portátil, por lo que necesita una extensión de idioma GHC. Vea here sus documentos.

En general, incluso los valores primitivos en Haskell (por ejemplo, de tipo Int y Float) están representados por thunks. Esto es de hecho requerido por la semántica no estricta; considera el siguiente fragmento:

bottom :: Int bottom = div 1 0

Esta definición generará una excepción de div por cero solo si se inspecciona el valor de la parte inferior, pero no si el valor nunca se utiliza.

Considere ahora la función de agregar:

add :: Int -> Int -> Int add x y = x+y

Una implementación ingenua de add debe forzar el thunk para x, forzar el thunk durante y, agregar los valores y crear un thunk (evaluado) para el resultado. Esta es una gran sobrecarga para la aritmética en comparación con los lenguajes funcionales estrictos (por no mencionar los imperativos).

Sin embargo, un compilador de optimización como GHC puede evitar esta sobrecarga; esta es una vista simplificada de cómo GHC traduce la función de agregar:

add :: Int -> Int -> Int add (I# x) (I# y) = case# (x +# y) of z -> I# z

Internamente, los tipos básicos como Int se ven como tipos de datos con un único constructor. El tipo Int # es el tipo de máquina "en bruto" para enteros y + # es la adición primitiva en tipos sin procesar. Las operaciones en tipos crudos se implementan directamente en patrones de bits (por ejemplo, registros) --- no en absoluto. El boxeo y el desempaquetado se traducen como aplicación de constructor y coincidencia de patrones.

La ventaja de este enfoque (no visible en este ejemplo simple) es que el compilador a menudo es capaz de subrayar tales definiciones y eliminar operaciones intermedias de boxeo / unboxing, dejando solo las más externas.

Respuesta corta: Sí.

Respuesta larga:

val = 5

Esto tiene que almacenarse en un procesador de segundo plano, porque imaginen si escribimos esto en cualquier parte de nuestro código (como, en una biblioteca que importamos o algo así):

val = undefined

Si esto tiene que evaluarse cuando se inicia nuestro programa, se bloqueará, ¿verdad? Si realmente usamos ese valor para algo, eso sería lo que queremos, pero si no lo usamos, no debería poder influir en nuestro programa de manera catastrófica.

Para su segundo ejemplo, permítanme cambiarlo un poco:

div x y = x / y

Este valor también debe almacenarse en un procesador de segundo plano, porque imagina un código como este:

average list = if null list then 0 else div (sum list) (length list)

Si div fuera estricto aquí, sería evaluado incluso cuando la lista sea null (también conocida como vacía), lo que significa que escribir la función de esta manera no funcionaría, porque no tendría la posibilidad de devolver 0 cuando se le presente la lista vacía. , a pesar de que esto es lo que queremos en este caso.

Su último ejemplo es solo una variación del ejemplo 1, y tiene que ser flojo por las mismas razones.

Habiendo dicho todo esto, es posible forzar al compilador a hacer algunos valores estrictos, pero eso va más allá del alcance de esta pregunta.

Sería absolutamente correcto ajustar cada valor en un procesador. Pero como Haskell no es estricto, los compiladores pueden elegir cuándo evaluar los thunks / expresiones . En particular, los compiladores pueden elegir evaluar una expresión antes de lo estrictamente necesario, si resulta en un mejor código.

La optimización de los compiladores Haskell (GHC) realiza un análisis de Estricto para determinar qué valores se calcularán siempre.

Al principio, el compilador tiene que suponer que ninguno de los argumentos de una función se usa alguna vez. Luego revisa el cuerpo de la función e intenta encontrar funciones que 1) son estrictas en (al menos algunos de) sus argumentos y 2) siempre deben evaluarse para calcular el resultado de la función.

En su ejemplo, tenemos la función (+) que es estricta en ambos argumentos. Por lo tanto, el compilador sabe que tanto x como y siempre se requieren para ser evaluados en este punto. Ahora sucede que la expresión x+y siempre es necesaria para calcular el resultado de la función, por lo tanto, el compilador puede almacenar la información de que la función add es estricta tanto en x como en y .

El código generado para add * esperará valores enteros como parámetros y no como thunks. El algoritmo se vuelve mucho más complicado cuando se trata de recursión (un problema de punto fijo), pero la idea básica sigue siendo la misma.

Otro ejemplo:

mkList x y = if x then y : [] else []

Esta función tomará x en forma evaluada (como un booleano) e y como un thunk. La expresión x necesita ser evaluada en cada ruta de ejecución posible a través de mkList , por lo tanto, podemos hacer que la persona que llama lo evalúe. La expresión y , por otro lado, nunca se usa en ninguna aplicación de función que sea estricta en sus argumentos. La función cons : nunca mira y solo la almacena en una lista. Por lo tanto, debe pasar como un thunk para satisfacer la semántica de Haskell.

mkList False undefined -- absolutely legal

*: add es por supuesto polimórfico y el tipo exacto de y depende de la instanciación.