Saturday, June 23, 2007

Episodic Computation

Or, How I Learned to Stop Returning and Embrace Yield!

You really should stop reading this and go read this.

To this point in my career, I've found that Addison Wesley can be counted upon to deliver the more academically-minded texts on the topics I'm interested. "Essential Windows Workflow Foundation" is no exception. I am so very happy that I took this book seriously and began studying it with an eye toward a deeper understanding than just solving the problem in front of me.

I am, however, consistently struck by my own naivete when it comes to what can only be considered foundation computer science concepts. For example, I don't think I would have been fully able to articulate the differences and purposes of Subroutines, Coroutines, Continuations, Closures, and Generators. So, after an hour with Wikipedia, I am attempting share what I've learned--more for my benefit than yours. Seek first to understand, then to be understood.

Subroutines are special cases of Coroutines. Coroutines can be implemented with Continuations, while Continuations are just bookmarks for Closures. And, Generators can be thought of as a special case of a Coroutine that returns a value when it yields.

Confused? Good, that means you'll read the rest.

So, a Subroutine is (if you're a C# or VB developer) just a function.

A Coroutine is a Subroutine that can pause its execution and resume it when control flow is given back to it.

A more correct way to say it is that a Subroutine is just a Coroutine that returns only once, i.e. it always starts with a clean slate--it never resumes.

In order to resume a Coroutine, you have to keep track of where the Coroutine left off and the current state of its values (its stack frame). Bottling all that up into a kind of primitive, we call it a Continuation. So, if your language allows us to store the stack frame and an execution pointer (the last instruction), you have Continuations. If you have Continuations, you can write Coroutines. C# does this with the yield statement, which is just a fancy compiler trick for creating a state machine around the current point of execution.

A Continuation, then, requires two things to be of use: a stored re-entry point (a bookmark) and a saved variable state for a function. The later is what is known as a Closure. Specifically, a Closure looks around in its current lexical context (the written code where names (of variables) can be resolved) and packages up all that stuff into its definition, as needed. So, a Continuation can use a Closure to pick up where it left off.

Closures have a lot more general usage than just as a crutch for Continuations, but I'll leave that digression as an exercise for the reader.

Finally, Generators are just Continuations, but they return a value. To my understanding, Generators are just iterators, though one might think of a Generator as an iterator for an infinite series (think Fibonacci numbers, digits of pi, etc.); the salient difference being wether the client has to stop the iteration/generation or if the Continuation will eventually stop resuming.

What does all of this have to do with Episodic Computation or Workflow Foundation (WF)? Well, one can think of WF as an attempt to extend these and related concepts to the application level, as an attempt to create resumable programs, as an enabler of "episodic" computation. Essentially, WF wraps your higher-level imperative concepts (e.g. GenerateBillOfLading, CheckProductInventory) in "Coroutines" that can execute across processes. In other words, it is a framework for programming at the logical level.

That last statement is the Gestalt of WF. Unfortunately, that kind of expressiveness comes at a price: about USD$33