Lambda the Ultimate

This post is follow up to my previous post about programming languages. If we apply the conceptual framework that was discussed in the post we will see that modern event-driven programs designed in OO paradigm (but not necessary in OO-language) has the following dimensions of analysis and discourse.

1. Steps (statements)
2. Work/evaluation (blocks/composite/statements/functions/procedures)
3. Processes (objects, methods, events)

IMHO component-based programming adds additional dimension: intentional/technical. But since this dimension is much more subtle and not universally accepted, I leave it out of this discussion.

Every piece of the code in modern OO-applications could be reasoned in the terms of these dimensions. It could be noted, that these dimensions of discourse are not independent. Each new dimension differentiate and integrates the previous one. And we could see dimensions were developed sequentially in mainstream languages:

1. Steps: FORTRAN, BASIC (line-based)
2. Steps+Work: Pascal, Algol, C
3. Steps+Work+Processes: C++, Java, ...

And modern mainstream OO-languages like Java even enforce this classification making every procedure or function belonging to some object or class. This raises some objections from functional programmers, but these objections are objected by OO programmers, that feel more comfortable when no code is left unclassified from point of view of these three dimensions.

The transitions between level 1 and level 1*2 was well documented in the essay “Go to considered harmful”. I would suggest to refresh line of reasoning used in that essay, since I would use the same line of reasoning later. I do not know the essay with similar clarity that discusses transition between 1*2 and 1*2*3.

The classical functional languages are much more tricky thing to classify. Firstly they try to suppress the first level Steps calling them non-pure, and then they introduce the first class functions, that clearly add to the process dimension of the program. So the primary focus of functional languages is level 2 with suppressed but leaking level 1 and half done level 3. The functional programming does add new “effects” dimension of discourse, but this dimension is somewhat underdeveloped, since some points on it are considered “better” then other. It is possible to write event-driven process-based programs in functional languages, it just less obvious since there less of language support.

Note that all of the above is directly describing the synchronous case. When things got to asynchronous case, the same dimensions can be applied. And here we will the same problems.

The step in the synchronous case was, modifying or reading program state, and going to the next statement to execute (either textually next, or jump). Work and processes based this step notions. Lets now consider how these dimensions map on asynchronous case:

1. Step: In asynchronous case the step is receiving event, modifying state, and sending events.
2. Work: The work dimension would be notion of block that has single point of entry (by events) and has a single exit (producing event). Then asynchronous blocks could be parametrised as asynchronous procedures and composed using asynchronous operators.
3. Process: The process based decomposition is quite obvious, it is a component that has state and receives and sends events.

Note that the classical actor model provides only two of these dimensions: 1*3. There is notion of step and there is notion process (actor). And there every event is processed in the single step.

Erlang truthfully implement this model. And it also assumes single step event processing. There is also no work-based decomposition. The work dimension is lost from Erlang. It is also lost from all Erlang-style implementation of actor model.

The proof is quite simple. It is not possible to esaly apply functional composition operators to Erlang actors. And it is possible to specify which events actor receives, but it is hard to specify specify which are directly or indirectly produced by the actor. So it is asynchronous version of “go to” mess of synchronous code.

Note that there is the language that support all three dimensions. It is E programming language. This is possibly the first language that allows for structured asynchronous programming. The primary enabler for such programming is “when” operator that takes operation that returns promise as parameter and returns promise as result. This allows composing asynchronous processes. However the set of asynchronous operators in E is not complete. I have also created AsyncScala library in the same paradigm, that has a richer set of asynchronous operators. There is also AsyncGroovy library in the source repository, but it somewhat dated (it could be revived, if someone wishes to take over it).

The key differences of E-style 1*2*3 actors in contrast with with classical 1*3 actors are the following:

1. There is a notion of asynchronous expression and asynchronous operation, and code reflects structure of assumed asynchronous operations. Usually there is a Promise object that represents outcome of composite asynchronous operation.
2. Actors are separate from event queue. Single event queue could support many actors.
3. Actors are lightweight.
4. The framework is responsible to delivering events to the specific objects that represent actors. The normal asynchronous code does not have operations that explicitly retrieve operations from event queue.

Since a collection of E-style actors in one vat logically represent single Erlang-style actor, then I would like to name this model sub-actor model, in order to distinguish it from classical actor model, but possibly there is a better name for them.

Thus I claim that E-style actors are more powerful then Erlang-style because they provide explicit support for additional dimension of analysis and discourse about asynchronous program: work-based decomposition of the program. Erlang-style actors do not provide explicit support for this dimension, and this causes much of the pain related to asynchronous programming in Erlang.

And if you are designing a new programming language or a library that supports asynchronous programming, please consider adding a explicit notion of compose-able asynchronous operations to it. A good smoke test for notion of asynchonous operation would be applicability of functional composition operations to asynchronous operations. It really is not that difficult, just try not to leave out the key features mentioned above. You could use E or AsyncScala as a sample.

Update 1 (2012-02-20): fixed some typos