loops - you - curioso sobre cómo se evalúa "loop=loop" en Haskell

syntax haskell

Question

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

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

let loop = loop
let loop = 1 + loop

Intenté 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>>

Entonces mi pregunta es: Obviamente, estas expresiones están compiladas en algo diferente a los bucles o llamadas recursivas en lenguajes 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é?

[EDITAR]:

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

Muchas gracias.

Answer 1

En algunos, casos limitados, el compilador puede determinar que tal bucle existe como parte de sus otros análisis de flujo de control, y en ese momento reemplaza el término de bucle con 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.

En cuanto a por qué Haskell encuentra esto más a menudo que otros idiomas:

• Estos casos no ocurren en lenguajes estrictos como C. Estos bucles ocurren específicamente cuando el cálculo de una variable perezosa depende de su propio valor.
• Los lenguajes como C tienen una semántica muy específica en bucles; es decir, qué orden hacer qué en. Como tales, se ven obligados a ejecutar realmente el ciclo. Haskell, sin embargo, define un valor especial _|_ ("el fondo"), que se usa 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 de 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.

Answer 2

GHC implementa Haskell como una máquina de reducción de gráficos. 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 entrar 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.

Entonces, debido al uso de agujeros negros, por varias razones, tenemos alguna noción de un "camino" marcado 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 obtener detalles técnicos super-geek sobre la implementación actual de los agujeros negros, vea la charla de Simon Marlow del Taller de Implementadores Haskell reciente, "Programar la evaluación lenta en multinúcleo" en la parte inferior de http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2010 .