Bill Clementson's Blog

Update on Termite (A Lisp for Concurrent/Parallel Programming)

Sunday, January 22, 2006

I recently wrote two posts on "Concurrent/Parallel Programming - The Next Generation" (see here and here). Part 2 dealt with Lisp alternatives for "Message-passing Concurrency" (which is the model that Erlang has used so successfully). In that post, I mentioned Termite, an Erlang-inspired Scheme implementation that was developed at the University of Montreal and which runs on Gambit Scheme. In that post, I bemoaned the fact that there didn't seem to have been much movement in the project since the presentations last year. However, since then, I have received a number of emails from Marc Feeley and Guillaume Germain on the status and progress of Termite. The following comments are from their emails (reproduced with permission):

Marc Feeley:

"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."

"Termite is a Lisp for distributed programming. The language is basically Scheme with Erlang's concurrency model added. The implementation is built on top of Gambit-C, which has a very efficient thread system (millions of threads can be running concurrently) and supports serialization of arbitrary data structures.

A quick intro to using Termite

You spawn new processes by calling the SPAWN procedure on a thunk:

(spawn (lambda () (write "hello world!"))

You send a message to a process using the ! operator (this is non-blocking), and you use the ? operator to receive a message (this is blocking):

(define pid (spawn (lambda () (write (?)))))
(! pid "hello world")

A message can be any first-class value. You can specify a timeout to wait for a maximum amount of time:

(? 1) ;; raises an exception if no message received within 1 second

You can give a second argument to specify a value to return in case of timeout:

(? 1 'ok) ;; ==> ok

Each process has a mailbox holding an unbounded number of messages, and it is possible to selectively retrieve messages (meaning not necessarly picking up the first message available) using the ?? operator:

(! (self) 123)
(! (self) 42)


(?? even?) ;; ==> 42

There's also the RECV (receive) form which uses pattern matching to selectively retrieve a message:

(! (self) (list "hello world" write))


(recv
  ((str f)
   (f str))) ;; display "hello world"

Distributed programming

Now, on to distributed programming. Typically, you'd run a Termite node on each computer that you want to connect together. Each node has a IP address and a TCP port number assigned. Here's how you start a node (which we'll call node "A"):

(node-init (make-node "127.0.0.1" 3000))

Let's say we already have a node "B" running on localhost, port 3001. We can start a new process on it from the REPL of node A:

(define B (make-node "127.0.0.1" 3001))
(remote-spawn B (lambda () (write "hello world!"))) ;; displayed on B

If we wanted the message to be printed on node A, but from code running on node B, we'd do:

(let ((port (current-output-port)))
  (remote-spawn B
    (lambda () (write "hello world!" port)))) ;; displayed on A

As we can see from the last example, I/O operations on ports are still valid across the network. This is because Scheme ports are hidden behind processes, and I/O operations are implemented by message-passing.

It is possible to build higher-level distribution abstraction. For example, here's the ON procedure, which allows you to run code on another node, then wait for the result and return it:

(define (on node thunk)
  (let ((tag (make-tag)) ;; a 'tag' is a universally unique id
        (from (self)))
    (remote-spawn node
                  (lambda ()
                    (! from (list tag (thunk)))))
    (recv
      ((,tag reply) reply)))) ;; we make sure we retrieve the right reply

Combining this operator and network-transparent ports, we could write a simple "upload file" procedure like this:

(define (upload file node)
  (let ((output (on node (lambda () (open-output-file file)))))
    (call-with-input-file file
      (lambda (input)
        (write (read-line port #f) output)
        (close output)))))

Snide remark: this program has about the same number of lines of code as a minimal "hello world" program in Java.

Process migration

Termite used to have "transparent" migration of processes, meaning that a process could move from a node to another with messages sent to it following up automatically. But that has been removed from the core because it is very difficult to implement a general form of migration that will have the right semantics for everybody. For example: how do you deal with a process migrating from A to B to C? You'll want to send messages intended for the migrating process which originate from a process running on A directly from A to C. But the thing is, there might be a firewall between A and C. Things like that are hard to predict, and will depend on the particular application.

Migration of processes is still possible. For example, here's how one would migrate a process without following up messages intended for it:

(define (migrate-task node)
  (call/cc
   (lambda (k)
     (remote-spawn node (lambda () (k #t))))
   (halt!)))

This captures the current continuation, resumes it onto another node, then kills the original. Very simple. Now, if you want messages sent to the migrated process to follow it, you can leave a proxy behind:

(define (proxy pid)
  (let loop ()
    (! pid (?))
    (loop)))


(define (migrate/proxy node)
  (call/cc
   (lambda (k)
     (proxy (remote-spawn node (lambda () (k #t)) linked: #t)))))

So those are just two simple examples of migration with different semantics. The fact that you can express such high-level abstractions with so little code is, IMHO, quite attractive.

Termite programs

So, what has Termite been used for? Well, up to now, an implementation of Erlang's behaviors (generic server, generic event handler, generic state machine) has been built for Termite. This makes it much easier to build complex software.

An AJAX-style web framework has also been built, with concurrent processes being used to handle the sessions, callbacks, etc. It is possible to have widgets with their content shared between multiple clients, etc. I built an interactive web-based multi-player game using it.

As for Termite itself, once I'm done with my master's thesis I'll write some documentation, clean up the source code and release it under a LGPL license."

• No reliance on explicit locks
• Support for millions of processes
• Asynchronous message-passing (using send/receive) with mailboxes to manage messages
• Semantics for distributed processes are consistent with those of local processes
• Ability to "migrate" a running process to another system