The DSI Project
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
The key ideas behind suspending construction are:
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.
- 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.
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
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
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
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.
Last modified: Sat Jan 17 00:16:36 HST 2004