Come ricorsive definizioni di macro vengono valutati

Question

Questa definizione ricorsiva di una macro fa quello che dovrebbe (interi somma da 1 a n):

(defmacro sum-int-seq (n) 
    `(cond 
    ((equal 0 ,n) 0) 
    (t (+ ,n (sum-int-seq (- ,n 1)))))) 

Per esempio (sum-int-seq 5) dà 15.

Ma perché lo fa lavoro? Quando la macro viene espansa ottengo questo:

(macroexpand '(sum-int-seq 5)) 
(IF (EQUAL 0 5) 0 (+ 5 (SUM-INT-SEQ (- 5 1)))) 

Ma poiché somma-int-Seq è una macro valutazione macro dovrebbe diventare un ciclo infinito. Il compilatore crea invece una funzione ricorsiva? Se questa definizione crea una funzione ricorsiva esiste un modo per definire le macro in maniera ricorsiva?

(Questo è un esempio stupido per brevità, una funzione sarebbe ovviamente lavorare meglio per questo)

Answer 1

L'esempio non funziona.

Può funzionare in un interprete. Ma con un compilatore vedrai un ciclo infinito durante la compilazione.

CL-USER 23 > (defun test (foo) 
       (sum-int-seq 5)) 
TEST 

Usiamo il LispWorks interprete:

CL-USER 24 > (test :foo) 
15 

Proviamo a compilare la funzione di:

CL-USER 25 > (compile 'test) 

Stack overflow (stack size 15997). 
    1 (continue) Extend stack by 50%. 
    2 Extend stack by 300%. 
    3 (abort) Return to level 0. 
    4 Return to top loop level 0. 

Type :b for backtrace or :c <option number> to proceed. 
Type :bug-form "<subject>" for a bug report template or :? for other options. 

Così, ora la prossima domanda: perché funziona l'interprete, ma il compilatore non può compilarlo?

Ok, lo spiegherò.

Diamo prima l'interprete.

• vede (sum-int-seq 5).
• it macro lo diventa (COND ((EQUAL 0 5) 0) (T (+ 5 (SUM-INT-SEQ (- 5 1))))).
• quindi valuta il modulo sopra. Determina che deve calcolare (+ 5 (SUM-INT-SEQ (- 5 1))). Per quello ha bisogno di macroexpand (SUM-INT-SEQ (- 5 1)).
• alla fine si espanderà in qualcosa come (cond ((EQUAL 0 (- (- (- (- (- 5 1) 1) 1) 1) 1)) 0) .... Che poi restituirà 0 e il calcolo può usare questo risultato e aggiungere gli altri termini ad esso.

L'interprete prende il codice, valuta cosa può e la macroespande se necessario. Il codice generato viene quindi valutato o espanso a macroistruzione. E così via.

Ora diamo un'occhiata al compilatore.

• vede (somma-int-seq 5) e macro lo ingrandisce in (COND ((EQUAL 0 5) 0) (T (+ 5 (SUM-INT-SEQ (- 5 1))))).
• ora la macroespansione verrà eseguita sulle sottomaschere, eventualmente.
• il compilatore eseguirà il macroexpand (SUM-INT-SEQ (- 5 1)). si noti che il codice non viene mai valutato, solo espanso.
• il compilatore eseguirà il macroexpand (SUM-INT-SEQ (- (- 5 1) 1)) e così via. finalmente vedrai uno stack overflow.

Il compilatore cammina (compila/espande in modo ricorsivo) il codice. Potrebbe non eseguire il codice (a meno che non funzioni ottimizzazioni o una macro la valuta in modo esplicito).

Per una macro ricorsiva è necessario eseguire il conto alla rovescia. Se si eval nella macro, allora qualcosa come (sum-int-seq 5) può funzionare. Ma per (defun foo (n) (sum-int-seq n)) questo è senza speranza, dal momento che il compilatore non sa quale sia il valore di n.

Answer 2

Espansione di un macro genera il codice Lisp che viene quindi valutata. Chiamare una funzione devia il flusso di esecuzione in una copia del codice Lisp preesistente che viene quindi eseguito. Oltre a questo, i due sono piuttosto simili e la ricorsione funziona allo stesso modo. In particolare, l'espansione della macro si interrompe per la stessa ragione per cui una funzione ricorsiva scritta correttamente si arresta: perché c'è una condizione di terminazione e la trasformazione tra una chiamata e la successiva è stata scritta in modo tale che la condizione sia effettivamente raggiunta. Se non fosse raggiunto, l'espansione della macro entrerebbe in un ciclo, proprio come una funzione ricorsiva scritta in modo improprio.

Answer 3

Alla risposta di Kilan aggiungo che lo macroexpand non deve produrre un'espansione completa di tutte le macro nel modulo, finché non rimane alcuna macro :) Se si guarda Hyperspec, vedrai, che valuta il modulo intero fino a quando non è una macro (nel tuo caso si ferma a if). E durante la compilazione tutte le macro vengono espanse, come se macroexpand fosse applicato a ciascun elemento dell'albero di origine, non solo alla sua radice.

Answer 4

Un'altra cosa da aggiungere: nel tuo esempio, l'occorrenza di sum-int-seq all'interno della macro è all'interno di un'espressione quotata, quindi non viene espansa quando viene valutata la macro. Sono solo dati finché non viene chiamata la macro. E poiché è annidato all'interno di un cond, in fase di esecuzione la macro interna viene chiamata solo quando la condizione è vera, come in una funzione normale.

Answer 5

Ecco un'implementazione che funziona:

(defmacro sum-int-seq (n) 
    (cond 
    ((equal 0 n) `0) 
    (t `(+ ,n (sum-int-seq ,(- n 1)))))) 

È possibile scrivere una macro ricorsiva, ma (come è stato detto), l'espansione deve essere in grado di colpire il caso base in fase di compilazione. Quindi i valori di tutti gli argomenti passati alla macro devono essere noti al momento della compilazione.

(sum-int-seq 5) 

Works, ma

(sum-int-seq n) 

non lo fa.