clojure - ¿Cómo implementar un sistema macro de Lisp?

macros

Question

He implementado mi propio Lisp encima de node.js, puedo ejecutar s-expresiones como esta:

(assert (= 3 (+ 1 2))) (def even? (fn [n] (= 0 (bit-and n 1)))) (assert (even? 4)) (assert (= false (even? 5)))

Ahora me gustaría agregar macros, la función defmacro , pero aquí es donde estoy atascado. Me pregunto cómo se implementan los sistemas de macros en otros Lisps pero no pude encontrar muchos punteros (aparte de this y this ).

He visto el sistema de macros Clojure, el Lisp con el que estoy más familiarizado, pero me pareció demasiado complicado y no pude encontrar pistas adicionales que pueda aplicar fácilmente (las macros de Clojure se compilan en última instancia en el código de bytes que no se aplica) a javascript, tampoco pude entender la función macroexpand1 .)

Entonces mi pregunta es: dada una implementación de Lisp sin macros pero con un AST, ¿cómo se agrega un sistema macro como el sistema macro de Clojure? ¿Se puede implementar este sistema de macros en Lisp o requiere características adicionales en la implementación en el lenguaje principal?

Una observación adicional: todavía no he implementado quote ( '' ) porque no pude averiguar qué tipo de valores deberían estar en la lista devuelta. ¿Debería contener elementos AST u objetos como Symbol y Keyword (este último es el caso de Clojure)?

Answer 1

Debe tener una fase de macroexpansión en su cadena de evaluación:

text-input -> read -> macroexpand -> compile -> load

Tenga en cuenta que la expansión de macros debe ser recursiva (macroexpand hasta que no quede nada de macroexpandable).

Sus entornos necesitan la capacidad de "mantener" las funciones de macroexpansión que se pueden buscar por nombre en esta fase. Tenga en cuenta que defmacro es una macro en Common Lisp, que configura las llamadas correctas para asociar el nombre con la función de expansión de macros en ese entorno.

Answer 2

Echa un vistazo a this ejemplo. Es una implementación de juguete de un compilador similar a Arc, con un soporte de macros decente.

Answer 3

Esto es de los Paradigmas de la Programación de Inteligencia Artificial de Peter Norvig, un tomo esencial para cualquier estante de programación de LISP.

Él asume que está implementando un lenguaje interpretado, y proporciona el ejemplo de un intérprete de esquema que se ejecuta en LISP.

Los siguientes dos ejemplos muestran cómo agrega macros a la función de eval primaria ( interp )

Aquí está la función para interpretar una expresión S antes de tratar con macros:

(defun interp (x &optional env)
  "Interpret (evaluate) the expression x in the environment env."
  (cond
    ((symbolp x) (get-var x env))
    ((atom x) x)
    ((case (first x)
       (QUOTE  (second x))
       (BEGIN  (last1 (mapcar #''(lambda (y) (interp y env))
                              (rest x))))
       (SET!   (set-var! (second x) (interp (third x) env) env))
       (IF     (if (interp (second x) env)
                   (interp (third x) env)
                   (interp (fourth x) env)))
       (LAMBDA (let ((parms (second x))
                     (code (maybe-add ''begin (rest2 x))))
                 #''(lambda (&rest args)
                     (interp code (extend-env parms args env)))))
       (t      ;; a procedure application
               (apply (interp (first x) env)
                      (mapcar #''(lambda (v) (interp v env))
                              (rest x))))))))

Y aquí está después de que se haya agregado una evaluación macro (los métodos secundarios han estado en el enlace de referencia para mayor claridad)

(defun interp (x &optional env)
  "Interpret (evaluate) the expression x in the environment env.
  This version handles macros."
  (cond
    ((symbolp x) (get-var x env))
    ((atom x) x)

    ((scheme-macro (first x))              
     (interp (scheme-macro-expand x) env)) 

    ((case (first x)
       (QUOTE  (second x))
       (BEGIN  (last1 (mapcar #''(lambda (y) (interp y env))
                              (rest x))))
       (SET!   (set-var! (second x) (interp (third x) env) env))
       (IF     (if (interp (second x) env)
                   (interp (third x) env)
                   (interp (fourth x) env)))
       (LAMBDA (let ((parms (second x))
                     (code (maybe-add ''begin (rest2 x))))
                 #''(lambda (&rest args)
                     (interp code (extend-env parms args env)))))
       (t      ;; a procedure application
               (apply (interp (first x) env)
                      (mapcar #''(lambda (v) (interp v env))
                              (rest x))))))))

Es interesante notar que el Capítulo inicial de Lisp In Small Pieces de Christian Queinnec tiene una función muy similar, la llama eval .

Answer 4

Todo lo que hace una macro es tomar formas no evaluadas como parámetros y realizar el reemplazo en su cuerpo. El truco para implementar un sistema macro es decirle a tu compilador que sea lazy .

Dicho de otra manera, cuando el compilador encuentra una función, primero evalúa su lista de parámetros formales, produce los resultados y los pasa a la función. Cuando el compilador encuentra una macro, pasa los argumentos sin evaluar al cuerpo, luego realiza cualquier cálculo que el cuerpo solicita y finalmente se reemplaza a sí mismo con el resultado de esos.

Por ejemplo, digamos que tienes una función:

(defun print-3-f (x) (progn (princ x) (princ x) (princ x)))

y una macro:

(defmacro print-3-m (x) `(progn (princ ,x) (princ ,x) (princ ,x)))

Entonces puedes ver la diferencia de inmediato:

CL-USER> (print-3-f (rand))
* 234
* 234
* 234

CL-USER> (print-3-m (rand))
* 24
* 642
* 85

Para entender por qué esto es así, necesita, como una manera de hablar, ejecutar el compilador en su cabeza.

Cuando Lisp encuentra la función, construye un árbol en el que (rand) se evalúa por primera vez y el resultado pasa a la función, que imprime dicho resultado tres veces.

Por otro lado, cuando Lisp se encuentra con la macro, pasa el formulario (rand) sin tocar al cuerpo, lo que devuelve una lista entre comillas donde se sustituye x por (rand) , lo que produce:

(progn (princ (rand)) (princ (rand)) (princ (rand)))

y reemplazando la macro llamada para este nuevo formulario.

Here encontrará una gran cantidad de documentación sobre macros en varios idiomas, incluido Lisp.