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.

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

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

Step Three: We're expanding the first 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.

I’ve been thinking about IronRuby and WPF and this means I’ve been seeing some differences between how a staticly typed language like C# builds APIs and dynamic languages. It basically boils down to the use of primitive types at the perimeter.

Let’s look at a simple C# API

   public MyDoc GetDocFromUrl(Url address){
      // do stuff here
   }
   public static void Main(String[] args){
      GetDocFromUrl(new Url("http://some.site/some.doc"));
   }

And now the Ruby version

  def get_doc_from_url(url)
     # do stuff
  end
  get_doc_from_url("http://some.site/some.doc")

what’s the difference? In the C# version, you need to insert a url. In the ruby version, you need to pass in a string.

The first time I realized this was working with WPF trying to get a picture to update. The Xaml code had an attribute Source="blah.png" but the C# code to change this after the fact was horrific. Starting , I need to call System.Windows.Interop.Imaging.CreateBitmapSourceFromHBitmap(...). Why was that my job? For those playing at home, this is why extension methods exist. The code to do all that junk has a spiritual home on the WPF control, not in my application.

        private static void ShowFile(string FileName)
        {
            var win = new Window();
            var stack = new System.Windows.Controls.StackPanel();
            var bmp = new System.Drawing.Bitmap(fileName);
            var img = System.Windows.Controls.Image();
            img.Source = System.Windows.Interop.Imaging.CreateBitmap.SourceFromHBitmap(
               bmp.GetHbitmap(),
               IntPtr.Zero,
               Int32Rect.Empty,
               System.Windows.Media.Imaging.BitmapSizeOptions.FromEmptyOptions());
            img.Stretch = System.Windows.Media.Stretch.None;
            win.Content = img;
            win.SizeToContent = SizeToContent.WidthAndHeight;
            win.ShowDialog();
        }

When I started writing this post, I was going to make a point about static vs dynamic languages. After chatting with Jon Fuller one night and chewing it over for a few days, I think the typing is a red herring. He mentioned that the rails source code seems to have a certain layer structure. The public facing APIs take the primitive types and then convert them to internal representations. You can do this in C#. So, why not?

WPF, for example, has to serve many masters. Let’s start by thinking about where you can get the images for your WPF application.

• Files
• Filtered Files
• Generated
• Taken from the web
• Taken from gopher

I see a pattern. The API would have a large number of transformers from all the possible sources, so instead of supplying any, they supply none. From the point of view of the API developer this is less work and easy, but in they eyes of the application developer, this bleeds your API concerns into the application. It fuzzes the layer boundary. To be blunt, Earlier this week I tweeted comparing this style of APIs to a sea-cucumber spewing its guts into the surrounding water.

A better metaphor is the realization that software contains estuaries, places where the fresh water of your application mixes with the marine conditions of the APIs and frameworks you use. Seawater kills freshwater animals, and very few organisms thrive in the swirling mix. The difference is where the estuaries are contained. In Ruby APIs, we tend to keep the estuary behind the API letting the API provider manage the conversion from one type to the other. In C# APIs, we see the estuary on the application side. The thing to be aware of with the application biased estuaries is that they tend to reach farther up stream than you may realize. Abstraction layers and extensions on the API can help manage the mix of waters. Be ecologically minded, save the programming environment and code green!