Lambda the Ultimate

Robin Milner's 1991 Turing Award Lecture describing CCS (Calculus for Communicating Systems) and pi-calculus.

The paper The Polyadic pi-Calculus: a Tutorial (1991) by Robin Milner doesn't appear to have been mentioned on the front page previously of LtU before. I think it is worth pointing to for beginners, since it appears to do a good job of covering the basics of pi-Calculus.

Abstract: The pi-calculus is a model of concurrent computation based upon the notion of naming . It is first presented in its simplest and original form, with the help of several illustrative applications. Then it is generalized from monadic to polyadic form. Semantics is done in terms of both a reduction system and a version of labelled transitions called commitment ; the known algebraic axiomatization of strong bisimilarity is given in the new setting, and so also is a characterization in modal logic....

For those fairly new to the group, pi-calculus is a formal calculus for studying concurrent computation. This would be a good thread for others not only to comment on this paper, but to mention other good entry points for the study of concurrency, and other calculi related to the pi-calculus.

TM (transactional memory) provides a new concurrency-control construct that avoids the pitfalls of locks and significantly eases concurrent programming. It brings to mainstream parallel programming proven concurrency-control concepts used for decades by the database community. Transactional-language constructs are easy to use and can lead to programs that scale. By avoiding deadlocks and automatically allowing fine-grained concurrency, transactional-language constructs enable the programmer to compose scalable applications safely out of thread-safe libraries.

Nothing new here for LtU regulars, I guess, but you may still want to check out this column.

Matti Rintala, Handling multiple concurrent exceptions in C++ using futures.

Aside from describing the way exceptions are handled in KC++, a concurrent C++ sytem based on active objects, this nice paper provides a short and readable description of the main difficulties in combining exceptions and asynchronous calls.

The KC++ approach is library based, and the paper explains how KC++ matches itself to the C++ exception handling model.

The description of the Ada model, in section 7, may be a bit unclear. Specifically, a nuance that is easy to overlook is that exceptions raised within an accept statement (and not handled there) are propagated both in the calling and in the called tasks. The Ada83 Rationale explains this in more detail and gives examples of use.

From an historical perspective it is a bit amusing (and also quite sad) that the issues resulting from the interaction of concurrency and exceptions, that the Ada designers had to tackle in late '70s early 80s, still occupy the time of language desginers today.

Event-Based Programming without Inversion of Control. Philipp Haller and Martin Odersky.

Scala is different from other concurrent languages in that it contains no language support for concurrency beyond the standard thread model offered by the host environment. Instead of specialized language constructs we rely on Scala's general abstraction capabilities to define higher-level concurrency models. In such a way, we were able to define all essential operations of Erlang's actor-based process model in the Scala library.

However, since Scala is implemented on the Java VM, we inherited some of the deficiencies of the host environment when it comes to concurrency, namely low maximum number of threads and high context-switch overhead. In this paper we have shown how to turn this weakness into a strength. By defining a new event-based model for actors, we could increase dramatically their efficiency and scalability. At the same time, we kept to a large extent the programming model of thread-based actors, which would not have been possible if we had switched to a traditional event-based architecture, because the latter causes an inversion of control.

(There's not really a proper abstract. The above is from the conclusion.)

I enjoyed this paper. It's a quick read and a nice demonstration of some of Scala's cool features. It's also a good example of using exceptions as delimited control operators, and in fact the one substantial restriction is imposed by the lack of the more powerful operators. They use Scala's type system to reduce the burden of this restriction, however, since they're able to state that a particular statement never returns normally (and thus must not be followed by more statements).

Those interested in the language/library boundary will also find it interesting for this reason:

The techniques presented in this paper are a good showcase of the increased flexibility offered by library-based designs. It allowed us to quickly address problems with the previous thread-based actor model by developing a parallel class hierarchy for event-based actors. Today, the two approaches exist side by side. Thread-based actors are still useful since they allow returning from a receive operation. Event-based actors are more restrictive in the programming style they allow, but they are also more efficient.

They have some fairly impressive empirical scalability results as well.

A Mobility Calculus with Local and Dependent Types, by Mario Coppo, Federico Cozzi, Mariangiola Dezani-Ciancaglini, Elio Giovannetti and Rosario Pugliese

Abstract:

We introduce an ambient calculus that combines ambient mobility with process mobility, uses group names to group ambients with homologous features, and exploits co-moves and runtime type checking to implement flexible policies for controlling process activities. Types rely on group names and, to support dynamicity, may depend on group variables. Policies can dynamically change also through installation of co-moves. The compliance with ambient policies can be checked locally to the ambients and requires no global assumptions. We prove that the type assignment system and the operational semantics of the calculus are ‘sound’, and we define a sound and complete type inference algorithm which, when applied to terms whose type decorations only express the desired policies, computes the minimal type annotations required for their execution.
As an application of our calculus, we present a couple of examples and linger on the setting up of policies for controlling the activities of the objects involved.

Nested commits for mobile calculi: extending Join
by Roberto Bruni, Hernan Melgratti, Ugo Montanari

In global computing applications the availability of a mechanism for some form of committed choice can be useful, and sometimes necessary. It can conveniently handle, e.g., contract stipulation, distributed agreements, and negotiations with nested choice points to be carried out concurrently. We propose a linguistic extension of the Join calculus for programming nested commits, called Committed Join (cJoin).
It provides primitives for explicit abort, programmable compensations and interactions between ongoing negotiations. We give the operational semantics of cJoin in the reflexive CHAM style. Then we discuss its expressiveness on the basis of a few examples and of the cJoin encoding of other paradigms with similar aims but designed in different contexts, namely AKL and Zero-Safe nets.

To me the main interest lies in section 4.2, which shows an encoding of a subset of AKL in cJoin.
More references to relationships between logic/constraint and "pi-family" approaches to concurrency are welcome!

Continuations for Parallel Logic Programming
by Eneia Todoran and Nikolaos S. Papaspyrou

This paper gives denotational models for three logic programming
languages of progressive complexity, adopting the
"logic programming without logic" approach. The first language
is the control ow kernel of sequential Prolog, featuring
sequential composition and backtracking. A committed-choice
concurrent logic language with parallel composition
(parallel AND) and don't care nondeterminism is studied
next. The third language is the core of Warren's basic Andorra
model, combining parallel composition and don't care
nondeterminism with two forms of don't know nondeterminism
(interpreted as sequential and parallel OR) and favoring
deterministic over nondeterministic computation. We show
that continuations are a valuable tool in the analysis and
design of semantic models for both sequential and parallel
logic programming. Instead of using mathematical notation,
we use the functional programming language Haskell
as a metalanguage for our denotational semantics, and employ
monads in order to facilitate the transition from one
language under study to another.

This paper happens to combine several topics that interest me lately - AKL (a precursor of Oz), denotational semantics, continuations, and implementing programming languages in Haskell.

If you share at least some of these interests - take a look!

I was going to post this to the front page, but it's already a Forum Topic. So go there to read about a preprocessor that adds continuations to JavaScript by transforming to CPS (I think).

Tim Harris, Simon Peyton-Jones. Transactional memory with data invariants. March 2006. TRANSACT '06, to appear.

This paper introduces a mechanism for asserting invariants that are maintained by a program that uses atomic memory transactions. The idea is simple: a programmer writes check E where E is an expression that should be preserved by every atomic update for the remainder of the program’s execution. We have extended STM Haskell to dynamically evaluate check statements atomically with the user’s updates: the result is that we can identify precisely which update is the first one to break an invariant.

The STM approach is sometimes described as being "like A and I" from ACID database transactions; that is, atomic blocks provide
atomicity and isolation, but do not deal explicitly with consistency or durability. This paper attempts to include “C” as well, by showing how to define dynamically-checked data invariants that must
hold when the system is in a consistent state.

While the basic idea is straightforward, the discussion of the design decisions in section 3.5-3.7 is an interesting exploration of the design space.

The implementation technique and operational semantics are the main contributions.

Previous draft discussed here.