¿Cómo unir la teoría y la implementación de los bucles while?

8

Estoy trabajando en mi propio lenguaje de programación con fines educativos, y me he encontrado con un pequeño problema. Hay algunas soluciones diferentes para ello, pero todas parecen poco elegantes, y por lo que entiendo, innecesarias. Pero leyendo los libros que tengo y las búsquedas en Google, no puedo encontrar la solución elegante.

Entonces, el problema es que estoy construyendo el cálculo básico de lambda tal como lo entiendo. He definido verdadero / falso como términos de abstracción. Puedo combinar estos con funciones para hacer tipo de comportamiento if / then / else. El problema viene con los bucles. Puedo definir un ciclo while básico a través de la recursión, pero en la práctica, eso causa un desbordamiento de la pila. Según tengo entendido, la solución habitual sería realizar la Optimización de llamadas de cola, pero no veo cómo puedo hacerlo: los condicionales se definen en el lenguaje. Debido a eso, el compilador no sabe que el cuerpo del ciclo while está en posición de cola.

El libro del dragón se centra en implementar el bucle suponiendo que haya etiquetas y gotos. Ciertamente podría hacer eso. Parece que otros lenguajes que no incorporan construcciones en bucle al menos incorporan condicionales y luego hacen TCO. Y ciertamente podría hacer eso también. Pero entiendo que mientras pueda aplicar abstracciones y realizar reducciones, los bucles (y todo lo demás) deberían poder construirse a partir de esos bloques básicos.

Entonces, ¿qué me estoy perdiendo? ¿O es este uno de esos casos en los que "puede modelar cualquier cosa una vez que tenga X e Y" no es lo mismo que "puede modelar cualquier cosa una vez que tenga X e Y en una computadora real" y las incorporaciones son necesarias para la práctica propósitos?

Telastyn
fuente
Creo que respondiste tu propia pregunta en ese último párrafo. Solo porque la teoría dice que puedes hacer algo no significa que sea práctico hacerlo.
svick
1
Muchos idiomas tienen condicionales y recursividad e implementan la optimización de llamadas de cola. Busca más allá del libro del dragón.
Dave Clarke
Déjame aclarar esto: estás empezando de puro λ-¿cálculo? Es decir, no tiene nada más queλ's y abstracciones?
Andrej Bauer
svick: claro, pero como aprendiz, no puedo decir si ese es el caso aquí o si ignoro algo. Dave Clarke: muchos lenguajes han incorporado condicionales e implementan la optimización de llamadas de cola. He hecho búsquedas y no dieron ningún resultado en el lenguaje condicional y TCO. Si tiene una referencia que he pasado por alto ... Andrej Bauer, no del todo, pero lo suficientemente cerca. Sin tipos incorporados, sin funciones incorporadas. Puede declarar funciones y aplicar funciones. Profundizar en mi situación particular sería una pregunta de mala calidad.
Telastyn
1
@Raphael El uso del cálculo lambda como lenguaje intermedio fue una gran cosa en los años setenta y ochenta. Creo que la intención era detectar optimizaciones semánticas. Mi comprensión (tenga en cuenta que no soy un experto en técnicas de compilación) es que las optimizaciones semánticas son realmente difíciles, mientras que las optimizaciones locales pueden pagar mucho y son más fáciles de ver en un idioma con asignaciones de registro y uso moderado de goto. No obstante, las ideas del cálculo lambda son relevantes para el diseño del compilador, por ejemplo, la idea de asignación única y el concepto de continuación.
Gilles 'SO- deja de ser malvado'

Respuestas:

5

Así que logré resolver este problema hoy. El código para mi bucle while:

while (condition: ~>bool) (body: ~>void) => void {
    if condition { 
        body; 
        while condition body; 
    };
}

Cuando voy a construir esto en CIL (un tiempo de ejecución basado en pila, importante para el psuedocode, no es importante para la respuesta) se ve así:

ldarg 0
<build closure from { body; while condition body; }>
call if

Lo importante que me faltaba es que en el whilecódigo, el condicional era la cosa en posición de cola. Desde la perspectiva del compilador, el bloque y la función while son dos funciones separadas, con dos "colas" separadas. Cada uno de ellos se evalúa fácilmente para la posición de la cola, lo que hace que la optimización sea viable a pesar de la falta de condicionales incorporados.

Telastyn
fuente
5

Creo que te estás perdiendo la noción de continuación . Aunque su compilador puede no confiar en esa noción, como diseñador de compiladores con un lenguaje funcional como fuente o lenguaje intermedio (o destino), es importante comprender esa noción y tener esto en cuenta.

La continuación de un fragmento de código describe hacia dónde sale el código. En términos imperativos, representa no solo la ubicación a la que salta o cae el código, sino también el estado del programa (pila y montón) en ese punto. En términos de cálculo lambda, la continuación de un subterráneo es el contexto en el que se evalúa.

Cuando traduce el código imperativo a un lenguaje funcional, una de las dificultades es hacer frente al código que puede salir de varias maneras diferentes. Por ejemplo, el código puede devolver o generar una excepción. O bien, el cuerpo de un bucle puede continuar comprobando la condición nuevamente o salir del bucle por completo ( breakconstrucción). Hay dos formas principales de hacer frente a esto:

  • Multiplexación: haga que el código devuelva un tipo de suma para todas las salidas posibles. En el caso de un cuerpo de bucle, eso sería Continue | Break.
  • Estilo de paso continuo : traduce el código a una función que toma un parámetro adicional, que es la función que se ejecutará a continuación. Este parámetro adicional es la continuación de la función. El código que puede salir de diferentes maneras recibe uno de esos parámetros para cada una de las formas.

El estilo de paso continuo es cómo las estructuras de datos se incrustan en el cálculo lambda puro. Por ejemplo, cuando representa verdadero comoλx,y.x y falso como λx,y.y, los argumentos x y y son las dos continuaciones posibles, y el booleano es una declaración "if" que selecciona una u otra continuación.

En estilo de paso continuo,

while (condition) body

se traduce a

let rec f (continuation) =
  if (condition, body (f (continuation)), continuation)

En la traducción de un programa en un lenguaje imperativo típico en estilo de paso continuo, la continuación es siempre lo último que ejecuta un fragmento de código. Por ejemplo, la continuación de lo bodyanterior se ejecuta después de todo el código de body, por lo que la optimización de la llamada de cola resulta en la liberación de todas las variables locales bodyjusto antes de ejecutar la continuación.

Algunos idiomas ofrecen continuaciones de primera clase con una construcción como call-with-current-continuation . En general, Call / cc no es apto para la optimización de llamadas de cola; de hecho, puede ser una operación bastante costosa ya que puede conducir a la duplicación de todo el estado del programa.

Gilles 'SO- deja de ser malvado'
fuente