Back to Questions
3.8k
views7
comments
CPS tail-recursion stack overflows
f#web

Hi, this is my first post. I hope you find it an interesting one.

I've been playing with F# since the Sept CTP was released, and I've been particularly interested in recursion. I'm reading up on various methods to convert a recursive function into a tail-recursive function namely the accumulator and continuation passing styles.

However, I've run into stack overflows concerning what I thought was a tail-recursive implementation of the list reverse function:

let rev l =

let rec rev' l cont =

match l where

| [] -> cont []

| x::xs -> rev' xs (fun r -> x::(cont r))

rev' l id

It overflows somewhere between a list size of 50-60k.

I get a similar problem in Haskell with the following function:

rev' [] cont = cont []

rev' l cont =

rev' xs (\r -> x:(cont r))

where x:xs = l

rev l = rev' l (\x -> x)

However, it throws a stack overflow somewhere between a list of 500-600k.

The problem seems to be that the continuations are not tail calls ie. the last thing the continuations do is cons an item with the previous continuations result.

You can easily show this by implementing these two functions and calling them with very large n (I used 1,000,000).

let sumCPS x =

let rec sum' x cont =

match x with

| 1 -> cont 1

| _ -> sum' (x - 1) (fun r -> cont (x + r))

sum' x id

let sumCPS2 x =

let rec sum' x cont =

match x with

| 1 -> cont 1

| _ -> sum' (x - 1) (fun r -> x + (cont r))

sum' x id

sumCPS's asymptotic behavior is apparently tail-recursive while sumCPS2's behavior is not.

From what I've read in the Expert F# on tail-recursion with CPS and various articles on the web (including the pdf with the above reverse algorithm: [link:www.cs.bu.edu] there's not mention of requiring the continuations to be tail calls. Is this a problem with how F# and Haskell handle recursion with CPS or are only certain forms of CPS (with continuations making tail calls) capable of asymptotic tail-recursive behavior?

.

Is this a problem with how F# and Haskell handle recursion with CPS or are only certain forms of CPS (with continuations making tail calls) capable of asymptotic tail-recursive behavior?

The latter. There's nothing magic about 'continuations', all the magic is in 'making tail calls', and continuation-style is just one programming pattern that makes it easier to put all the calls-with-potentially-much-more-work-left in tail call position.

By on 12/11/2008 9:11 PM ()

Thanks for the replies. I was so caught up with CPS that I neglected to realize how simple the reverse algorithm is with an accumulator.

1
2
3
4
5
6

let rev l =
    let rev' l acc =
        match l with
        | [] -> acc
        | x::xs -> rev' xs (x::acc)
    rev' l []

I was enamored by how easily it was to express certain tail-recursive algorithm in CPS. Instead of thinking how the callee should construct the partial result in an accumulator, I could pass "everything after the recursive call" in a continuation and treat the argument to the cont as the "partial answer" as calculated by earlier recursive calls. However the reverse algorithm as a tail-recursive CPS function looks like:

1
2
3
4
5
6

let rev l =
    let rev' l cont =
        match l with 
        | [] -> cont [] 
        | x::xs -> rev' xs (fun r -> cont (r @ [x])) 
    rev' l []

which has terrible performance with singly linked lists.

I enjoy using recursion but I'd love to use it without introducing possible stack overflows. I wish there were a more automated way of transforming direct-style recursive algorithms into tail-recursive forms without sacrificing performance. However, since accumulator and CPS seem to have different complexities for the same algorithm (the reverse algorithm above) I wonder if we'll ever have compilers which can automatically perform the transformation while maintaining the lowest complexity. Some algorithms that have natural and easy to understand recursive forms like quicksort and mergesort would be rather difficult to implement with accumulator style and implementing with a simple CPS algorithm runs into the same problem as above i.e. appending singly linked lists which is a O(n) operation. I suppose implementing bidirectional lists would a better idea. Better to fit the data structure to the algorithm than the algorithm to the data structure.

On one last note, I wonder if the CPS algorithm:

1
2
3
4
5
6

let rev l = 
    let rev' l cont =
        match l with 
        | [] -> cont [] 
        | x::xs ->rev' xs (fun r -> x::(cont r)) 
    rev' l []

could be converted to a tail-recursive form by adding another layer of continuations and transform x::(cont r) into a CPS operation. My gut tells me yes, but it would look pretty ugly.

By on 12/12/2008 8:17 AM ()

I just wanted to point out that it's a little ironic that you picked "rev" for this example; most switched-to-using-accumulators-to-be-tail-recursive algorithms on lists create the list in reverse order, and then have to call 'rev' as the last step before returning the result (to get the final results in the right order). In contrast, those same algorithms made tail-recursive using CPS do not need the extra reversal step.

By on 12/12/2008 9:34 AM ()

Agreed. I was stuck on reverse for that very reason. Most data building/traversing algorithms are rather trivial to convert to CPS tail-calls and slightly faster perhaps since the final reverse isn't needed (although if you reversed the list using lazy evaluation you wouldn't take the performance hit). However, the reverse algorithm seemed a pathological case. The trivial CPS transformation is horrible in both time and space complexity (from what I've seen by demoing them in FSI). As I said, I was caught up in the CPS paradigm, hoping perhaps it was a panacea to tail-recursion transformations. Not that I view accumulator style as inferior, but trying to figure out how to implement an algorithm using only tail-calls seems to break the elegance of a functional language's declarative aspect. Instead of saying what you want done, you have to tell the compiler how to implement the function to avoid stack overflows. Nonetheless I'm enjoying developing software and algorithms, recursive or not, in F#.

By on 12/12/2008 10:40 AM ()

See also the continuation monad as on

[link:lorgonblog.spaces.live.com]

for an alternative syntax that makes CPS style potentially nicer to write.

By on 12/12/2008 12:06 PM ()

Thanks Brian.

I enjoyed your posts on the continuation monad and catamorphisms. Quite a bit to wrap my head around.

By on 12/12/2008 1:28 PM ()

Hi and welcome to the hub :-) !
This is definitely an interesting area. Here is a hint that should explain why you're getting a stack overflow. I marked an expression below in the code, which isn't a tail call:

1
2
3
4
5
6

let rev l = 
   let rec rev' l cont = 
      match l where 
      | [] -> cont [] 
      | x::xs -> rev' xs (fun r -> (* [here] *) x::(cont r) (* [/here] *) ) 
rev' l id

It calls the continuation first (which can call other functions and occupy a lot of stack space) and then constructs a new list, so in this case you'll probably have to use "accumulator" technique.

By on 12/10/2008 10:07 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper