The DSI Project

What's DSI?

DSI is an architecture designed to support list-oriented, symbolic, concurrent programming languages. The architecture is currently implemented as a virtual machine for Unix-like OSes.

What's behind the name?

DSI was originally an acronym for "Data Space Interpreter", because it described a simple, interpreter-based virtual machine that traversed a suspending construction data space (see illustration at right).

A Suspending Construction Data Space
Drawing by Steven D. Johnson, 1980. Reproduced with permission.

DSI has evolved to the point where there is more to it than this simple characterization implies, but we haven't come up with a better name or acronym for it, so "DSI" it remains, at least for the time being.

What's suspending construction?

Suspending construction is a computation model for list processing languages (e.g. "Lisp family" languages). The model provides a novel way to simplify programming by subsuming many "administrative" programming details that are required for concurrency and I/O.

The key ideas behind suspending construction are:

Suspended threads (suspensions) are created implicitly via list creation. Since lists are the ubiquitious compound data structure in the system, simply executing a program can create large interconnected networks of suspensions in the heap (see figure).
Suspensions are activated singularly by trying to access a list field that contains one, or in numbers by various primitives manipulating such lists.
Once activated, a suspension may run for a while and then be suspended again, or terminate and overwrite any reference to itself in its host list with the computed result.
All interactions between suspensions are transparently handled by the system, which subsumes any detection, scheduling, synchronization or coordination issues.

If a language based on suspending construction is suitably designed, suspensions are also independent of each other (subject only to result dependences), and thus may execute in arbitrary orders, including concurrently.

Suspending construction can also provide a seamless and transparent interface between the heap and the I/O devices. If device drivers and I/O routines are implemented with suspensions, I/O just "happens" with the ease of producing or consuming a list (i.e. all I/O is naturally memory-mapped).

The bottom line: the programmer is not required to handle any of the complicated aspects of thread management or I/O and can concentrate on writing a suitably concurrent algorithm. Programs become cleaner and more concise, even more so than in traditional Lisp-like languages that just automate memory management. Of course, there are arguments about expressiveness or efficiency, as with any language.

What languages are supported?

At present there is only one surface language implemented on the VM: Daisy. However, we are also working on a version of DSI-hosted Scheme.

Although the architecture is tailored for Lisp-like languages, the results of the research are relevant to other symbolic languages, especially functional languages.

Who's behind this project?

Suspending construction was proposed by Dan Friedman and David Wise of Indiana University in 1976, as an outgrowth of research into Lisp-derived lazy functional programming languages. The duo iteratively refined the model in a series of seminal papers in the late 70s and early 80s, incorporating concurrency, nondeterminism and other ideas that were hot language topics at the time.

The suspending construction model was the basis for a VM-based architecture designed and implemented by Steve Johnson in the early 80s. Eric Jeschke joined the project as Johnson's student in 1984 and further refined the architecture and surface language, particularly the multiprocessing capabilities, culminating in a dissertation on the topic in 1995. Jeschke and Johnson have been working sporadically on the project ever since.

What about related work?

We should note that similar and parallel lines of research have ocurred elsewhere in the same time frame; most notably Robert Halstead's work on Multilisp and futures at MIT in the 80s. There are many similarities between the two projects, with the main differences stemming from the semantic and philisophical approaches taken in the surface languages. For more information on this and other related projects, follow the dissertation link in the documentation section below. We don't know of anyone still working on Lisp with futures stuff; if you do, please let us know.

Can I download your system?

Yes, you can get the source here.

The system is known to build "out of the box" on recent versions of Mac OS X and Intel-Linux. Other systems have been used in the past, including Sparc/Solaris, Alpha, MIPS and Next, but some configuration or porting may be necessary.

At some point in the future we may provide binaries.

What about documentation?

There is some (rather sketchy) documentation in the source package.

The best documentation on the DSI architecture at present is probably Jeschke's 1995 dissertation: An Architecture for Parallel Symbolic Processing Based on Suspending Construction. Although the architecture has evolved since 95, the key ideas behind the resource management algorithms are still intact.