Continuation passing style makes things tail recursive?

Question

It hurts to ask it here. It really does. Every time I search in vain for the answers to my troubles, I see it. Taunting me. Stack Overflow.

Anyway, some hellish influence caused me to attempt to solve the Towers of Hanoi. My first solution was incomplete, as it resulted in a memory error if run with too many disks:

(define hanoi
  (lambda (n from to other)
    (cond ((< n 0)
       (error `(Error! Number of disks ,n cannot be less than 0!)))
      ((= n 0)
       '())
      (else
       (append (hanoi (- n 1)
              from
              other
              to)
           `((,from ,to))
           (hanoi (- n 1)
              other
              to
              from))))))

I read somewhere that continuation-passing style would solve the problem. However, this didn't help either:

(define hanoi_cps
  (lambda (n from to other c)
    (cond ((< n 0)
       (error `(Error! Number of disks ,n cannot be less than 0!)))
      ((= n 0)
       (c '()))
      (else
       (hanoi_cps (- n 1)
              from
              other
              to
              (lambda (x)
            ((lambda (w)
               (w `((,from ,to))))
             (lambda (y)
               (hanoi_cps (- n 1)
                      other
                      to
                      from
                      (lambda (z)
                    (c (append x y z))))))))))))

Aerograph

How many disks is too many disks, out of curiosity? – Buryat

@Buryat for hanoi: 19 disks; for hanoi_cps: 15 disks – Aerograph

Answer 1

In continuation passing style, rather than extending the stack-space with recursive calls, you're building up recursively-defined lambdas in the environment that your continuations are executed in ... in other words, memory is used up somewhere along the line. For instance, with a simple factorial algorithm, you would normally write it something like:

(define (factorial x)
    (cond ((eq? x 0) 1))
          ((eq? x 1) 1))
          (else (* x (factorial (- x 1))))))

With this recursive definition for factorial, stack space is going to be used up to hold the arguments to the deferred multiply operation peformed in each recursive function call. A continuation-passing version of the same function would look like:

(define (factorial x cont)
    (cond ((eq? x 0) (cont 1))
          ((eq? x 1) (cont 1))
          (else (factorial (- x 1) (lambda (y) (cont (* x y)))))))

What would have consumed stack-space before is now used up by the environment of the anonymous lambda. The environment of the lambda in this case is being filled with values that are required in order to resolve the value of x and cont with each recursive call to factorial. Since cont itself is a lambda with an environment, you can see how memory will eventually be consumed as each lambda-continuation will need to store in its environment the lambda from the previous call to factorial ... this creates a recursively defined lambda-continuation that has an environment that is basically a recursive list of all the continuations that have been accrued though the recursive calls to factorial.

One way of looking at continuation-passing style is that while you've basically converted the function-calling mechanism to a tail-recursive method, the actual definitions of the continuations themselves are recursive in nature, so you're not really removing the recursive-nature of the algorithm per-se ... in other words evaluating a continuation built up over tail-recursive calls requires evaluating a recursively defined continuation inside of it, which itself has another recursively defined continuation inside of it, etc. The environment for the lambda-continuations ends up looking like a list-of-a-list-of-a-list, etc. Storing all those recursive definitions in the environment of the lambda-continuation requires memory, so whether you're consuming space on the stack via a normal recursive calling convention, or consuming memory space by storing recursively defined environments in every lambda-continuation, either way you're eventually going to run out of space.

Leviathan

Ah, so there's no way to get around the need for memory. – Aerograph

No, that's unfortunately the downside of recursive algorithms ... keep in mind that a true "tail-recursive" calling convention is actually not a true recursive algorithm since it can be exchanged with a loop. – Leviathan

Answer 2

CPS won't help you make things more memory-efficient, since by performing it, you're just replacing stack frames with anonymous functions. If you want your program to use less memory, try a backtracking search (but note that you have to be careful to avoid infinite move sequences).

Haye