¿Cómo se evalúan las definiciones de macros recursivas

Question

Esta definición recursiva de una macro hace lo que debe (suma enteros de 1 a N):

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

Por ejemplo (sum-int-seq 5) da 15.

Pero ¿por qué lo hace ¿trabajo? Cuando la macro se expandió me sale esto:

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

Pero debido suma-int-ss es una macro macro la evaluación debe convertirse en un bucle infinito. ¿El compilador crea una función recursiva en su lugar? Si esta definición crea una función recursiva, ¿hay alguna manera de definir macros recursivamente?

(Este es un ejemplo tonto en aras de la brevedad, una función sería, por supuesto funcionar mejor para esto)

Answer 1

Su ejemplo no funciona.

Puede funcionar en un intérprete. Pero con un compilador verás un bucle infinito durante la compilación.

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

Usemos el LispWorks intérprete:

CL-USER 24 > (test :foo) 
15 

Vamos a tratar de compilar la función:

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. 

lo tanto, ahora la siguiente pregunta: ¿por qué funciona en el intérprete, pero el compilador no puede compilarlo?

Bien, lo explicaré.

Miremos primero al intérprete.

• ve (sum-int-seq 5).
• macroexpando a (COND ((EQUAL 0 5) 0) (T (+ 5 (SUM-INT-SEQ (- 5 1))))).
• luego evalúa el formulario anterior. Determina que necesita calcular (+ 5 (SUM-INT-SEQ (- 5 1))). Para eso, necesita macroexpandir (SUM-INT-SEQ (- 5 1)).
• finalmente se expandirá en algo así como (cond ((EQUAL 0 (- (- (- (- (- 5 1) 1) 1) 1) 1)) 0) .... Que luego devolverá 0 y el cálculo puede usar este resultado y agregarle los otros términos.

El intérprete toma el código, evalúa lo que puede y macroexpansa si es necesario. El código generado es luego evaluado o macroexpandido. Y así.

Ahora veamos el compilador.

• se ve (suma-int-ss 5) y macroexpands en (COND ((EQUAL 0 5) 0) (T (+ 5 (SUM-INT-SEQ (- 5 1))))).
• ahora la macroexpansión se realizará en los subformularios, eventualmente.
• el compilador macroexpandirá (SUM-INT-SEQ (- 5 1)). tenga en cuenta que el código nunca se evalúa, solo se expande.
• el compilador macroexpandirá (SUM-INT-SEQ (- (- 5 1) 1)) y así sucesivamente. finalmente verá un desbordamiento de pila.

El compilador camina (compila/expande recursivamente) el código. Puede que no ejecute el código (a menos que optimizaciones o una macro realmente lo evalúe de manera explícita).

Para una macro recursiva necesitarás realmente contar hacia atrás. Si evalúa dentro de la macro, algo como (sum-int-seq 5) puede funcionar. Pero para (defun foo (n) (sum-int-seq n)) esto no tiene solución, ya que el compilador no sabe cuál es el valor de n.

Answer 2

Expansión de un macro genera código Lisp que se evalúa a continuación. Llamar a una función desvía el flujo de ejecución a una copia del código de lisp preexistente que luego se ejecuta. Aparte de eso, los dos son bastante similares, y la recursividad funciona de la misma manera. En particular, la macroexpansión se detiene por la misma razón por la que se detiene una función recursiva correctamente escrita: porque hay una condición de terminación, y la transformación entre una llamada y la siguiente se ha escrito para que realmente se alcance esta condición. Si no se alcanza, la macro expansión entraría en un bucle, al igual que una función recursiva escrita incorrectamente.

Answer 3

Para la respuesta de Kilan me gustaría añadir, que macroexpand no tiene que producir una expansión completa de todas las macros en su forma, hasta que no macro izquierda :) Si nos fijamos en Hyperspec, verá, que evalúa el formulario entero hasta que no sea una macro (en su caso se detiene en if). Y durante la compilación, todas las macros se expanden, como si se aplicara macroexpand a cada elemento del árbol fuente, no solo a su raíz.

Answer 4

Otra cosa para agregar: en su ejemplo, la ocurrencia de sum-int-seq dentro de la macro está dentro de una expresión entrecomillada, por lo que no se expande cuando se evalúa la macro. Solo son datos hasta que se llama a la macro. Y dado que está anidado dentro de un cond, en el tiempo de ejecución, la macro interna solo se llama cuando la condición es verdadera, igual que en una función normal.

Answer 5

Aquí es una implementación que hace el trabajo:

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

Es posible escribir una macro recursiva, pero (como se ha mencionado), la expansión debe ser capaz de golpear el caso base en tiempo de compilación. Por lo tanto, los valores de todos los argumentos pasados ​​a la macro deben conocerse en tiempo de compilación.

(sum-int-seq 5) 

Works, pero

(sum-int-seq n) 

no lo hace.