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?
fuente
Respuestas:
Así que logré resolver este problema hoy. El código para mi bucle while:
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í:
Lo importante que me faltaba es que en el
while
có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.fuente
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 (
break
construcción). Hay dos formas principales de hacer frente a esto:Continue | Break
.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,
se traduce a
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
body
anterior se ejecuta después de todo el código debody
, por lo que la optimización de la llamada de cola resulta en la liberación de todas las variables localesbody
justo 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.
fuente