compiler construction - ¿Es posible implementar el sistema de macros de Common Lisp en esquema?

compiler-construction scheme (3)

Esperemos que esta no sea una pregunta redundante.

Como recién llegado al esquema, soy consciente de que syntax-case macros de syntax-case son más poderosas que la alternativa de syntax-rules , a costa de una complejidad no deseada.

Sin embargo, ¿es posible implementar el sistema de macros de Common Lisp en un esquema, que es más poderoso que syntax-rules de syntax-rules , usando syntax-case ?

Aquí está la implementación de define-macro de define-macro . Tenga en cuenta que se implementa totalmente con syntax-case :

(define-syntax define-macro (lambda (x) "Define a defmacro." (syntax-case x () ((_ (macro . args) doc body1 body ...) (string? (syntax->datum #''doc)) #''(define-macro macro doc (lambda args body1 body ...))) ((_ (macro . args) body ...) #''(define-macro macro #f (lambda args body ...))) ((_ macro transformer) #''(define-macro macro #f transformer)) ((_ macro doc transformer) (or (string? (syntax->datum #''doc)) (not (syntax->datum #''doc))) #''(define-syntax macro (lambda (y) doc #((macro-type . defmacro) (defmacro-args args)) (syntax-case y () ((_ . args) (let ((v (syntax->datum #''args))) (datum->syntax y (apply transformer v)))))))))))

Guile tiene soporte especial para las cadenas de documentación de estilo Common Lisp, por lo que si su implementación de Scheme no usa cadenas de documentación, su implementación de define-macro podría ser aún más sencilla:

(define-syntax define-macro (lambda (x) (syntax-case x () ((_ (macro . args) body ...) #''(define-macro macro (lambda args body ...))) ((_ macro transformer) #''(define-syntax macro (lambda (y) (syntax-case y () ((_ . args) (let ((v (syntax->datum #''args))) (datum->syntax y (apply transformer v)))))))))))

Aquí está la implementación de define-macro de mi Preludio estándar , junto con los ejemplos del libro de Paul Graham:

(define-syntax (define-macro x) (syntax-case x () ((_ (name . args) . body) (syntax (define-macro name (lambda args . body)))) ((_ name transformer) (syntax (define-syntax (name y) (syntax-case y () ((_ . args) (datum->syntax-object (syntax _) (apply transformer (syntax-object->datum (syntax args))))))))))) (define-macro (when test . body) `(cond (,test . ,body))) (define-macro (aif test-form then-else-forms) `(let ((it ,test-form)) (if it ,then-else-forms))) (define-macro (awhen pred? . body) `(aif ,pred? (begin ,@body)))

Trataré de ser breve, lo cual es difícil, ya que generalmente es un problema muy profundo, más que el nivel promedio de preguntas y respuestas de SO ... así que esto seguirá siendo bastante largo. También trataré de ser imparcial; aunque vengo desde una perspectiva de Raqueta, he estado usando Common Lisp en el pasado y siempre me ha gustado usar macros en ambos mundos (y en otros, en realidad). No se verá como una respuesta directa a su pregunta (en un extremo, eso sería simplemente "sí"), pero está comparando los dos sistemas y esperamos que esto ayude a aclarar el problema para las personas, especialmente las personas externas. de lisp (todos los sabores) quien se preguntaría por qué es esto tan importante. También describiré cómo se puede implementar defmacro en los sistemas de "caso de sintaxis", pero solo en general para mantener las cosas claras (y como puede encontrar tales implementaciones, algunas de ellas se encuentran en los comentarios y en otras respuestas).

En primer lugar, su pregunta no es redundante, está muy justificada y, como dije, es una de las cosas que los recién llegados de Lisp a Scheme y los recién llegados a Lisp encuentran.

En segundo lugar, la respuesta muy breve y muy breve es lo que la gente le ha dicho: sí, es posible implementar el defmacro de CL en un Esquema que soporta syntax-case , y como es de esperar, tiene múltiples sugerencias para tales implementaciones. Ir por el otro lado e implementar syntax-case utilizando defmacro simple es un tema más complicado del que no voy a hablar demasiado; Solo diré que se ha hecho , solo a un costo muy alto para la reimplementación de lambda y otras construcciones de enlace, lo que significa que es básicamente una reimplementación de un nuevo lenguaje con el que debería comprometerse si desea usarlo. implementación.

Y otra aclaración: las personas, especialmente los CLers, muy a menudo colapsan dos cosas relacionadas con las macros de Scheme: la higiene y syntax-rules . El problema es que en R5RS todo lo que tienes son syntax-rules , que es un sistema de reescritura basado en patrones muy limitado. Al igual que con otros sistemas de reescritura, puede usarlo de forma ingenua, o utilizarlo de nuevo para definir un lenguaje pequeño que luego puede usar para escribir macros. Consulte este texto para obtener una explicación conocida sobre cómo se hace esto. Si bien es posible hacerlo, la conclusión es que es difícil, estás usando un poco de lenguaje pequeño y extraño que no está directamente relacionado con tu lenguaje real, y esto hace que esté muy lejos de la programación de Scheme, probablemente en un peor momento. La forma en que el uso de la macro implementación higiénica en CL no es realmente usar CL simple. En resumen, es posible usar solo syntax-rules , pero esto es principalmente en un sentido teórico, no algo que querrás usar en código "real". El punto principal aquí es que la higiene no implica estar limitado a syntax-rules .

Sin embargo, syntax-rules no fueron concebidas como "el" sistema de macros de Scheme (la idea era siempre tener una implementación de macros de "bajo nivel" que se usa para implementar syntax-rules pero también puede implementar macros que rompen la higiene) es solo que no hubo acuerdo sobre la implementación de bajo nivel en particular. R6RS lo corrige al estandarizar el sistema de macros "sintaxis" (tenga en cuenta que estoy usando "caso de sintaxis" como nombre del sistema, diferente del syntax-case de syntax-case que es la forma en que se destaca). Como para señalar que la discusión aún está viva, R7RS dio un paso atrás y la excluyó, volviendo a tener syntax-rules sin compromiso en un sistema de bajo nivel, al menos en lo que respecta al "lenguaje pequeño". .

Ahora, para entender realmente la diferencia entre los dos sistemas, lo mejor es aclarar la diferencia entre los tipos con los que están tratando. Con defmacro , un transformador es básicamente una función que toma en una expresión (s) S y devuelve una expresión en S. Una expresión S aquí es un tipo que se compone de un montón de tipos literales (números, cadenas, booleanos), símbolos y estructuras anidadas de listas de estos. (Los tipos reales utilizados son un poco más que eso, pero eso es suficiente para hacer el punto.) El problema es que este es un mundo muy simple: se está metiendo en algo que es muy concreto: realmente puede imprimir la entrada / Los valores de salida y eso es todo lo que tienes. Tenga en cuenta que este sistema usa símbolos para denotar identificadores, y un símbolo es algo muy concreto en ese sentido: una x es una pieza de código que tiene ese nombre, x .

Sin embargo, esta simplicidad tiene un costo: no puede usarla para macros higiénicas ya que no tiene manera de distinguir dos identificadores diferentes que se llaman x . El defmacro basado en CL habitual tiene algunos bits adicionales que compensan algo de esto. Uno de estos bits es gensym , una herramienta para crear símbolos "nuevos" que no están incrustados y por lo tanto se garantiza que sean diferentes de cualquier otro símbolo, incluidos los que tienen el mismo nombre. Otro bit defmacro es el argumento del &environment para defmacro transformers, que contiene una cierta representación del entorno léxico de la ubicación donde se utiliza la macro.

Es obvio que estas cosas complican el mundo defmacro ya que ya no se trata de valores imprimibles simples, y ya que necesita estar al tanto de alguna representación de un entorno, lo que hace que sea aún más claro que una macro es en realidad una pieza de código que es un gancho de compilador (ya que este entorno es esencialmente un tipo de datos con el que el compilador generalmente trata, y uno que es más complicado que solo las expresiones S). Pero resulta que no son suficientes para implementar la higiene. Al utilizar gensym se puede gensym un aspecto sencillo de la higiene (evitando las capturas del código de usuario en el lado del macro), pero el otro aspecto (evitar el código de macro de captura del código del usuario) aún se deja abierto. Algunas personas se conforman con esto y argumentan que el tipo de captura que puede evitar es suficiente, pero cuando se trata de un sistema modular en el que el entorno de una macro a menudo tiene enlaces diferentes a los utilizados en su implementación, el otro lado se convierte en mucho mas importante

Pase a los sistemas de macros de caso de sintaxis (y felizmente saltándose syntax-rules , que se implementan de manera trivial utilizando syntax-case ). En este sistema, la idea es que si las expresiones S simbólicas simples no son lo suficientemente expresivas para representar el conocimiento léxico completo (es decir, la diferencia entre dos enlaces diferentes, ambos llamados x ), entonces los "enriqueceremos" y utilizar un tipo de datos que lo hace. (Tenga en cuenta que hay otros sistemas de macros de bajo nivel que adoptan diferentes enfoques para proporcionar información adicional, como el cambio de nombre explícito y los cierres sintácticos).

La forma en que se hace esto es haciendo que los transformadores de macros sean funciones que consumen y devuelven "objetos de sintaxis", que son exactamente ese tipo de representación. Más precisamente, estos objetos de sintaxis generalmente se construyen sobre la representación simbólica llana, solo envueltos en estructuras que tienen información adicional que representa el alcance léxico. En algunos sistemas (especialmente en Racket), todo se envuelve en objetos de sintaxis, símbolos y otros literales y listas. Teniendo en cuenta esto, no es sorprendente que sea fácil eliminar las expresiones S de los objetos de sintaxis: solo saca los contenidos simbólicos y, si se trata de una lista, continúe haciéndolo de forma recursiva. En los sistemas de caso de sintaxis, esto se realiza mediante syntax-e que implementa el elemento de acceso para el contenido simbólico de un objeto de sintaxis, y syntax->datum que implementa las versiones que reducen el resultado de forma recursiva para producir una expresión-S completa. Como nota al margen, esta es una explicación aproximada de por qué en el Esquema la gente no habla de que los enlaces se representan como símbolos , sino como identificadores .

Por otro lado, la pregunta es cómo empezar a partir de un nombre simbólico dado y construir un objeto de sintaxis de este tipo. La forma en que se hace esto es con la función datum->syntax - pero en lugar de hacer que la API especifique cómo se representa la información del alcance léxico, la función toma un objeto de sintaxis como primer argumento y una expresión S simbólica como segundo argumento, y crea un objeto de sintaxis envolviendo correctamente la expresión S con la información del alcance léxico tomada del primero. Esto significa que, para romper la higiene, lo que suele hacer es comenzar con un objeto de sintaxis suministrado por el usuario (por ejemplo, una forma de cuerpo de una macro) y utilizar su información léxica para crear un nuevo identificador como this que sea visible en el mismo ámbito.

Esta breve descripción es suficiente para ver cómo funcionan las macros que le mostraron. La macro que @ ChrisJester-Young mostró simplemente toma el (los) objeto (s) de sintaxis, lo elimina en una S-expresión sin syntax->datum con syntax->datum , lo envía al transformador defmacro y recupera una S-expresión, luego usa la syntax->datum para convertir el resultado de nuevo a un objeto de sintaxis utilizando el contexto léxico del código de usuario. La implementación de defmacro de Racket es un poco más sofisticada: durante la etapa de extracción, mantiene una tabla hash que asigna las expresiones S resultantes a sus objetos de sintaxis originales, y durante la etapa de reconstrucción consulta esta tabla para obtener el mismo contexto que los bits de código originalmente tenía. Esto hace que sea una implementación más robusta para algunas macros más complejas, pero también es más útil en Racket, ya que los objetos de sintaxis tienen mucha más información en ellos, como ubicación de origen, propiedades, etc., y esta reconstrucción cuidadosa generalmente dará como resultado valores de salida (sintaxis objetos) que mantienen la información que tenían en su camino hacia la macro.

Para una introducción un poco más técnica para los programadores de defmacro en el sistema de caso de sintaxis, vea mi blog de macros de syntax-case escritura . Si viene del lado del Esquema, no será tan útil, pero seguirá siendo útil para aclarar todo el problema.

Para acercar esto a una conclusión, debo señalar que tratar con macros antihigiénicos todavía puede ser complicado. Más específicamente, hay varias formas de lograr tales ataduras, pero son diferentes en varias formas sutiles, y generalmente pueden regresar y morderle, dejando marcas de dientes ligeramente diferentes en cada caso. En un sistema defmacro "verdadero" como el CL, aprendes a vivir con un conjunto específico de marcas de dientes, unas que son relativamente conocidas, y por lo tanto hay cosas que simplemente no haces. Lo más notable aquí es el tipo de composición modular de idiomas con diferentes enlaces para los mismos nombres que Racket utiliza con tanta frecuencia. En los sistemas de casos de sintaxis, un mejor enfoque es fluid-let-syntax que se utiliza para "ajustar" el significado de un nombre de ámbito léxico y, más recientemente, que se ha convertido en "parámetros de sintaxis". Hay una buena descripción general de los problemas de las macros que rompen la higiene , que incluye una descripción de cómo puede intentar resolverlo solo con syntax-rules higiénicas, con caso de sintaxis básica, con defmacro estilo defmacro , y finalmente con parámetros de sintaxis . Este texto se vuelve un poco más técnico, pero es relativamente fácil de leer las primeras páginas, y si lo entiende, tendrá una muy buena imagen de todo el debate. (También hay una publicación de blog más antigua que se trata mejor en el periódico).

También debo mencionar que está lejos de ser el único problema "candente" relacionado con las macros. El debate dentro de los círculos del Esquema sobre qué sistema macro de bajo nivel es mejor puede ser bastante intenso a veces. Y hay otros problemas relacionados con las macros, como la cuestión de cómo hacer que funcionen en un sistema de módulos donde una biblioteca puede proporcionar macros, así como valores y funciones, o si se deben separar el tiempo de ejecución y el tiempo de ejecución de la macro en fases separadas, y más.

Esperemos que esto presente una imagen más completa del problema, hasta el punto de estar al tanto de las compensaciones y poder decidir por ti mismo qué es lo que mejor funciona para ti. También espero que esto aclare algunas de las fuentes de las llamas habituales: las macros higiénicas ciertamente no son inútiles, pero dado que el nuevo tipo es más que simples expresiones S, hay más funcionalidades a su alrededor, y muy a menudo poco profundas. La lectura de los transeúntes llega a la conclusión de que "es demasiado complejo". Peor aún son las llamas en el espíritu de "en el mundo del Esquema, la gente casi no sabe nada acerca de la metaprogramación": siendo muy dolorosas al tanto del costo adicional y también de los beneficios deseados, las personas en el mundo del Esquema han gastado muchos más esfuerzos colectivos. sobre el tema. Es una buena opción seguir con defmacro si los envoltorios adicionales alrededor de las expresiones en S son demasiado complicados para su gusto, pero debe tener en cuenta el costo que implica aprender lo que paga al deshacerse de la higiene (y lo que obtiene al aceptar eso).

Desafortunadamente, las macros de cualquier sabor son, en general, un tema bastante difícil para los novatos (tal vez excluyendo las syntax-rules extremadamente limitadas), por lo que las personas tienden a encontrarse en medio de esas llamas sin tener la experiencia suficiente para conocer su izquierda desde su derecha. En última instancia, nada es mejor que tener una buena experiencia en ambos mundos para aclarar las ventajas y desventajas. (Y eso es de una experiencia personal muy concreta: si el esquema PLT no cambiara a la sintaxis hace N años, probablemente nunca me hubiera molestado con eso ... Una vez que lo hicieron, me tomó mucho tiempo convertir mi código, y solo entonces me di cuenta de lo maravilloso que es tener un sistema robusto donde los nombres no se "confundan" por error (lo que daría como resultado errores extraños, y %%__names__ ).

(Aún así, es muy probable que ocurran llamas de comentarios ...)