惯用地避免方案中的递归限制
Idiomatically avoiding recursion limit in scheme
请注意，我使用的是为我的学校定制的方案实现，因此功能可能看起来不熟悉，您的解决方案可能无法直接工作。我正在寻找一种通用方法。
我有一个演化 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 ....)
现在的问题是，这个列表很快就会变得非常大。经过仅仅五次演变，我已经超过了递归限制。我可以只增加堆栈大小，但实际上不行，因为我需要将其演化数十次。
evolve 的工作方式是采用可变数量的参数，第一个参数有条件地进行比较，然后附加到对列表的其余部分调用 evolve 的结果。像这样：
(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))))))
那么我怎样才能解开这种类型的东西，使其迭代而不是递归地工作？
evolve 宏
听起来您可能正在使用 CS 61A Scheme 实现。
原则上，您应该做的是将工作从宏中移出到辅助程序，然后从宏中调用。
辅助过程应该使用累加器来存储结果，以便递归调用在尾部位置，提供迭代过程；每次调用辅助过程时，一个新的符号列表 appended 到累加器的末尾，但是当过程 returns.
时没有更多的工作要做
(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))))))))
调用此过程的宏是可变的。由于宏用于创建要计算的 表单 ，因此该宏必须创建的不是列表，而是计算为列表的表单。 Quasiquotation 用于创建计算结果为列表的最终形式。
(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)
= (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)
= (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)))
您可以通过在 evolve-n 宏中使用 eval 来避免辅助过程，但是使用 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)
= (lsys A A < A < B > B > A < B > B)
scheme@(guile-user)> (evolve-n 1 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)
scheme@(guile-user)> (evolve-n 2 lsys A A < A < B > B > A < B > B)
= (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)
= (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 的定义，这个昂贵的过程在每次递归调用时都会被调用。当输入变大时，这会加起来。特别是，在 (evolve-n 10 lsys A A < A < B > B > A < B > B) 中输入 OP 示例的十个演变在结果到达之前有一个显着的延迟。由于 OP 声明“我可能需要将其进化数十次”，因此这种延迟是一个真正的问题。
可以通过将 append 移出迭代过程来改善这种情况。由于 cons 更便宜，我们可以使用 cons 将子列表添加到累加器的前面，而不是将它们附加到末尾。当达到基本情况时，必须先反转累加器，然后 append 将所有子列表组合在一起以获得最终结果。在非正式测试中，与原始定义相比，这个改进的程序导致加速大约 10 倍； (evolve-n 10 lsys A A < A < B > B > A < B > B) 的结果在不到一秒的时间内到达。这也说明了为什么最好将尽可能多的工作从宏中转移到函数中；宏比常规函数更难编写，也更脆弱。通过仅在需要的地方使用宏，在其他地方使用函数，简化了此处进行必要的优化。
(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 的更简单的辅助函数版本。或者我会重新考虑输入和输出应该是什么样子；为什么不直接将符号列表作为输入？
请注意，我使用的是为我的学校定制的方案实现，因此功能可能看起来不熟悉，您的解决方案可能无法直接工作。我正在寻找一种通用方法。
我有一个演化 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 ....)
现在的问题是，这个列表很快就会变得非常大。经过仅仅五次演变，我已经超过了递归限制。我可以只增加堆栈大小，但实际上不行，因为我需要将其演化数十次。
evolve 的工作方式是采用可变数量的参数，第一个参数有条件地进行比较，然后附加到对列表的其余部分调用 evolve 的结果。像这样：
(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))))))
那么我怎样才能解开这种类型的东西，使其迭代而不是递归地工作？
evolve 宏
听起来您可能正在使用 CS 61A Scheme 实现。
原则上，您应该做的是将工作从宏中移出到辅助程序，然后从宏中调用。
辅助过程应该使用累加器来存储结果，以便递归调用在尾部位置，提供迭代过程；每次调用辅助过程时，一个新的符号列表 appended 到累加器的末尾，但是当过程 returns.
(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))))))))
调用此过程的宏是可变的。由于宏用于创建要计算的 表单 ，因此该宏必须创建的不是列表，而是计算为列表的表单。 Quasiquotation 用于创建计算结果为列表的最终形式。
(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)
= (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)
= (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)))
您可以通过在 evolve-n 宏中使用 eval 来避免辅助过程，但是使用 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)
= (lsys A A < A < B > B > A < B > B)
scheme@(guile-user)> (evolve-n 1 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)
scheme@(guile-user)> (evolve-n 2 lsys A A < A < B > B > A < B > B)
= (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)
= (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 的定义，这个昂贵的过程在每次递归调用时都会被调用。当输入变大时，这会加起来。特别是，在 (evolve-n 10 lsys A A < A < B > B > A < B > B) 中输入 OP 示例的十个演变在结果到达之前有一个显着的延迟。由于 OP 声明“我可能需要将其进化数十次”，因此这种延迟是一个真正的问题。
可以通过将 append 移出迭代过程来改善这种情况。由于 cons 更便宜，我们可以使用 cons 将子列表添加到累加器的前面，而不是将它们附加到末尾。当达到基本情况时，必须先反转累加器，然后 append 将所有子列表组合在一起以获得最终结果。在非正式测试中，与原始定义相比，这个改进的程序导致加速大约 10 倍； (evolve-n 10 lsys A A < A < B > B > A < B > B) 的结果在不到一秒的时间内到达。这也说明了为什么最好将尽可能多的工作从宏中转移到函数中；宏比常规函数更难编写，也更脆弱。通过仅在需要的地方使用宏，在其他地方使用函数，简化了此处进行必要的优化。
(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 的更简单的辅助函数版本。或者我会重新考虑输入和输出应该是什么样子；为什么不直接将符号列表作为输入？