Just passing through

work safe

Continuation Passing Style is a functional pattern where all work that can’t be passed into a tail recursive function call is passed in as an additional argument via a closure or anonymous function, delaying execution.

What got me confused for years on this was the explanation, almost like a mantra, “A continuation is like a callback.” I don’t use callbacks much and I believe that phrase is actually expressing a different pattern, simple first-class functions. So what do I think a continuation is? It is a promise to get to it later, after a tail call. I do agree with the literature that it turns the function inside out. And Don Syme’s reasoning that you’re trading heap to avoid spending stack.

I know you hate fibonacci, but it’s simple to explain. Here it is in all it’s glory.

You note, however, that since the results of two recursive calls need to be stored, we can’t dump the stackframe and tail optimize the call, right? We could pass around two accumulators, essentially mimicking the imperative for-loop solution to the problem

This works because the Fibonacci sequence is just that, a sequence. It can also be represented by a tree, and that’s what’s causing it to be a problem for recursion in the first place. We are still left with, “How do I process a tree without risking a blown stack?” That’s what Continuation Passing hopes to solve by using a continuation (read: anonymous function) that wraps our core functionality in a heap object so we don’t call down one leve. I’m not making this clear, so I’ll show this in pictures.

Continutation Passing Style, step one.

Step One: We're abstracting the problem to it's simplest form

Step Two: We're making a promise to do something later

Step Two: We're making a promise to do something later

Step Three: We're expanding the first abstraction

Step Three: We're expanding the first abstraction

Step Four: We're expanding the second abstraction

Step Four: We're expanding the second abstraction

Step Five: Fill in the base-cases for both our promise, and the function.

And now for the punchline. Why do I care? This goes back to the spreadsheet challenge I talked about earlier. I was evaluating my abstract tree and noticed a lot of code that looked like: | Sum(a,b) -> eval a + eval b and I knew it wasn’t going to scale past my toy problem. I had a few tests, so I branched it with Git and tried replacing it with a tail recursive version. I know a spreadsheet doesn’t need that, but it really didn’t add any complexity once I figured out what it was actually doing. Just thought I’d share.

3 Comments

3 Comments

  1. Jon Fuller  •  Nov 19, 2009 @9:56 am

    I always kind of kept continuations out of my behavior too, and definitely stayed away from figuring out what it actually is and where it fits into my world.

    After your definition above, I realize I reviewed some code on Tuesday that did just this! Craziness.

  2. Jon Fuller  •  Nov 19, 2009 @10:02 am

    Oh yeah, the whole Gist thing doesn’t work out for feedreaders :-/

  3. Ball  •  Nov 19, 2009 @11:05 am

    Sorry about that. My syntax plugin doesn’t do F#, so I went with Gist this time around. I’ll see what I can do since I’m really enjoying coding in F#.

Leave a Reply

You must be logged in to post a comment.