Introduction to Continuation-Passing Style
This post #1 of the Continuations Explained with Ruby Series
Photo by gadl
Recursion & Tail-Recursion
For those of you that are reading my blog, you already probably know what recursion is. Still, I would like to share with you one of my favorite definitions of recursion: “Definition of Recursion: If you still don’t get it, see the definition of recursion.”
Now, it is generally agreed upon that using recursion tends to be a lot slower and occupies a lot more memory that the iterative version. This isn’t always the case. It is more accurate to say that a naive implementation of iteration is usually more efficient than a naive implementation of recursion.
The major advantage that iteration has over recursion is that it doesn’t allocate as much space on the run-time stack to store local variable and bookkeeping information.
This advantage can be minimized if an “optimizing” compiler is used, in particular, one for a Functional Programming Language which is able to generate excellent code for recursive functions, especially for tail-recursive functions.
A tail-recursive function is one that doesn’t have any additional computations along with the recursive call. In other words, the function’s return statement is just another call to the function itself, without any pending operations. Let’s take a look at some code to better illustrate the point:
# Normal recursive version of Factorial
def fact_r(n)
return 1 if n == 0
# Here's the pending operation with a call to a recursive function:
n * fact_r(n - 1)
end
# Tail-Recursive version of Factorial
def fact_tr(n)
def fact_aux(n, accumulator)
return accumulator if n == 0
# No pending operations here, only a call to the recursive function:
fact_aux(n - 1, accumulator * n)
end
fact_aux(n, 1)
end
The tail-recursive function is much faster because the compiler doesn’t need to dynamically allocate space on the stack for the pending operations. It can just reuse the space belonging to the current iteration when the tail-recursive function is called.
Transforming Non-Tail-Recursive functions into Tail-Recursive ones
By using Continuation-Passing style, a compiler for a functional language can automatically optimize a non-tail-recursive function into a tail-recursive one, which, in turn, allows it to apply further optimizations.
But before we continue, we need to know what a Continuation is. According to Wikipedia, a Continuation is an abstract representation of the control state. In other words, they allow you to represent computations with dependencies in an explicit manner.
Now, let’s take a look at the fact_r function from the above example, more specifically, the last line of the function: n * fact_r(n - 1)
What we see here is a clear example of a computation with dependencies: fact(3) has to wait for 3 * fact(2) to be computed, which in turn needs to wait for 2 * fact(1) to be computed, which still needs to wait for 1 * fact(0) to be computed.
Now, how can remove those dependencies? First, we have to add a new argument to the function that will contain the continuation. Then, instead of performing the operation that causes the recursive function to wait, we wrap it in a lambda to be calculated later on. Only when we get to the base condition of the recursive function do we actually execute the continuation, which will then calculate the result and present it to us. This is easier to see in an example:
def fact_cps(n, c)
if n == 0
c.call(1)
else
fact_cps(n - 1, lambda { |r| c.call(n * r) })
end
end
> fact_cps(5, lambda { |r| r })
120
What we’re doing is transferring the control to another function, either fact_cps or to the continuation c, without leaving any dependent computations in the stack.
As I said earlier, using CPS results in a tail-recursive function, so the stack doesn’t grow like a normal recursive function. But, because we use lambdas and chain them, they get allocated in the heap instead. Once used, the Garbage Collector will then clean up after us.
First steps towards imitating Prolog’s backtracking capability
Now let’s have some fun messing around with CPS: when n reaches 0, what would happen if we saved the continuation in a global variable?
def fact_cps(n, c)
if n == 0
$end_fact_cps = c
c.call(1)
else
fact_cps(n - 1, lambda { |r| c.call(n * r) })
end
end
> fact_cps(5, lambda { |r| r })
120
After calling the new fact_cps for the first time, the global variable $end_fact_cps contains a reference to the continuation that was used, i.e. we now have access to the computations that were performed while calculating the factorial of 5. We can now play around with them:
> $end_fact_cps.call(1) # 5 * 4 * 3 * 2 * 1 120 > $end_fact_cps.call(2) # 5 * 4 * 3 * 2 * 2 240 > $end_fact_cps.call(3) # 5 * 4 * 3 * 2 * 3 360
Calling the saved continuation with 1 makes it calculate the result as if we were calling fact_cps with 5. When we call it with 2, or 3, what we’re doing is changing the value that’s used when the base condition of the recursive function is reached. So, instead of calculating the factorial of 5, we calculate the double and the triple of the factorial of 5.
Now, I admit this is nothing special, but it’s the basis for what we’re going to explore in the next blog post in the series. We’re going to be doing something similar to create a recursive backtracking function that will allow us to produce different solutions to the 4-Queens problem (simpler version of the 8-Queens problem) depending on user input – something that Prolog does easily.
I hope you were able to understand how to use Continuation-Passing style to explicitly represent computations with dependencies in a recursive function.
If you have any questions, I’ll gladly try and answer them. Just drop me a comment!
That’s it for now, hope to see you here for the next post in the series where we’ll do a lot more interesting things! Until then…