Recursing on Recursion - Continuation Passing

In this continuing series of my back to basics, I've been talking about recursion, and various strategies around using it effectively.  This includes covering the basic types of recursion, whether it be linear, binary, and tail.  Then I took it a step further with topics on list recursion and memoization techniques.  This is an ongoing part of my back to basics series in which I hope is a refresher for many who don't use these things on a daily basis.

Let's catch up to where we are today:

This time, we're going to talk about recursion and Continuation Passing Style (CPS).  We'll include both samples in F# as well as C# for these examples.

 

Continuation Passing Style

Earlier in the series, I talked about several different ways to approach recursion.  Today we're going to bring CPS into the terminology.  Let's first discuss the first word in the title, Continuation.  Simply put, a continuation represents the remainder of a computation given a point in the computation.  You could almost think that a continuation is GOTO with a parameter that is the value of the function that transferred the control. It is unlike a function call because, while it is possible to return to the original computation it is not always expected or necessary.  Yet, many people get tripped up by this definition.

Writing a function using CPS takes an explicit continuation function argument which is meant to receive the result of the computation that was performed in the function.  When doing this, the caller is expected to give the function to be invoked during the end of the function.  So, what this means is instead of returning a value from a function, the value is passed to the code that will continue the computation.  Using this programmatic style gives us a few things, which include intermediate values, order of argument processing and tail recursion.  Why is this important?  Besides making you the obvious hit at any party, and an absolute dev maven, it's important if you want to understand another fun topic of Monads as well as asynchronous calls.  But, that's for another day.  I'll go into a scenario below where it's absolutely useful in regards to recursion.  But, in the mean time, let's look at how CPS differs from direct calls.

Let's first show a quick example of CPS in action using F#:

#light 

let square_func x = x * x 
(* val square_func : int -> int *)

let square_cps x cont = cont(x * x) 
(* val square_cps : int -> (int -> 'a) -> 'a *)

let result = square_cps 4 (fun x -> x)

 

What I did in the above syntax is take a standard squaring function, and applied a continuation which handled the result of the computation.  Then in the calling function, I gave it an identity continuation which is simply taking the input and returning it.  This is all well and good, but let's try to apply this more towards our story at hand with recursion.

 

CPS and Recursion

In this series, I showed how you could take a normal recursive function and move it from linear to tail recursive.  This time, we'll take that same approach with going towards CPS.  In the past I've been guilty of showing the standard Fibonacci sequence as well as factorial, so let's switch it up and go towards our ImmutableList, or just a List<'a> for those in the F# world.  The immutable list is part of my Functional C# library on MSDN Code Gallery.

Let's first go with our standard linear recursion and what that looks like when calculating the length of our list.

F#
let rec length = function
  | [] -> 0
  | _ :: t -> 1 + length t

 

C#
public static int Length<T>(this IImmutableList<T> list)
{
    if (list.IsEmpty) return 0;
    return 1 + Length(list.Tail);
}
 

 

As you notice, our last calculation wasn't a tail call, instead we were adding 1 to the result of the recursive call.  Now, instead of this, which could stack overflow on rather large data sets, let's optimize it for the tail call.  This usually includes an inner function to do this with an accumulator involved. 

F#

let length_tail lst = 
  let rec length_acc l acc =
    match l with
    | [] -> acc
    | _::t -> length_aux t (1 + acc)
  
  length_acc lst 0

 

C#
public static int LengthTail<T>(this IImmutableList<T> list)
{
    Func<IImmutableList<T>, int, int> length_acc = null;
    length_acc = (l, acc) => 
      l.IsEmpty ? acc : length_acc(l.Tail, 1 + acc);

    return length_acc(list, 0);
}

 

Now these functions are optimized by the tail call.  I created an inner function which takes the list and an accumulator and recurses over itself by adding 1 to the accumulator.  But, as I've stated before, the C# compiler doesn't optimize for the tail call.  This has been a known issue for some time now, and I don't think it's on the highest priority to fix.  After all, the JITer does do a simple optimization with a tail call on x64 only.  If you're running on an x86, you'll still get stack overflows.  More reason to look at F# when doing recursive algorithms. 

But, let's take this a step further.  What would it take, to take this above function and turn it into CPS?  Well, to think about turning something like that function, you have to think backwards just a little bit.  You'll see what I mean.

F#
let length_cps lst =
  let rec length_cont l cont =
    match l with
    | [] -> cont 0
    | _::t -> length_cont t (fun x -> cont(1 + x))
  
  length_cont lst (fun x -> x)

 

C#
public static int LengthCont<T>(this IImmutableList<T> list)
{
    Func<IImmutableList<T>, Func<int, int>, int> length_cont = null;
    length_cont = (l, cont) => 
      l.IsEmpty ? cont(0) : length_cont(l.Tail, x => cont(1 + x));

    return length_cont(list, x => x);
}
 

As you can see from above, it really turned our function inside out.  It's enough to make someone's head hurt sometimes.  Let's give one last example on how it can turn a function inside out, and yes, I lied about not bringing our standard Fibonacci sequence in here as well:

F#
let fibonacci_cps n =
  let rec fibonacci_cont a cont =
    if a <= 2 then cont 1
    else
      fibonacci_cont (a - 2) (fun x ->
        fibonacci_cont (a - 1) (fun y -> 
          cont(x + y)))
          
  fibonacci_cont n (fun x -> x)

 

C#
static int FibonacciCont(int n)
{
    Func<int, Func<int, int>, int> fibonacci_cont = null;
    fibonacci_cont =
      (a, cont) => a <= 2 ? cont(1
        : fibonacci_cont(a - 2, x => fibonacci_cont(a - 1, y => cont(x + y)));

    return fibonacci_cont(n, x => x);
}
 

This by itself is quite interesting.  But, the problem is still that C# isn't optimized for the tail call, so I see no benefit of writing it this way.  Also, CPS has a tendency to be an order of magnitude slower than standard tail calls and even tail calls for that matter.  With regards to F# though, since it's optimized for the tail call, produces well formed and fast code.  But, there are areas where you should care with regards to using CPS versus standard tail calls.  One such scenario is for parsing unbalanced trees.

 

Parsing Unbalanced Trees

When dealing with tree structures, it's a lot harder to get right when using tail recursion as opposed to very structured data.  Therefore, CPS comes to the rescue here.  For these examples, I'm only going to use F# because C# doesn't have the support I need when accomplishing this.  First, let's define a tree structure that we're going to parse and a binary recursive function that calculates the size of our tree.

type Tree<'a> = 
  | Node of 'a * Tree<'a> * Tree<'a>
  | Leaf of 'a

let rec tree_size = function
  | Leaf _ -> 1
  | Node(_, left, right) -> tree_size left + tree_size right

 

The problem with this function is that when I start getting large unbalanced trees, we are at risk of a stack overflow.  So, let's try to move it towards using tail calls in order to fix the issue.

let tree_size_tail tree =
  let rec size_acc tree acc =
    match tree with
    | Leaf _ -> 1 + acc
    | Node(_, left, right) -> 
        let acc = size_acc left acc
        size_acc right acc
  size_acc tree 0

 

As you can see, the way this code as written is that the left side is not actually tail recursive at all, and instead only on the right side.  This might be acceptable if the tree were balanced to the right, but if the tree is skewed to the left, then we'll have a problem.  This is where CPS can help to solve this issue.  Let's try now to apply our knowledge from above on how to modify our functions to use CPS with an accumulator, instead.

let tree_size_cont tree =
  let rec size_acc tree acc cont =
    match tree with
    | Leaf _ -> cont (1 + acc)
    | Node(_, left, right) ->
        size_acc left acc (fun left_size ->
          size_acc right left_size cont)
  
  size_acc tree 0 (fun x -> x)

 

What we were able to accomplish is the following:

  • Create an inner function which uses an accumulator, our tree and a continuation function as input.
  • Return 1 plus the accumulator if we've reached the leaf of the tree
  • Else, we're going to call the function to get the left tree size recursively until we reach the leaf.  We create a continuation to get the right tree size.
  • Finally, we call the right tree size while passing in the accumulator and our continuation. 

Using this approach, we don't face the the threat of stack overflows, but as well, we've used only two short lived continuations to compute this item.  This is a pretty advanced technique in most languages and isn't used too much.  But once you understand how they work and their uses, it's very powerful.

 

Wrapping it Up

I hope this brief introduction to CPS with regards to recursion was interesting.  If you'd like to know more about continuations in general, Wes Dyer, of the Volta team has a pretty good explanation and the various uses of CPS here.  From here, it's best to move onto monads (aka computation expressions in F#), especially with regards to the asynchronous processing.  As always, I make my code samples available through the MSDN Code Gallery in the Functional C# library.



kick it on DotNetKicks.com
Published Wednesday, August 13, 2008 4:45 PM by podwysocki

Comments

# re: Recursing on Recursion - Continuation Passing

Friday, April 1, 2011 7:15 PM by Akh

Your F# example of function "length_cps" fails with the StackOverflowException. Try:

let length_cps lst =

 let rec length_cont l cont =

   match l with

   | [] -> cont 0

   | _::t -> length_cont t (fun x -> cont(1 + x))

 length_cont lst (fun x -> x)

let lst = [1.. 100000]

length_cps lst |> printfn "Length is %d"

# re: Recursing on Recursion - Continuation Passing

Sunday, May 22, 2011 4:09 PM by weblogs.asp.net

Recursing on recursion continuation passing.. Bang-up :)

# re: Recursing on Recursion - Continuation Passing

Saturday, August 4, 2012 4:47 AM by Littlejohn

I did a search on this subject and i think most people will

agree with you.

# re: Recursing on Recursion - Continuation Passing

Thursday, December 13, 2012 3:24 AM by Barham

Somebody essentially help to make seriously posts I would state.

This is the very first time I frequented your website page and thus far?

I surprised with the research you made to create this particular publish

incredible. Wonderful job!

# re: Recursing on Recursion - Continuation Passing

Saturday, December 29, 2012 2:52 PM by Sheppard

Enjoyed reading through this, very excellent stuff, thankyou .

# re: Recursing on Recursion - Continuation Passing

Sunday, December 30, 2012 7:05 AM by Hightower

Can I just say what a reduction to look for someone who really is aware of what theyre talking about on the web.

You undoubtedly recognize how it is easy to bring an issue to

gentle and make it important. Extra folks have to read

this and perceive this aspect of the story. I cant consider youre

not more in style since you undoubtedly have the gift.

# re: Recursing on Recursion - Continuation Passing

Wednesday, January 2, 2013 7:08 AM by Mount

Immigration Lawyers… [...]that the time to read or visit that the content or

online resources we have linked to below the[...]…

# re: Recursing on Recursion - Continuation Passing

Thursday, January 3, 2013 1:30 PM by Abner

I think your blog is getting more and much more visitors.

*;~::

# re: Recursing on Recursion - Continuation Passing

Tuesday, January 8, 2013 10:53 AM by Loftin

It was some sort of contentment coming across your site the other day.

I got here at the moment hoping to uncover out new things.

I was not dissatisfied. Your ideas upon different tactics

on this topic were enlightening and a wonderful help to me.

Much gratitude for leaving out time to create

these things as well because for sharing your opinions.

# re: Recursing on Recursion - Continuation Passing

Thursday, January 17, 2013 2:18 PM by Mcgough

This article is very appealing to thinking people something like me.

It’s not simply thought-provoking, it draws you in out of that the beginning.

This is well-written content. That the views here have been also appealing

to me. Thank you.

# re: Recursing on Recursion - Continuation Passing

Sunday, March 17, 2013 11:11 AM by Marr

The following litigate is removing sap that left hand on coating Green Coffee by tempestuousness and stadium to compound; add refined

sugar, vanilla extract, and table salt until amply unified.

A gazillion dollar bill industry, In that location are

many companies who stand to to misplace weighting in 2012?

# re: Recursing on Recursion - Continuation Passing

Monday, March 25, 2013 11:00 PM by Arrington

This volition hair's-breadth is a footling whiter, thinner, this yr than Net twelvemonth. ConstructionOrdinarily, executive Office Chairs are made of upshot of pitiable arm support whilst functional at your calculator.

# re: Recursing on Recursion - Continuation Passing

Friday, April 5, 2013 3:26 AM by Burkholder

Juicing Fatlosss are essentially a certain plan where you'll replace your typical food with just fresh juice. But they were also hunted by aboriginals for food and salads. Mayo Clinic says that no link has been found to be associated with a reduced sperm count. Too expensive, especially if you eat foods such as sweets & chips.