Appendix C:
Suspending Construction

Daisy is based on a model of computing called suspending construction. It is not necessary to understand this model to use Daisy, but it can clarify semantic issues and help explain how certain primitives (e.g. set) work.

Suspending Construction

Whenever a Daisy program constructs a list, the system defers (suspends) the computation of the list elements, but still returns a list object. If the program later tries to manipulate the contents of the list (i.e. access any part of it) the system intervenes, computes any needed elements, and resumes processing where it left off. We say that

Daisy has lazy lists or lazy list construction. Daisy's lazy lists are accomplished by creating suspensions in place of list values (ergo suspending construction). Each suspension represents the future value of one or more list elements. Creating a suspension captures any information necessary to compute the proper value(s) in a context-independent way if they are ever needed. Suspensions are created implicitly by the list constructor and other list creating primitives. Suspensions are not first-class objects that can be explicitly manipulated in Daisy. Since they are handled by the system "behind the scenes", they remain transparent to programs.

Many Daisy primitives operate on lists. Each such primitive accesses its argument list according to a particular demand pattern. This has the effect of implicitly coercing some number of suspensions (if any) in the list to values. The order of coercion can occur sequentially, concurrently, or in an unspecified way, depending on the nature of the primitive. For example, in the expression

seq:[E0 E1 ...]
we know that the expressions E0 E1 etc. are evaluated from left to right. Contrast that to:
add:[E0 E1 ...]
Here the expressions E0 E1 etc. are evaluated in some unspecified order, but we know that they must all be evaluated otherwise an answer cannot be computed. Contrast that to:
any?:[E0 E1 ...]
Here also the values are also computed in some unspecified order, but only until a non-nil value is obtained. User-defined functions have complex demand patterns formed by combining the patterns from the base primitives that make up the body of the function.

Because suspensions are implemented as super-lightweight process threads, Daisy programs are inherently multithreaded. Complex demand patterns make it difficult for the programmer to keep track of when computations are being suspended, when they are being coerced, and how they are being coerced. The good news is you don't need to. All of the details associated with creating and coercing suspensions occur transparently. As far as the Daisy programmer is concerned, the program is simply manipulating lists and atomic elements like numbers and symbols. This can take getting used to when learning Daisy from an imperative programming background. Most Daisy programmers eventually learn to reason about programs in terms of inputs and outputs rather than control flow. Nevertheless, a basic understanding of the deferred coercion behavior of the system is conducive to understanding the behavior of certain programs.

The transparent decoupling of computations in lists (through suspensions) requires Daisy to restrict side-effects to local state within each suspension. In other words, because suspensions may execute in arbitrary orders, they may not mutate shared structures, including variables. This restriction allows the system to avoid unnecessary computation or synchronization and to take advantage of implicit parallelism opportunities.

Why suspending construction?

Daisy programming represents a somewhat radical departure from traditional imperative programming in both programming technique and reasoning about program behavior. The advantage that Daisy promulgates with other high-level symbolic languages is that traditional control-flow reasoning is vastly complicated by many factors including the complexity of the modern software development cycle as well as concurrency, storage management, and other factors. Modern programming systems require a higher level design and reasoning framework. Object-oriented languages encapsulate complexity within objects and describe a computing problem in terms of the interaction of objects. Daisy programs describe computing problems in terms of the interaction of a network of autonomous finely-grained processes.

Demand-driven Computation

A suspension may in probe other suspensions during the course of its execution. In this way computation ripples through the data space as demand is propagated from one suspension to others, each one oblivious to the rest.