Lazy lists - an implementation.

[Thomas Lindgren]

> Anyway, after talking to Björn G. on the phone, I'm prepared to drop
> my suggestion in exchange for the following:
> 
> - functions like map, foldl, etc. on ets and mnesia tables
> - list comprehensions on ets tables

This sounds much more attractive than generic lazy lists to me.
And mnemosyne could benefit as well. There are interesting possibilities
in allowing various definitions of list comprehension generators, not
just adding a first/next generator.

For example, I'd like to add these operations over binaries
as well (that is, compiling the generating expression intelligently;
not just with an implicit binary_to_list). 

The function binary:foldl(fun crc/2,0,Bin) could _efficiently_ compute
the CRC of a binary, without converting to a list. (Using the default
8b size.)

Finally, a compiler technique that potentially subsumes all of the above
is deforestation: it is capable of collapsing multiple traversals over
a list into a single one.

As an example, first consider the slow program:
----------------------------------------------------------------------
%% collect all keys, then process some prefix of them

process_keys_of_table(P,F,Table) ->
   process_keys_until(P,F,collect_all_keys(Table)).

%% collect all keys of a table into a list

collect_all_keys(Table) ->
   collect_loop(Table,ets:first(Table)).

collect_loop(Tab,'$end_of_table') ->
   [];
collect_loop(Tab,Key) ->
   [Key|collect_loop(ets:next(Tab,Key))].

%% process the keys of a list until P is false

process_keys_until(P,F,Table,[Key|Keys]) ->
   case P(Table,Key) of
     true ->
        [F(Table,Key)|process_keys_until(P,F,Keys)];
     false ->
        []
   end.

----------------------------------------------------------------------
This can be _automatically_ rewritten by deforestation (with some
restrictions on P and F) into:
----------------------------------------------------------------------

process_keys_of_table(P,F,Table) ->
   p_c(P,F,Table,ets:first(Table)).

%% p_c traverses the keys until P(Key) is no longer true

p_c(P,F,Table,'$end_of_table') ->
   [];
p_c(P,F,Table,Key) ->
   case P(Table,Key) of
     true ->
        [F(Table,Key)|p_c(P,F,Table,ets:next(Table))];
     false ->
        []
   end.

----------------------------------------------------------------------

Nice, huh? There was a masters thesis working on applying
deforestation to Erlang at Uppsala a couple of years
back. (Unfortunately, it got derailed and ended up not being about
Erlang at all.) 

I think there is some scope for sophisticated compilation/program
transformation here. Deforestation is an attractive case.

			Thomas
--
Thomas Lindgren					thomasl+junk@REDACTED
Alteon Websystems Sweden			http://www.bluetail.com

"The need of a constantly expanding market for its products chases the
bourgeoisie over the entire surface of the globe. It must nestle
everywhere, settle everywhere, establish connections everywhere."
-- Communist Manifesto