Idiomatically avoiding recursion limit in scheme

Question

Note that I am using a custom implementation of scheme made for my school, so the functions may not look familiar, and your solutions may not work directly. I'm looking more for a generalized method.

I have a recursive macro that evolves an L-system. Basically, it looks something like this:

(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)

And so I've constructed a macro that essentially does this:

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

Now the issue is, this list can get really very large very quickly. After just five evolutions I've exceeded the recursion limit. I could just increase the stack size, but not practically because I need to evolve this perhaps tens of times.

The way that evolve works is takes a variadic number of arguments, the first of which is compared conditionally, and then appended to the result of calling evolve on the rest of the list. Something like this:

(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))))))

So how can I unwrap this type of thing so it works iteratively rather than recursively?

I meant "why is it entirely a macro"? You should be able to have a macro at the "top level" just to avoid evaluation of the arguments and pass them to a regular procedure that does the work. — molbdnilo, May 02 '20 at 11:00

ad absurdum · Accepted Answer · 2020-05-03T17:08:10.693

The `evolve` Macro

It sounds like you may be using the CS 61A Scheme implementation.

In principle, what you should do is move the work out of the macro to a helper procedure which is then called from the macro.

The helper procedure should use an accumulator to store the results so that recursive calls are in tail position, providing an iterative process; each time the helper procedure is called, a new list of symbols is appended to the end of the accumulator, but there is no more work to do when the procedure 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))))))))

The macro that calls this procedure is variadic. Since macros are used to create forms to be evaluated, this macro must create not a list, but a form that evaluates to a list. Quasiquotation is used to create the final form which evaluates to a list.

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

All of this should work in the CS 61A implementation, according to the documentation. But, if you prefer:

(define-macro (evolve-2 (variadic xs))
  (quasiquote (quote (unquote (evolve-helper xs '())))))

Example REPL interaction:

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)

The `evolve-n` Macro

A helper procedure should also be used with evolve-n. This helper does not need to call the evolve macro, but instead calls the evolve-helper procedure. The recursive call to evolve-n is in tail position, so this is an iterative process; each call simply passes an evolved list of arguments to the next.

(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)))

You could avoid the helper procedure by using eval in the evolve-n macro, but it is bad style to use eval when a procedure will do as well.

(define-macro (evolve-n-2 n . xs)
  (if (zero? n)
      `(quote ,xs)
      `(evolve-n-2 ,(- n 1) ,@(eval `(evolve ,@xs) (interaction-environment)))))

Example REPL interaction:

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)

Performance Issues

The append procedure is expensive, and with the definition of evolve-helper above, this expensive procedure is called on every recursive call. This adds up when input gets large. In particular, with ten evolutions of OP example input in (evolve-n 10 lsys A A < A B > A B) there is a significant delay before results arrive. Since OP states that "I need to evolve this perhaps tens of times," this delay is a real issue.

The situation can be improved by moving append out of the iterative process. Since cons is much cheaper, we can use cons to add sublists to the front of the accumulator instead of appending them to the end. When the base case is reached, the accumulator must then be reversed before appending all of the sublists together for the final result. In informal tests this improved procedure led to a speedup of approximately 10x when compared with the original definition; the result from (evolve-n 10 lsys A A < A B > A B) arrived in a fraction of one second. This also illustrates why it is better to move as much work as possible out of macros and into functions; macros are more difficult to write, and more fragile than regular functions. Making the necessary optimizations here was simplified by using macros only where needed, and functions elsewhere.

(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)))))

A Macro-Only Solution

The evolve macro can avoid custom external helper functions and explicit recursion altogether by mapping a procedure that applies the transformation rules over the input.

(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))))

This seems like a nice solution, but at the moment I don't see a straightforward way to use this definition in the evolve-n macro, unless eval is employed.

(define-macro (evolve-n n . xs)
  (if (zero? n)
      `(quote ,xs)
      `(evolve-n ,(- n 1) ,@(eval `(evolve ,@xs) (interaction-environment)))))

Several informal tests using (evolve-n 15 lsys A A < A B > A B) showed that both versions, the one using helper functions and the one using only macro definitions, had indistinguishable performance; both took between 20 and 24 seconds to complete the task. In the absence of any significant performance advantage, I would stick with the simpler helper-function version of evolve-n. Or I would reconsider what inputs and outputs should look like; why not just take a list of symbols directly for input?

it could be interesting to know the orders of growth for the execution time vs the produced list size -- is it linear, quadratic, or what (the WP link's in my profile), esp. with the change from append to cons (which I'd expect to change it from quadratic to about linear). measuring at two size points (with non-negligible run times, say at 12 and at 15) would be quite enough to get a rough [estimate](https://stackoverflow.com/q/24202687/849891) for, say, 20 or 100. :) (Q&A linked as a reference/amusement) — Will Ness, Nov 21 '20 at 13:38

Idiomatically avoiding recursion limit in scheme

1 Answers1

The evolve Macro

The evolve-n Macro

Performance Issues

A Macro-Only Solution

The `evolve` Macro

The `evolve-n` Macro