optimization of list comprehensions

Ulf Wiger (AL/EAB) ulf.wiger@REDACTED
Fri Mar 3 13:51:51 CET 2006


 
Richard A. O'Keefe wrote:
>
> As for combining accumulation with list comprehension, one 
> can already write
>     lists:foldl(fun (X,Y) -> X+Y end, 0, 
> 	        [some list comprehension goes here]) which 
> isn't *that* bad.

... and I, for one, sometimes do this, too.
Of course, it has the unwanted property that you have 
to make an extra pass over the list. One could imagine
a refactoring optimization that recognizes the use of 
a list comprehension as input to a map or fold, and 
rewrites it into something else.

What complicates matters somewhat (for us hobby hackers)
is that the list comprehension transforms are written 
in core erlang. Thus:

lc1(List) ->
    _ = [foo(X) ||
	    X <- List,
	    X > 17].

gets transformed to:

'lc1'/1 =
    %% Line 10
    fun (_cor0) ->
        let <_cor6> =
            %% Line 11
            letrec
                'lc$^0'/1 =
                    fun (_cor3) ->
                        case _cor3 of
                          <[%% Line 12
                            X|_cor2]> when %% Line 13
                                           call 'erlang':'>'
                                               (X,
                                                17) ->
                              let <_cor4> =
                                  apply 'foo'/1
                                      (X)
                              in  let <_cor5> =
                                      %% Line 12
                                      apply 'lc$^0'/1
                                          (_cor2)
                                  in  [_cor4|_cor5]
                          ( <[_cor1|_cor2]> when 'true' ->
                                %% Line 12
                                apply 'lc$^0'/1
                                    (_cor2)
                            -| ['compiler_generated'] )
                          <[]> when 'true' ->
                              []
                          ( <_cor3> when 'true' ->
                                primop 'match_fail'
                                    ({'function_clause',_cor3})
                            -| ['compiler_generated'] )
                        end
            in  apply 'lc$^0'/1
                    (_cor0)
        in  %% Line 14
            'ok'

Now, the _ seems to be implied by the fact that _cor0
is not used, but if I understand the above code correctly,
it is not quite as obvious at this level that we deliberately
ignore the return value of the lc.

Perhaps the combination of a parse_transform and a core_transform
could do it, where the parse_transform detects

     [{match,
       11,
       {var,11,'_'},
       {lc,11,
        {call,
         11,
         {atom,11,foo},
         [{var,11,'X'}]},
        [{generate,
         12,
         {var,12,'X'},
         {var,12,'List'}},
         {op,13,'>',{var,13,'X'},
         {integer,13,17}}]}},

and perhaps inserts a pseudo-function as a wrapper,
which is later removed by the core_transform, which
re-writes the accumulator expression in the core
erlang code for the lc ([_cor4|_cor5])?

The core erlang specification can be found here:
http://www.it.uu.se/research/publications/reports/2000-030/2000-030-nc.p
df

The module cerl.erl in the compiler application seems to 
be a useful utility for those who want to write core
erlang transforms.

/Ulf W



More information about the erlang-questions mailing list