Bill Clementson's Blog

Parallel Computing in Lisp - Part 3

Wednesday, January 19, 2005

At the Lightweight Languages Workshop #2 (LL2) in 2002, Todd Proebsting of Microsoft Research gave a presentation titled "Disruptive Programming Language Technologies" (see presentation, view video). In that presentation, he used Clayton Christensen's excellent book The Innovator's Dilemma to illustrate how even entrenched programming languages such as Java and C could lose dominance and market share when confronted with disruptive changes in technology. As part of that presentation, he listed a number of potentially disruptive technologies. One of these was "Concurrent Programming". He speculated that the opportunity for concurrent programming to be a distruptive technology is in that many applications are either explicitly or implicitly concurrent or distributed but are poorly catered for by concurrency features (OS threads, language threads, RPC) in use today. If a language provided superior concurrency capabilities, it could displace more popular languages in specific application areas. Once the "innovator" language assumes prominence in the "niche" area, it would expand further in usage and popularity and potentially displace the more popular languages in other areas as well.

At the same workshop, Joe Armstrong gave a presentation on "Concurrency Oriented Programming in Erlang" (see presentation, view video). In it, he illustrated how Erlang, with its built-in support for lightweight processes and extremely fast process creation, was far superior to either Java or C# in its ability to quickly create new processes. In fact, when an Erlang-based web server was compared to Apache (comparing KBytes/sec vs session load), the ability of Erlang to effectively support many concurrent, parallel processes meant that the Erlang-based web server was able to run over 80,000 sessions while the Apache web server died at around 4,000 sessions. (Note: in the illustration below, the green and blue plots represent Apache running locally and on an NFS file system, the red plot represents the Erlang-based web server running on an NFS file system)

Think of the types of applications that could benefit from a language with the ability to create huge numbers of lightweight, robust processes (e.g. -- parallel MRP/CRP runs in ERP systems, new types of airline fare searches, multi-user/process OS development, "swarm" applications, etc). A language with the ability to effectively support fast, cooperative, concurrent processing could have a significant "disruptive" potential in certain application areas and create the type of innovative disruption described in Christensen's book and Todd's presentation at LL2.

So, what would a language need to provide in order to have concurrency capabilities that are superior to existing popular languages? In his presentation, Joe Armstrong listed the characteristics of a COPL (Concurrency Oriented Programming Language):

• Processes are truly independent
• No penalty for massive parallelism
• No unavoidable penalty for distribution
• Concurrent behavior of program same on all OSs
• Can deal with failure

• Dirk Gerrits is working on Erlisp, a project that attempts to bring Erlang-like concurrency to Common Lisp. Although the project is still at a very early stage, it looks promising.
• Luke Gorrie (well-known in Lisp circles for the work he has done on SLIME) used to work for Bluetail, a Swedish startup that did some amazing work with Erlang. He is now working at another Swedish startup. He created Distel, a distributed Emacs Lisp with Erlang-style processes and message passing, and the Erlang distribution protocol. With Luke's strong CL and Erlang hacking background, it will be worth following what he does in the future!
• When Paul Graham showed off Arc (his work-in-progress new dialect of Lisp) at LL1 (see presentation, view video), it didn't have any special concurrency functionality. However, there were some good suggestions made as to what additional functionality should be included in the language, including a good discussion about concurrency (search for "Concurrency" in this page) and why current languages don't fare well. It will be interesting to see how much of this Paul includes in his development of Arc.
• Robert Morris founded Viaweb with Paul Graham and Paul often speaks highly of Robert's programming ability in his articles. Robert had some early experience ;-) with parallel programming before he and Paul founded Viaweb. He is now a Professor at MIT in the Parallel & Distributed Operating Systems Group. Although there is no evidence that his work is Lisp-related, it will be interesting to see what comes out of his current research at MIT.
• Kenny Tilton's Cells is more an example of constraint-based programming than it is concurrent programming; however, it does provide an interesting mechanism for data-driven concurrency. If Cells were to be combined with multi-processor support, this could be an interesting and innovative approach for multi-processor applications.
• There are a lot of Scheme research papers and links on Distributed, Parallel, and Concurrent Programming on the read-scheme web site.