Лисп: может ли макрос быть рекурсивным? - PullRequest
Новая
       10

Лисп: может ли макрос быть рекурсивным?

8 голосов
/ 14 ноября 2011

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

Относительно оптимизации: я посыпал аннотации типов (много "fixnum") в том же коде.Как только я добавил 3 или 4 из них, я понял, что делаю это неправильно - для этого и нужны макросы, не повторяйте себя ... 

; whenever we want to indicate that the result of an operation 
; fits in a fixnum, we macro expand (the fixnum (...))
(defmacro fast (&rest args)
  `(the fixnum ,args))
...
(cond
  (...)
  (t (let* ((forOrange (+ (aref counts 5)
                          (fast * 2 (aref counts 6))
                          (fast * 5 (aref counts 7))
                          (fast * 10 (aref counts 8))))
            (forYellow (+ (aref counts 3)
                          (fast * 2 (aref counts 2))
                          (fast * 5 (aref counts 1))
                          (fast * 10 (aref counts 0))))

... и действительно, это сработало:вместо того, чтобы писать много "(fixnum (...))" везде, я просто быстро добавляю к выражению выражение "fast" - и все хорошо.

Но тогда ...

Я понял, что даже это не то, где все должно останавливаться: в принципе, макрос "быстрый" должен ... вызываться в начале оценки, в этом случае: 

            (forYellow (fast + (aref counts 3)
                          (* 2 (aref counts 2))
                          (* 5 (aref counts 1))
                          (* 10 (aref counts 0))))

...и он должен рекурсивно «насаживать» (fixnum (...)) »во всех подвыражениях.

Можно ли это сделать?Может ли "defmacro" быть рекурсивным?

ОБНОВЛЕНИЕ : я столкнулся с некоторыми действительно странными проблемами, пытаясь это сделать, поэтому я закончил делать то, что предложил Рорд ниже - то есть реализовал функцию, протестировал еев ответе и вызывая его из макроса: 

(defun operation-p (x)
  (or (equal x '+) (equal x '-) (equal x '*) (equal x '/)))

(defun clone (sexpr)
  (cond
    ((listp sexpr)
     (if (null sexpr)
       ()
       (let ((hd (car sexpr))
             (tl (cdr sexpr)))
         (cond
           ((listp hd) (append (list (clone hd)) (clone tl)))
           ((operation-p hd) (list 'the 'fixnum (cons hd (clone tl))))
           (t (cons hd (clone tl)))))))
    (t sexpr)))

(defmacro fast (&rest sexpr)
  `(,@(clone sexpr)))

И он работает нормально при SBCL: 

$ sbcl
This is SBCL 1.0.52, an implementation of ANSI Common Lisp.
...
* (load "score4.cl")

T
* (setf a '(+ (1 2) (- 1 (+ 5 6)))
...
* (clone a)

(THE FIXNUM (+ (1 2) (THE FIXNUM (- 1 (THE FIXNUM (+ 5 6))))))

* (macroexpand '(fast + 1 2 THE FIXNUM (- 1 THE FIXNUM (+ 5 6))))

(THE FIXNUM (+ 1 2 THE FIXNUM (THE FIXNUM (- 1 THE FIXNUM (THE FIXNUM (+ 5 6))))))
T

Все хорошо, кроме одного побочного эффекта: CMUCL работает,но больше не компилирует код: 

; Error: (during macroexpansion)
; Error in KERNEL:%COERCE-TO-FUNCTION:  the function CLONE is undefined.

Ну хорошо: -)

ОБНОВЛЕНИЕ : ошибка компиляции была решена и решена в другой вопрос SO.

Ответы [ 3 ]

6 голосов
/ 15 ноября 2011

Макрос не только вызывается, но и расширяется при использовании, поэтому обращение к макросу в его собственном определении может привести к путанице.Но вам не нужно этого делать: макросы могут вызывать обычные функции, поэтому вы можете написать обычную функцию для обработки рекурсивного списка, а затем просто использовать это из макроса.

6 голосов
/ 22 марта 2012

Вы определенно можете написать макрос, который использует себя в своем собственном расширении.Это имеет смысл, и это естественный способ написания макроса COND, который имеет регулярную расширяющуюся структуру из-за произвольно длинного списка пар cond, который может быть выражен обычной рекурсией car / cdr или first / rest.

(defmacro new-cond (&rest cond-pairs)
  (cond      ;; you need cond to compile new-cond syntax, LOL!
    ((null cond-pairs) nil)
    ((atom cond-pairs) (error "new-cond: bad syntax!"))
    (t `(if ,(first (first cond-pairs))
           (progn ,@(rest (first cond-pairs)))
           (new-cond ,@(rest cond-pairs))))))


> (macroexpand-1 '(new-cond (1 2) (3 4)))

(IF 1 (PROGN 2) (NEW-COND (3 4)))

Это очень похоже на ленивую обработку списка.macroexpand расширяет только внешний макрос, оставляя объект "обещание" для продолжения расширения.Этот объект "обещания" - это макро-вызов (NEW-COND (3 4)) в хвосте.

Конечно, настоящий макроэкспандер будет обходить всю форму и "форсировать" все эти обещания (нерасширенные макро-вызовы) до тех пор, пока больше не останется.

Я думаю, что у этого стиля есть некоторые преимущества, такие как легкая отладка с macroexpand.Вы получаете небольшое расширение.Если его рекурсивный характер очевиден, это победа.Если макрос таков, что ваш мозг должен видеть, что все это расширено, это потеря.

Здесь я вижу, что (IF 1 (PROGN 2) (NEW-COND (3 4))) - правильная компиляция.Если 1 верно, оцените список форм (2).В противном случае продолжайте идти с другими парами cond.Теперь мы должны проверить случай с одной парой: 

> (macroexpand-1 '(new-cond (3 4)))
(IF 3 (PROGN 4) (NEW-COND))

Отлично, а случай без пары (NEW-COND), по очевидной проверке, сводится к нулю.

6 голосов
/ 14 ноября 2011

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

Quicklisp включает hu.dwim.walker, который, по-видимому, является улучшенной версией arnesi кодового обходчика.

...