Lazy Evaluation

[Paul Prescod <papresco@xxxxxxxxxxxxxxxxxxxxxxxxx>]

Someone asked me about lazy evaluation. I don't know of a website to point to
that will describe this without getting into hoary functional programming 
background, but the concept is quite simple and isn't really related to 
functional programming at all -- some fp languages just happen to provide 
built-in support for it.

Imagine something like this:

(node-list-first 
   (node-list-union
	(select-elements 
            (node-list-reverse
			(descendents (current-root))) "FOO")
        (... (descendants (current-node)))

etc. This isn't a well thought out example, just meant to get across the point
that it is a complicated query involving a lot of nodes (potentially) but you
really only care about the *first* node that is returned. An eager 
implementation would actually fetch the list of ancestors, reverse them, search
for "FOO"s, union them with the second half and then throw away all but the 
first node. What a lot of work for one node!

A lazy implementation, on the other hand, presumes that you probably don't care
about ALL of the nodes and so it only passes a specification for a node, 
not a nodelist. It would build up a specification of a nodelist and then when
it got to the (node-list-first ...) it would find the first node that actually
met the specification, instead ofxaminining thousands of nodes when only one
is actually needed in the end. As you can probably imagine, laziness
is very important to an efficient DSSSL implementation.

When you think about SDQL in terms of lazy implementation, it becomes clearer
that it is actually a query language, not just a set of Scheme functions.
The implementation has a lot of flexibility about how to do the actually 
"query", just as it does in SQL. 

This brings us back to functional programming languages.  In DSSSL,
basically only nodelists (and sosofos?) are lazy. Plain 'ol Scheme lists are
not. Function calls are not. In a full lazy language like Haskell, more stuff
is lazy. Lists don't get constructed until someone iterates down them. 
Functions don't get called or expressions evaluated until their values are 
needed, etc. You can actually define a "list" as holding "all" of the integers
and it doesn't take up any more physical RAM than one holding a fixed list of
integers (it probably takes up less!). Of course there are efficiency concerns
in passing around these "specifications" everywhere, so laziness is not a 
complete "win", but it sure is in typical uses of node-lists.

As should be clear, you can do laziness "by hand" in non-lazy languages, which
is what James has done in C++ in Jade with node-lists..

 Paul Prescod


 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist