=head1 NAME

Multimethods - Perl 6 Multimethod Dispatch

=head1 DESCRIPTION

=head2 Properties

We would like the following properties in a multimethod system:

=over

=item * 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.

=item * Symmetry

Switching the order of two invocants in all variants and all calls has
no effect on the decision.

=item * 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.

=back

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

=over

=item * 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.

=back

Notice that stability also applies to the return type.

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

=head2 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 L<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.  

=head2 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 C<< 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 C<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 C<< 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 C<=>.