Type tree traversals [Re: Modeling multiple inheritance]

[Simon Peyton-Jones]

| 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.

| 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.

| Overloading resolution:
| This one is really half-baked, but sometimes it would be nice if there
was
| some way to look at
| class MyNumber a where
|   one::a
| instance MyNumber Int where
|   one = 1
| 
| then see (one+1) and deduce that the 1 must have type Int, rather than
| complaining about being unable to deduce MyNumber a from Num a. This
is
| really nice for some cases, like a lifting class I wrote for an
Unlambda
| interpreter, with instances for LiftsToComb Comb and (LiftsToComb a =>
| LiftsToComb (a -> Comb)). With some closed world reasoning lift id and
| lift const might give you I and K rather than a type error. Also, for
| this work with modelling inheritance you almost always have to give
type
| signatures on numbers so you find the method that takes an Int, rather
| than not finding anything that takes any a with Num a. This obviously
| breaks down if you have instances for Int and Integer, and I don't yet
| know if it is worth the trouble for the benefits in the cases where it
| would help. Implementation is also a bit tricky. I think it requires
| unifying from both sides when deciding if a rule matches a goal.

I'm much less sure about this stuff.  Mark Shields and I did something
about closed classes in our OO paper
http://research.microsoft.com/~simonpj/Papers/oo-haskell/index.htm, and
Martin Sulzmann and colleagues have done lots of foundational work --
but the dust is still swirling I think.

Simon