I had a couple of responses (from Mark Johnson and Bob Futrelle), and
thought I would supplement my previous mail/posting accordingly:
Bob suggests Peter Norvig's book, Paradigms of AI Programming for its
discussion of lazy evaluation. He is preaching to the choir as far as
I'm concerned!
However, the response is not quite to the point. I actually do have a
reasonable understanding of how lazy evaluation can be implemented.
What I am looking for is a clear, elegant way to express LE in Common
lisp, and it does not seem to me that Scheme's promise method is such.
For example, the SERIES macro makes it possible to have a single
series concept which can be used either across functions (returning
series) or within functions (when it will be converted to a loop).
Promises, on the other hand, do not really make sense within functions
(why bother making the closure?), but only when returning a series of
values. Also, I find it inelegant that one has to force them "by
hand."
Mark responds primarily to stress the point that when one returns
streams some optimizations cannot be done. He cites the fact that CL
optimization is primarily a local-to-defun operation (I apologize for
the oversimplification). Of course, this problem is exacerbated by
the fact that the SERIES package is a MACRO, rather than being
something handled by the optimizing compiler. I would imagine that if
the SERIES package was integrated into CL, the judicious use of INLINE
function declarations would make better optimizations possible.
Mark also suggests that generators and gatherers might be a better way
of expressing what I'm after.
This leads me to make one clarification of purpose, and to reiterate a
previously-asked question:
First of all, I understand that returning series values will make many
optimizations impossible, because of the need for continuations. It
is my guess that the use of continuations makes optimization VERY
difficult. I am willing to pay this price when doing some lazy
evaluation: it seems to me that LE is primarily worthwhile when the
computation of each value is expensive enough to deter computation of
any extra values. In this case, some overhead is an acceptable price
to pay for avoiding excess work.
One thing I particularly like about using SERIES is the idea of using
multiple-values to handle parallel streams of values. this, of
course, is what one does in LOOP using the FOR...AS... construct, but
LOOP does not support LE. This is what I would like here. However,
it seems very difficult to take two such streams and filter them in
parallel. This seems to require either pairing the stream elements
and filtering the result of that, or catching the results of a mapping
using multiple-value-bind, and then filtering the two streams in
parallel.
The first approach seems to me inelegant: it's the equivalent of the
old approach of consing together values to get the effect of
multiple-value functions. The second seems to offend the SERIES
optimizer.
Surely the pattern of applying a filter to a mapping which produces
a pair (or more) of parallel series is not such an outre piece of
programming practice! Shouldn't there be some elegant way of
supporting this?
The reiteration: Does anyone have any insight about when it is
relevant to use SERIES vs. GENERATORS/GATHERERS? Any rules of style?
Any rules of thumb for efficiency?
Finally, does anyone know anything about further developments of the
SERIES package? Does anyone have any experiences programming with it
that they'd like to share?
Best,
R