Maintained by Steven D. Johnson and Eric Jeschke .
Revision posted September 26, 2001
A hardware self-managing heap memory (RCM) for languages like LISP, SMALLTALK, and JAVA has been designed, built, tested and benchmarked. On every pointer write from the processor, reference-counting transactions are performed in real time within this memory, and garbage cells are reused without processor cycles. A processor allocates new nodes simply by reading from a distinguished location in its address space. The memory hardware also incorporates support for off-line, multiprocessing, mark-sweep garbage collection. Performance statistics are presented from a partial implementation of SCHEME over five different memory models and two garbage collection strategies, from main memory (no access to RCM) to a fully operational RCM installed on an external bus. The performance of the RCM memory is more than competitive with main memory.
Symbolic languages relieve the programmer from many resource management considerations that are required for traditional programming languages, such as memory and process management. This makes them promising candidates for solving a large, general class of programming problems on shared-memory MIMD-class parallel computers. The incorporation of these resource management problems into the parallel language implementation domain is a topic of active research. This dissertation discusses the design of a list processing engine for implementing parallel symbolic languages on stock multiprocessors. The design results from experience implementing an applicative language on the BBN Butterfly multiprocessor. The language and engine are based on suspending construction, a fine-grained, concurrent, non-strict computation model. The contributions of the dissertation are: (1) A virtual machine architecture for fine-grained parallel list multiprocessing. This virtual machine design identifies key areas where hardware support would accelerate the execution of programs using computational models similar to suspending construction, such as Lisp with futures. (2) A microkernel providing memory management, process management and device management for high level parallel symbolic programs. The resource management techniques described represent new approaches to these problems for many parallel symbolic languages. (3) An analysis of Daisy, a language based on suspending construction and implemented on this architecture and microkernel
Second edition of a Daisy manual describing Daisy version 2
The theme of this paper is symbolic modeling, specifically, the development of functional representations for behavioral aspects of hardware. Various treatments of `bidirectionality' are discussed. Data recursion is used to set up representations of transistor networks which compute their directionality depending on the condition of external signals. Daisy's undetermined lists are used to implement a guarded expression. A conclusion of the paper is that bidirectionality is not an implicitly relational notion. It can be dealt with in a functional framework at some notational expense.
This paper extends the use of streams defined by sets of recursion equations for describing hardware circuits. A set of recursion equations defined inside a letrec expression corresponds to a level of abstraction in the circuit --- a ``black box''. High order functions can generate these black boxes. The meaning of a circuit description depends on the meanings of its components. Two sets of primitive component definitions are introduced. One set defines the behavioral meaning of components such as AND gates and latches, while the other set defines their structural meanings. Interpreting the circuit specification with the first set of definitions produces a function that simulates the circuit, while evaluation with the second set generates a wiring list that gives complete information about the interconnection structure of the circuit. The paper briefly indicates how the technique can be extended to give geometric specifications as well as interconnection specifications. All the programs are written in Daisy.
An informal presentation of an approach to digital design synthesis (See [Johnson-84a, Johnson-84b]). Daisy is used to illustrate the use of lazy languages to model circuit behavior.
Traditional techniques for debugging imperative programs don't work in applicative languages without side effects. For example, imperative programmers often insert extra output statements to trace the execution, but output statements cause side effects. However, tracing and other debugging tools can be implemented applicatively using streams to pass debugging information among functions. Several examples of the technique are given using Daisy.
A description of components for a multi-processing implementation of the suspending construction model, focusing on storage reclamation.
A common paradigm in computing is the interaction between two processes that possess evolving states. Sometimes one of the processes is a human user. For example, when you use a text editor, you type commands to the computer, and your knowledge (or ``state'') is updated when the computer replies. The computer also updates its state when it receives commands from you, and it sends output back to you. There are also many cases where both interacting processes are parts of the operating system or the computer hardware. These interactions are called ``dialogues''. Dialogues can be modeled elegantly using streams to represent both state and communications. The paper implements a dialogue function in Daisy, and illustrates its use in implementing a simple command language interpreter and structure editor.
The book is a comparative survey of descriptive constructs for concurrency. Chapter 5 presents an approach to applicative system description, and develops several examples, including one taken from [J83]. Much of the material presented in Chapter 5 reflects research surrounding the suspended-construction model of Friedman and Wise.
Daisy is used to model digital circuit behavior and simulate the behavior of circuit for tree searching.
This dissertation develops an approach to hardware synthesis based on correctness-preserving transformations on recursion equations. It promotes the use of normal-order languages for direct experimentation of circuit behavior through their descriptions. A formal syntax and semantics for Daisy are presented in Chapter 5. There are numerous examples of Daisy's use for circuit modeling.
Extended version of [21]
The article relates the executable specification of software systems to the modeling of circuit behavior. The example, a system of two communicating terminals, illustrates a use of frons to specify asynchronous communication. This example is reproduced in Chapter 5 of Coordinated Computing by Friedman and Filman.
Report on a simulation of elements of a switching network for a multi-processor implementation of the suspending construction model, on which Daisy is based. This report is summarized in [18].
A report stating the high level organization of Daisy's implementation--as of 1981--and discussing the motivation for and history of the development effort. There are lots of references to related research.
This report uses a revised version of the suspending interpreter of [54] to develop an elementary operating system in applicative style.
Early and extensive description of ferns, a generalization of both Lisp list and multisets (QLisp bags). Introduction of a new constructor, frons which adds a suspended item to a structure, but (unlike cons) without specifying its position. A structure built purely with frons has no predetermined order; thus, a multiset. Intention is that order be determined upon access. All candidate suspensions whose value might become the head of the accessed structure are ``coaxed'' in parallel. Any that converges may be promoted to first. The choice is indeterministic, raising semantic problems of correct implementations. Almost anything can happen, except that non-convergent ( perp ) values never get promoted. Much consideration given to hybrid structures, built with both cons and it frons, and to Shared references: what happens if two ferns share a common ``suffix''? (Answer: the eventual order of that suffix must be reflected within both those ferns.)
Formal presentation of functional combination, introduced in Friedman-Wise-77. Many examples.
Contitional expressions (that is, if-then-else) may be distributed across construction of suspended data structures. By implication, most functions may be distributed across data structures, so that content may be determined without (or before) the value of the tested predicate. Since most languages take conditionals to be strict in their predicates, this perspective is unconventional in software, but it turns out to be routine in hardware, where tests often are distributed over results. This tack admits more mathematical manipulation of programs, making programming languages more attractive to hardware designers.
The first of hardware proposals arising from Daisy. In a multiprocessor, operations similar to test-and-set may be implemented in off-line memory, freeing the processor to do anything not dependent on the result of that operation (which must be refetched.) Conventional synchronization examples provided.
Exploration of programming with (suspended) infinite objects as tangible (bindable) data objects. Examples include convergent series of approximations to real arithmetic (Newton's approximation) and Daisy's version of some applicative programming chestnuts: Sieve of Eratosthenes and Composites of 2,3,5.
Reviews the interaction of lazy evaluation and a rudimentary file system. Exhibits style and space implications for suspended and shared-suffix files. A rudimentary text editor is provided.
First description of functional combination, Daisy's generalization of Lisp's mapcar, which is heavily used in sequel papers relating to parallelism, systems, and hardware.
The first implementation of a Daisy-like interpreter. This language, called ``The Interpreter,'' supported major semantic constructs, including functional combination and frons. However, it did not permit data recursion. Storage management was by incremental reference counting, an a number of internal algorithms (e.g., multiset promotion) exploited the reference count, implementing in-place effects when the count was one.
The mark bit in each node may be used between garbage collections to distinguish between uniquely and multiply (or uncertainly) referenced objects. In this way many nodes can be recycled between collections, postponing full garbage collection in a hybrid system.
Seminal paper in the Daisy project. Introduces suspended (lazy) data structures and explores implications for a pure Lisp interpreter. mbox cons becomes a special form rather than a primitive function Effect when used within interpreter is lazy evaluation of program. (Term, lazy, is due to Henderson and Morris whose similar work was published earlier that year.) The intended space-saving behavior of [Frideman-Wise-75] is delivered implicitly.
Extends the (almost independent) theme of storage management (cf. [60]). Under a mark-sweep collector, buckets may be cleansed without excessive traversal by inverting them as contents are marked, and restoring them during the sweep phase.
First projection of Daisy onto the multiprocessing environment. Since suspensions are mutually independent, several dwelling within a data structure may be evaluated simultaneously without mutual interference or synchronization. Function combination [Friedman-Wise-77] is most useful here.
Since the hunger of the (serial) output device drives any lazy computation, its driver is very important. This paper presents a preorder traversal algorithm as an efficient iterative program that uses reference counts to recycle the space used by the output stream as soon as it has been printed. Programs for printing simple infinite structures, like a stream of integers, thereby run in constant space--just as equivalent iterative programs do.
Describes a compiler that translates linear recursions (like the conventional code for member?) into straight-line interation without stacking (even of continuations). Achieved the goal of code homomorphic to that which might appear in Knuth's Art of Computer Programming.