What's a good way to rewrite this non-tail-recursive function?

Question

For some reason, I am having trouble thinking of a good way to rewrite this function so it uses constant stack space. Most online discussions of tree recursion cheat by using the Fibonacci function and exploiting the properties of that particular problem. Does anyone have any ideas for this "real-world" (well, more real-world than the Fibonacci series) use of recursion?

Clojure is an interesting case since it does not have tail-call optimization, but only tail recursion via the "recur" special form. It also strongly discourages the use of mutable state. It does have many lazy constructs including tree-seq, but I am not able to see how they can help me for this case. Can anyone share some techniques they have picked up from C, Scheme, Haskell, or other programming languages?

(defn flatten [x]
  (let [type (:type x)]
    (cond (or (= type :NIL) (= type :TEXT))
          x
          (= type :CONCAT)
          (doc-concat (flatten (:doc1 x))
                      (flatten (:doc2 x)))
          (= type :NEST)
          (doc-nest (:level x)
                    (flatten (:doc x)))
          (= type :LINE)
          (doc-text " ")
          (= type :UNION)
          (recur (:doc1 x)))))

edit: By request in the comments...

Restated in general terms and using Scheme -- how do I rewrite the following recursion pattern so it doesn't consume stack space or require tail-call optimization of non-self-calls?

(define (frob x)
  (cond ((foo? x)
         x)
        ((bar? x)
         (macerate (f x) (frob (g x))))
        ((thud? x)
         (frobnicate (frob (g x))
                     (frob (h x))))))

I chose annoying names to drive home the point that I am looking for answers that don't rely on the algebraic properties of x, macerate, frobnicate, f, g, or h. I just want to rewrite the recursion.

UPDATE:

Rich Hickey has kindly added an explicit trampoline function to Clojure.

Answer 1

The main hurdle to easily transforming your algorithm is that it doesn't result in a sequence of calls to the same function; but alternates between a few ones, each operating on the result of the other.

i'd say you have three alternatives:

1. totally reformulate the algorithm (that's what the Fibonacci examples do).
2. combine all functions into a single one with lots of cond's (ugly, and maybe won't result in a real tail-recursion, even with a single function).
3. turn the flow inside-out: write a single, simple tail-recursive function that transforms the input data into the sequence of operations that have to be performed, and then eval it.

Answer 2

If flatten calls itself twice (in the :CONCAT case) how can it be turned into a loop? Maybe I'm missing something. Seems it's inherently a tree-walk.

I mean, there are ways to do a tree-walk without stack, but something has to be unbounded, like if you do it with a FIFO, or as was suggested, with continuations.

Answer 3

You could use continuation-passing:

(define (frob0 x k)
  (cond ((foo? x)
         (k x))
        ((bar? x)
         (frob0 (g x) 
           (lambda (y) 
             (k (macerate (f x) y))))
        ((thud? x)
         (frob0 (g x) 
           (lambda (y)
             (frob0 (h x) 
               (lambda (z)
                 (k (frobnicate y z))))))))

(define (frob x)
  (frob0 x (lambda (y) y))

This will not make things easier to understand :-(

Answer 4

The best I can come up with is something like this:

(define (doaction vars action)
  (cond ((symbol=? action 'frob)
         (cond ((foo? (first vars))
                (first vars))
               ((bar? (first vars))
                (doaction (list (f (first vars)) (doaction (g x) 'frob)) 'macerate)
etc...

It's not fully tail recursive, but likely the best you can get. TCO is really the way to go. (I understand that Clojure can't have it due to the JVM).

Answer 5

Please don't downvote this because it's ugly. I know it's ugly. But it's a way to do it in trampoline-style (no system stack overflow), and without using gotos.

push x,1 on homemade stack
while stack length > 1
  n = pop
  if (n==1)
    x = pop
    if (type(x)==NIL || type(x)==TEXT)
      push x // this is the "return value"
    else if (type(x)==CONCAT)
      push 2 // say call doc-concat
      push doc2(x), 1 // 2nd recursion
      push doc1(x), 1 // 1st recursion
    else if (type(x)==NEST)
      push 3 // say call doc-nest
      push level(x) // push level argument to doc-nest
      push doc(x), 1 // schedule recursion
    else if (type(x)==LINE)
      push " " // return a blank
    else if (type(x)==UNION)
      push doc1(x), 1 // just recur
  else if (n==2)
    push doc-concat(pop, pop) // finish the CONCAT case
  else if (n==3)
    push doc-nest(pop, pop) // finish the NEST case
  endif
endwhile
// final value is the only value on the stack

Answer 6

The standard general technique is conversion to trampolined style. For your particular problem (implementing prettyprinting combinators) you might find helpful Derek Oppen's 1980 paper "Prettyprinting" (not on the web AFAIK). It presents a stack-based imperative algorithm similar to Wadler's later functional one.