¿Cómo implementar un sistema macro Lisp?

Question

he aplicado mi propia Lisp en la parte superior de Node.js, puedo correr s-expresiones como ésta:

 
(assert (= 3 (+ 1 2))) 

(def even? (fn [n] (= 0 (bit-and n 1)))) 

(assert (even? 4)) 
(assert (= false (even? 5))) 

Ahora me gustaría añadir macros - la función defmacro - pero esto es donde yo' estoy atascado. Me pregunto cómo se implementan los macro sistemas en otros Lisps pero no pude encontrar muchos punteros (aparte de this y this).

He visto el sistema macro de Clojure, el Lisp con el que estoy más familiarizado, pero parecía demasiado complicado y no pude encontrar pistas adicionales que pueda aplicar fácilmente (las macros Clojure finalmente compilan en código de bytes que no se aplica a Javascript, tampoco pude entender la función macroexpand1)

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

Una observación adicional: no he implementado quote (') todavía 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 (siendo este último el caso de Clojure)?

Answer 1

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 macro sistema 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, cede 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 solicite, y finalmente se reemplaza con el resultado de esos.

Por ejemplo, digamos que usted tiene 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))) 

A continuación se puede 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é es así? Necesitas, por así decirlo, ejecutar el compilador en tu cabeza.

Cuando Lisp encuentra la función, crea 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 viene a través de la macro, que pasa a la forma (rand)intacta al cuerpo, que devuelve una lista citado donde x se sustituye por (rand), obteniéndose:

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

y reemplazando la macro llamada para esta nueva forma.

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

Answer 2

Usted necesita tener una fase macro-expansión de su cadena de evaluación:

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

Tenga en cuenta que la expansión de la macro debe ser recursivo (macroexpand hasta que nada es macroexpandable izquierda).

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

Answer 3

Eche un vistazo al ejemplo this. Es una implementación de un compilador similar al Arc, con un soporte macro decente.

Answer 4

Esto es de Peter Norvig's Paradigms of Artificial Intelligence Programming - un tomo esencial para cualquier estantería de programadores LISP.

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

The following two examples here muestran cómo se agrega macros para la función primaria eval (interp)

Aquí es la función para la interpretación de una S-expresión 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í es después una evaluación macro ha sido añadido (métodos niños 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 observar que el Capítulo de apertura Christian Queinnec'sLisp In Small Pieces tiene una función muy similar, él lo llama eval.