[PRL] laziness

[David A. Herman]

I've got a few questions about laziness:

1) Does laziness fuse multiple traversals?

Say there are 3 traversals, T1, T2, and T3. Each one has some number of
steps. The program's "observer" will try and get the first piece of the
result, which needs the first piece of the result of T3, which needs the
first piece of T2, which needs the first piece of T1. So T1 does its first
little bit and thunkifies the rest, and so on through T3. We've now done
the first piece of each traversal. Next the observer requests the second
piece, etc. So in effect we have taken three traversals and fused them,
because we perform them all in lock-step.

That's the idea behind stream programming anyway, right? We want to start
getting results as early as possible. The overall amount of work might
be proportional to the eager version, but this way we don't have to wait
for all traversals to finish before we get results.

But I suspect that in fact the control flow of lazy programs is much more
subtle and hard to predict than my description suggests.

2) Will it "automatically" buy me better performance?

In my multiple-traversal program, which is going very slowly, if I make
all the constructors into DELAY-s and the observers into FORCE-s, will my
program suddenly be faster? In light of (1), I would think its overall
performance should be the same, although ostensibly the big gain is when
you delay computations that never end up needing to be performed. In a
program transformation, though, don't you end up doing all the
computations anyway? So is it just DELAY-ing the inevitable?

3) Is laziness a magic bullet, or an undebuggable pain?

(Okay, this is probably way too squishy.) As an analog to automatic memory
management (could you call it "automatic computation management?"), it's a
nice idea -- DELAY/FORCE is a paired call and thus error-prone, so the
language will handle it for you automatically. But if this makes for
programs that are just too hard to understand, it may cause more problems
than it solves.

All right, long-winded way of saying, if I'm writing a side-effect-free
(or mostly so) program transformation engine, am I better off using a
strict or lazy language?

Dave