Matt's Blog

Delimited continuations are best thought of as the difference of continuations. Anywhere where one continuation encloses another (i.e. running from one point you reach the second) leads to a well defined difference. Consider a simple subroutine as such a difference, between the entry point to the subroutine and the exit point. In high level languages the exit point of a subroutine is the end of the block or an explicit return statement wholely equivalent to the final statement in a program. So consider a subroutine as if it were a program itself; the entry continuation runs the subroutine and then stops; the exit continuation simply stops. The difference between them is the body of the subroutine followed by some undefined behaviour. When you call the subroutine you provide the context necessary to fully define the thread of execution. The return continuation is implicit and the resulting code is well structured, modular and readable.

Invoking a delimited continuation behaves just like a subroutine call and not like a jump. The return context is necessary to fully define the thread of execution and is provided implicitly at the point of invocation. It is as easy to use such a delimited continuation in as modular and readable way as any subroutine. Capturing a delimited continuation as a first-class value in a high level language involves some new control structures. In Scheme we can define these control structures directly using macros, and then hide call/cc for common use. In other languages we may add only delimited continuations as first-class values. Using the end of a program as the second part of difference it can be seen that delimited continuations encompass ordinary continuations as a special case, so no expressive power is lost in using delimted continuations only.

I've become enamoured of delimited continuations. For the unenlightened, continuations in a high level language are equivalent to addresses you can shove into a program counter in a machine language --- i.e. a continuation is a jump target and is used for looping and for subroutine calls. In an assembly langauge you can create these addresses either as branch labels or using a opcode like `call' or `jsr' which pushes the current address into a register or onto the stack and then branches to a subroutine. Both the jump to the subroutine and the return address saved are continuations but the return address has the interesting property of being generated dynamically and saved as a data word. High level languages dont usually let you meddle with the flow of control like you can in an assembly language, but a few like the Scheme which support first-class continuations do, and the results can be incredibly powerful and just as unreadable as assembly language.

Scheme is a dialect of lisp and to handle the functional (lambda calculus) nature of the language continuations need to take a single argument to pass on the value that all lisp expressions (and hence all jump targets) must return. The call/cc command gives access to the continuation in the roundabout way of lambda calculus by realizing a lambda expression with the return continuation of call/cc expression.

(define (sgn x)
  (call/cc
    (lambda (return-sgn) ; `return-sgn' is just a variable bound to the continuation
      (if (< x 0) (return-sgn -1))
      (if (> x 0) (return-sgn +1))
      (return-sgn 0)
      (explode) ; we never explode
    )
  )
)

Here is a simple Scheme procedure that returns the sign of a number. Continuations are unnessesary to achieve this simple result but it demonstrates the basic idea of continuations; they are first-class objects that can be stored in a variable (here I used the variable name `return-sgn') and in calling them you never return to the point of invocation. Continuations can also be aggregated into arbitrary data structures of any scope, may be invoked anywhere whatsoever, perhaps repeatedly to create loops. They can be called from deeply nested recursive procedures jumping out from the recursion in one step and conversely you can jump into a deeply recursive procedure from a previously saved continuation. Trying to follow the thread of execution can cause your brain to explode. Gotos are wimps when it comes to the obfuscation you can achieve with first-class continuations.

Delimited continuations are a refinement that go some way to improving the structure and readabilty of the code over what you would get when using the undeliminated variety.

I've just come to the realization that two months of haskell progress in my regatta scoring programme was a waste of time. I was porting from python so I couldn't escape from the imperative mindest. My problem was I needed to analyze some racing results and compute results progressively proceeding from raw data, through a sucession of refinements, until finally being able to compute overall results. This was too messy to hand around piece by piece so I needed an overall record to contain the data as it was computed. This was my downfall.

Because I was generating the data progressively, later computations depending on earlier ones, I was assuming that to define the overall computation in a purely functional way the declarative form would have to mirror the data flow. I saw myself as having to pass a record with undefined fields from function to function, adding fields and passing the more defined record onto later computations. Consequently I decided I would have to use a monadic approach to emulate the imperative style. This would avoid the unecessary duplication and bookkeeping of the purer approach.

I'm tempted. They are quite nice core 2 machines with everything on the motherboard. No weird drivers needed as far as I can tell. Intel video which is a plus for someone who likes to compile their own kernels. The price isn't bad but it isn't much cheaper than the XP machines which are usually discounted from their advertized price.

Using forall as a quantifier is very confusing. It implies predicate logic and, while I am sure there is a formal system of types, it is not a predicate logic. Here forall represents "don't care" or "I'm not looking inside anyway so why should I care". There is still a one-to-one mapping between the type formalism and model. Not at all the same concept as universal quantification which models as "all these possibilties". There is one function which treats that data as a black box. If dynamic dispatch is needed for instances of a class the calling function doesn't need to know about the details, even if the runtime has to add dispatch code (that haskell 98 would never need).

I constantly worry about efficiency in my haskell code. Lazy evaluation helps here. Many algorithms that look like they loop repeatedly are actually linear because of haskell's laziness. Recursive string manipulations that return concatenated strings are usually linear despite strings being represented as linked lists. Laziness helps you avoid needleesly higher order implementations but has its own costs in memory allocation. Haskell's own Show class implements conversions to strings using a tail recursive showsPrec function instead of a lazily concatenating strings. The lazy functions are prettier though.

Container types can be horribly inefficent in haskell. I am trying to learn to use the ST monad to avoid unnecessary copying. This drops me back into an imperative world-view for the duration of the ST run.

Worrying about efficiency changes the way you think about the overall structure of your programme. Not necessarily for the better. These are not genuine concerns about higher order algorithms but about not implementing lower order algorithms properly.

In my two month odyssey to master haskell there have been many frustrations. The type and class extensions in GHC (and other modern haskells) has been an endless source of pain. Documentation is bad and there are infuriating syntactic snags. I spent an hour trying to use runST using the form

runST $ do
    ...

only to discover you can't use ($) in this situation but must use brackets instead. Why? It doesn't really make any sense.

I've tried to code to work over tuples substituting tuple pairs for the list constructor (:) but the class system just wont work this way

Finally figured out how to make haskell process a big pile of data without passing each drop of data around as an explicit arguement. I can't believe it has taken me a month to achieve such a simple outcome. The difficulty with the most obvious approach of bundling all the data together into a record and just changing the fields you are interested in is that you rewrite the master record each time. That's a lot of bookkeeping for the savings. A Monadic approach using a state monad is the way around that problem but it still scares me from an efficiency point of view. Even though this will be a shallow copy per update and not that expensive it still rankles to be do all that work for no reason.

In dynamically typed languages object-orientation is nice but not necessary to reperesent arbitrarily complex data. Weakly typed compiled procedural langauges (of which C is the most prominant) can deal with the bit representation of memory directly and avoid the strictures of strong typing. C++ is weirdly both more and less flexible than C. Nothing matches the rigours of Haskell. Data definitions in Haskell (and other typed functional programming languages) are usually easier to use than structures in C but cannot be circumvented at all. Representing your data in Haskell requires careful planning. In the standard Haskell98 there are no ways to represent data polymorphically which makes it odd that Haskell has a way of defining ``classes'' that sound a lot like an object-oriented class. It isn't; it does work somewhat like C++.

C++0x will include the STL notion of ``concept'' into the syntax of the language. Concepts are a kind of meta-type that corresponds closely to Haskell's class.

Not having a textbook to ease my introduction to Haskell, I have had to make do with what I could grab off net. It hasn't been very enlightening and the material on monads couldn't have been harder to digest. My years old copies of Byte Magazine have been great resources for all kinds of programming exotica including functional programming --- but Haskell and Monads are too old for Byte.