Lambda the Ultimate

The majority of existing languages are sequential; concurrency was added as an afterthought. This makes concurrent programming difficult for them. A typical example is Java: it has monitors (shared-state concurrency) and expensive threads. Two years ago, when I told the head of our department I wanted to teach concurrent programming in a second-year course, he exploded "That's impossible!".

The reaction of our department head is understandable: shared-state concurrency, the kind that Java has, is the hardest to program in. There are two other kinds of concurrency that are just as practical, but much easier to program: message-passing concurrency (asynchronous messages between sequential objects) and declarative concurrency (threads and dataflow synchronization added to functional programming).

The easiest is declarative concurrency (see chapter 4 of CTM). This seems to have been forgotten by almost everybody. Yet it is not new: the first article on it I found was by Gilles Kahn in 1974.

Declarative concurrency is so nice that I believe it should be the baseline execution model for functional programming. (Not strict or lazy evaluation, which are both sequential.) This leads to many good things, for example here are two. (1) All the usual functional building blocks become concurrency patterns. For example, Map is a broadcast that collects results, and FoldL is the heart of a concurrent object with internal state (it accumulates an internal state from a stream of messages). (2) I/O becomes very simple: program input is a stream and program output is a stream. This is a perfectly good solution to the problem of declarative I/O.

You argue that sequential languages make concurrency hard. I agree. You say COP solves this problem. That sounds fine.

But to change our dominant approach from seuqential to COP, I want to know how COP languages help solve the well known difficulties we have with sequential programming. To wit, building software systems is still something were are not very good at doing.

Would you consider implementations of Scheme (e.g. Gambit and I think PLT) that support processes on the scale and efficiency of Erlang to be COP?

Why or why not?

It's not enough to have cheap concurrency (although it is an important first step). To be easy to use, concurrency must also be transparent. For example, in Oz I can use any list operation in a concurrent setting (since a stream is simply a list with unbound tail that can grow during execution). In Erlang, when I send a message to a process, I don't know whether the process is on my machine or across the network, and I don't care. Does this work in Gambit and PLT or do I have to write different code?

(FWIW, PLT has a concurrency library that introduces the same primitives CML does.)

This isn't really surprising. There are very real limits on how much work can be squeezed through the bottleneck of a single CPU.

Prior to discovering the concepts behind declarative concurrency, the best solution I had found was Eiffel's SCOOP. It's not so much a question of Should we write our code in a distributed fashion, rather, given the need How can we do so? I find it surprising personally that this is an issue that is still yet to be widely addressed by language designers.

Wondering whether relational databases teaches us anything useful in terms of concurrency and declarative forms of programming? Or are sets too specific to model more general forms of concurrent languages?

Also, since Oz is heavily influenced by Prolog, I was wondering about your thoughts on the Mercury programming language. Mercury didn't really delve deeply into concurrency, but it is a nice marriage of logic and functional programming.

[So if Erlang does something like this then I guess it would be nice for the Scheme implementations too; I'm pretty sure such things exist (they do for CL, iirc)]

Regarding Mercury: it is much closer to the traditional Prolog style than Oz. Mercury keeps the Horn clause syntax. Mercury adds higher-order functions, static typing, and modes to Prolog. Mercury has no specific support for concurrency (it still supports global backtracking, AFAIK). Mercury in its original version jettisoned logic variables and constraints (they are coming back, though). Personally, I find that Mercury is too strongly attached to the Prolog tradition--many interesting language ideas have not been tried out in Mercury because of that.

Erlang does not use dataflow variables (which are actually logic variables in Oz). It synchronizes using the 'receive' statement, which takes a message out of a process mailbox using pattern matching. Erlang has no specific support for declarative programming, but it could be programmed in a 'declarative style': without race conditions. This is not quite as elegant as Oz, e.g., using functional building blocks as concurrency patterns is not possible in Erlang.

Unlike Erlang threads, CML threads aren't born with a message queue -- instead, channels (message queues) are first class values in CML and a thread can be handed a set of channels it can listen on when it is created. (Or if you're really hard core you can create a channel over which channels can be sent as values.) Note that you never directly send a thread a message in CML: you always send a message into a channel, where some potentially unknown other thread can pick it up.

Dually, sends and receives (and other synchronous operations like nondeterministic choice) are also first-class values in CML; you can compose them to build fairly complex protocols and then treat them as single conceptual entities.

That's not quite true. CML supports both synchronous and asynchronous messages natively - channels create synchronous communication and mailboxes create asynchronous communication. They have similar interfaces, but a CML.send (which works on a channel) blocks until somebody actually reads the message whereas Mailbox.send won't ever block.

You can implement mailboxes with channels but not the other way around (more generally, you can't get n-way rendezvous if all you have is (n-1)-way rendezvous), so if you've got to pick one channels are your best bet. But having both is awfully convenient. Besides, if you really want to, you can give yourself as big a headache as you'd like by creating channels over mailboxes, mailboxes over channels, channels that send channels that send mailboxes that receive channels, syncvars that hold mailboxes of channels, and so on.

By the way, hope you're enjoying CMU. Too bad we couldn't lure you over to U of C ... :)

That's the beauty of it, as they say.

In the terminology of CTM, a spreadsheet would look like this: each operation is a port object and each spreadsheet cell is a port object. The operations and spreadsheet cells are connected in a bipartite graph. Updating a spreadsheet cell sends a message to all the operations taking input from that spreadsheet cell.

Exercise for the reader: implement this :-) !

I would love to be proven wrong here--please give me evidence for others, if they exist! I mean good implementations, not paper designs.

Chasing some previous remarks I'll float LabVIEW. Certain terms in the Oz literature ring LabVIEW bells in my head. When I hear the term "data flow," LabVIEW's graphical wires come to mind. LabVIEW gives automatic concurrency - if no wires form dependencies between computational nodes, the nodes execute concurrently. It's concurrency for free. LabVIEW is a very professional, mature, compiled, commercial language, with a user base in the low millions, but seemingly little known in academic CS circles. That's a shame because it might be an ideal tool for introductory education. One of the problems is that NI markets the language not as the wonderful, general-purpose software development tool it really is, but as a vehicle to sell specialized NI hardware in the niche DAQ market. I have it from an employee that NI makes money on DAQ boards, not software.

Lazy evaluation between a producer and a consumer does coroutining. There is a kind of lockstep synchronization between producer and consumer. Whenever the consumer needs something, it passes control to the producer and waits. When the producer has produced it, it passes control back to the consumer, which continues where it left off.

If you want to build a bounded buffer between the producer and consumer, then you need to give the producer some slack. That is, if the buffer is of size n, then the producer can be anywhere from 0 elements ahead of the consumer to n elements ahead. With lazy evaluation, it's not possible to have this slack. To get it, you need concurrency. Chapter 4 in CTM gives code that shows how this works. BTW, the simplest implementation of a bounded buffer uses *both* lazy evaluation and concurrency.

Lazy evaluation is more an issue of resource management. For example, let's say you want to read and process a very big file, which may be bigger than the memory size of your program. If the file is read lazily (according to the need of the consumer), then this can be done even if your system has very little memory (as long as the consumer only needs to look at a small part of the file at a time!). For this use of lazy evaluation, you don't need concurrency.

This only scratches the surface of the relationship between laziness and concurrency! For more information, see chapter 4 in CTM.