Re: Data structures for efficient overload resolution

Steve Horne wrote:


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


> What I'm really interested in is the case with multiple independent
> parameters. I have very little idea how to even approach this problem.


This may or may not be useful to your specific case, in so far as it
may give another direction to look for ideas:


I look at overload resolution as a sorting problem where the actual
argument types provide the sorting key for a partial order. Any given
argument type needs to be able to compare two parameter types, and
return one of (<, >, =, <> (incompatible with either)), or possibly more
nuanced for narrowing vs. widening etc., assuming the sorting function
normalises this. There may be more argument types than there are
parameter types (e.g. the 'nil' or 'null' type, in such languages that
support it, usually cannot be a parameter type).


However, multiple parameters doesn't (normally) mean a lexicographical
ordering. Instead, the sorting function taking the key (composed of the
actual argument types) should return the ordering if only some of the
types in the key indicate an ordering; return incompatible if any
indicate <>; etc. with details governed by the specifics of your
overloading semantics.


Overload resolution is then reduced to creating and maintaining a list
of the "max" candidates, i.e. candidates which compare greater than any
previously seen candidate and equal to one another. If at the end of the
search, there are multiple candidates, then the result is ambiguous; no
candidates, not compatible; a single candidate, job done.


If the overload type ordering is sane, then this process should be
linear in the number of candidates (and arguments). By sane, I mean that
any candidate which compares greater than any previous candidate should
also compare greater than any candidate equal to the previous candidate,
preventing a potential quadratic mini-explosion.


-- Barry


--
http://barrkel.blogspot.com/

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