[erlang-questions] Compiler list comprehension optimizations

[Richard A. O'Keefe]

On 8/07/2013, at 5:17 AM, Anthony Ramine wrote:

> Hello Richard,
> 
> What is the point of the skip constructor?

To a first approximation:  to handle filtering.

> Couldn't the unfolder call itself on its own with the updated state?

No.  Part of the point of the 'stream' approach is that every step
along the way is *non*-recursive code that's amenable to inlining,
right up to the end where you "pull" the results in a tail-recursive
loop (which would like to have the rest of the pipeline inlined into
it, thank you very much).
> 
> Also, could you formalize that in an EEP?

There's more formalisation than you could shake a banana at in

	Stream Fusion:
	Practical shortcut fusion for coinductive sequence types
	Duncan Coutts
	PhD thesis, Worcester College, University of Oxford, 2010.

I don't have an EEP, what I _do_ have is a module -- which has
undergone **minimal** testing -- to try the idea out.  There are
three classes of functions:

 - producers turn lists, tuples, integer ranges, &c into streams

 - transformers turn streams (possibly more than one) into streams

 - consumers accept streams and pull results out of them

It's pretty amazing what you can do with stream transformers.

	t_alternate(S1, S2)
	   elements of S1 interleaved with elements of S2

	t_drop(N, S)
	   all but the first N elements of S

	t_drop_while(P, S)
	   all the elements of S starting with the first to satisfy P

	t_fby(S1, S2)
	   concatenation of streams

	t_filter(P, S)
	   all the elements of S that satisfy P

	t_map(F, S)
	   F(X) for each X in S

	t_merge(S1, S2)
	   Merge two sorted streams producing sorted output.
	   (Ordered-set union, intersection, difference, &c are
	   obviously doable since merge is doable; I happen not
	   to have done them.)

	t_repeat(F, S)
	   each element X of S repeated F(X) times

	t_scan(F, A, S)
	   <X1,X2,...> -> <Y1,Y2,...>
	   where Y1 = F(A,X1), Y2 = F(Y1,X2), ...

	t_take(N, S)
	   the first N elements of S

	t_take_while(P, S)
	   the leading elements of S satisfying P

	t_zip(S1, S2)
	   If S1 is <X1,...> and S2 is <Y1,...> then <{X1,X2}, ...>

	t_zip_with(F, S1, S2)
	   the same as t_zip but F(X,Y) instead of {X,Y}.

That's all I have at the moment.

Quite a few of these transformers would be somewhere between difficult
and impossible to write _as_ transformers without 'skip'.

One reason to care about this stuff, especially in the context of list
comprehension, is that a consumer fed by a network of transformers from
some producers can be compiled into a single block of code that assigns
to hidden local stack variables but preserves over-all functional
purity and would require no change to the garbage collector, so an
astonishingly rich extension of list comprehension *could* be provided

The current draft of the module can be found at
http://www.cs.otago.ac.nz/staffpriv/ok/stream.erl

It was thrown together in something of a hurry to explore the idea,
and is rather short of comments.  I must do something about that,
but since the 2nd semester has just started, I've already spent too
long on this.

I must stress that if you take the code as it stands, it's going to do
*lots* of short-lived allocations.  Think of it as a prototype to see
what a compiler *could* do and it makes a lot more sense.