Как рекурсивные макроопределения оцениваются

Question

Это рекурсивное определение макроса делает то, что должно (сумма целых чисел от 1 до n):

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

Например (sum-int-seq 5) дает 15.

Но почему это работает? Когда макрос раскрывается, я получаю это:

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

Но поскольку sum-int-seq является макросом, оценка макроса должна стать бесконечным циклом. Создает ли компилятор рекурсивную функцию вместо этого? Если это определение создает рекурсивную функцию, есть ли способ определить макросы рекурсивно?

(Для краткости это глупый пример, функция, конечно, будет работать лучше для этого)

Answer 1

Ваш пример не работает.

Может работать в переводчике. Но с компилятором вы увидите бесконечный цикл во время компиляции.

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

Давайте использовать интерпретатор LispWorks:

CL-USER 24 > (test :foo)
15

Давайте попробуем скомпилировать функцию:

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.

Итак, теперь следующий вопрос: почему он работает в интерпретаторе, но компилятор не может его скомпилировать?

Хорошо, я объясню.

Давайте сначала посмотрим на переводчика.

• видит (sum-int-seq 5).
• макрос расширяет его до (COND ((EQUAL 0 5) 0) (T (+ 5 (SUM-INT-SEQ (- 5 1))))).
• Затем он оценивает форму выше. Он определяет, что ему нужно вычислить (+ 5 (SUM-INT-SEQ (- 5 1))). Для этого нужно макроэкспандировать (SUM-INT-SEQ (- 5 1)).
• в конце концов он расширится до (cond ((EQUAL 0 (- (- (- (- (- 5 1) 1) 1) 1) 1)) 0) .... Который затем вернет 0, и вычисление может использовать этот результат и добавить к нему другие условия.

Интерпретатор берет код, оценивает, что он может, и при необходимости расширяет макрос. Сгенерированный код затем оценивается или расширяется макросом. И так далее.

Теперь давайте посмотрим на компилятор.

• он видит (sum-int-seq 5) и макрос расширяет его до (COND ((EQUAL 0 5) 0) (T (+ 5 (SUM-INT-SEQ (- 5 1))))).
• теперь макроразложение будет выполнено для подчиненных форм, в конце концов.
• компилятор будет макроэкспандировать (SUM-INT-SEQ (- 5 1)). обратите внимание, что код никогда не оценивается, только раскрывается.
• компилятор будет макроэкспандировать (SUM-INT-SEQ (- (- 5 1) 1)) и так далее. наконец, вы увидите переполнение стека.

Компилятор просматривает (рекурсивно компилирует / расширяет) код. Он может не выполнять код (если он не выполняет оптимизацию или макрос не выполняет его явно).

Для рекурсивного макроса вам нужно будет вести обратный отсчет. Если вы используете eval внутри макроса, то что-то вроде (sum-int-seq 5) может работать. Но для (defun foo (n) (sum-int-seq n)) это безнадежно, так как компилятор не знает, каково значение n.

Answer 2

Еще одна вещь, которую нужно добавить: в вашем примере вхождение sum-int-seq внутри макроса находится внутри выражения в кавычках, поэтому оно не раскрывается при оценке макроса.Это просто данные, пока не будет вызван макрос.А поскольку он вложен в cond, во время выполнения внутренний макрос вызывается только тогда, когда условие истинно, так же, как в обычной функции.

Answer 3

Вот реализация, которая работает:

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

Можно написать рекурсивный макрос, но (как уже упоминалось), расширение должно быть в состоянии достичь базового варианта во время компиляции. Поэтому значения всех аргументов, передаваемых макросу, должны быть известны во время компиляции.

(sum-int-seq 5)

Работает, но

(sum-int-seq n)

Не.

Answer 4

К ответу Килана я бы добавил, что macroexpand не должен производить полное раскрытие всех макросов в вашей форме, пока не останется макросов :) Если вы посмотрите на Hyperspec , вы увидите, что он оценивает целую форму, пока не станет макросом (в вашем случае он останавливается на if).А во время компиляции все макросы раскрываются, как если бы macroexpand был применен к каждому элементу исходного дерева, а не только к его корню.

Answer 5

Расширение макроса генерирует код Lisp, который затем оценивается. Вызов функции переводит поток выполнения в копию существующего кода LISP, который затем запускается. Кроме того, они очень похожи, и рекурсия работает аналогичным образом. В частности, раскрытие макроса останавливается по той же причине, по которой останавливается правильно написанная рекурсивная функция: потому что существует условие завершения, и преобразование между одним вызовом и следующим было записано так, что это условие фактически достигается. Если бы оно не было достигнуто, расширение макроса вошло бы в цикл, как неправильно написанная рекурсивная функция.