[m-dev.] Deforestation question

[Ralph Becket]

I've just been talking to Nick Benton here about his MLj compiler for ML.

It seems MLj carries out two optimizations that, according to him, are
very effective.

The first is that it is almost always better to flatten data structures,
at least within module boundaries.  For example,

:- type t(T1, T2) == list(pair(T1, T2)).

will be translated into

:- type t(T1, T2)
	--->	[]
	;	'.'(T1, T2, t(T1, T2)).

The caveat here is that we only `flatten in' non-recursive data types
that have either a single constructor or (for bonus points) for which
all constructors have the same signature (apparently this happens enough
that it's worth doing).

The above really depends upon optimization no. 2 to really pay off...

The second optimization is basically what I've been talking about:
a tail recursive function that deconstructs one of its arguments
should be converted into a wrapper function with the original
signature and an arity-raised core function.

For example, from

fib(N, {A, B}) = ... fib(N - 1, {B, A + B})

we go to

fib(N, {A, B}) = fib_2(N, A, B).

fib_2(N, A, B) = ... fib(N - 1, B, A + B).

The type flattening game above works well if there's a good chance
that an appropriate matching arity raised function exists (e.g. if
we have flattened our list(pair(T1, T2)) datatype and map a function
f(pair(T1, T2)) = T3 over it, we would hope that (a) map would be
specialised for the expanded datatype and argument f (if known at
compile time) would be converted into the arity raised version.

Now, some heuristics are required to stop this sort of term
rewriting going mad, but it seems that it wouldn't be too hard to
start off with very conservative constraints and work up from there.

[N.B. The arity-raising version can be adapted to handle functions
of arguments with several different possible constructors; this is all
doable as a source-source transformation.]

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 

--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------