curiosidad sobre cómo se evalúa "loop = loop" en Haskell

Question

Pensé que expresiones como esta harían que Haskell evaluara para siempre. Pero los comportamientos tanto en GHCi como en el programa compilado me sorprendieron.

Por ejemplo, en GHCi, estas expresiones bloquearon hasta I Control+C, pero no consumieron CPU. Parecía que estaba durmiendo.

let loop = loop 
let loop = 1 + loop 

he intentado compilar estos programas con GHC:

main = print loop 
    where loop = 1 + loop 

main = print loop 
    where loop = if True then loop else 1 

Lo que se imprimió fue:

Main: <<loop>> 

Así que mi pregunta es: Es evidente que estas expresiones se compilan a algo diferente de bucles o llamadas recursivas en idiomas imperativos. ¿A qué están compilados? ¿Es esta una regla especial para manejar las funciones 0-arg que se encuentran en el lado derecho, o es un caso especial de algo más general que yo no sé?

[EDIT]:

Una pregunta más: Si esto resulta ser un manejo especial del compilador, ¿cuál es la razón de hacer esto cuando es imposible de comprobar todos los bucles infinitos? Los idiomas "familiares" no se preocupan por casos como while (true); o int f() { return f();}, ¿verdad?

Muchas gracias.

Answer 1

GHC implementa Haskell como una máquina de reducción de gráfico. Imagina tu programa como un gráfico con cada valor como un nodo, y líneas desde él a cada valor de que depende ese valor. Excepto que somos perezosos, así que realmente comienzas con un solo nodo, y para evaluar ese nodo, GHC tiene que "ingresarlo" y abrirlo a una función con argumentos. Luego reemplaza la llamada de función con el cuerpo de la función, e intenta reducirla lo suficiente como para ponerla en la forma normal de la cabeza, etc.

Lo anterior es muy manual y estoy seguro de que eludir algunos detalles necesarios en aras de la brevedad.

En cualquier caso, cuando GHC ingresa un valor, generalmente lo reemplaza con un agujero negro mientras se evalúa el nodo (o, dependiendo de su terminología, mientras se reduce el cierre) Esto tiene varios propósitos. Primero, conecta una posible fuga de espacio. Si el nodo hace referencia a un valor que no se usa en ninguna otra parte, el agujero negro permite que ese valor sea recolectado como basura incluso mientras el nodo está siendo evaluado. En segundo lugar, esto evita ciertos tipos de trabajo duplicado, ya que en un entorno de subprocesos múltiples, dos subprocesos pueden intentar ingresar el mismo valor. El agujero negro hará que el segundo hilo bloquee en lugar de evaluar el valor que ya se está evaluando. Finalmente, esto permite una forma limitada de detección de bucles, ya que si un hilo intenta volver a ingresar en su propio agujero negro, podemos lanzar una excepción.

Aquí hay un poco de una explicación más metafórica. Si tengo una serie de instrucciones que mueven una tortuga (en el logotipo) alrededor de la pantalla, no hay una sola forma de decir qué forma producirán, o si esa forma termina sin ejecutarlas. Pero si, al correrlos, noto que el camino de la tortuga se ha cruzado, puedo indicarle al usuario "¡Ajá !, la tortuga se ha cruzado en su camino". Así que sé que la tortuga ha alcanzado un punto en el que ha estado antes; si la ruta es un circuito mediante la evaluación de los nodos de un gráfico, eso nos indica que estamos en un bucle. Sin embargo, la tortuga también puede entrar, por ejemplo, en una espiral en expansión. Y nunca terminará, pero tampoco cruzará su camino anterior.

Por lo tanto, debido al uso de agujeros negros, por varias razones, tenemos alguna noción de una "ruta" marcada que ha seguido la evaluación. Y si el camino se cruza a sí mismo, podemos decir y lanzar una excepción. Sin embargo, hay un millón de formas en que las cosas divergen que no involucran el camino que se cruza a sí mismo. Y en esos casos, no podemos decir, y no lanzar una excepción.

Para detalles técnicos súper geek sobre la implementación actual de agujeros negros, vea la charla de Simon Marlow del Taller de Implementadores Haskell reciente, "Programar evaluación diferida en multinúcleo" en la parte inferior de http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2010.

Answer 2

En algunos casos, el compilador puede determinar que existe un bucle como parte de sus otros análisis de flujo de control, y en ese momento reemplaza el término de bucle con el código que arroja una excepción apropiada. Esto no se puede hacer en todos los casos, por supuesto, pero solo en algunos de los casos más obvios, donde cae naturalmente de otro trabajo que está haciendo el compilador.

cuanto a por qué Haskell encuentra con más frecuencia que otros idiomas:

• Estos casos no se producen en idiomas que son estrictamente tales como C. Estos bucles se producen específicamente cuando el cálculo de una variable flojo depende de su propio valor .
• Los lenguajes como C tienen una semántica muy específica en los bucles; es decir, qué orden hacer qué en. Como tales, se ven obligados a ejecutar realmente el ciclo. Sin embargo, Haskell define un valor especial _|_ ("la parte inferior"), que se utiliza para representar valores erróneos. Los valores que son estrictos en sí mismos, es decir, dependen de su propio valor para computar, son _|_. El resultado de la coincidencia de patrones en _|_ puede ser un bucle infinito o una excepción; su compilador está eligiendo el último aquí.
• El compilador Haskell está muy interesado en realizar un análisis de rigor, es decir, probar que cierta expresión depende de otras expresiones, para realizar ciertas optimizaciones. Este análisis de bucle cae naturalmente como un caso extremo en el analizador de rigor que debe manejarse de una manera u otra.