Thoughts on laziness (long)

Thomas Lindgren <>
Mon Oct 23 11:53:23 CEST 2000


> I remember reading that the 'Mercury' people hoped to be able to
> perform complexity reducing source->source transforms. Does HIPE do
> that, or does the potential (I read "in general" to mean "there are
> some cases where we can do better". That may have been reading too
> much into what you wrote.) come from 'striking it lucky' when doing 
> (local) optimisations on object code?

As far as I am aware, the HIPE compiler does not reduce complexity
apart from removing simple dead computations. For example, it can't
remove a loop (exception-free, etc) producing an unused value. Or
at least it couldn't when I left Uppsala. Maybe there are some new
tricks I'm not aware of.

The Mercury compiler (among others) is capable of one form of
optimization that should be possible at nearly-source level:
reordering of conses (and other term constructions). This reduces
space complexity, e.g., from linear into running at constant stack
space. (Prolog implementations tend to use this by default, btw.)

Here is an illustration of the basic technique. Take simple append:

append([],Ys) -> Ys;
append([X|Xs],Ys) ->
   Zs = append(Xs,Ys),
   [X|Zs].

The code above pushes X on the stack in each append iteration, then
constructs the list one step at a time as the stack pops, when
append/2 returns. You can say this constructs the list back-to-front:
the last cons of the (new) list is the first to be constructed

This code can basically be rewritten into the more efficient:

append([],Ys) -> Ys;
append([X|Xs],Ys) ->
   Res = [X|empty],
   append_loop(Xs,Ys,Res).

append_loop([],Ys,Tail) -> setcdr(Tail,Ys);  %% setcdr not really in erlang
append_loop([X|Xs],Ys,Tail) ->
   Res = [X|empty],
   setcdr(Tail,Res),
   append_loop(Xs,Ys,Res).

Here, we construct the list 'front-to-back' instead. We keep a pointer
to the last cons of the list (which is incomplete, as indicated by 'empty')
and zap it with the next cons.

What is the gain? append_loop/3 is tail recursive. At each iteration,
append/2 saves (a) a return address and (b) X. Thus, we save 2 stores
+ 2 loads per list element, which isn't bad for append.

			    Thomas
--
Thomas Lindgren					
Alteon Websystems Sweden			http://www.bluetail.com



More information about the erlang-questions mailing list