Type tree traversals [Re: Modeling multiple inheritance]

[Brandon Michael Moore]

On Wed, 5 Nov 2003, Simon Peyton-Jones wrote:

> | More overlapping:
> | Allow any overlapping rules, and apply the most specific rule that
> | matches our target. Only complain if there is a pair of matching
> | rules neither of which is more specific than the other.
> | This follow the spirit of the treatment of duplicate imports...
>
> Happy days.  I've already implemented this change in the HEAD.  If you
> can build from source, you can try it.

Great. But I can't build from the source: I'm getting errors about a
missing config.h.in in mk. I'm just trying autoconf, comfigure. I'll look
closer over the weekend.

> | Backtracking search:
> | If several rules matched your target, and the one you picked didn't
> | work, go back and try another.
> |
> | This isn't as well through out: you probably want to backtrack through
> all
> | the matching rules even if some are unordered by being more specific.
> It
> | would probably be godd enough to respect specificity, and make other
> | choices arbitrarilily (line number, filename, etc. maybe Prolog has a
> | solution?). This probably isn't too hard if you can just add
> | nondeterminism to the monad the code already lives in.
>
> I didn't follow the details of this paragraph.  But it looks feasible.

It's an unclear paragraph. I meant that if we are just looking for the
first match, we should try more specific rules before less specific rule.
That doesn't give us a complete ordering so we might do something
arbitrary for the rest, unless there is a better solution.

I think we should make sure that there are not multiple solutions, but we
want more specific rules to take priority. Order the solutions
lexicographically by how specific each rule in the derivation was and
complain if there isn't a least element in this set of solutions.  To
implement, if at each step there is a most specific rule in the set we
haven't tried, and making that choice at every step gives us a solution,
we know we have the most specific solution and don't need to keep
searching.

I don't want to be too strict about having a unique solution because
that can prevent modelling multiple inheritance

Brandon