Data structures for efficient overload resolution

I'm interested in data structures for efficient overload resolution.


If there was only one parameter to a function (and assuming single
inheritance) it would be easy to build an index for efficient overload
resolution. A tree structured the same as the heirarchy of the classes
would handle it. I imagine that better balanced tree structures are
possible using partial-ordering comparisons (is these two classes
super-and-subclass, sub-and-superclass, equal, or other), at least for
single inheritance cases. I'm certainly interested in reading any good
papers you can point me to on this kind of thing, but this is only a
very simplified case of the real problem.


What I'm really interested in is the case with multiple independent
parameters. I have very little idea how to even approach this problem.
The only guess I can make is along the lines of treating each
parameter as a separate dimension and using a spacial structure such
as R-trees, quadtrees or whatever, but of course normal spacial
indexes require that the keys are fully ordered along each dimension.


I have done overload resolution stuff in the recent past, for a tool I
wrote which is very similar to Rhys Weatherlys treecc - ie a code
generator for supporting multiple dispatch with a single inheritance
class heirarchy. However, the code I wrote for the overload resolution
is extremely naive. It evaluates all possible cases, then uses a rule
induction system to try to derive an efficient dispatch handler. Yes,
the rule induction bit is probably overkill, but I did it anyway. It
does minimise the average number of parameters explicitly tested in
the dispatch handler, so it's not totally pointless.


Getting back to the point, because it evaluates every possible
combination, it's vulnerable to combinatorial explosion issues. Not
good, but then the overload resolution needed to take priority rules
and constraint conditions into account as well as the basic
inheritance rules. Overall, I decided I don't care that much, and its
just something I wrote for my own use anyway.


But I now have a different problem with a very similar structure. It's
not overload resolution in the normal compiler sense, but it has the
same basic form. No arbitrary constraint conditions in this case, but
resolution does need to take into account (effectively) several
parameters with a single-inheritance type structure. Not sure whether
I need to resolve ambiguities with a priority system - probably not,
though.


So far, it's a simpler problem that the one I've already solved. The
trouble is, I need to cope with changes to the class heirarchies and
the set of overloads in real time. Hence I cannot precalculate
everything to build a simple decision tree. I need a more dynamic data
structure.


The actual application involves abstracting input methods so they can
be easily reconfigured at run-time. The idea is to have a heirarchy of
target processes and modes, and a heirarchy of physical/abstract input
source types, with each event mapping taking a form analogous to a
single function overload. If it sounds like I'm making things too
complex, that's probably true, but the investigation is more out of
curiosity than practical problem solving ;-)


So, can anyone point me to some interesting papers along these lines?


Thanks in anticipation.

Return to the comp.compilers page.
Search the comp.compilers archives again.