I am implementing new instantiation rules and have run into a
nasty bug.
What happens is this: when we do inlining we have to "clone"
the function to be inlined and all its descendants (nested functions,
local variables etc), specialising them, and reparenting them to
the caller.
So if f calls g, and g has a kid h, then after inlining g's body into f,
we have a clone of h which is now a child of f. We have to do that
because g will probably be calling h (why else give g a child if you're
not going to call it?)
Now, if g was originally a child of f, after we inline it (in all locations
its called in f) if it isn't recursive, then g is not needed any more
so we can delete it (its not needed as a separate function because it's
been inlined)
Deleting such unused children isn't optional, it has to be done to prevent
and exponential explosion, otherwise we may try to optimise g, when it
isn't used, and we could be repeatedly be cloning stuff which generates
more and more children. If I take the child removal out of Felix a program
that compiles in 60 seconds runs for over and hour without terminating.
Now, everything appeared to work before, until I added a new instantiation
rule. Previously this instance:
instance[T] X[T] { fun f: T -> T = ... }
would match
class X[T] { fun f:T -> T = .. }
with a call like
fun g[T] (x:T) => f(x);
Due to a non-optimal algorithm, this is no longer the case.
the reason is this:
instance [U] X[U->U]
If we have that instance as well as the X[T] one we cannot match
against the X[T] instance because after T is replaced by double -> double
for example, the U->U instance would be more specialised.
So we defer the match against X[U] until we can be sure X[U->U] could
not be matched. This delay occurs whenever the are at least two
instances that cannot be excluded as matches in the future:
one (the X[T]) could match right now, but we still can't take it if the
other one X[U->U] could match in the future and that is ALWAYS
the case if the caller is polymorphic in its variable (and there is at
least one instance other than the fully general one).
The new algorithm isn't very smart about making the decision
I suspect, its (hopefully) conservative though. A proper match
can always be selected when the call is reduced down to a
concrete type by substitution of type variables. So all of this should
work (actually it doesn't seem to work but that isn't the issue here :)
So the effect is that now we have dispatches that used to be taken
that are delayed, including a common one that is causing a heap
of breakages now but worked before:
repr -> str
This is Python repr function, which by default is just str.
The problem is that this used to go through polymorphically
because that match can ALWAYS be taken because its the default.
But now it is never taken if there's a possible definition of repr
other than the default.
Ok that's the context. So here's the problem: normally only the parent
of a function, or its siblings (more generally any descendant of the
parent) can call a function. So we can delete that child if none
of the parents descendant family call the function.
Unfortunately that rule is only true for direct calls. It fails if you have
a closure of the the descendant hiding somewhere else.
Any function which can see the child can make a closure
of it, and save it or return it. However, this is like a direct call
and can be treated the same way: the closure can only be created
if the function making it is itself called, so the transitive closure
of direct calls PLUS closure object constructions is still enough
to determine if a function can be called or not.
The PROBLEM is that there's another kind of indirect call
than through a closure (which is effectively an indirect dispatch
through a pointer). And that is of course:
A call to instance via a virtual function.
Now, normally an instance isn't a child of anything let alone
the caller. But consider now in general inlining a global function,
its children get cloned and become children of the caller.
So if you inline an instance, even one which is global, its children
become children of the caller.
Ok, so far so good, except for one thing: polymorphic recursion.
When you clone a function you specialise it with the call arguments:
this applied not only to the values passed to the function but also
to the types: when you inline a polymorphic function in T, with
a call using a double value, the cloned children of the called
function become children of the caller -- specialised with T replace
by double.
BUT there is a special exception. If the function with type parameter T
calls itself with a type other than T, that call is NOT recursive. Its call
to the original function with a DIFFERENT specialisation. This is
called "polymorphic recursion".
Polymorphic recursion is exactly what I'm trying to implement!
A simple example:
instance[T,U] Str[T * U] {
fun str (x: T, y: U) => str x + ", " + str y;
}
That inner call to str dispatches through the same virtual function
virtual str: T -> T
that call IT, but it doesn't usually won't recurse to the same
function. It might though, if you
str ( (1,2.4), "Hello")
then the dispatch to T*U splits to a dispatch on T and on U,
and the dispatch on U does polymorphic recursion again,
and dispatches to str on int * double, in this case the same
polymorphic instance of the virtual function: we end up with three
dispatches to the concrete str functions for int, double, and string,
joined by two dispatches to the tuple specialisation.
So the problem I am having seems to be like this: a function
calls str which makes a str clone child specialised on some
type which in turn calls ITSELF, as a child, via another
function (such as repr calling str) and the virtual function
dispatch is ignored when forming the closure.
This really complicated! It shouldn't happen. It never happened
before. In principle, the compiler has to distinguish between
a dispatch to self via the same type arguments (actual recursion)
and dispatch through a distinct type, which is a call to the original
function, not the clone, and isn't recursive at all (if it is, you have
an infinite regress on instantiations which Felix can't handle)
Its very important this be exactly right because attempting to
inline a recursive function will lead to an infinite unrolling,
so we have to stop it. On the other hand dispatching to an instance
on a distinct type can only cause an infinite unrolling if we screwed
up (by definition!). A trivial example is dispatch
A -> B dispatches to function on type B -> A
.. .which dispatches to A->B again .. infinite expansion
Felix can't detect this oscillation (Haskell can). Its easy to write:
fun str[A,B] (x:A, y:B) => str (y,x)
Here str calls itself with different type arguments so the call is not
recursive, but polymorphic recursive. After one expansion, the call
becomes recursive.
Anyhow .. if you're now lost .. me too!
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
