Closure elimination transformation (continuation style passingcode)

Claus Reinke claus.reinke at
Wed May 20 05:50:54 EDT 2009

>1- avoid forming the (iter xs) and (count i+1) closures by passing the 
>function and the arguments instead of the function bound to the argument
>  iter []     next i done = done
>  iter (x:xs) next i done = next i x iter xs
>  count i x step xs = step xs count (i+1) (i+1)
>  test xs = iter xs count 0 0

I'm not at all sure what you're aiming for (the above doesn't compile),
just some guesses/hints:

- your original version allowed both 'next' and 'done' to change at every
    step, so specializing 'iter' for 'count' would seem to involve something
    like fixpoint reasoning for the general case or at least unfolding a finite 
    number of recursions for the special case

- if 'next' is supposed to be constant, inlining 'iter' would provide enough
    context to specialize the recursion for that constant parameter, but 
    GHC doesn't inline recursive definitions (see also ) and even if it did
    the equivalent of loop peeling (unfold a few iterations of the recursion
    at the call site), it might not spot the constant parameter

- a common workaround -if there are constant parts to the recursion-
    is to split the recursive definition into non-recursive wrapper and
    recursive worker (with some parameters made constant), then 
    to let GHC inline the wrapper; this is particularly interesting if the 
    constant parts are functions

So, if you are happy with 'next' being constant throughout the iteration
(encoding any variation in the accumulator 'done'), something like this
might do:

    iter next = iterW
      iterW done []     = done
      iterW done (x:xs) = next done x iterW xs

    count i x step xs = step (i+1) xs

    test xs = iter count 0 xs

GHC should do more wrt recursive definitions, but it can't guess your
intentions. There are facilities for library-defined optimizations (RULES),
but they wouldn't cover the kind of transformations you seem to be
looking for. Work is underway to make library-specified optimizations
more expressive (as core2core pass plugins), though I don't know 
the status of either that  (Max?-) or whether #3123 is on anyone's list.


More information about the Glasgow-haskell-users mailing list