Макрос evolve
Похоже, вы можете использовать CS 61A Scheme реализацию.
В принципе, что вы следует переместить работу из макроса в вспомогательную процедуру, которая затем вызывается из макроса .
Вспомогательная процедура должна использовать аккумулятор для хранения результатов, чтобы рекурсивные вызовы в хвостовой позиции, обеспечивая итеративный процесс; каждый раз, когда вызывается вспомогательная процедура, новый список символов append редактируется до конца аккумулятора, но больше нет работы, когда процедура возвращается.
(define (evolve-helper xs acc)
(if (null? xs)
acc
(let ((x (car xs)))
(evolve-helper (cdr xs)
(append acc
(cond ((eq? x 'A) '(A A))
((eq? x 'B) '(A < B > B))
(else (list x))))))))
Макрос, который вызывает эту процедуру variadi c. Поскольку макросы используются для создания форм для оценки, этот макрос должен создавать не список, а форму, которая оценивает список. Квазиквотация используется для создания окончательной формы, которая оценивается как список.
(define-macro (evolve . xs)
`(quote ,(evolve-helper xs '())))
Все это должно работать в реализации CS 61A, согласно документации. Но, если вы предпочитаете:
(define-macro (evolve-2 (variadic xs))
(quasiquote (quote (unquote (evolve-helper xs '())))))
Пример взаимодействия REPL:
scheme@(guile-user)> (evolve lsys A A < A < B > B > A < B > B)
$8 = (lsys A A A A < A A < A < B > B > A < B > B > A A < A < B > B > A < B > B)
scheme@(guile-user)> (evolve-2 lsys A A < A < B > B > A < B > B)
$9 = (lsys A A A A < A A < A < B > B > A < B > B > A A < A < B > B > A < B > B)
Макрос evolve-n
Вспомогательная процедура также должна использоваться с evolve-n. Этому помощнику не нужно вызывать макрос evolve, а вместо этого вызывается процедура evolve-helper. Рекурсивный вызов evolve-n находится в хвостовой позиции, так что это итеративный процесс; каждый вызов просто передает развитый список аргументов следующему.
(define (evolve-n-helper n xs)
(if (zero? n)
xs
(evolve-n-helper (- n 1)
(evolve-helper xs '()))))
(define-macro (evolve-n n . xs)
`(quote ,(evolve-n-helper n xs)))
Вы можете избежать вспомогательной процедуры, используя eval в макросе evolve-n, но использование eval - плохой стиль когда процедура будет делать то же самое.
(define-macro (evolve-n-2 n . xs)
(if (zero? n)
`(quote ,xs)
`(evolve-n-2 ,(- n 1) ,@(eval `(evolve ,@xs) (interaction-environment)))))
Пример взаимодействия REPL:
scheme@(guile-user)> (evolve-n 0 lsys A A < A < B > B > A < B > B)
$6 = (lsys A A < A < B > B > A < B > B)
scheme@(guile-user)> (evolve-n 1 lsys A A < A < B > B > A < B > B)
$7 = (lsys A A A A < A A < A < B > B > A < B > B > A A < A < B > B > A < B > B)
scheme@(guile-user)> (evolve-n 2 lsys A A < A < B > B > A < B > B)
$8 = (lsys A A A A A A A A < A A A A < A A < A < B > B > A < B > B > A A < A < B > B > A < B > B > A A A A < A A < A < B > B > A < B > B > A A < A < B > B > A < B > B)
scheme@(guile-user)> (evolve-n-2 2 lsys A A < A < B > B > A < B > B)
$9 = (lsys A A A A A A A A < A A A A < A A < A < B > B > A < B > B > A A < A < B > B > A < B > B > A A A A < A A < A < B > B > A < B > B > A A < A < B > B > A < B > B)
Проблемы производительности
Процедура append дорогой, и с определением evolve-helper выше, эта дорогая процедура вызывается при каждом рекурсивном вызове. Это складывается, когда ввод становится большим. В частности, при десяти изменениях ввода примера OP в (evolve-n 10 lsys A A < A < B > B > A < B > B) существует значительная задержка до получения результатов. Поскольку OP заявляет, что « мне нужно развить это, возможно, в десятки раз », эта задержка является реальной проблемой.
Ситуацию можно улучшить, если вывести append из итерационного процесса. , Поскольку cons намного дешевле, мы можем использовать cons для добавления подсписков в начало аккумулятора вместо добавления их в конец. Когда базовый случай достигнут, аккумулятор должен быть полностью изменен, прежде чем append объединит все подсписки вместе для окончательного результата. В неофициальных тестах эта улучшенная процедура привела к ускорению примерно в 10 раз по сравнению с первоначальным определением; результат от (evolve-n 10 lsys A A < A < B > B > A < B > B) прибыл в доли секунды. Это также показывает, почему лучше перенести как можно больше работы из макросов в функции; Макросы сложнее написать, и на 10 * 10 больше, чем обычные функции. Выполнение необходимых оптимизаций здесь было упрощено за счет использования макросов только там, где это необходимо, и функций в других местах.
(define (evolve-helper xs acc)
(if (null? xs)
(apply append (reverse acc))
(let ((x (car xs)))
(evolve-helper (cdr xs)
(cons (cond ((eq? x 'A) '(A A))
((eq? x 'B) '(A < B > B))
(else (list x)))
acc)))))
Решение только для макросов
Макрос evolve может Избегайте пользовательских внешних вспомогательных функций и явной рекурсии в целом, отображая процедуру, которая применяет правила преобразования ко входу.
(define-macro (evolve . xs)
`(quote ,(apply append (map (lambda (x) (cond ((eq? x 'A) '(A A))
((eq? x 'B) '(A < B > B))
(else (list x))))
xs))))
Это кажется хорошим решением, но в настоящий момент я не вижу прямого пути использовать это определение в макросе evolve-n, если не используется eval.
(define-macro (evolve-n n . xs)
(if (zero? n)
`(quote ,xs)
`(evolve-n ,(- n 1) ,@(eval `(evolve ,@xs) (interaction-environment)))))
Несколько неформальных тестов с использованием (evolve-n 15 lsys A A < A < B > B > A < B > B) показали, что обе версии, одна с использованием вспомогательных функций и одна с использованием только макроса определения, имели неразличимые характеристики; обе задачи заняли от 20 до 24 секунд. В отсутствие какого-либо существенного преимущества в производительности, я бы остановился на более простой версии вспомогательных функций evolve-n. Или я бы пересмотрел, как должны выглядеть входы и выходы; почему бы просто не взять список символов непосредственно для ввода?