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.
Numbers are expressed in standard decimal or floating point notation:
1 3.1415 5.6001+e6Literals
foo "A literal with spaces"
Functions are first-class objects. Lambda forms use a syntax reminiscent of the lambda calculus:
\ formals . bodywhere 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.
Application is expressed by infix colon. So, for example,
mpy:[x y]means to multiply the values of x and y.
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.
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 = valueSo, for example,
add5 = \ x. add:[x 5]defines the function add5.
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.
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  ] ]
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
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.
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: functionis 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.
Last modified: Sat Jan 17 00:12:58 HST 2004