I’ve been spending a lot of time recently tinkering with different constructs and methodologies in Javascript, and one of the most fascinating things I’ve come across is Spencer Tipping’s use of continuation-passing style.

It’s ok if you aren’t familiar with CPS, but I think anyone hoping to make the cognitive leap to functional programming should study it. As a bare miniumum, you need to know that a continuation is:

[a reification of] an instance of a computational process at a given point in the process’s execution

Therefore, continuation-passing style is just:

a style of programming in which control is passed explicitly in the form of a continuation

NOTE: I have replaced my crappy examples just below with Outis’s much more reasonable (and correct) ones. I take no credit for the simple CPS code below. Thank you Outis and David for the suggestions.

Consider the naive implementation of the recursive fibonacci function:

Then, identify function calls and returns. For each such point, create a continuation and pass it to the function call or return it. For example, the continuation for `fibr(n-1) + fibr(n-2)` is:

and you get:

Apply this process to the linear recursive fibonacci function and you get:

The only problem with this, however, is that Javascript engines to not optimize tail recursion, so calling: fibonacci_cps(10000) would cause a StackOverflowError in some browsers.

However, by adding to Function.prototype and changing the way we pass continuations, we can fix this problem.

## How CPS and TCO can be practical

All this talk about styles and optimizations can sound rather like “over-engineering” to those of us who aren’t familiar with these concepts. While it’s a risk, good engineers will know when it is effective. Here’s how I would recommend you use these concepts:

1. Processing large structures in a recursive way, perhaps recursing through an Object or HTML tree of indeterminate depth