[erlang-questions] Compiler list comprehension optimizations

[Jonathan Leivent]

I have some questions about compiler optimizations on list comprehensions.

The efficiency guide says that list comprehensions that are "neither
assigned to a variable, nor passed to another function, nor returned"
will be optimized by the compiler to avoid the list construction.

However, Dialyzer sometimes complains about such list comprehensions
with "Expression produces a value of type ['ok'], but this value is
unmatched". So I have developed the habit of assigning to "_", as with:

foo(...) ->
...,
_ = [bar(X) || ...],
....

After re-reading that line in the efficiency guide, it seems like this
assignment might actually defeat the above compiler optimization. Does
it? Or does the compiler still manage to do the optimization?

If this does prevent the optimization, is there a way to get the
optimization and prevent the Dialyzer warning while still using a list
comprehension?

Another question about list comprehension optimizations: If a list
being iterated over is generated from a function that just builds the
list element-wise, can the compiler inline that function so that the
intermediate list isn't built? For instance, if the function is
something like the very useful list of all non-empty tails of a list:

alltails(L=[_|T]) -> [L|alltails(T)];
alltails([]) -> [].

[... || T <- alltails(L), ...]

can the compiler generate code that avoids actually building the list of
all tails of L?

Obviously, one could write alltails in (reversed) tail-recursive form,
but I would think that if the compiler has any chance of inlining
alltails into that list comprehension to remove the intermediate list,
the best chance would be with the simpler non-tail-recursive form.

-- Jonathan
_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://erlang.org/mailman/listinfo/erlang-questions

[Anthony Ramine]

Hello Jonathan,

Replied inline.

Regards,

--
Anthony Ramine

Le 14 juin 2013 à 03:38, Jonathan Leivent a écrit :

> I have some questions about compiler optimizations on list comprehensions.
>
> The efficiency guide says that list comprehensions that are "neither assigned to a variable, nor passed to another function, nor returned" will be optimized by the compiler to avoid the list construction.
>
> However, Dialyzer sometimes complains about such list comprehensions with "Expression produces a value of type ['ok'], but this value is unmatched". So I have developed the habit of assigning to "_", as with:
>
> foo(...) ->
> ...,
> _ = [bar(X) || ...],
> ....
>
> After re-reading that line in the efficiency guide, it seems like this assignment might actually defeat the above compiler optimization. Does it? Or does the compiler still manage to do the optimization?

It doesn't, the compiler knows that "_" is not a variable and thus that the value of the expression ins't used. The match is there solely to silence the Dialyzer warning, to tell him you know what you are doing.

> If this does prevent the optimization, is there a way to get the optimization and prevent the Dialyzer warning while still using a list comprehension?
>
> Another question about list comprehension optimizations: If a list being iterated over is generated from a function that just builds the list element-wise, can the compiler inline that function so that the intermediate list isn't built? For instance, if the function is something like the very useful list of all non-empty tails of a list:
>
> alltails(L=[_|T]) -> [L|alltails(T)];
> alltails([]) -> [].
>
> [... || T <- alltails(L), ...]
>
> can the compiler generate code that avoids actually building the list of all tails of L?
>
> Obviously, one could write alltails in (reversed) tail-recursive form, but I would think that if the compiler has any chance of inlining alltails into that list comprehension to remove the intermediate list, the best chance would be with the simpler non-tail-recursive form.

If you tell the compiler to inline alltails/1, it could do some optimisations but I don't think it is smart enough, at the very least it won't inline anything if you don't tell it so.

[Thomas Lindgren]

First, I don't think this is done today. 

Second, it's a difficult issue in the general case. Unlike Haskell, Erlang is a strict language, so if you're a stickler for having the program behave the same before and after optimization, you will see that, in the general case, you run a risk of getting different answers if you reorder computations that way. For example, a different exception or different side effects could be generated in the new program. Ensuring the optimization is safe can quickly get intractable to a compiler. (So in practice it might be applied only in rare or simplistic cases.)

With that said, I think it could be interesting to investigate this optimization further, perhaps simply by being more relaxed about such issues. It can obviously yield great results in Haskell.

Best,

Thomas

---

From: Jonathan Leivent <jlei...@comcast.net>

[Jonathan Leivent]

On 06/14/2013 03:48 AM, Anthony Ramine wrote:
> ...

> It doesn't, the compiler knows that "_" is not a variable and thus that the value of the expression ins't used. The match is there solely to silence the Dialyzer warning, to tell him you know what you are doing.

Thanks - that's nice to know.

-- Jonathan

[Jonathan Leivent]

On 06/14/2013 05:16 AM, Thomas Lindgren wrote:
> First, I don't think this is done today.
>
> Second, it's a difficult issue in the general case. Unlike Haskell, Erlang is a strict language, so if you're a stickler for having the program behave the same before and after optimization, you will see that, in the general case, you run a risk of getting different answers if you reorder computations that way. For example, a different exception or different side effects could be generated in the new program. Ensuring the optimization is safe can quickly get intractable to a compiler. (So in practice it might be applied only in rare or simplistic cases.)
>
> With that said, I think it could be interesting to investigate this optimization further, perhaps simply by being more relaxed about such issues. It can obviously yield great results in Haskell.
>
> Best,
> Thomas

OK - I'm trying to develop a feel for when list comprehensions can be
used to make code more readable without fear that they also might make
that code slower and/or more wasteful of memory.

I obviously wouldn't want the Erlang compiler to introduce an
optimization that re-ordered side-effects - I just assumed it would be
able to tell when functions are side-effect-free in many simple cases
(and presume that they might have side effects in the more complex cases).

Maybe the particular case of iterating over tails of a list is itself
useful enough to warrant an addition to the Erlang list comprehension
syntax - maybe something like:

[... || Tail <+ List, ...]

That would, for example, make code that generates all 2-combinations of
elements from a list very easy to read:

[{X, Y} || [X|Rest] <+ List, Y <- Rest]

One could also imagine a more general case, with an initial expression,
continue condition, and next expression, kind of like a for loop common
to other languages:

[... || I := 0; I < 100; I + 1, ...]

[o...@cs.otago.ac.nz]

We have seen [... where I = 0 then I+1 while I < 100]
proposed, but that's not actually as general as a functional
language should be. What's needed is a general 'unfold'
proposal, and we've had that for a while too.

Semicolons in Erlang always have either the actual or
the metaphorical force of "OR", so they make no sense in
this context.

[Peer Stritzinger]

On 2013-06-15 12:21:25 +0000, o...@cs.otago.ac.nz said:
> We have seen [... where I = 0 then I+1 while I < 100]
> proposed, but that's not actually as general as a functional
> language should be. What's needed is a general 'unfold'
> proposal, and we've had that for a while too.

Somehow I have difficulty to find the "unfold" proposal, in the EEPS I
only found tuple comprehensions EEP12 and multigenerators EEP19.

Unfold sounds very interesting, I'd like to read the proposal on this.

Cheers
-- Peer

[Richard A. O'Keefe]

On 5/07/2013, at 2:09 AM, Peer Stritzinger wrote:

> On 2013-06-15 12:21:25 +0000, o...@cs.otago.ac.nz said:
>> We have seen [... where I = 0 then I+1 while I < 100]
>> proposed, but that's not actually as general as a functional
>> language should be. What's needed is a general 'unfold'
>> proposal, and we've had that for a while too.
>
> Somehow I have difficulty to find the "unfold" proposal, in the EEPS I only found tuple comprehensions EEP12 and multigenerators EEP19.

I didn't say that there was an unfold EEP,
I said that a certain syntax had been proposed (by me,
in this mailing list) and that there had been an
unfold proposal (also by me, also in this mailing list).

The unfold approach I described used

your_unfold(Your_State) -> [] or [Next|Your_State']

However, Haskell has led the way. What we really want is
something closer to streams.

A "stream" function maps a state to one of
done
{skip,New_State}
{next,New_State,Item}

to_list(Unfolder, State) ->
case Unfolder(State)
of done -> []
; {skip,New_State} -> to_list(Unfolder, New_State)
; {next,New_State,Item} -> [Item | to_list(Unfolder, New_State)]
end.

The nice thing about streams is that they can handle mapping and
filtering.

s_map(F, Unfolder) ->
fun (State) ->
case R = Unfolder(State)
of done -> R
; {skip,State1} -> R
; {next,State1,Item} -> {next,State1,F(Item)}
end
end.

s_filter(P, Unfolder) ->
fun (State) ->
case R = Unfolder(State)
of done -> R
; {skip,State1} -> R
; {next,State1,Item} ->
case P(Item)
of false -> {skip,State1}
; true -> R
end
end
end.

They can also handle a 'while':

s_while(P, Unfolder) ->
fun (State) ->
case R = Unfolder(State)
of done -> R
; {skip,State1} -> R
; {next,State1,Item} ->
case P(Item)
of false -> done
; true -> R
end
end
end.

So we can compose any chain of "map", "filter", and
"takeWhile" steps into a single unfolder->unfolder
function, which can then be applied to anything we
can convert to a stream, which includes lists,
integer ranges, tuples, and other things.

With a little ingenuity, we can squeeze in "expanding
the state" so that we can include "dropWhile", every Nth,
and other wrinkles into our chains.

[Anthony Ramine]

Hello Richard,

What is the point of the skip constructor? Couldn't the unfolder call itself on its own with the updated state?

Also, could you formalize that in an EEP?

Regards,

--
Anthony Ramine

[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.