Functional Programming Seminar

Last week (21 Feb), I had the pleasure of co-hosting a seminar on Functional Programming at Ericsson. We were able to bring an impressive cast of speakers:

  • Simon Peyton-Jones, Microsoft Research
  • Satnam Singh, Microsoft Research
  • John Hughes, Chalmers
  • John Launchbury, Galois

Some notable people in the audience were Seif Haridi, Joe Armstrong, Thomas Arts, Mary Sheeran, Koen Claessen

I want to extend my sincere thanks to all the speakers and distinguished guests, and post the seminar slides and videos of the talks for your enjoyment. Some Ericsson-specific content from the seminar has been omitted.

You may view them as streaming video, or download them and watch them locally (using e.g. VLC, QuickTime or the Wimpy FLV Player). I’ve noted some trouble viewing this many embedded flash streams on a single page, so I’ve posted each talk individually under the FP Seminar category.

Links follow, in the order in which they were presented:

Simon Peyton-Jones:
“Taming Effects – The Next Big Challenge”

Satnam Singh:
“Declarative Programming Techniques for Many-Core Architectures”

John Hughes:
“Testing with QuickCheck”

Simon Peyton-Jones:
“Composing Contracts – An Adventure in Financial Engineering”

John Launchbury: “High-Assurance Software”

Panel discussion

What is Erlang-Style Concurrency?

Every now and then, a blog article appears on how to do “Erlang-Style Concurrency” in language X. I think this is a very good thing, as it indicates that people are starting to take a long hard look at concurrency.

However, there doesn’t seem to be any authoritative definition of the term “Erlang-Style Concurrency”. I thought I’d at least try to give my view.

Joe Armstrong writes the following in his book, Programming Erlang:

“In Erlang:

  • Creating and destroying processes is very fast.
  • Sending messages between processes is very fast.
  • Processess behave the same way on all operating systems.
  • We can have very large numbers of processes.
  • Processes share no memory and are completely independent.
  • The only way for processes to interact is through message passing.”

I guess this is about as concise and authoritative definition as any. However, it’s not the whole story.
I would add the following items:

  • Message passing is asynchronous.
  • Processes can monitor each other.
  • It is possible to selectively receive messages.
  • Remote processes appear largely the same as local processes.

So this roughly describes how concurrency works in Erlang. Are all these bullets necessary for Erlang-style Concurrency? Perhaps not.

I would pick the following items as necessary for Erlang-style Concurrency:

  • Fast process creation/destruction
  • Ability to support >> 10 000 concurrent processes with largely unchanged characteristics.
  • Fast asynchronous message passing.
  • Copying message-passing semantics (share-nothing concurrency).
  • Process monitoring.
  • Selective message reception.

A few words to explain the above:

Speed and scalability
In order for concurrency to be useful as a fundamental modelling paradigm, the programmer must feel that processes are cheap enough you can efficiently create as many processes as the problem calls for. If there is any single defining characteristic of Erlang-style Concurrency, it is that you should be able to model your application after the natural concurrency patterns present in your problem. If creating a process is perceived as expensive, programmers will reuse existing processes instead; if message passing is perceived to be expensive, various techniques will be invented to avoid sending messages. These workarounds are nearly always detrimental.

There will always be limits. Erlang was designed for agent-style concurrency; not for massive data parallelism. You can “only” have ca 120 million concurrent processes in Erlang, provided you have enough memory. Personally, I’ve verified that Erlang performs consistently up to 20 million concurrent processes (I didn’t have enough memory to go further.) The cost of creating an Erlang process (ca 5-10 us) will be prohibitive for some applications, but it’s at least an order of magnitude cheaper than creating UNIX processes or POSIX threads. It’s reasonable to expect Erlang-style Concurrency to use roughly the same process granularity as Erlang does.

Asynchronous message passing
It has been argued that synchronous message passing is a better building block than asynchronous message passing. It is probably true that synchronous message passing is much easier to reason about, but asynchronous communication (“send and pray”) feels more intuitive in a distributed environment (in which case environments based on synchronous message passing will resort to some form of asynchronous communication as well). Anyway, it is reasonable to argue that asynchronous communication is a defining characteristic of Erlang-style Concurrency.

Copying semantics
Note that this doesn’t necessarily mean that messages must be copied, but they must act as if they were. There are several reasons why this is important:

  • For reliability reasons, processes must not share memory
  • In the distributed case, copying is inevitable, and we want as similar semantics as possible between local and distributed message passing.

It is perhaps too strong to require that processes share nothing, as this would rule out Erlang-style concurrency in most existing languages (even languages like Scala make it possible to share data between processes). Let’s just say that the Erlang style is to make it easier to use share-nothing concurrency than to use sharing.

Process monitoring
This is the enabler of “out-of-band” error handling, or the “let it crash” philosophy, which is very typical for Erlang. The idea is that you program for the correct case, and rely on supervising processes for error handling. This has turned out to be a beautiful way of handling fault tolerance in large systems.

Selective message reception
There are many ways to achieve selective message reception, but for complex multi-way concurrency, you have to support at least one of them. This is something often overlooked when approaching concurrency. It’s not obviously needed in simple programs, but when it is needed, you will suffer complexity explosion if you don’t have it.

I would suggest that ability to support selective message reception is sufficient for Erlang-style concurrency. It can be done either by matching on a single message queue (Erlang, OSE Delta), or by using different mailboxes/channels (Haskell, .NET, UNIX sockets). Pick one, and find a suitable example to experiment with. You may use my presentation “Structured Network Programming” (also attached as pdf) as inspiration, if you like.