Daisy/DSI Bibliography

Maintained by Steven D. Johnson and Eric Jeschke .

Revision posted September 26, 2001

D.S. Wise, Brian Heck, Caleb Hess, Willie Hunt, and Eric Ost. Uniprocessor performance of reference-counting hardware heap. Lisp and Symbolic Computation, 10:159-181, July 1997.
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.

Eric R. Jeschke. An Architecture for Parallel Symbolic Processing Based on Suspending Construction. PhD thesis, Indiana University Computer Science Department, 1995.
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

Steven D. Johnson. Daisy, DSI, and LiMP: architectural implications of suspending construction. Technical Report 288, Indiana University Computer Science Department, Bloomington IN, 1989. (PostScript)

Steven D. Johnson. Daisy Programming Manual. Indiana University Computer Science Department, Bloomington IN, second edition, 1989. Draft in progress, dated material. (PostScript)
Second edition of a Daisy manual describing Daisy version 2

Steven D. Johnson. How daisy is lazy. Technical Report 286, Indiana University Computer Science Department, Bloomington IN, 1989. (PostScript)

Steven D. Johnson and C. David Boyer. Modeling transistors applicatively. In Jr. George J. Milne, editor, Fusion of Hardware Design and Verification. North-Holland, 1988. (Proceedings of the IFIP WG10.2 working conference on formal aspects of VLSI, Strathclyde University, Glasgow, July, 1988).
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.

Cordelia Hall. Strictness analysis applied to programs with lazy list constructors. PhD thesis, Indiana University Computer Science Department, 1987.

Cordelia Hall and David S. Wise. Compiling strictness into streams. In Fourteenth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, Munich, West Germany, January 21-23, pages 132-143, 1987.

Steven D. Johnson, Bhaskar Bose, and C. David Boyer. A tactical framework for digital design. In Graham Birtwistle and P. A. Subramanyam, editors, VLSI Specification, Verification and Synthesis, pages 349-384. Kluwer Academic Publishers, 1987. Proceedings of the 1987 Calgary Hardware Verification Workshop.

John T. O'Donnell. Hardware description with recursion equations. In Proc IFIP 8th International Symposium on Computer Hardware Description Languages and their Applications [CHDL], 1987.
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.

John T. O'Donnell and Cordelia Hall. Debugging in applicative languages. Technical Report 223, Indiana University Computer Science Department, Bloomington IN, June 1987. To appear in the International Journal on Lisp and Symbolic Computation.

David S. Wise. Matrix algebra and applicative programming. In Functional Programming Languages and Computer Architecture, Lecture Notes in Computer Science 274, pages 134-153. Springer-Berlin, 1987.

David S. Wise and John Franco. Costs of quadtree representation of non-dense matrices. Technical Report 229, Indiana University Computer Science Department, Bloomington IN, October 1987.

Steven D. Johnson. Digital design in a functional calculus. In G. J. Milne and P. A. Subrahmanyam, editors, Workshop on Formal Aspects of VLSI Design (Proceedings of the Workshop on VLSI, Edinburgh) rm , 1985. North-Holland, Amsterdam, 1986.
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.

David S. Wise. An applicative programmer's approach to matrix algebra, lessons for hardware, and software. In Workshop on Future Directions in Computer Architecture and Software, rm Army Research Office, 1986.

David S. Wise. Parallel decomposition of matrix inversion using quadtrees. In Proc. 1986 IEEE Intl. Conf. on Parallel Processing. IEEE, 1986.

Cordelia V. Hall and John T. O'Donnell. Debugging in a side effect free programming environment. In sl ACM SIGPLAN Symposium on Programming Languages and Programming Environments, rm in sl ACM SIGPLAN Notices, rm Vol. 20, No. 7, July 1985.
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.

Steven D. Johnson. Storage allocation for list multiprocessing. Technical Report 168, Indiana University Computer Science Department, Bloomington IN, March 1985.
A description of components for a multi-processing implementation of the suspending construction model, focusing on storage reclamation.

John T. O'Donnell. An architecture that efficiently updates associative aggregates in applicative programming languages. In 1985 IFIP Symposium on Functional Programming Languages and Computer Architecture, Lecture Notes in Computer Science 201, pages 164-189. Springer, 1985.

John T. O'Donnell. Dialogues: a basis for constructing programming environments. In sl 1985 ACM SIGPLAN Symposium on Programming Languages and Programming Environments rm , in sl ACM SIGPLAN Notices rm , Vol. 20, No. 7, July 1985.
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.

David S. Wise. The applicative style of programming. Abacus, 2:20-32, Winter 1985.

David S. Wise. Design for a multiprocessing heap with on-board reference counting. In J. P. Jouannaud, editor, Functional Programming Languages and Computer Architecture, pages 289-304. Springer-Berlin, 1985.

David S. Wise. Representing matrices as quadtrees for parallel processors. Information Processing Letters, 20:195-199, May 1985.

Robert E. Filman and Daniel P. Friedman. Coordinated Computing: Tools and Techniques for Distributed Software. McGraw-Hill, 1984.
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.

Steven D. Johnson. Applicative programming and digital design. In Eleventh Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pages 218-227, January 1984.
Daisy is used to model digital circuit behavior and simulate the behavior of circuit for tree searching.

Steven D. Johnson. Synthesis of Digital Designs from Recursion Equations. The ACM Distinguished Dissertation Series, The MIT Press, Cambridge, MA, 1984.
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.

David S. Wise. The applicative style of programming. Technical Report 84-2, Computer Science Department, Oregon State University, May 1984.
Extended version of [21]

David S. Wise. Parallel decomposition of matrix inversion using quadtrees. In Proc. 1984 International Conference on Parallel Processing, pages 92-99, 1984. (available as IEEE Cat. No. 86CH2355-6).

David S. Wise. A powerdomain semantics for indeterminacy. Technical Report 142, Indiana University Computer Science Department, Bloomington IN, 1984. (revised: January 1984).

David S. Wise. Representing matrices as quadtrees for parallel processors. ACM SIGSAM Bulletin, 18:24-25, August 1984. (extended abstract).

Steven D. Johnson. Circuits and systems: Implementing communication with streams. IMACS Transactions on Scientific Computation, Vol. II, pages 311-319, 1983.
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.

David S. Wise. Functional programming. In A. Ralston, editor, Encyclopedia of Computer Science, pages 647-650. rm Van Nostrand Reinhold, New York, 1983.

David S. Wise. Interpreters for functional programming. In J. Darlington, P. Henderson, and D. Turner, editors, Functional Programming and its Applications, pages 253-280. rm Cambridge University Press, 1982.

Daniel P. Friedman and David S. Wise. Fancy ferns require little care. In S. Holmstrom, B. Nordstrom, and A. Wikstrom, editors, Symposium on Functional Languages and Computer Architecture, Lab for Programming Methodology, Goteborg, Sweden, 1981.

Steven D. Johnson. Connection networks for output-driven list multiprocessing. Technical Report 114, Indiana University Computer Science Department, Bloomington IN, 1981.
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].

Steven D. Johnson and Anne T. Kohlstaedt. DSI program description. Technical Report 120, Indiana University Computer Science Department, Bloomington IN, 1981.
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.

Anne T. Kohlstaedt. Daisy 1.0 reference manual. Technical Report 119, Indiana University Computer Science Department, Bloomington IN, 1981. ( [3] should be delivered implicitly).

David S. Wise. Compact layout of banyan/fft networks. In H. Kung, B. Sproull, and G. Steele, editors, VLSI Systems and Computations, pages 186-195. rm Computer Science Press, Rockville, MD, 1981.

Daniel P. Friedman and David S. Wise. A conditional, interlock-free store instruction. Technical Report 74, Indiana University Computer Science Department, Bloomington IN, 1980. (revised 1980).

Daniel P. Friedman and David S. Wise. An indeterminate constructor for applicative multiprogramming. In Record 7th ACM Symp. on Principles of Programming Languages rm (January, 1980), pages 245-250, 1980.

Thomas M. Grismer. Solving common programming problems with an applicative programming language. Master's thesis, Indiana University Computer Science Department, 1980. (available as IU Technical Report No. 109).

Daniel P. Friedman and David S. Wise. An approach to fair applicative multiprogramming. In G. Kahn and R. Milner, editors, Semantics of Concurrent Computation, pages 203-225. Berlin, Springer, 1979.

Dale M. Grit, J. C. Harwell, and Rex L. Page. An operating system in an applicative language. Technical report, Colorado State Univ, 1979.
This report uses a revised version of the suspending interpreter of [54] to develop an elementary operating system in applicative style.

W. Riddle, V. Berzins, Daniel P. Friedman, and David S. Wise. Approaches to specifications--various models. In ACM Software Engineering Notes, volume 4, pages 17-18, July 1979. Panel Session, Conf. on Specifications for Reliable Software (April 5, 1979).

David S. Wise. Morris's garbage compaction algorithm restores reference counts. ACM Trans. on Programming Languages and Systems, 1:115-120, July 1979.

Daniel P. Friedman and David S. Wise. Applicative multiprogramming. Technical Report 72, Indiana University Computer Science Department, Bloomington IN, 1978. Revised: December, 1978.
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.)

Daniel P. Friedman and David S. Wise. Aspects of applicative programming for parallel processing. IEEE Transactions on Computers, C-27:289-296, April 1978.

Daniel P. Friedman and David S. Wise. Functional combination. Computer Languages, 3:31-35, 1978.
Formal presentation of functional combination, introduced in Friedman-Wise-77. Many examples.

Daniel P. Friedman and David S. Wise. A note on conditional expressions. Comm. ACM, 2l:93l-933, November 1978.
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.

Daniel P. Friedman and David S. Wise. Sting-unless: a conditional, interlock-free store instruction. In M. B. Pursley and Jr. J. B. Cruz, editors, 16th Annual Allerton Conf. on Communication, Control, and Computing, rm University of Illinois (Urbana-Champaign), pages 578-584, 1978.
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.

Daniel P. Friedman and David S. Wise. Unbounded computational structures. Software-Practice and Experience, 8:407-416, July-August 1978.
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.

Daniel P. Friedman and David S. Wise. Aspects of applicative programming for file systems. In Conf. on Language Design for Reliable Software, ACM SIGPLAN Notices, volume 12, pages 41-55. ACM, March 1977.
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.

Daniel P. Friedman and David S. Wise. An environment for multiple-valued recursive procedures. In B. Robinet, editor, Programmation, pages 182-200. Dunod Informatique, Paris, 1977.
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.

Steven D. Johnson. An interpretive model for a language based on suspended construction. Master's thesis, Indiana University Computer Science Department, 1977.
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.

David S. Wise and Daniel P. Friedman. The one-bit reference count. BIT, 17:351-359, September 1977.
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.

David S. Wise Daniel P. Friedman and Mitchell Wand. Recursive programming through table look-up. In Symposium on Symbolic and Algebraic Computation, pages 85-89. ACM, 1976.

Daniel P. Friedman and David S. Wise. CONS should not evaluate its arguments. In S. Michaelson and R. Milner, editors, Automata, Languages and Programming, pages 257-284. Edinburgh University Press, Edinburgh, 1976.
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.

Daniel P. Friedman and David S. Wise. Garbage collecting a heap which includes a scatter table. Information Processing Letters, 5(6):161-164, December 1976.
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.

Daniel P. Friedman and David S. Wise. The impact of applicative programming on multiprocessing. In International Conference on Parallel Processing, pages 263-272. IEEE, 1976. IEEE Cat. No. 76CH1127-OC.
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.

Daniel P. Friedman and David S. Wise. Output driven interpretation of recursive programs, or writing creates and destroys data structures. Information Processing Letters, 5:155-160, December 1976.
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.

Daniel P. Friedman and David S. Wise. Unwinding structured recursions into iterations. Technical Report 19, Indiana University Computer Science Department, Bloomington IN, 1975. (revised 1976).
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.

Eric R. Jeschke. DSI assembler reference manual. (draft, unpublished).

John T. O'Donnell. An applicative programming environment. (draft, unpublished).