mmd-draft.txt

[TSa]

HaloO,

I figure that
http://svn.openfoundry.org/pugs/docs/notes/multi_method_dispatch/mmd-draft.txt
hasn't made it into S06 yet. So what is the current state of affairs?

Could someone explain me the voting mechanism mentioned in the
document? I get that it works from left to right and compares
the narrowness of types of the competing targets at that position.
But what information is recorded on the score cards and how is
that finally used in selecting the dispatch target?

Regards, TSa.
--

[Audrey Tang]

在 Oct 26, 2006 10:26 AM 時，TSa 寫到：
> I figure that
> http://svn.openfoundry.org/pugs/docs/notes/multi_method_dispatch/

> mmd-draft.txt
> hasn't made it into S06 yet. So what is the current state of affairs?

The original plan was to have Larry review it in Brazil and check it
in along with an
implementation (or two), but that may have to wait a bit now that
Larry can't make it to Brazil...

> Could someone explain me the voting mechanism mentioned in the
> document? I get that it works from left to right and compares
> the narrowness of types of the competing targets at that position.
> But what information is recorded on the score cards and how is
> that finally used in selecting the dispatch target?

A variant's score cards only records two Boolean values for each
variant: "voting" and
"qualified".

The final resolution is by consensus: After all the positions are
processed, if all variants
consider a single unique variant to be qualified, it is chosen.
Otherwise an
ambiguity error is raised.

Thanks,
Audrey

[TSa]

HaloO,

Audrey Tang wrote:
> A variant's score cards only records two Boolean values for each
> variant: "voting" and "qualified".

Here is a summary of the explanation Audrey gave me on #perl6.
Note that this is from memory because I didn't save the log.
In particular I don't remember exactly where the intersection
of QS and VS was taken. But I hope I understood the algorithm.
So, correct me if there is a mistake below.

The following assumes a call with

\($fido,$fido) # (Dog,Dog)

to two multi targets M1 and M2. For each target two sets of
methods are maintained: QS (Qualified Set) and VS (Voting Set).
The numbers indicate the values after the evaluation of the
argument positions. Step 0 is the applicability test. When the
sets are the same for M1 and M2 they are listed only once.

:(Dog, Animal) # M1
:(Animal, Dog) # M2

0: QS={M1,M2} VS={M1,M2}
1: QS={M1} VS={M1,M2}
2: QS={} VS={M1,M2}

Result is ambiguity because of the empty QS.

:(Dog; Animal) # M1
:(Animal; Dog) # M2

0: QS={M1,M2} VS={M1,M2}
1: QS={M1} VS={M1,M2}
2: QS={M1} VS={M1}

M1 is chosen. Both VS are reduced by M2 which is
already disqualified. That is the new VS is the
intersection of the old VS and QS.

:(Dog; Animal) # M1
:(Animal, Dog) # M2

0: QS={M1,M2} VS={M1,M2}
1: QS={M1} VS={M1,M2}
2: QS1={M1} VS1={M1}
QS2={} VS2={M1,M2}

Single semicolon is local action on VS of M1.
Result is ambiguity because of non-consensus.

:(Dog, Animal) # M1
:(Animal; Dog) # M2

0: QS={M1,M2} VS={M1,M2}
1: QS={M1} VS={M1,M2}
2: QS1={} VS1={M1,M2}
QS2={M1} VS2={M1}

Result is ambiguity because of non-consensus.

:(Dog;; Animal) # M1
:(Animal, Dog) # M2

0: QS={M1,M2} VS={M1,M2}
1: QS={M1} VS={M1,M2}
2: QS={} VS={M2}

Double semicolon is a global operation to take M1 out of
all VS, hence no case distinction. The remaining M2 in VS
of step 2 disqualifies M1 and we end up with ambiguity.

:(Dog, Animal) # M1
:(Animal;; Dog) # M2

0: QS={M1,M2} VS={M1,M2}
1: QS={M1} VS={M1,M2}
2: QS={M1} VS={M1}

This dispatches to M1.

Note that the purpose of the VS is to disqualify other
methods. Only the methods in QS remain contenders.

Regards, TSa.
--

[TSa]

HaloO,

I have one further question to the document. It mentions
chains of type coercions that are applied in the compatibility
stage. A type that has fewer conversion steps is considered
more specific. But is that a wise thing to do in an MMD system?

I would expect no coercions to occur. How can the number of
steps be important? Consider one chain Foo --> Bar --> Baz and
one Blahh --> Baz. Why should the second be more specific? In
the end the type system has to decide if Foo or Blahh is more
specific with respect to Baz or if they are incomparable. This
depends on the partial order of parameter types of the candidates.
Note that this order is rooted at the actual argument type.

Actually the type narrowness consideration touches the core of
the type system! Here the partial order of types manifests itself.
What are its building blocks? Wouldn't some structural type
analysis be helpful here?

Regards, TSa.
--

[TSa]

HaloO,

I wrote:
> This depends on the partial order of parameter types of the
> candidates. Note that this order is rooted at the actual argument
> type.

I don't know if the following is obvious but I want to rant about it ;)
This partial order of the parameter types is in the case of a readonly
parameter built up from supertypes of the argument type. E.g.

G H I
\ / \ /
D E F
\ \ /
B C
\ /
A

Here A is the argument type and B to I are types of parameters of
methods in a multi. There are four chains of subtypes A to G, A to H
via E and F, and A to I. Within these chains the methods are comparable
for specificity. I don't know if this is what is meant by "type
compatibility path" in mmd-draft.txt.

For writeonly parameters the partial order extends in the other
direction and is built from subtypes. For a rw parameter only exact
type match at A is type safe.

Regards, TSa.
--