This file was automatically generated from http://svn.pugscode.org/pugs/docs/notes/multi_method_dispatch/multimethods.pod on Wed Jun 6 22:16:47 2007 GMT, revision 16639.

Multimethods

NAME
DESCRIPTION

NAME

Multimethods - Perl 6 Multimethod Dispatch

DESCRIPTION

Properties

We would like the following properties in a multimethod system:

* Sanity: (This is the pretty much definition of a multimethod system) A variant will only be chosen if all of its invocants are members of the corresponding parameter types. If a variant A's parameter types are all subtypes of the corresponding parameter types of a variant B and at least one is a proper subtype (that is, A is strictly more specific than B), and A and B both match a set of invocants, B will never be chosen.
* Symmetry: Switching the order of two invocants in all variants and all calls has no effect on the decision.
* Stability: Adding new types, but changing no subtype relationships between types that were previously there, to the subtype hierarchy does not change which variant is selected.

Multimethods specify a return type, and they take a context type as an argument. We would like this to have a similar sanity property:

* Return-sanity: A variant will only be chosen if its return type is a subtype of the context type. If a variant A's return type is a supertype of a variant B's return type, and both A and B match the context, then B will never be chosen.

Notice that stability also applies to the return type.

Pure multimethod dispatch

The simplest system that has these properties is the system that is ambiguous for all calls. But here's a useful system with these properties:

Define the method specificity relation << to be:

    A <<= B  iff  all invocant types of A are <: the  corresponding
                  invocants types in B and the return type of A is :>
                  the return type of B.
    A << B   iff  A <<= B and !(B <<= A)

Then the dispatch is defined as follows:

    A variant A is chosen iff all invocants are members of their
        corresponding parameter types, the return type is a subtype of
        the context type, and for all variants B != A which also match,
        A << B.  If no such variant exists, then the call fails.

(Note, this is now blessed by the rest of @Larry)

Theorem: Pure dispatch is sane and return-sane.

Proof: The matching condition is obvious.

Suppose that A and B match some context and set of invocants, that A << B (and thus A != B). If B were chosen, then by definition of the dispatch, B << A (because A also matches). So B must not match.

Theorem: Pure dispatch is symmetric.

Proof: Obvious: the definition depends only on "correspondence" of invocant parameters, which is invariant with respect to order.

Theorem: Pure dispatch is stable.

Proof: Obvious: the definition depends only on subtype relations between invocant types (i.e. not on the space of all defined types), which the property states do not change.

Trusting pure multimethod dispatch

There is another system that is worth exploring, called the "trusting pure multimethod dispatch". This amends the pure dispatch's rule with:

    If there are no matching variants for a call, there is a set of
    variants As which match the invocants but not the context, whose
    return types are :> the context, and which are <<= to all matching
    variants (so all items in this set differ only by return type), and
    there is one variant B in As whose return type is <: all return
    types in As, then B is selected.

This obviously does not have the return-sanity property, but it does maintain all other properties. The idea is that the context is a type, and any member of that type is a valid return value. If it is a subtype of the declared return value, there is a chance that the actual return value will be in the context type (especially if the context is propagated for coersion). We take the most specific such return value (rather than the most general which is usually used for selecting returns), as it is the "most likely" to match the context.

This may seem to be a contrived attempt to be over-dwimmy, but it is necessary for eg. a function to decide between list/item context when applied a stringification operator (it should choose item :-).

See context_coersion.pod, "What's in a Context?", for a proof that if there is no multiple inheritance in the context hierarchy, that this rule will never be ambiguous.

Static inference of multimethods

Multimethod variants can be defined in multiple modules and even at runtime. We have a proto form to tell us the overall signature of a multimethod, but that doesn't help us infer infix:<=>, when it can take on many different forms.

If we require one condition of multimethods, then it becomes possible to do partial inference on the variants:

    If a variant A <<= a variant B, then all non-invocants of A are :>
    to the corresponding non-invocants of B.

So to make a proto where the multimethods are free to decide what kinds of parameters they will take:

    proto foo(Any $longname; None $param) {...}

And this call will never typecheck (because None never accepts any values); however if there is a variant in scope:

    multi foo(Str $longname; Int $param) {...}

Then if the compiler can prove that the longname parameter is a subtype of Str, it is guaranteed that the param is a supertype of Int, and it is thus safe to pass an Int.

We get to infer infix:<=> now, but we have to assume the existence of a Sink reference that accepts writes but not reads. Since you're assigning, you only need a Sink.

    multi infix:<=> (Sink[Num] $dest; Num $src) {...}
    multi infix:<=> (Sink[Int] $dest; Int $src) {...}

Note that Sink[a] <: Sink[b] exactly when b <: a. In order for this to be well behaved, the following has to be true:

    If Sink[Int] <: Sink[Num] then Int :> Num
    If Sink[Num] <: Sink[Int] then Num :> Int

Taking the contravariant Sink type, we see that they are both true!

The only thing that remains is how to get Plural context on the right side of =.