compiler-construction - programacion - scheme dialect of lisp

¿Cómo compilas macros en un compilador Lisp? (4)

Cómo funciona esto es muy diferente en varios dialectos Lisp. Para Common Lisp, está estandarizado en el estándar ANSI Common Lisp y las diferentes implementaciones de Common Lisp difieren principalmente si usan un compilador, un intérprete o ambos.

Lo siguiente asume Common Lisp.

EVAL no es el intérprete . EVAL se puede implementar con un compilador. Algunas implementaciones de Common Lisp incluso no tienen un intérprete. Entonces EVAL es una llamada al compilador para compilar el código y luego llama al código compilado. Estas implementaciones utilizan un compilador incremental, que puede compilar también expresiones simples como 2 , (+ 2 3) , (gensym) , etc.

La macroexpansión se realiza con las funciones MACROEXPAND y MACROEXPAND-1 .

Una macro en Common Lisp es una función que espera algunas formas y devuelve otra. DEFMACRO registra esta función como una macro.

Tu macro

(defmacro cube (n) (let ((x (gensym))) `(let ((,x ,n)) (* ,x ,x ,x))))

no es más que una función Lisp, que se registra como una macro.

El efecto es similar a este:

(defun cube-internal (form environment) (destructuring-bind (name n) form ; the name would be CUBE (let ((x (gensym))) `(let ((,x ,n)) (* ,x ,x ,x))))) (setf (macro-function ''my-cube) #''cube-internal)

En una implementación de CL real, DEFMACRO expande de manera diferente y no usa un nombre como CUBE-INTERNAL . Pero conceptualmente es definir una función macro y registrarla.

Cuando el compilador Lisp ve una definición de macro, generalmente compila la función de macro y la almacena en el llamado entorno actual. Si el entorno es el entorno de tiempo de ejecución, se recuerda en el tiempo de ejecución. Si el entorno es el entorno del compilador mientras se compila un archivo, la macro se olvida después de compilar el archivo. El archivo compilado debe cargarse para que Lisp conozca la macro.

Entonces, hay un efecto secundario al definir una macro y compilarla. El compilador recuerda la macro compilada y almacena su código.

Cuando el compilador ahora ve un código que usa la macro (cube 10) , el compilador simplemente llama a la función de macro que está almacenada en el entorno actual con el nombre CUBE , llama a esta función de macro que 10 es un argumento y luego compila el forma generada. Como se mencionó anteriormente, no se realiza directamente, sino a través de las funciones MACROEXPAND.

Aquí está la definición de la macro:

CL-USER 5 > (defmacro cube (n) (let ((x (gensym))) `(let ((,x ,n)) (* ,x ,x ,x)))) CUBE

Compilamos la macro:

CL-USER 6 > (compile ''cube) CUBE NIL NIL

MACRO-FUNCTION devuelve la función para una macro. Podemos llamarlo como cualquier otra función con FUNCALL . Espera dos argumentos: una forma completa como (cube 10) y un entorno (aquí NIL ).

CL-USER 7 > (funcall (macro-function ''cube) ''(cube 10) nil) (LET ((#:G2251 10)) (* #:G2251 #:G2251 #:G2251))

También es posible tomar una función (que acepta dos argumentos: una forma y un entorno) y almacenarla utilizando SETF como una función macro.

Resumen

Cuando se ejecuta el compilador Common Lisp, simplemente conoce las funciones de la macro y las llama cuando es necesario para expandir el código a través del expansor de macros incorporado. Las funciones de macro son simplemente el código Lisp. Cuando el compilador Lisp ve una definición de macro, compila la función de macro, la almacena en el entorno actual y la usa para expandir los usos posteriores de la macro.

Nota: Esto hace necesario en Common Lisp que una macro esté definida antes de que el compilador pueda utilizarla.

En un intérprete Lisp, puede haber fácilmente una rama en eval que pueda expandir una macro, y en el proceso de expandirla, llame a las funciones para construir la expresión expandida. He hecho esto antes de usar macros de bajo nivel, es fácil de resolver.

Pero, en un compilador, no hay ninguna función a la que llamar para crear el código expandido: el problema se puede ver simplemente en el siguiente ejemplo:

(defmacro cube (n) (let ((x (gensym))) `(let ((,x ,n)) (* ,x ,x ,x))))

Cuando la macro es expandida por un intérprete, llama a gensym y hace lo que usted espera. Cuando se expande por un compilador, generaría el código para un let que une x a (gensym) pero el símbolo gensymmed solo es necesario para que el compilador haga lo correcto. Y como gensym no se llama antes de compilar la macro, no es muy útil.

Esto se vuelve aún más extraño para mí cuando una macro crea una lista para ser utilizada como la expansión mediante el uso de un map o filter .

Entonces, ¿cómo funciona esto? Seguramente el código compilado no está compilado para (eval *macro-code*) porque sería terriblemente ineficiente. ¿Hay un compilador Lisp bien escrito donde esto esté claro?

Encontraste una de las principales diferencias entre Lisp y otros idiomas.

En Lisp, la ejecución de código creado dinámicamente es esencial y, por ejemplo, necesaria para la expansión de macros.

Mientras escribía un compilador de Lisp to C, descubrí esto ahora algo obvio y llegué a la conclusión de que si desea escribir un compilador Lisp, solo hay dos soluciones:

Escribe AMBOS un compilador y un intérprete para poder llamar al intérprete para la expansión de macros durante la compilación.
Debe poder compilar dinámicamente el código y llamarlo (o usar peores "trucos", como compilar un módulo que se puede cargar dinámicamente y luego cargarlo).

Si está trabajando en un compilador para C, una posibilidad es utilizar la biblioteca TCC de Fabrice Bellard que permite la compilación directa de código C en un búfer de memoria.

Estoy escribiendo un compilador de Lisp a Javascript y en este caso, por supuesto, no hay problema porque "el hardware" puede manejarlo muy bien y puede pedirle a Javascript que evalúe, por ejemplo, una cadena "function(...){...}" y luego llamar al objeto resultante. El uso de Javascript también resuelve lo que es IMO, uno de los problemas más difíciles para un kernel Lisp que es la implementación adecuada de cierres léxicos.

De hecho, en mi javascript compilador eval es más o menos

(defun eval (x) (funcall (js-eval (js-compile x))))

donde js-compile es la interfaz principal del compilador y dado un formato lisp devolverá una cadena que contiene código javascript que cuando se evalúa (con la eval de javascript que exporté al nivel lisp como js-eval ) ejecuta el código. Curiosamente, también eval nunca se usa (con la única excepción no esencial de una macro de conveniencia en la que tengo que ejecutar el código definido por el usuario durante la expansión de la macro).

Una cosa importante a considerar es que mientras Common Lisp tiene una especie de separación entre "tiempo de lectura", "tiempo de compilación" y "tiempo de ejecución", esta separación es más lógica que física, ya que el código en ejecución siempre es Lisp. Compilar en Lisp es solo llamar a una función. Incluso la fase de "análisis" es solo una función normal que se está ejecutando ... es Lisp completamente abajo :-)

Enlaces a mi compilador de juguetes Lisp → Js

Hay muchos enfoques para esto. Un extremo es algo llamado "FEXPER", que son cosas similares a una macro que esencialmente se vuelven a expandir en cada evaluación. Provocaron mucho ruido en algún momento en el pasado, pero casi han desaparecido por completo. (Hay algunas personas que todavía hacen cosas similares, sin embargo, newlisp es probablemente el ejemplo más popular).

Así que los FEXPER fueron descartados en favor de las macros, que de alguna manera se "comportan mejor". Básicamente haces una expansión de macro una vez, y compilas el código resultante. Como es habitual, hay algunas estrategias aquí, que pueden llevar a resultados diferentes. Por ejemplo, "expandir una vez" no especifica cuándo se expande. Esto puede suceder tan pronto como se lee el código, o (generalmente) cuando se compila, o incluso solo la primera vez que se ejecuta.

Otra pregunta aquí, y en lo que esencialmente se encuentra, es en qué entorno evalúa el código de macro. En la mayoría de los Lisps, todo sucede en el mismo entorno global feliz. Una macro puede acceder a las funciones libremente, lo que puede llevar a algunos problemas sutiles. Un resultado de esto es que muchas implementaciones comerciales de Common Lisp le brindan un entorno de desarrollo en el que hace la mayor parte de su trabajo y compila las cosas; esto hace que el mismo entorno esté disponible en ambos niveles. (En realidad, como las macros pueden usar macros, aquí hay una cantidad arbitraria de niveles). Para implementar una aplicación, se obtiene un entorno restringido que no tiene, por ejemplo, el compilador (es decir, la función de compile ), ya que si implemente el código que usa eso, su código es esencialmente un compilador de CL. Entonces, la idea es que compile el código en su implementación completa, y eso expande todas las macros, lo que significa que el código compilado no tiene usos adicionales de las macros.

Pero, por supuesto, eso puede llevar a esos problemas sutiles de los que hablé. Por ejemplo, algunos efectos secundarios pueden llevar a un desorden en el orden de carga, donde debe cargar el código en un orden específico. Peor aún, podría caer en una trampa en la que el código corre de una manera para usted y otra cuando está compilado, ya que el código compilado ya tenía todas las macros (y las llamadas que hicieron) expandidas de antemano. Existen algunas soluciones de pirateo, como eval-when que especifica ciertas condiciones para evaluar algunos códigos. También hay algunos sistemas de paquetes para CL donde se especifican cosas como el orden de carga (como asdf ). Aún así, no hay una solución realmente sólida allí, y aún puedes caer en estas trampas (ver, por ejemplo, esta perorata extendida ).

Hay alternativas, por supuesto. En particular, Racket utiliza su sistema de módulos. Un módulo puede ser "instanciado" varias veces, y el estado es único para cada instancia. Ahora, cuando se usa algún módulo tanto en macros como en tiempo de ejecución, las dos instancias de estos módulos son distintas, lo que significa que la compilación siempre es confiable, y no hay ninguno de los problemas anteriores. En el mundo de Scheme, esto se conoce como "fases separadas", donde cada fase (tiempo de ejecución, tiempo de compilación y niveles superiores con macros que usan macros) tiene instancias de módulo separadas. Para una buena introducción a esto y una explicación completa, lea Macros compilables y compilables de Matthew Flatt . También puede simplemente mirar los documentos de Racket , por ejemplo, la sección Fases de compilación y tiempo de ejecución .

No hay nada particularmente mágico acerca de las macros.

En un nivel alto, son simplemente funciones. Funciones que devuelven S-Exprs para formularios Lisp. El "tiempo de ejecución" de la macro está disponible en la función macroexpand, que como ya sabrá, expande las macros.

Por lo tanto, puede verlo en términos que el compilador detecte que un formulario es una macro, lo evalúa y luego compila el formulario subsiguiente que se devuelve como resultado de esa macro.

Normalmente, hay muchas citas y uniones y otras cirugías dentro de las macros para que sean más fáciles de escribir, como un sistema de plantillas. Pero esas construcciones no son necesarias. Puedes devolver un S-Expr construido como quieras. Entonces, si se ve de esa manera, puede ver que, en su núcleo, son simplemente funciones evaluadas en el momento de la compilación.