在方案中习惯上避免递归限制

Question

请注意，我正在使用为我的学校定制的方案实现，因此功能可能看起来并不熟悉，并且您的解决方案可能无法直接使用。我正在寻找一种通用方法。

我有一个递归的宏，它演化了一个L系统。基本上，它看起来像这样：

(evolve lsys A A < A < B > B > A < B > B)
;; (lsys A A A A < A A < A < B > B > A < B > B > A A < A < B > B > A < B > B)

因此，我构建了一个本质上可以做到这一点的宏：

(evolve-n 3 lsys ...)
;; (evolve evolve evolve lsys ....)

现在的问题是，这个列表很快就会变得非常大。经过五次演变，我已经超过了递归限制。我可以增加堆栈大小，但实际上不能这样做，因为我可能需要发展数十次。

进化工作的方式是采用各种参量，其中第一个是有条件地进行比较，然后附加到列表其余部分上调用进化的结果。像这样的东西：

(define-macro (evolve (variadic ls))
    (if (eq? ls '())
        '()
        (let ((l (car ls)))
            (append 
                (cond ((eq? l 'A) '(A A))
                      ((eq? l 'B) '(A < B > B))
                      (else (list l)))
                (apply evolve (cdr ls))))))

所以我如何解开这类东西，使其以迭代方式而不是递归地起作用？

Answer 1

听起来您可能正在使用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))))))))

调用此过程的宏是可变的。因为宏用于创建要评估的
forms

，所以此宏必须创建的不是列表，而是一个求值列表的表单。准引号用于将可变参量的列表传递给助手，而准引号用于创建最终形式以求出一个列表。

(define-macro (evolve . xs)
  `(quote ,(evolve-helper `,xs '())))

根据文档，所有这些都应在CS 61A实施中起作用。但是，如果您愿意：
(define-macro (evolve-2 (variadic xs))
  (quasiquote (quote (unquote (evolve-helper (quasiquote (unquote 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)