Come implementare un sistema macro Lisp?

Question

Ho implementato il mio Lisp in cima node.js, posso correre s-espressioni come questa:

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

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

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

Ora vorrei aggiungere macro - la funzione defmacro - ma questo è dove ho' m bloccato Mi chiedo come i sistemi macro siano implementati in altri Lisps ma non sono riuscito a trovare molti puntatori (a parte lo this e lo this).

Ho esaminato il sistema macro Clojure - il Lisp con cui ho più familiarità - ma mi sembrava troppo complicato e non sono riuscito a trovare ulteriori indizi che posso facilmente applicare (le macro Clojure alla fine compilano il codice byte che non si applica a javascript, inoltre non ho potuto dare un senso alla funzione macroexpand1.)

Quindi la mia domanda è: data un'implementazione Lisp senza macro ma con un AST, come si aggiunge un sistema macro come la macro di Clojure sistema? Questo sistema macro può essere implementato in Lisp o richiede funzionalità aggiuntive nell'implementazione nella lingua host?

Un'osservazione aggiuntiva: non ho ancora implementato quote (') perché non sono riuscito a capire quale tipo di valori dovrebbe essere presente nell'elenco restituito. Dovrebbe contenere elementi AST o oggetti come Symbol e Keyword (quest'ultimo è il caso di Clojure)?

Answer 1

Tutte le macro eseguono moduli non valutati come parametri ed eseguono la sostituzione sul suo corpo. Il trucco per implementare un sistema macro è dire al tuo compilatore di essere lazy.

In un altro modo, quando il compilatore incontra una funzione, prima valuta la lista dei parametri formali, produce i risultati e li passa alla funzione. Quando il compilatore trova una macro, passa gli argomenti non valutati al corpo, quindi esegue qualsiasi calcolo richiesto dal corpo e infine si sostituisce con il risultato di quelli.

Per esempio, supponiamo di avere una funzione:

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

e una macro:

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

allora si può vedere la differenza da subito:

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

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

Per capire perché questo è, è necessario, in un certo senso, eseguire il compilatore nella tua testa.

Quando Lisp rileva la funzione, crea un albero in cui viene valutato per la prima volta (rand) e il risultato viene passato alla funzione, che stampa il risultato tre volte.

D'altra parte, quando Lisp incontra la macro, passa la forma (rand)intatta al corpo, che restituisce un elenco citato in cui x è sostituito dal (rand), cedendo:

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

e sostituendo la chiamata macro per questo nuovo modulo.

Here troverete una grande quantità di documentazione relativa alle macro in una varietà di lingue, tra cui Lisp.

Answer 2

È necessario disporre di una fase di espansione delle macro nella vostra catena di valutazione:

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

Si noti che la macro di espansione dovrebbe essere ricorsiva (macroexpand fino nulla macroexpandable è a sinistra).

Gli ambienti devono poter "tenere" le funzioni di macro-espansione che possono essere ricercate per nome in questa fase. Notare che defmacro è una macro stessa in Common Lisp, che imposta le giuste chiamate per associare il nome alla funzione di espansione della macro in quell'ambiente.

Answer 3

Dai un'occhiata all'esempio this. È un'implementazione giocattolo di un compilatore Arc-like, con un supporto macro decente.

Answer 4

Questo è da Peter Norvig Paradigms of Artificial Intelligence Programming - un tomo essenziale per qualsiasi libreria di programmatori LISP.

Suppone che si stia implementando una lingua interpretata e fornisce l'esempio di un interprete di schema in esecuzione in LISP.

The following two examples here mostrano come egli aggiunge macro per la funzione primaria eval (interp)

Qui è la funzione per interpretare un S-espressione prima di trattare con le macro:

(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)))))))) 

E qui è dopo una macro valutazione è stata aggiunta (i metodi figlio sono stati nel link di riferimento per chiarezza

(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)))))))) 

È interessante notare che il capitolo di apertura di Christian Queinnec'sLisp In Small Pieces ha una funzione molto simile, lo chiama eval.