I'm about to commit a new optimisation called 'uncurrying'.
Given a function like:
fun f(x:int) (y:int)=> x + y;
and a call like:
var x = f 1 2;
Felix synthesises a new function
fun f'(x:int, y:int)=> x + y;
and replaces the call with
var x = f (1,2);
The idea is seen when you look at the function f in detail:
fun f(x:int):int -> int = {
fun g(y:int)=>x+y;
return g;
}
So f is actually defined to return a closure of g, which is bound to
the passed x. g then accepts y and adds it to x, returning the result.
Implemented literally, f would be returning a
pointer to a heap allocated C++ class instance for g, and
f itself would have to be a heap allocated C++ class instance
too, so g can bind to it.
Now, what we'd really like to implement is:
x = 1 + 2;
and if you try the above function in the current Felix (prior
to my commit) you will actually get that .. even if you have
20 curried arguments .. :)
So what's the big deal?? The answer is, with the newly enabled
function inlining, I had to exclude recursive functions unless
they were children, and the optimisation known as 'apply lifting'
which eliminates left nested applications by inlining cannot
be effective.
I found this when examining the recursive implementation
of fold_left. The problem is that fold_left is defined by:
fun fold_left[T,U] (_f:U->T->U) (init:U) (x:list[T]):U =
{
return
match x with
| Empty[T] => init
| Cons[T] (?h,?t) => fold_left _f (_f init h) t
endmatch
;
}
Now, after flattening t he inner body by inlining the anonymous
functions generated by the match (which happens, because they're
children, even though recursive), the result should be tail
recursive, and optimised to a loop.
But this doesn't happen (try it! examine the C++ ..).
The reason is that the ACTUAL definition (skipping
type annotations):
fun fold_left[T,U] (_f:U->T->U) =
{
fun fold_left'2 (init) {
fun fold_left'3 (x)=>
match x with
| Empty[T] => init
| Cons[T] (?h,?t) => fold_left _f (_f init h) t
endmatch
;
return fold_left'3;
}
return fold_left'2;
}
So fold_left can't be inlined by outsiders because it is recursive,
and it can't be inlined inside fold_left'3 because it is fold_left'3s
grand-parent.
And fold_left'2 can't be inlined into fold_left either, because
it is a function, not an application.
[Note: possibly this can be done by turning the functions inside
out by continuation passing style transform -- not sure]
But if we rewrite the function as:
fun fold_left[T,U] (_f:U->T->U, init:U, x:list[T]):U =
{
return
match x with
| Empty[T] => init
| Cons[T] (?h,?t) => fold_left (_f, (_f init h), t)
endmatch
;
}
then it is trivially tail recursive. So it should then be possible
after inlining the matchy stuff so that the function is now
self-tail-recursive, to replace the recursion with a loop.
An lo! Since it is now a loop, it isn't recursive at all, and
can be inlined! :) :)
The effect is to completely eliminate all closure creation.
[Except possible for the argument function _f]
As I write there are still bugs: the tail-rec optimisation
is happening, but the resulting non-rec function isn't
being inlined (possibly because it is tailed too late).
Also two regression tests fail, so there are still bugs.
Note: you can still curry such functions: if the function
has arity N, Felix generates N functions, each on eating
up one extra argument.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
-------------------------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc.
Still grepping through log files to find problems? Stop.
Now Search log events and configuration files using AJAX and a browser.
Download your FREE copy of Splunk now >> http://get.splunk.com/
_______________________________________________
Felix-language mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/felix-language
