Lambda the Ultimate

I come from a world where asynchronous message passing is the normal way of designing your applications. The operating system, called OSE, is designed primarily for this. It took a large number of years before it got a mutex...

Now that things are becoming more and more concurrent, this programming paradigm starts to become more and more attractive. The reason is that this will create concurrency on a much higher level, making communications between processes taking less bandwidth.

My own finding is that if you construct a thread/process that has the following design:

myProcess
   initialization code
   forever
      getMessage
      if message in wait queue
         continue executing message
      else
         start message execution
         if response needed, put message into wait queue
      end if
   end forever
end myProcess

The important thing here is that the process has only one synchronization point, the line saying "getMessage". After that, it will work on the message until it needs a response from someone in order to continue, or until the work is done and a reply has been sent.

The problem is that above construction is non-trivial to implement in languages like C, and it is the wait queue that has the complexity. I would like support from a language to make this easier.

If you also consider that you might want to make decision about what objects will be put in which core/process/thread late in the design, and maybe also being able to change this after the first version has been shipped, this becomes an interesting problem. I come from a real-time world where you want things to be quick and easy to design and implement from the beginning, and then possible to fine tune until the performance and characteristics are just the way you want it.

My idea here was to concentrate on the popular object-oriented approach. The process above would then be a (special?) class, where the methods would actually be messages being sent to an instance of that class. This way, the programmer does not need to learn any new special stuff to get things done.

The idea here would be that the methods describe sequences to be executed, where each method corresponds to an asynchronous message being received by the object. If the sequence calls another object that uses asynchronous message passing, the compiler handles the fact that the method will return to main loop, put its state into a wait queue, send the request and then wait for an answer. When the answer comes, it will continue in the method where it left off.

One implication of this is that the accesses to the internal state of the object is subject to concurrency, so some way of specifying what needs to be atomic must be offered to the programmer to help the compiler. Or at least, I think so...

Anyone has any thoughts on this? Am I on to something here, or just out in the blue dreaming?

A Monadic Framework for Delimited Continuations (PDF), R. Kent Dybvig, Simon Peyton Jones, Amr Sabry. TR, June 2005.

Delimited continuations are more expressive than traditional abortive continuations and they apparently seem to require a framework beyond traditional continuation-passing style (CPS). We show that this is not the case: standard CPS is sufficient to explain the common control operators for delimited continuations. We demonstrate this fact and present an implementation as a Scheme library. We then investigate a typed account of delimited continuations that makes explicit where control effects can occur. This results in a monadic framework for typed and encapsulated delimited continuations which we design and implement as a Haskell library.

A fascinating paper about delimited control. I'm very much a newbie to delimited control, but this paper has been enormously helpful - despite the title. ;)

The basic idea of the paper is to represent the execution context as a sequence containing prompts (control delimiters) and the (partial) continuations between prompts. This model is formalized with an operational semantics, which was insightful even though it's the first operational semantics I've studied.

The authors then present an implementation of the model in terms of call/cc in Scheme. The basic idea here is to always perform user code after aborting to a context near the bottom of the stack, just above a call to an underflow function - this means that even though we use undelimited call/cc, we only ever capture our (small, partial) execution context. The whole execution context (the "metacontinuation") is maintained as a sequence data structure in a global variable (basically, a list containing prompts and Scheme continuations). The underflow function destructures the metacontinuation, and executes (returns to) the partial continuations stored in it. Pushing a prompt adds a delimiter to the metacontinuation, capturing a delimited continuation splits the metacontinuation at a delimiter, and composing a continuation appends to the metacontinuation.

I haven't even gotten to the later parts of the paper yet, but this model and the Scheme implementation alone is worth a look.

(The paper seems to be a reworked version of A Monadic Framework for Subcontinuations, discussed previously.)

I realize that many of you here aren't big fans of big languages like C++, but perhaps D is more palatable to you? Andrei Alexandrescu answers the question "Why D (not the name, but why make D, what problems does it solve that C++ can't, etc)?".

This is generally a really good discussion among three titans of the native(C++ and D) programming world -> Herb Sutter, Scott Meyers and Andrei Alexandrescu. They also dig into language design principles/processes and discuss some of the trade offs (theory versus pragmatics) and unforced errors that human language designers all make. Tune in if you have the time. It's worth it, in my opinion.

Charles