Daisy in a Nutshell

[This page is adapted from my dissertation, An Architecture for Parallel Symbolic Processing Based on Suspending Construction.]

Daisy is a statically-scoped, demand-driven, applicative language. The design of Daisy is based on suspending construction, a model for demand-driven parallel computation developed at Indiana University.

In the geneology of languages, Daisy is a descendant of pure Lisp and is a contemporary of Scheme. In syntax and semantics, however, Daisy differs significantly from most Lisp-family languages.

In this document we introduce Daisy and describe how suspending list construction gives rise to both lazy and concurrent programs. This description is necessarily brief; for a fuller description of the language, see the Daisy QuickStart Guide and Language Reference Manual.

Syntax

Daisy's syntax is a departure from standard Lisp s-expressions, yet is still relatively simple. It employs a bracket syntax for lists, but uses infix notation for other constructs such as application.

Atomic Objects

Daisy provides a few atomic objects, such as numbers, literals (atoms) and function closures.

Numbers
Numbers are expressed in standard decimal or floating point notation:

        1       3.1415       5.6001+e6

Literals
Literals (identifiers and strings) are expressed as an alphanumeric sequence beginning with a letter; optionally, double quotes can be used to quote literals with embedded spaces and other characters.

	foo	"A literal with spaces"

Functions
Functions are first-class objects. Lambda forms use a syntax reminiscent of the lambda calculus:

        \ formals . body

where formals is a single identifier or an arbitrarily bushy formal argument list, and body is a Daisy expression. Evaluating a function expression yields a closure; an atomic object that contains the function code and the bindings of all free variables.

Compound Expressions

Lists
Lists glue together atomic objects and other lists to create complex structures.
Brackets [ ] are used to denote list structure, and used with ! (like Lisp's dot-notation) creates dotted pairs. The default interpretation of a bare list is evaluation/list construction, not application, as in Lisp.

Application
Application is expressed by infix colon. So, for example,

        mpy:[x y]

means to multiply the values of x and y.

Quotation
Expressions can be quoted with the hat (caret) character to suppress evaluation of embedded literals in evaluation contexts. For example,

        mpy:^[x y]

would return an error about non-numerical operands, because the carat supresses the evaluation of x and y in the argument list.

Assignment
Daisy restricts the use of side-effects to certain contexts to facilitate demand-driven evaluation and implicit concurrency. Currently, assignment can occur only at top level source evaluation or compilation. It is specified by the form

        identifier = value

So, for example,

        add5 = \ x. add:[x 5]

defines the function add5.

Special Forms

Daisy has two main local binding forms that extend the environment for the scope of the form.

        let: [formals actuals body]

extends the environment by locally binding the formals to actuals, both of which may be arbitrarily bushy structures. body is evaluated in the extended environment. The rec form is similar, but creates recursive bindings. It is somewhat similar to Scheme's letrec, but is fully general, allowing data recursions. For example,

        rec: [L [0 ! map:[inc L]] L]

specifies the list of integers.

An Example

Here is an example of the Quicksort program, written in Daisy:

quick = \L. 
  rec:[loop 
          \[dc L]. let:[[X ! Xs] L
             if:[ nil?:L  dc
                  nil?:Xs [X ! dc]
                     let:[[lo hi] partition:[X Xs]
                           loop:[[X ! loop:[dc hi]] lo]
                         ]
                ]]
       loop: [[] L]
      ]

partition = \[p L].
  rec:[part
         \[p L lo hi]. let:[[X ! Xs] L
            if:[ nil?:L      [lo hi]
                 le?:[X p]   part:[p Xs [X ! lo] hi]
                    part:[p Xs lo [X ! hi]]
               ]]
       part: [p L [] []]
      ]

Semantics

Daisy's laziness is a byproduct of list construction, not lazy interpretation or compilation (there are exceptions, such as the binding forms described above). The evaluation of a list of expressions yields a list of suspensions for evaluating those expressions; in essence, lists are suspended-process builders. Application is strict; the application of a primitive to a list applies a demand pattern to the list, coercing some of the suspensions in it. The demand pattern of a primitive depends on the semantics and implementation of the primitive.

Many demand-patterns allow implicit parallelism. For example, the add operator is strict in both its arguments, which could be evaluated in parallel. In general, this is true of all strict Daisy primitives that take lists as arguments. This concurrency is possible because Daisy restricts side-effects, a property which allows suspensions to execute in any order.

Daisy does not explicitly specify whether most of its primitives actually coerce their arguments in parallel, since

the definition of these operators does not imply concurrency, even though the opportunity exists, and
it leaves the choice up to the implementation. On a sequential machine they would not be coerced in parallel, but on a parallel machine they might.

However, some Daisy primitives do imply concurrency semantics. For example,

        seq:[exp1 exp2 ... expN]

is a sequencer, which coerces suspensions sequentially from left to right. The only Daisy primitive that directly implies concurrency is set:

        set:[exp1 exp2 ... expN]

set returns a new list of values corrosponding to the order that the suspensions converge in its argument list. This implies that the expressions will be concurrently evaluated, at least until the first one to converge. If the tenth element of the result is requested, one can assume that the expressions will be concurrently evaluated at least until ten of them have converged, and so forth.

Classifying Concurrency
The parallel example using add (see above) is a type of conservative parallelism; Daisy provides many more opportunites for speculative parallelism. For example, a speculative OR-parallelism can be specified by

        any?:[exp1 exp2 ... expN]

which returns true if any of its arguments are non-nil. Similarly, a speculative AND-parallelism is

        all?:[exp1 exp2 ... expN]

which returns nil if any of its arguments are nil. Even if is potentially (speculatively) parallel:

        if:[pred1 then1 pred2 then2 ... else]

if can speculatively schedule all its then, else, and subsequent (all but the first) predicate arguments, and evaluate the first predicate sequentially.

There is also abundant potential parallelism in all mapping primitives.

        map: function

is an example of a higher-order primitive. It returns a closure that maps function over a list. That mapping, of course, can be entirely parallel.

Many other potential sources of concurrency exist in Daisy; it has vast amounts of latent parallelism. The DSI kernel is charged with managing this concurrency so that it does not overwhelm the machine. Daisy primitives can freely schedule their arguments without worrying about resource management issues.

[contact info]

Last modified: Sat Jan 17 00:12:58 HST 2004