lazy thoughts

[Andrei Alexandrescu]

(I originally emailed this to Walter and a couple others, but I thought 
it might be better to gather insights from the community.)

I'm gearing up for changing std.algorithm, and I am thinking of making 
the major change of favoring lazy evaluation throughout. For example, 
consider the map function. Right now map allocates and returns a new 
vector, for example:

int[] arr = [ 1, 2, 3, 4 ];
auto squares = map!("a * a")(arr);
assert(squares == [ 1, 4, 9, 16 ]);

What happens is unfortunate because (1) all evaluation is done upfront 
even if it is only partially needed, (2) allocation is done every call, 
(3) the whole scheme won't work with unbounded inputs, e.g. generators 
or even large files.

So now that we have nice range support in the language, I'm thinking 
very seriously of switching full-bore to lazy semantics. In that case 
map returns a range - a little struct that saves the input and trickles 
out results one at a time.

One nice thing about lazy is that lazy includes eager. If you actually 
want to "eagerize" map, you just call eager against the returned range:

int[] arr = [ 1, 2, 3, 4 ];
auto squares = eager(map!("a * a")(arr));
assert(squares == [ 1, 4, 9, 16 ]);

The real advantage comes when you actually exploit the laziness, e.g.:

int[] arr = [ 1, 2, 3, 4 ];
auto squares = map!("a * a")(arr);
foreach (x; squares) {
     writeln(x);
}

Look ma, no allocation!

I just wanted to gauge your opinion on this. It is a major departure 
from the STL, and I think in the right direction. It is a departure 
nonetheless and some STL users might feel uncomfortable.

Also, lazy evaluation has the risk of getting confusing as there's a lot 
of escaping. Consider:

int[] arr = [ 1, 2, 3, 4 ];
auto squares = map!("a * a")(arr);
arr[] = [ 5, 6, 7, 8 ];

Now iterating squares will see different numbers than the original ones.

Please let me know what you think!


Andrei