Erlang In Lisp
Google Summer of Code Proposal, 2008

Matt Bone

Abstract: The actors model presents a shared-nothing approach to concurrency that can be used on a parallel (i.e. multicore) machine or in a distributed environment. While some of the original implementations of the actors model were Lisp dialects, one of the few modern implementations is found in Erlang. For the Google Summer of Code, 2008, I propose an implementation of this functionality in Common Lisp that builds on previous attempts including cl-muproc and philip-jose.

1  Summary

The rise of multicore machines has led some to say there is a ’multicore crisis’. Many are searching for programming models that allow for parallelization without decreasing programmer productivity. All the while, interest in distributed systems continues to grow. Fortunately the actors model provides a solution to both of these problems simultaneously. Computation is decomposed into actors, each of which holds its own state and communicates with other actors via message passing. Thus actors without mutual time or data dependencies can execute in parallel and are easily mapped to threads, processes, or distinct machines.

Erlang provides a practical implementation of the actors model. It is easy to spawn an Erlang process (more like a lightweight thread than a traditional process), and the processes can be distributed to other machines transparently. An Erlang-like implementation in Common Lisp would be the best of both worlds, providing a computational model for concurrent and distributed systems without losing the many benefits of Lisp including meta-programming and a concise syntax. While cl-muproc accomplishes much toward this goal, it does not support the transparent distribution of processes. philip-jose allows the creation of processes on remote machines, but does not include the pattern matching or messaging facilities of Erlang. ErlangInLisp will rectify this situation using the work of both of these projects. Applications in ErlangInLisp will be written with an API similar to that of cl-muproc while preserving Erlang semantics. These applications will be able to be distributed transparently.

ErlangInLisp will be useful to those whose existing cl-muproc applications grow beyond the confines of one machine and now must run in a distributed fashion. The similiarties in API should make the porting process trivial. For those designing a distributed application from the outset, the transparency that ErlangInLisp will provide will be useful in debugging and development. The developer need not worry about running the programming in a distributed setting for initial testing.

2  Biography

I have worked on several small open source projects in the past, including Computational Neighborhood, a cluster computing framework, the Java Commodity Grid Kit, a grid computating abstraction layer, and BetterXML, a framework for simplifying the handling of various kinds of markup. Overall, I believe that we should strive to remove the mystery and brittleness of software, and the elegance and simplicity of Lisp can help in this regard.

My work on Computationaal Neighborhood (CN), makes me an ideal candidate for this project. The system decomposes computations into jobs and tasks. Tasks communicate to accomplish their work, and jobs organize the results of these tasks. Though the project went through many phases, it slowly approached the actors model. My work included the development of a pluggable messaging system as well as the development of a multicast system to to maintain a global picture of the cluster so as to distribute work fairly. Though CN is written in Java, the time spent thinking about concurrency and distribution issues will be applicable to ErlangInLisp.

3  Additional Notes

Eligibility
In the fall of 2008 I will continue my graduate studies with the department of Computer Science at Indiana University. Documentation can be provided upon request. I received an M.S. in Software Technology from Loyola University Chicago in December of 2007.
Mentor
François-René Rideau, Software Engineer at ITA Software Ltd.
Development Process
ErlangInLisp will be hosted in Git repository at repo.or.cz under the New BSD License. Development will be tracked with a blog.
Deliverables
An ASDF-Installable package implementing the functionality described in the document, complete with intelligible docstring-based developers documentation and a users manual.

4  Roadmap

4.1  Fork-Based Concurrency

While cl-muproc allows for intraprocess communication within a Lisp image via threads, in order to support communication in a distributed environment, ErlangInLisp must support interprocess communication. The first step will be to implement support for fork-based concurrency with an API similar to that of cl-muproc (something resembling muproc-spawn). This API will only spawn processes (i.e. heavyweight Unix processes), and the semantics must match Erlang, as a future goal is to compile Erlang to ErlangInLisp in order to leverage the tests, benchmarks, etc.

4.2  Message Passing with Sockets

Once processes can be forked, they must be able to communicate. Again using the cl-muproc API as a guide, messaging will be implemented via BSD sockets.

4.3  Distribution

Erlang requires the interpreter to be started on each of the remote machines, however, using philip-jose this will not be necessary. Instead, the appropriate process will be invoked with philip-jose as usual, and then the sockets will be set up for communication.

4.4  Pluggable Messaging

Though the initial messaging implementation will be handled via BSD sockets, it will be constructed so that other messaging strategies can be plugged in. For example, this could be used to implement an SSL messaging system, allowing ErlangInLisp to be useful on wide area networks where security is a concern.

4.5  Pluggable Concurrency

Similar to the messaging implementation, the creation of actors should be pluggable as well. Though ErlangInLisp will initially only support process level concurrency, it would be a mistake to abandon the thread level concurrency of cl-muproc. Thus the API created as the first step of the roadmap should be done so that concurrency strategies can also be pluggable. Ideally these strategies should be mixable, too, so that thread and process level concurrency can be used within one application if desired.

4.6  Testing

ErlangInLisp will use the interactive and exploratory aspects of the Lisp environment (SLIME and Emacs) but will also contain regression tests. It will use one of the many existing open source Common Lisp testing frameworks to be agreed upon later.


This document was translated from LATEX by HEVEA.