Closure elimination transformation (continuation style
passingcode)
Claus Reinke
claus.reinke at talk21.com
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
http://hackage.haskell.org/trac/ghc/ticket/3123 ) 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
where
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.
Claus
More information about the Glasgow-haskell-users
mailing list