Clementson's Blog

Concurrent/Parallel Programming - The Next Generation - Part 2

Wednesday, January 11, 2006

A few days ago, I posted about the need to look at alternative concurrency approaches in order to take advantage of the opportunities offered by the move towards multiple processors and parallel machines. In that post, I highlighted the 3 different main concurrent programming paradigms (Shared-state Concurrency, Message-passing Concurrency, and Declarative/Dataflow Concurrency). I indicated that "Shared-state Concurrency" is the most widespread but that it doesn't scale (complexity-wise) very well. In the remainder of the post, I focused on the "Declarative/Dataflow Concurrency" paradigm and provided some examples. In this post, I'll talk a little bit about the Lisp alternatives for "Message-passing Concurrency" (which is the model that Erlang has used so successfully).

First of all, for those who are not familiar with Erlang, it is worthwhile to highlight the characteristics of Erlang that have contributed to its success (from the Erlang white paper):

• Concurrency: Erlang has extremely lightweight processes whose memory requirements can vary dynamically. Processes have no shared memory and communicate by asynchronous message passing. Erlang supports applications with very large numbers of concurrent processes. No requirements for concurrency are placed on the host operating system.
• Distribution: Erlang is designed to be run in a distributed environment. An Erlang virtual machine is called an Erlang node. A distributed Erlang system is a network of Erlang nodes (typically one per processor). An Erlang node can create parallel processes running on other nodes, which perhaps use other operating systems. Processes residing on different nodes communicate in exactly the same way as processes residing on the same node.
• Robustness: Erlang has various error detection primitives which can be used to structure fault-tolerant systems. For example, processes can monitor the status and activities of other processes, even if these processes are executing on other nodes. Processes in a distributed system can be configured to fail-over to other nodes in case of failures and automatically migrate back to recovered nodes.
• Soft real-time: Erlang supports programming "soft" real-time systems, which require response times in the order of milliseconds. Long garbage collection delays in such systems are unacceptable, so Erlang uses incremental garbage collection techniques.
• Hot code upgrade: Many systems cannot be stopped for software maintenance. Erlang allows program code to be changed in a running system. Old code can be phased out and replaced by new code. During the transition, both old code and new code can coexist. It is thus possible to install bug fixes and upgrades in a running system without disturbing its operation.
• Incremental code loading: Users can control in detail how code is loaded. In embedded systems, all code is usually loaded at boot time. In development systems, code is loaded when it is needed, even when the system is running. If testing uncovers bugs, only the buggy code need be replaced.
• External interfaces: Erlang processes communicate with the outside world using the same message passing mechanism as used between Erlang processes. This mechanism is used for communication with the host operating system and for interaction with programs written in other languages. If required for reasons of efficiency, a special version of this concept allows e.g. C programs to be directly linked into the Erlang runtime system.

• Termite: This is an Erlang-inspired Scheme implementation that was developed at the University of Montreal and runs on Gambit Scheme. There were a number of presentations and papers on it last year (e.g. - at Montreal and Glasgow); however (unfortunately), there doesn't appear to have been much movement in the project since the presentation at the 2nd European LISP and Scheme Workshop. (Note: see the update at the bottom of this posting.)


• Erlisp: I've mentioned the Erlisp project that Dirk Gerrits (and others) has been working on in the past. Erlisp is an attempt to implement an Erlang-like approach to concurrency in Common Lisp. There is some code available; however, progress has been slow. Incidentally, in addition to the Erlisp code, Dirk has assembled an excellent "References" page in which he links to many concurrency-related resources.


• CL-MUPROC: A fairly new development effort, CL-MUPROC is an implementation of a number of Erlang concepts in Common Lisp. Its goal is to create an embedded language in CL that provides for message-passing concurrency, scalability, reliability, and that is expandable to distributed operation. Klaus Harbo recently gave a presentation to the Danish CL user group and he has sent his presentation to me. I am hosting it here (with his permission) as I think it's an excellent presentation that shows how an Erlang-like implementation in CL could work. There are a lot of examples from the Erlang white paper in the presentation where Erlang code is compared with the equivalent CL-MUPROC code. As Peter Norvig has demonstrated in the past, this approach is a very good way to introduce either a new programming language or new concepts to people.
  
  I asked Klaus a number of questions regarding CL-MUPROC:
  1. Q. Is CL-MUPROC an internal development only or will it be made available at some stage (if so, with what type of license?)?
     A. Well, it's an issue we're struggling with, and have been for some time. Basically, we'd like to release it, but we also need to look out for Mu's commercial interests, and right now we're not in a position to make that decision. Personally, I hope we'll be able to do it.
  2. Q. What Lisp implementation (or implementations) does CL-MUPROC work with?
     A. We've chosen to go with Lispworks, so that's what it runs on. I believe it ports quite easily, though. If we release it, I hope to move it to acl-compat.mp to make it more easily accessible.
  3. Q. Have you compared performance of equivalent programs written in CL-MUPROC with Erlang?
     A. Not at all. I have no idea how they'll compare. It's worth noting, though, that CL-MUPROC piggy-packs on the CL implementation's threading system, which will not compare favourably under some circumstances. Also, the number of threads supported by CL implementations is far lower than that of Erlang; I believe Allegro v7 is restricted to no more than 650 simultaneous Lisp processes, for example. This also means that programming scalably in CL-MUPROC will be different than programming scalably in Erlang.
     [Note (comment from Bill, not Klaus): Actually, ACL v7 (and v8) only supports 350 simultaneously running processes. I'm not sure what the limit is with LispWorks. I've heard rumours that LW is enhancing their MP support in v5.0; however, I don't know that for certain. It would be nice to have a CL implementation that supports large numbers of lightweight processes.]
  4. Q. Is there any sharing of code (or other sharing) with Erlisp (Dirk Gerrits' project)?
     A. No. I took at look at what Dirk had in early 2005. It did not seem to me that it would be worthwhile for us to try to leverage his efforts, there just did not seem to be more than what we could do very quickly, and then we'd have complete control. It's not that we do not want to co-operate, we just thought we'd be able to move more quickly if we could control everything ourselves. (I was quite a bit confused by what was proposed wrt. Erlisp in the Summer of Code project; it didn't seem to mesh well with what we're trying to achieve with CL-MUPROC, so it kind of reinforced my impression that not trying to build on Erlisp was the right decision). I'm quite envious of the Erlisp name, though! ;-)
  5. Q. Do you have any objection to me mentioning CL-MUPROC on my blog and posting a link to your presentation? Is there an online location for your presentation that I can link to? (if not, I can upload it to my blog's server).
     A. We don't mind you mentioning it at all. At this point, there's no 'official' web place for CL-MUPROC, so it should be okay for you to make the presentation available via your blog site.
  6. Q. Is there any other material and/or code available?
     A. Not that we can release at this point.
  7. Q. In the presentation, you mentioned that this project was being done for an online betting system. Is the client already using the software in production? Are there any other current (or prospective) customers for CL-MUPROC?
     A. No, we do not have any production system up as yet. However, we do consider CL-MUPROC production quality; we have no concerns putting it into production systems.
  8. Q. In the presentation, you mention a goal as being "expandable to distributed operation" but it is not clear from the presentation whether this has been done yet. Has any progress been made on implementing this in CL-MUPROC or is CL-MUPROC currently limited to running on a single machine?
     A. No, we haven't done anything on that front yet. However, I have taken care to design the API so that it should support distributed operation with very little change; I believe only 'muporc-spawn' absolutely has to change. But the changes required in the run-time system is a different matter!
  9. Q. What are the "next steps" that you have planned for CL-MUPROC?
     A. Well, right now we're really busy _using_ CL-MUPROC in a system we're building; it actually does just about everything we need from it right now, so we don't have big, immediate plans (I added the Generic Server and Supervisor functionality in November, so it's not that we've stopped developing it! ;-).
  Klaus also indicated that he will be presenting CL-MUPROC at the next Euro Lisp Users Conference (tentatively planned for April in Hamburg). So, if you want to hear more about Erlang-like processing in CL, that would be a terrific opportunity!


• Distel: Luke Gorrie (of SLIME fame!) developed Distel before he got involved with SLIME. He describes it as:

  "Distel extends Emacs Lisp with Erlang-style processes and message passing, and the Erlang distribution protocol. With this you can write Emacs Lisp processes and have them communicate with normal Erlang processes in real nodes. This makes it easy to write convenient Emacs user-interfaces to Erlang programs."

  I had (vaguely) known about Distel for some time; however, I think I was mentally confusing it with Ermacs (another Luke Gorrie project, but Ermacs is Emacs re-implemented in Erlang rather than just being an add-on to Gnu Emacs as Distel is). I recently downloaded Distel and had a play with it using Aquamacs Emacs in OS X. It is really cool! Although Emacs does not natively support multiple processes, Luke has managed to emulate that capability by using a combination of Emacs buffers, trampolines, simulated continuations, and a bit of #8 baling wire ;-). Not only does Distel provide a nice development environment for working with Erlang code, it also provides Erlang-like support for Emacs Lisp. It's also interesting to examine the Distel code and recognize some of the similarities to things that have gone into SLIME! By the way, did I mention that it is really cool?
  
  Here's a screenshot using an example from Distel of two processes communicating (one sending messages and the other receiving and printing them):
  
  
  
  Luke has produced some great documentation for Distel as well:
  • A User Manual
  • A Reference Manual
  • A Conference Paper (from the 2002 Erlang User Conference)
  
  So, if you're interested in playing around with Erlang, Distel+Emacs is a really great IDE; however, Distel is still useful even if you never touch a line of Erlang code. And, if you want to play around with message-passing concurrency in Lisp, Distel provides an easy way (for someone who is confortable with Emacs Lisp) to experiment with the concepts.

"Since the Termite paper was presented at the European Scheme and Lisp workshop a few things have happened:

1. The mailbox mechanism has been integrated into Gambit's thread model, which improves the performance of messaging in Termite, and allows "message-passing" programming (between local threads) in the standard Gambit system. Serialization and deserialization has also been improved.
2. A "Distributed Computing" example was added to the examples in the distribution. It shows how to implement a distributed computing library in about 700 lines of Scheme code (including process migration, location transparency, and serialization of I/O ports).
3. Guillaume Germain will soon be done with his thesis, and has written several interesting Termite examples. Stay tuned.

The most difficult aspect of this distributed programming language research is that there are so many abstraction levels to choose from. Should Termite be a minimal language on which others can build their own distributed computing system, or should it provide a large set of predefined features (such as process migration, location transparency, etc)? In the spirit of Scheme, Termite aims to be a small maleable distributed programming language. We're hoping that it will be the basis for other more specific distributed programming languages developed here or elsewhere."