[clean-list] Transform to CPS

[Fergus Henderson]

On 05-Feb-2003, Jerzy Karczmarczuk <karczma@info.unicaen.fr> wrote:
> Well, first of all, I wouldn't call this transformation a 'continuation',
> this is a variant of optimization with an accumulating parameter. It is
> quite simple to do when you have an *associative* operator involved, here
> the concatenation. The same principle can be used to optimize the power,
> the factorial, etc. All has been formalized by Darlington and Burstall
> many years ago.

This optimization, which we call "accumulator introduction", has been
implemented in the Mercury compiler.  If the user declares that an
operation is associative, the Mercury compiler can apply the optimization
automatically.  See the following reference:

     * "Making Mercury programs tail recursive".
       Peter Ross, David Overton and Zoltan Somogyi.
       Proceedings of the Ninth International Workshop on Logic-based
       Program Synthesis and Transformation, Venice, Italy, September 1999.
       <http://www.cs.mu.oz.au/research/mercury/information/papers.html#tail_lopstr_lncs>

While I'm at it, let me also give a reference for the Mercury compiler's
deforestation optimization which I mentioned in my previous mail:

     * "Optimization of Mercury programs".
       Simon Taylor.
       Honours report. Department of Computer Science,
       University of Melbourne, November 1998.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.