Roadmap

Erlisp is now defunct. These pages merely serve to preserve its history.

Stage 1: Erlang

Erlang is a small but powerful functional, parallel, and distributed programming language originally developed at Ericsson for use in the telecom industry. It’s been really successful as a parallel and distributed programming language, and is pretty Lisp-like for a language with syntax, so it seems like a good starting point. Therefore having (most of) Erlang in Common Lisp is the goal for phase 1 of this project. I plan to go about this “port” in a modular, step-by-step fashion, guided by the different features of the Erlang language.

Erlang features

• Functional programming
  Common Lisp has pretty much got that one covered. However, that Common Lisp in addition has mutable data structures is something that will have to be taken into account at all stages. It raises some issues, like circular data, that cannot occur in Erlang.

• Module system
  Common Lisp’s package system is more than adequate.

• “Hot” code upgrades
  Common Lisp already supports this, albeit in a slightly different fashion. The problem is that the behaviour is not really well defined. A CLRFI might be necessary…

• Data types
  Erlang supports only a small but powerful set of primitive and compound data types. Most of these have very close Common Lisp counterparts, the rest should be easily implementable as Common Lisp classes or structures.

• Pattern matching
  Pattern matching is used extensively in Erlang. Common Lisp doesn’t really offer a pattern matcher, but it’s not overly hard to write one. However, there’s no consensus on what would make the best pattern matcher for Common Lisp. Therefore I intend to give Erlisp a pretty simple but adequate one by default, and allow the user to replace it.

• Tail recursion
  Erlang, like Scheme, is properly tail-recursive. Therefore, recursion can (also) be used to do iteration, hence keeping the language small and clean. Tail recursion is not essential to Erlang however, so it is no problem that Common Lisp has iteraction constructs and that it isn’t guaranteed to be properly tail-recursive.

• Ports
  Ports allow Erlang programs to interact with their environment. A port could be connected to a program written in another language, a file, or some other external resource. Processes can treat ports as if they were also processes by sending them messages and receiving messages back.

  While I think ports are a great idea for Erlang, I’m not going to support them in Erlisp. If a single process wants to use an external resource it can do so in the normal Common Lisp way. If multiple processes need to have access to a single external resource you can simply introduce an extra “server”-process that controls the resource for its “client”-processes.

• Standard library
  The Erlang standard library is pretty small, and has some overlap with that of Common Lisp, so Erlisp will probably provide a substantial part of Erlang’s standard library. Functionality that is better provided by a pure Common Lisp library will be kept out of Erlisp though. For example, Erlang has a nice, declarative syntax for constructing and destructuring binary data, but that’s completely orthogonal to its other features, and can be done in pure Common Lisp. See Binary-types, for example.

• Error handling
  Common Lisp’s condition system is way more advanced than Erlang’s. However, Erlang supports parallel (and even distributed) processes to be “linked” together. If a process terminates, the reason for termination gets broadcast to all the linked processes. If the terminating process terminated abnormally, the default action is for the linked process to terminate as well. For a normal termination, the default behavior is to ignore it. The default behavior can be changed so that instead the linked process receives an actual message, than can be dealt with as any other.

  I do not currently foresee any problems in adding this functionality to the Common Lisp condition system. An abnormal termination in Common Lisp will involve a condition that was raised and not handled. This condition could be sent to the linked processes, where it would then be reraised (with a different condition class) by default.

• Parallel programming
  Concurrency in Erlang is based on light-weight, sequential processes communicating with asynchronous “send-and-pray” message-passing. Apart from a per-machine process registry, Erlang processes are totally independent, and cannot access each other’s data directly.

  Most Common Lisp implementations support threads which could be used to implement concurrency. However, operating-system threads have a lot more overhead than Erlang processes, and user-level threads are usually non-preemptive. Also, to have true independence, special variable bindings should be on a per process basis.

• Distributed programming
  Erlang handles distributed programming exactly the same way as parallel programming. Whether messages are sent over a network or not is mostly transparent to the Erlang programmer.

  Implementation of this is not totally straightforward, but with a low-level socket library and a good look at an open-source Erlang implementations it should be doable. The CLOS MOP makes serialization of most Common Lisp objects pretty simple in principle, but dealing with circularity may be costly, and not dealing with it might lead to unwanted behavior.

• Soft real-time programming
  Common Lisp may be useful to build tools and languages to do real-time programming, but as far as I know it isn’t itself usable for it. Erlisp may support Erlang’s time-outs and process priorities, but I’m certainly not going to try to make Common Lisp suitable for soft real-time programming as Erlang is.

Step 0: Get it started

I will be setting up a publically visible GNU Arch darcs repository to do my development in. I’m not currently looking for co-developers, but anyone is of course free to check-out the code and send me their suggested changes.

[DONE] As of 24 October 2004, the latest code is accessible at all times through the download page.

[UPDATE] As of 11 November 2004, there is an Erlisp mailing list, courtesy of Common-Lisp.net. See the discussion page for details.

[UPDATE] As of 21 February 2005, I’ve switched to darcs for its much greater ease of use compared to GNU Arch. See the download page for details.

Step 1: Make it parallel

The first Erlisp milestone will just offer Erlang-style parallelism on one machine. Light-weightness is not an immediate goal. The most promising target platform for this release is SBCL, as it provides operating-system threads with thread-local special variable bindings. SBCL-dependencies will be kept to a bare minimum though, in order to allow Erlisp to be ported to other Lisps later on.

[STATUS] Currently implemented features are:

• Processes as threads.
• Local message sending and receiving.
• API to plug in your own pattern matcher.

Step 2: Make it distributed

The next milestone will add distribution to the mix. As SBCL supports BSD sockets, sticking to SBCL will probably be a good choice. This milestone is nothing to sneeze at, as implementing a fault tolerant distribution model is not an easy task. It seems prudent to take a good look at an open-source Erlang implementation for guidance.

Step 3: Make it fast

When all the functionality is basically there, it’s time to see if processes can be made more light-weight. I see two ways to do this:

• Using continuations as green threads.
  This would limit the points at which processes can be preempted, but that can be partially alleviated by assigning an operating system thread to every few green threads. Also, less preemption is not necessarily a problem.

• Hacking the Common Lisp implementation.
  If SBCL would have more light-weight threads, then so would Erlisp. Alternatively, Erlisp could be ported to CLISP, where light-weight processes could be added to the virtual machine from scratch. CLISP also has a socket library so porting Erlisp’s distribution aspects should be straightforward.

Step 4: Make it portable

If sockets and light-weight processes with process-local special variable bindings were standardized, Erlisp could be made a lot more portable. The idea is to either get CLRFIs of my own accepted, or to participate in the discussion period of relevant CLRFIs by others. A compelling case for light-weightness should be prepared for the CLRFI discussion.

Stage 2: Metaobject protocol

With Erlisp having been realized, it seems time to look beyond Erlang. There are a lot of interesting models of parallelism and distribution out there and many of them will not be easily implementable with threads and sockets, or even with Erlisp.

A similar situation occurred once in Common Lisp’s early history. There was a proliferation of Lisp object systems that had a lot in common in implementation, yet were not adequately implementable in terms of each other. In order to be backward compatible with all of these, the Common Lisp Object System (CLOS) was designed with a metaobject protocol (MOP). The CLOS MOP allows users to change the object system in a controlled way, thus giving users not one object system, but any object system they desire.

I aim to do develop something similar for parallel and distributed programming. This is very much a long term goal, as the design of a metaobject protocol is a hard and evolutionary process with which I have absolutely no experience.

Any ideas you may have on the matter will be appreciated.