Как написать рекурсивный вызов макроса для параметра & REST в Лиспе? - PullRequest
6 голосов
/ 10 февраля 2010

Я написал несколько простых тестовых примеров для одного из моих заданий и создал небольшой набор тестов с использованием макросов. У меня есть run-test и run-test-section и так далее. Я бы хотел, чтобы run-test-section взял ряд параметров, которые были вызваны run-test, и подсчитал количество ПРОЙДОВ и НЕИСПРАВНОСТЕЙ.

run-test возвращает T на PASS и NIL на FAIL.

Что я сейчас хочу сделать, так это написать макрос, который принимает параметр &REST и вызывает каждый из элементов этого списка, в конце концов возвращая количество ИСТИННЫХ значений.

Это то, что у меня сейчас есть:

(defmacro count-true (&rest forms)
`(cond
    ((null ,forms)
      0)
    ((car ,forms)
      (1+ (count-true (cdr ,forms))))
    (T
      (count-true (cdr ,forms)))))

Однако это помещает мой REPL в бесконечный цикл. Может кто-нибудь сможет указать, как я могу более эффективно манипулировать аргументами. Это даже хорошая идея? Есть ли лучший подход?

редактирование:

Как отмечается в ответах, в этом случае макрос не нужен. Использование встроенного COUNT будет достаточно. Однако в ответах на рекурсивные вызовы макросов содержится полезная информация.

Ответы [ 6 ]

5 голосов
/ 10 февраля 2010

Во время раскрытия макроса cdr не оценивается. Итак, (count-true t t nil) достигает бесконечного расширения, как это:

(count-true t t nil)
=>
(1+ (count-true (cdr (t t t nil))))
=>
(1+ (1+ (count-true (cdr (cdr (t t t nil))))))
=>
(1+ (1+ (1+ (count-true (cdr (cdr (cdr (t t t nil))))))))
=> ...

Ну, на самом деле это происходит одновременно для обеих рекурсивных ветвей. Так что взрывается даже быстрее, чем в примере.

Лучшая идея?

  1. Попытка сначала написать то же самое, что и функция. Выясните, где вы должны положить лямбды, чтобы отложить оценку. Затем абстрагируйте функцию в макрос, чтобы вы могли исключить лямбды.

    Кстати, смысл сначала писать функцию в том, что иногда вы обнаружите, что функция достаточно хороша. Написание макроса, в котором выполнялась бы функция, является ошибкой.

  2. Обычно, когда вы пишете макросы в Common Lisp, начинайте с loop, а не с рекурсией. Рекурсивные макросы хитры (и обычно ошибочны :).

Edit:

Вот более правильный (но гораздо более длинный) пример:

(count-true t nil) =>
(cond
  ((null '(t nil)) 0)
  ((car '(t nil)) (1+ (count-true (cdr '(t nil)))))
  (T (count-true (cdr '(t nil)))))
=>
(cond
  ((null '(t nil)) 0)
  ((car '(t nil)) (1+ (1+ (count-true (cdr (cdr '(t nil)))))))
  (T (count-true (cdr (cdr '(t nil))))))
=>
(cond
  ((null '(t nil)) 0)
  ((car '(t nil)) (1+ (1+ (1+ (count-true (cdr (cdr (cdr '(t nil)))))))))
  (T (count-true (cdr (cdr (cdr '(t nil)))))))
=>
(cond
  ((null '(t nil)) 0)
  ((car '(t nil)) (1+ (1+ (1+ (1+ (count-true (cdr (cdr (cdr (cdr '(t nil)))))))))))
  (T (count-true (cdr (cdr (cdr (cdr '(t nil))))))))
4 голосов
/ 10 февраля 2010

Забудьте рекурсивные макросы.Они трудны и действительно только для опытных пользователей Lisp.

Простая нерекурсивная версия:

(defmacro count-true (&rest forms)
  `(+
    ,@(loop for form in forms
            collect `(if ,form 1 0))))

CL-USER 111 > (macroexpand '(count-true (plusp 3) (zerop 2)))
(+ (IF (PLUSP 3) 1 0) (IF (ZEROP 2) 1 0))

Ну, вот рекурсивный макрос:

(defmacro count-true (&rest forms)
  (if forms
      `(+ (if ,(first forms) 1 0)
          (count-true ,@(rest forms)))
    0))
3 голосов
/ 10 февраля 2010

Проблема в том, что ваш макрос расширяется до бесконечной формы. Система попытается развернуть все это на этапе расширения макроса и, следовательно, должна исчерпать память.

Обратите внимание, что тест конца списка форм никогда не оценивается, а выражается в виде кода. Это должно быть за пределами выражения обратного удара. И, как объяснил другой человек, (формы cdr) нужно оценивать также во время расширения макроса, а не оставлять как код для компиляции.

т.е. что-то вроде этого (не проверено):

(defmacro count-true (&rest forms)
  (if forms
      `(if (car ',forms)
           (1+ (count-true ,@(cdr forms)))
         (count-true ,@(cdr forms)))
    0))
2 голосов
/ 10 февраля 2010

Я полагаю, что у вас есть два ложных представления о том, что такое макросы.

Макросы написаны для расширения, функции для исполнения. Если вы напишите рекурсивный макрос, он будет рекурсивно раскрываться, не выполняя ничего из кода, который он производит. Макрос совсем не что-то вроде встроенной функции!

Когда вы пишете макрос, он может расширяться до вызовов функций. Когда вы пишете макрос, вы не рискуете в «страну земель», где функции были бы недоступны. Нет смысла писать count-true как макрос.

1 голос
/ 17 мая 2017

Это хорошее приложение для простой макрорекурсии:

(defmacro count-true (&rest forms)
  (cond
    ((null forms) 0)
    ((endp (rest forms)) `(if ,(first forms) 1 0))
    (t `(+ (count-true ,(first forms)) (count-true ,@(rest forms))))))

Тесты:

[2]> (count-true)
0
[3]> (count-true nil)
0
[4]> (count-true t)
1
[5]> (count-true nil t)
1
[6]> (count-true t nil)
1
[7]> (count-true t t)
2
[8]> (count-true nil nil)
0
[9]> (macroexpand '(count-true))
0 ;
T
[10]> (macroexpand '(count-true x))
(IF X 1 0) ;
T
[11]> (macroexpand '(count-true x y))
(+ (COUNT-TRUE X) (COUNT-TRUE Y)) ;
T
[12]> (macroexpand '(count-true x y z))
(+ (COUNT-TRUE X) (COUNT-TRUE Y Z)) ;
T

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

Вы сразу же ошибаетесь, когда делаете это:

`(cond ((null ,forms ...) ...)

вы вводите метасинтаксический расчет (сколько форм у нас в синтаксисе?) В шаблон сгенерированного кода, который будет оцениваться во время выполнения. У вас есть правильные части в этом базовом случае, но они поставлены неправильно. В моем решении у меня есть cond только в самом теле макроса, а не в обратной кавычке:

(cond ((null forms) ...) ...)

В основном:

(cond (<if the syntax is like this> <generate this>)
      (<if the syntax is like that> <generate that>)
      ...)

Если вы не знаете, что делать, напишите код, который вы хотите написать в макросе. Например:

;; I want this semantics:
(if (blah) 1 0)   ;; count 1 if (blah) is true, else 0

;; But I want it with this syntax:
(count-true (blah))

Хорошо, для этого точного случая мы напишем:

(defmacro count-true (single-form)
  `(if ,single-form 1 0))

Готово! Теперь предположим, что мы хотим поддерживать (count-true) без форм.

Wanted Syntax                   Translation

(count-true)                    0
(count-true x)                  (if x 1 0)

Когда есть форма, расширение if остается, но когда форм нет, нам просто нужен постоянный ноль. Легко, сделайте аргумент необязательным:

(defmacro count-true (&optional (single-form nil have-single-form))
   (if have-single-form
     `(if ,single-form 1 0)  ;; same as before
      0))                    ;; otherwise zero

Наконец, распространяем на N-арную форму:

Wanted Syntax                   Translation

(count-true)                    0
(count-true x)                  (if x 1 0)
(count-true x y)                (+ (if x 1 0) (if y 1 0))
                                   ^^^^^^^^^^ ^^^^^^^^^^

Но! Теперь отметим, что подчеркнутые термины соответствуют выводу одного случая.

(count-true x y)                (+ (count-true x) (count-true y))

Что обобщает

(count-true x y z ...)          (+ (count-true x) (count-true y z ...))

Это прямо соответствует шаблону генерации кода с car/cdr рекурсией:

`(+ (count-true ,CAR) (count-true ,*CDR))  
0 голосов
/ 11 февраля 2010

Как уже говорили другие, избегайте рекурсивных макросов. Если вы хотите сделать это в функции, вы можете использовать apply:

(defun count-true (&rest forms)
  (cond
    ((null forms) 0)
    (t (+ 1 (apply #'count-true (cdr forms))))))
...