Re: Data structures for efficient overload resolution

On Mar 17, 2:44 pm, Barry Kelly <barry.j.ke...@gmail.com> wrote:


> > Comparisons must be done both with the call being resolved
> > and with those previously identified candidates that have yet to be
> > eliminated.
>
> Candidates 1 & 2 compare equal to one another. By sane, I mean that it
> is only necessary to compare candidate 3 with candidate 1, because, by
> my sanity rule (see quote above), you don't need to compare against 2.


Ah - this is the problem. By my rules, 1 & 2 do not compare equal -
they compare is incompatible, since a call with either signature could
not match a candidate with the other.


I think you are considering cases ambiguous that I would consider as a
more specialised case overriding a more general one. Probably your
rule is the norm for most programming languages - it's not something
I've given a thought to for some time. When I wrote my tool, I went
with the rule that any candidate can be considered to override any
other provided that all parameters are at least as specialised, and
that at least one parameter is more specialised, with no incompatible
parameters. It seemed a natural generalisation of the single dispatch
rules to multiple dispatch, I think it's what treecc does, and to be
honest it didn't occur to me that any other rule might be valid.


That is, I can (and do) quite validly have code that includes
candidates for (parent, parent), (parent, child), (child, parent) and
(child, child) for the same function. The (child, child) case takes
precedence over all others. I also have cases with (parent, parent),
(parent, child1) and (child2, parent) - in this case a call for
(child2, child1) is ambiguous, but I allow candidates to be given
priorities so that the ambiguity can be resolved.


An extreme case for using priorities would be a dynamic version of the
overloading rules for arithmetic operators in C etc. You get a pattern
something like...


    priority 1 variant add (int8, any) ...;
    priority 2 variant add (any, int8) ...;
    priority 3 variant add (int16, any) ...;
    priority 4 variant add (any, int16) ...;
    ...


It obviously leaves the 'any' parameter still to be resolved in each
case, but at least the selected implementation knows what type to
return.


> Of course, many exponential and high polynomial algorithms work fine
> when n is small. Can you give some numbers - number of types, average
> compatibility rates (for any random type, what fraction of the total set
> of types is it compatible with, on average), numbers of candidates,
> numbers of parameters, cost of testing for compatibility?


I only wrote it around christmas time, and I haven't formally analysed
it. I'm not likely to, either. I just hit limitations in treecc and
needed to work around them. I only have two real applications, and one
of those is itself. It's generating maybe 15,000 lines (carriage
return count) in total of useful code, 3,000 or so for itself and the
rest for this other utility. I like my code generators to generate
readable code, so it's not all that dense either.


The main application is in the development of another code generation
utility, and it's basic handling walking of the AST using multiple
dispatch as an alternative to visitor-like patterns, plus dynamically-
typed values for expression evaluation. The expression evaluation
supports compiling expressions to C++ code with static type checking
to ensure the generated code will be valid, as well as evaluating
other expressions at compile time.


The number of parameters involved is rarely that large - two or three
normally, I don't recall ever needing four - which is one reason why
the rule induction is a bit daft. All it can do is order the parameter
checks in the decision tree, and there isn't much scope for re-
ordering them anyway. It *can* make a difference with two or three
parameters, but rarely does.


As for numbers of types, the worst case ATM is around 80, though at
least 10 are abstract. Most of what's left are the AST nodes - I'm
minimising my dynamic typing issues by using a variable-width integer
class (the priority example earlier is purely hypothetical). The AST
nodes tend to work OK since only a couple of additional context-
setting parameters are relevant to the dispatch for operations on
these nodes, with few cases for each. The usual pattern is something
like...


    function handle_ast_node (sum_node, context)
    {
        call handle_sum (sum_node->arg1, sum_node->arg2);
    }


That is, the dispatch for dynamic typing and for AST node stuff are
kept separate. I considered allowing the dispatch handler to look at
objects pointed to by fields as well as the object itself, but it's a
lot of work for a small gain.


The two real-world uses I have for the utility are itself and this
other code generator, and both build in a few seconds on my P4
machine. Much slower than the before-the-return-key-bounces response
of most code generation utilities these days, but obviously not a real
problem. I have one deliberately perverse test case which takes about
25 seconds.


> Basically, given that some of the problems with exponential explosion
> are both setup time and space for the approach you describe, I'm
> wondering if there's a compromise possible: a shorter setup time with a
> less explosive space, at the cost of doing a little max-finding at the
> end.
>
> Candidates can be trivially bucketed by number of parameters, so the
> number of candidates is only interesting for any given fixed number of
> parameters, so assume the below for each possible number of parameters:


I already evaluate one named function, with a known number of
parameters and a strict most-general-possible signature, at a time.
I'm pretty sure I have the smallest possible buckets.


> In other words, I think the above would be madness in a real-world
> compiler with e.g. Java-style overloading and typically only a small
> handful of candidates that ever need to be considered, but it may make
> sense for your case.


I need to re-read what you said, I think, but I have to agree with the
"it would be madness" comment here. My existing utility is doing mad
things anyway, and could work more efficiently by simply not doing
those mad things.

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