Musing on PMD dispatch problems

[Lee Salzman]

So, Bryan managed to run into a pathological dark corner of PMD, that
turns out is not all as pathological as it had seemed at first. We just
got lucky it never popped up before. To illustrate this, suppose the
following:

We have objects A, B, and C where B is derived from A, and C is derived
from B. Suppose we have methods "A foo: B [x]" and "A foo: C [y]"
defined.

>From the dispatcher's point of view on selector "foo:", things look like this:

*   foo:  *

C:{}      C:{y}
|         |
|         |
B:{}      B:{x}
|         |
|         |
A:{x,y}   A:{}

where the bars represent the delegation links, top of the column being the most
specific object.

To simplify, dispatch to a particular method "x" happens when atleast one "x"
has been seen in each column, and they happen to all be visited before "y" 
would otherwise be dispatched this way.

Now, the current way PMD/Slate visits each object is by scanning each
row horizontally (i.e. visits each argument once), then moves down to the
next row, scans it, moves down...

The problem here is that on the first two scans, both "y" and "x" have
been visited in the second column, but neither "x" nor "y" have been
seen in the first row yet. So once it hits the third row, it now first
starts off by scanning "A". But both "x" and "y" are defined here on
this "A", so depending on which one it sees first, it can dispatch
either "x" or "y" -- and in Bryan's case it was actually dispatching "x",
which is not the most specific method!

Also consider the following scenario:

*  foo:  *
B:{x}    B:{y}
|        |
|        |
A:{y}    A:{x}

In this case "y" would always get dispatched first! This is fairly
related to the problem described above. The ordering of methods is
ambiguous because methods are dispatched as quickly as possible, when 
found by scanning along the rows.

So how do you fix this? There are two ways, and both will give you a
sensible (identical to how CLOS works) full ordering of
methods.

1) 
   The first time you see a method, you tag it with a number, that
represents the order it was visited in. When you dispatch, instead of
dispatching immediately when you come across something that satisfies
the dispatching conditions, you scan the WHOLE row first. Then, as you
come across methods that need to be dispatched, you pick the one that
was seen first over the other methods - this is fairly simple, you just
compare the currently found method's number with the one you found
previously, and replace it if it was seen first. Then once you've hit
the end of the row, you finally dispatch on whichever method was left
standing.

   This fixes both of the cases above, and doesn't add too much
overhead, but it will add some.

2)
   This is the more interesting thought that occurred to me, and the
reason I felt compelled to write a long drawn out post. Quite simply,
scan down the columns first instead of rows! This yields the exact same
method ordering as the first solution, but it will actually make the PMD
algorithm SIMPLER. For multiple dispatch cases this could possibly make
PMD slower, but for single dispatch cases, it can actually make PMD
faster since it will actually do no more work than single dispatch! As
soon as you would see a method in the first column, you would simply
dispatch it - no different than what single dispatch itself does. 

   This also potentially simplifies some of the bookkeeping done during
dispatch.

Lee