Transformación Lisp a C++

Question

estoy trabajando en un lenguaje de juguete que se compila en C++ basado en Lisp (muy pequeño subconjunto de esquema), estoy tratando de encontrar la manera de representar expresión let,

(let ((var 10) 
     (test 12)) 
    (+ 1 1) 
    var) 

Al principio Pensé en ejecutar todas las exprs y luego devolver la última, pero al volver se anulará mi capacidad para anotar let expresiones, ¿cuál sería el camino a seguir para representar Let?

Además, cualquier fuente de recursos sobre la transformación de origen se appriciated, he buscado en Google, pero todo lo que pude fing es el compilador de esquema de 90 min.

Answer 1

Una forma de ampliar let es tratarlo como un lambda:

((lambda (var test) (+ 1 1) var) 10 12) 

Entonces, transformar esta a una función y una llamada correspondiente en C++:

int lambda_1(int var, int test) { 
    1 + 1; 
    return var; 
} 

lambda_1(10, 12); 

Así, en un contexto más amplio :

(display (let ((var 10) 
       (test 12)) 
      (+ 1 1) 
      var)) 

convierte

display(lambda_1(10, 12)); 

Hay muchos más detalles, como la necesidad de acceder a las variables léxicas fuera del let desde dentro de la let. Como C++ no tiene funciones léxicas anidadas (a diferencia de Pascal, por ejemplo), esto requerirá una implementación adicional.

Answer 2

Si usted está buscando herramientas para ayudar con la traducción de fuente a fuente, me gustaría recomendar ANTLR. Es excelente.

Sin embargo, tendrá que pensar en cómo traducir de un idioma escrito débilmente (ceceo) a un lenguaje menos vagamente mecanografiados a (c). Por ejemplo, en su pregunta, ¿cuál es el tipo de 10? A short? ¿Un int? A double?

Answer 3

Trataré de explicar un enfoque ingenuo para compilar anidados lambda s. Dado que la explicación de Greg de ampliar let en un lambda es muy buena, no me referiré a let en absoluto, voy a suponer que es let una forma derivada o macro y se expande en una forma que es lambda llamada inmediatamente.

La compilación de las funciones Lisp o Scheme directamente en las funciones C o C++ será complicado debido a los problemas que plantean otros carteles. Dependiendo de el enfoque, el C o C++ resultante no será reconocible (o incluso muy legible).

Escribí un compilador de Lisp-to-C después de terminar la Estructura e Interpretación de Programas de Computadora (es uno de los ejercicios finales, y de hecho engañé y simplemente escribí un traductor del código de bytes SICP a C). El subconjunto de C que emitió no usó funciones C para manejar funciones Lisp. Esto se debe a que el lenguaje de máquina de registro en el capítulo 5 de SICP es realmente de nivel inferior que C.

Suponiendo que tiene algún tipo de entorno, que une nombres a valores, puede definir la esencia de la función llamando así: extienda el entorno en el que se definió la función con los parámetros formales vinculados a los argumentos, y luego evaluar el cuerpo de la función en este nuevo entorno.

En compilador de SICP, el medio ambiente se mantiene en una variable global, y hay otros variables globales que sostienen la lista de argumentos de una llamada de función, como así como el procedimiento objeto que se está llamando (el objeto procedimiento incluye una puntero al entorno en el que se definió), y una etiqueta para saltar cuando devuelve una función.

Tenga en cuenta que cuando se está compilando una expresión lambda, hay son dos componentes sintácticos que conoce en tiempo de compilación: los parámetros formales y el cuerpo de la lambda.

Cuando se compila una función, el código emitido se ve algo como este pseudocódigo:

some-label 
*env* = definition env of *proc* 
*env* = extend [formals] *argl* *env* 
result of compiling [body] 
... 
jump *continue* 

... donde *env* y *argl* son las variables globales que sostienen el medio ambiente y lista de argumentos, y extend es cierta función (esto puede ser una función apropiada de C++) que amplía el entorno *env* por emparejando nombres en *argl* con valores en [formals].

Entonces, cuando se ejecuta el código compilado, y hay una llamada a este lambda otra parte de su código, la convención de llamada es poner el resultado de la evaluación de la lista de argumentos en la variable *argl*, estimaron el rendimiento etiqueta en la variable *continue*, y luego salta al some-label.

En el caso de anidados lambda s, el código emitido sería algo como esto :

some-label 
*env* = definition env of *proc* 
*env* = extend [formals-outer] *argl* *env* 
another-label 
*env* = definition env of *proc* 
*env* = extend [formals-inner] *argl* *env* 
result of compiling [body-inner] 
... 
jump *continue* 
rest of result of compiling [body-outer] 
... somewhere in here there might be a jump to another-label 
jump *continue* 

Esto es un poco difícil de explicar, y estoy seguro de que he hecho un trabajo confuso de eso No puedo pensar en un ejemplo decente que no me implique básicamente describir descuidadamente todo el capítulo 5 del SICP. Como pasé el tiempo escribiendo esta respuesta, la voy a publicar, pero lo siento mucho si es completamente confusa.

Recomiendo encarecidamente SICP y Lisp in Small Pieces.

El SICP cubre la interpretación metacircular para principiantes, así como una serie de variantes en el intérprete, y un compilador de código de bytes que he logrado ofuscar y desmenuzar. Son solo los dos últimos capítulos, los primeros 3 capítulos son igual de buenos. Es un libro maravilloso. Absolutamente léelo si aún no lo has hecho.

LiSP incluye una serie de intérpretes escritos en Scheme, un compilador de código de bytes y un compilador de C. Estoy en el medio y puedo decir con confianza que es un libro rico y profundo que bien vale la pena el tiempo de cualquiera interesado en la implementación de Lisp. Puede ser un poco anticuado en este punto, pero para un principiante como yo, sigue siendo valioso. Sin embargo, es más avanzado que el SICP, así que ten cuidado. Incluye un capítulo en el medio sobre la semántica de denotación que básicamente pasó por encima de mi cabeza.

Algunas otras notas:

Darius Bacon's self-hosting Lisp to C compiler

lambda lifting, que es una técnica más avanzada que creo que Marc Feeley utiliza