Можно ли переписать рекурсивную функцию как макрос в lisp? - PullRequest
Новая
       25

Можно ли переписать рекурсивную функцию как макрос в lisp?

4 голосов
/ 20 января 2010

Я написал эту функцию быстрой сортировки: 

(defun quicksort (lst)
  (if (null lst)
      nil
      (let ((div  (car lst))
            (tail (cdr lst)))
        (append (quicksort (remove-if-not (lambda (x) (< x div)) tail))
                (list div)
                (quicksort (remove-if     (lambda (x) (< x div)) tail))))))

но я не могу переписать его как макрос, он не работает, и, например, этот простой foo (рекурсивная сумма - я знаю, немного глупо, но в качестве примера): 

(defun Suma (lst)
  (if (cdr lst) 
      (+ (Suma (cdr lst))
         (car lst))
      (car lst)))

работает нормально, но макрос: 

(defmacro SumaMacro (lst)
  '(if (cdr lst)
       '(+ (prog (SUMAMACRO (cdr lst)))
           (prog (car lst)))
       '(car lst)))

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

Ответы [ 2 ]

4 голосов
/ 21 января 2010

Вы смешиваете макрос и время выполнения; или, другими словами, вы смешиваете значения и синтаксис. Вот очень простой пример: 

(defmacro while (condition &body body)
  `(when ,condition ,@body (while ,condition ,@body)))

Плохая вещь в том, что макрос не выполняет тело, он просто создает фрагмент кода с заданным телом в нем. Таким образом, когда в функции есть такой цикл, он защищен условным кодом типа if, который предотвращает бесконечный цикл. Но в этом макрокоде такого условия нет - вы можете видеть, что макрос раскрывается в точную исходную форму, что означает, что он пытается развернуться в какой-то бесконечный фрагмент кода. Это как если бы вы написали 

(defun foo (blah)
  (cons 1 (foo blah)))

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

4 голосов
/ 21 января 2010

Нет смысла писать рекурсивные функции, такие как SUM или QUICKSORT, в качестве макросов. Кроме того, нет, в целом это невозможно. Макрос расширяет исходный код. Во время компиляции макрос видит только исходный код, но не реальные аргументы, с которыми вызывается код. После компиляции макрос исчезает и заменяется кодом, который он производит. Этот код затем вызывается с аргументами. Поэтому макрос не может выполнять вычисления во время компиляции, основываясь на значениях аргументов, которые известны только во время выполнения.

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

Практическое правило. Если вы хотите выполнять рекурсивные вычисления, используйте функции. Если вы хотите обработать исходный код, используйте макрос.

Также попробуйте использовать форматирование, подобное Лиспу. Редактор считает скобки, делает подсветку и отступ. Не ставьте скобки в свои строки, они чувствуют себя одинокими. Обычный стиль Lisp более компактен и больше использует горизонтальное пространство. Если вы работаете со списками, используйте FIRST и REST вместо CAR и CDR.

Ваша функция 'suma' будет выглядеть так: 

(defun suma (list) 
  (if (rest list)
      (+ (suma (rest list))
         (first list))
    (first list)))

Забудьте о макросе. Но, если вы хотите узнать больше о макросах, то книга Пола Грэма « On Lisp » (доступна для скачивания) является хорошим источником знаний.

...