=head0 Multis
Z<sec:multis>

X<multidispatch>
X<multis>

Perl usually decides which function to call based on the name of the function
or the contents of a function reference.  This is simple to understand.  Perl
can also examine the contents of the arguments provided to decide which of
several variants of a function--each with the same name--to call.  In
this case, the amount and types of the function's arguments help to distinguish
between the variants of a function.  This is called I<multidispatch>, and the
functions to which Perl can dispatch in this case are I<multis>.

X<JSON>

Javascript Object Notation (I<JSON>) is a simple data exchange format often
used for communicating with web services.  It supports arrays, hashes, numbers,
strings, boolean values, and C<null>, the undefined value. Here you can find
an implementation that turns Perl 6 data structures to JSON.

This snippet demonstrates how multis make the code simpler and more obvious.

The other way round, converting a JSON string to a Perl 6 data structure, is
covered in the chapter A<sec:grammars>.

=begin sidebar

The code presented here is runnable. It is part of the libary C<JSON::Tiny>,
which is available from U<http://github.com/moritz/json/>. It also includes
tests and documentation.

=end sidebar

=begin programlisting

    multi to-json(Bool $d) { $d ?? 'true' !! 'false'; }
    multi to-json(Real $d) { ~$d }
    multi to-json(Str  $d) {
        '"'
        ~ $d.trans(['"',  '\\',   "\b", "\f", "\n", "\r", "\t"]
                => ['\"', '\\\\', '\b', '\f', '\n', '\r', '\t'])
        ~ '"'
    }

    multi to-json(Array $d) {
        return  '[ '
                ~ $d.values.map({ to-json($_) }).join(', ')
                ~ ' ]';
    }

    multi to-json(Hash  $d) {
        return '{ '
                ~ $d.pairs.map({ to-json(.key)
                ~ ' : '
                ~ to-json(.value) }).join(', ')
                ~ ' }';
    }

    multi to-json($d where {!defined $d}) { 'null' }

    multi to-json($d) {
        die "Can't serialize an object of type " ~ $d.WHAT.perl
    }

=end programlisting

X<candidates>

This code defines a single multi sub named C<to-json>, which takes one argument
and turns that into a string. C<to-json> has many I<candidates>; these subs all
have the name C<to-json> but differ in their signatures.  Every candidate
resembles:

=begin programlisting

    multi to-json(Bool $data) { ... }
    multi to-json(Real $data) { ... }

=end programlisting

Which one is actually called depends on the type of the data passed to the
subroutine.  A call such as C<to-json(Bool::True)> invokes the first candidate.
Passing a numeric value of type C<Real> instead invokes the second.

The candidate for handling C<Real> is very simple; because JSON's
and Perl 6's number formats coincide, the JSON converter can rely on Perl's
conversion of these numbers to strings. The C<Bool> candidate returns a literal
string C<'true'> or C<'false'>.

The C<Str> candidate does more work: it wraps its parameter in quotes and
escapes literal characters that the JSON spec does not allow in strings--a
tab character becomes C<"\t">, a newline C<"\n">, and so on.

The C<to-json(Array $d)> candidate converts all elements of the array to JSON
with recursive calls to C<to-json>, joins them with commas, and surrounds them
with square brackets.  The recursive calls demonstrate a powerful truth of
multidispatch: these calls do not necessarily recurse to the C<Array>
candidate, but dispatch to the appropriate candidate based on the types of
I<their> arguments.

The candidate that processes hashes turns them into the form C<{ "key1" :
"value1", "key2" : [ "second", "value" ] }>. It does this again by recursing
into C<to-json>.

=head1 Constraints

X<constraints>
X<multidispatch, constraints>

Candidates can specify more complex signatures:

=begin programlisting

    multi to-json($d where {!defined $d}) { 'null' }

=end programlisting

=for author

Link to C<Any> discussion.

=end for

X<types, constraints>
X<constraints>
X<types, subset>
X<subset type>

This candidate adds two new twists.  It contains no type definition, in which
case the type of the parameter defaults to C<Any>, the root of the normal
branch of the type hierarchy.  More interestingly, the C<where {!defined $d}>
clause is a I<constraint>, which defines a so-called I<subset type>.  This
candidate will match only I<some> values of the type C<Any>--those where the
value is undefined.

X<nominal type>
X<types, nominal>

Whenever the compiler performs a type check on the parameter C<$d>, it first
checks the I<nominal> type (here, C<Any>). A nominal type is an actual class
or role, as opposed to additional constraints in the form of code blocks.

If that check succeeds, it calls
the code block. The entire type check can only succeed if the code block
returns a true value.

The curly braces for the constraint can contain arbitrary code.  You can abuse
this to count how often a type check occurs:

=begin programlisting

    my $counter = 0;

    multi a(Int $x)  { }
    multi a($x)      { }
    multi a($x where { $counter++; True }) { }

    a(3);
    say $counter;       # says B<0>
    a('str');
    say $counter;       # says B<2>

=end programlisting

This code defines three multis, one of which increases a counter whenever its
C<where> clause executes.  Any Perl 6 compiler is free to optimize away type
checks it knows will succeed.  In the current Rakudo implementation, the second
line with C<say> will print a higher number than the first.

In the first call of C<a(3)>, the nominal types alone already determine the
best candidate match, so the where block never executes and the first
C<$counter> output is always C<0>.

The output after the second call is at least C<1>. The compiler has to execute
the C<where>-block at least once to check if the third candidate is the best
match, but the specification does not require the I<minimal> possible number of
runs.  This is illustrated in the second C<$counter> output. The specific
implementation used to run this test actually executes the C<where>-block twice.
Keep in mind that the number of times the subtype checks blocks execute is
specific to any particular implementation of Perl 6.

=for author

Verify Rakudo * behavior at press time.

=end for

=begin sidebar

Avoid writing code like this in anything other than example code.  Relying on
the side effects of type checks produces unreliable code.

=end sidebar

=head1 Narrowness

One candidate remains from the JSON example:

=begin programlisting

    multi to-json($d) {
        die "Can't serialize an object of type " ~ $d.WHAT.perl
    }

=end programlisting

With no explicit type or constraint on the parameter C<$d>, its type defaults
to C<Any>--and thus it matches any passed object. The body of this function
complains that it doesn't know what to do with the argument.  This works for
the example, because JSON's specification covers only a few basic structures.

The declaration and intent may seem simple at first, but look closer.  This
final candidate matches not only objects for which there is no candidate
defined, but it can match for I<all> objects, including C<Int>, C<Bool>,
C<Num>.  A call like C<to-json(2)> has I<two> matching candidates--C<Int>
and C<Any>.

X<multidispatch, narrowness>

=for author

C<A> and C<B> are abstract; how about Integer and Positive Integer?  That has
its flaws too, but it's more concrete.  It also fixes the subsequent example.

Good idea, but Positive Integer would be a subset type, which doesn't count as
a narrower nominal type. Array and List would work, but are hard to get right.
C<Int ~~ Num> is subject to change, so currently I can't think of a good idea
with builtin types - any other idea? --moritz

=end for

If you run that code, you'll discover that the C<Int> candidate gets called.
Because C<Int> is a type that conforms to C<Any>, it is a I<narrower> match for
an integer.  Given two types C<A> and C<B>, where C<A> conforms to C<B> (C<A ~~
B>, in Perl 6 code), an object which conforms to C<A> does so more narrowly
than to C<B>.  In the case of multi dispatch, the narrowest match always wins.

A successfully evaluated constraint makes a match narrower than a similar
signature without a constraint.  In the case of:

=begin programlisting

    multi to-json($d) { ... }
    multi to-json($d where {!defined $d}) { ... }

=end programlisting

... an undefined value dispatches to the second candidate.

However, a matching constraint always contributes less to narrowness than a
more specific match in the nominal type.

=begin programlisting

    TODO: Better example

    multi a(Any $x where { $x > 0 }) { 'Constraint'   }
    multi a(Int $x)                  { 'Nominal type' }

    say a(3), ' wins';       # says B<Nominal type wins>

=end programlisting

This restriction allows a clever compiler optimization: it can sort all
candidates by narrowness once to find the candidate with the best matching
signature by examining nominal type constraints. These are far cheaper to
check than constraint checks. Constraint checking occurs next, and only if
the constraint check of the narrowest candidate fails, other candidates are
tried that are lass narrow by nominal type.

=for author

I could use a table or figure here to illustrate the hierarchy of narrowing.

=end for

The C<Int> type object both conforms to C<Int>, but it is also an undefined
value. If you pass it to the multi C<a>, the second candidate, which is
specific to C<Int> wins, because nominal types are checked first.

=head1 Multiple arguments

Candidate signatures may contain any number of positional and named arguments,
both explicit and slurpy. However only positional parameters contribute to the
narrowness of a match:

=begin programlisting

    class Rock     { }
    class Paper    { }
    class Scissors { }

    multi wins(Scissors $, Paper    $) { +1 }
    multi wins(Paper    $, Rock     $) { +1 }
    multi wins(Rock     $, Scissors $) { +1 }
    multi wins(::T      $, T        $) {  0 }
    multi wins(         $,          $) { -1 }

    sub play($a, $b) {
        given wins($a, $b) {
            when +1 { say 'Player One wins' }
            when  0 { say 'Draw'            }
            when -1 { say 'Player Two wins' }
        }
    }

    play(Scissors, Paper);
    play(Paper,    Paper);
    play(Rock,     Paper);

=end programlisting

=for figure
        \includegraphics[width=0.8\textwidth]{../src/images/mmd-table.pdf}
        \caption{Who wins the \emph{Rock, Paper, Scissors} game?}
        \label{fig:mmd-rock-paper-scissors}

This example demonstrates how multiple dispatch can encapsulate all of the
rules of a popular game.  Both players independently select a symbol (rock,
paper, or scissors).  Scissors win against paper, paper wraps rock, and
scissors can't cut rock, but go blunt trying.  If both players select the same
item, it's a draw.

The code creates a class for each possible symbol.
For each combination of chosen symbols for which Player One
wins there's a candidate of the form:

=begin programlisting

    multi wins(Scissors $, Paper $) { +1 }

=end programlisting

X<parameters, anonymous>

Because the bodies of the subs here do not use the parameters, there's no
reason to force the programmer to name them; they're I<anonymous parameters>.
A single C<$> in a signature identifies an anonymous scalar variable.

X<types, capture>
X<type capture>

The fourth candidate, C<multi wins(::T $, T $) {  0 }> uses C<::T>, which is a
I<type capture> (similar to I<generics> or I<templates> in other programming
languages). It binds the nominal type of the first argument to C<T>, which can
then act as a type constraint. If you pass a C<Rock> as the first argument,
C<T> acts as an alias for C<Rock> inside the rest of the signature and the body
of the routine. The signature C<(::T $, T $)> will bind only two objects of the
same type, or where the second is a subtype of the first.

In this game, that fourth candidate matches only for two objects of the same
type.  The routine returns C<0> to indicate a draw.

The final candidate is a fallback for the cases not covered yet--every case
in which Player Two wins.

If the C<(Scissors, Paper)> candidate matches the supplied argument list,
it is two steps narrower than the C<(Any, Any)> fallback, because both
C<Scissors> and C<Paper> are direct subtypes of C<Any>, so both contribute
one step.

If the C<(::T, T)> candidate matches, the type capture in the first parameter
does not contribute any narrowness--it is not a constraint, after all.
However C<T> I<is> a constraint for the second parameter which accounts for as
many steps of narrowness as the number of inheritance steps between C<T> and
C<Any>.  Passing two C<Rock>s means that C<::T, T> is one step narrower than
C<Any, Any>.  A possible candidate:

=begin programlisting

    multi wins(Rock $, Rock $) {
        say "Two rocks? What is this, 20,000 years ago?"
    }

=end programlisting

... would win against C<(::T, T)>.

=head1 Bindability checks

X<traits, implicit constraints>
X<implicit constraints>

Traits can apply I<implicit constraints>:

=begin programlisting

    multi swap($a is rw, $b is rw) {
        ($a, $b) = ($b, $a);
    }

=end programlisting

This routine exchanges the contents of its two arguments. It must bind the two
arguments as C<rw>--both readable and writable. Calling the C<swap> routine
with an immutable value (for example a number literal) will fail.

X<substr>
X<functions, substr>

The built-in function C<substr> can not only extract parts of strings, but
also modify them:

=begin programlisting

    # substr(String, Start, Length)
    say substr('Perl 5', 0, 4);         # prints B<Perl>

    my $p = 'Perl 5';
    # substr(String, Start, Length, Substitution)
    substr($p, 6, 1, '6');
    # now $p contains the string B<Perl 6>

=end programlisting

You already know that the three-argument version and the four-argument version
have different candidates: the latter binds its first argument as C<rw>:

=begin programlisting

    multi substr($str, $start = 0, $length = *) { ... }
    multi substr($str is rw, $start, $length, $substitution) { ... }

=end programlisting

X<arity>
X<functions, arity>

=for author

The discussion of slurpy versus optional parameters seems out of place here;
functions chapter?

=end for

This is also an example of candidates with different I<arity> (number of
expected arguments). This is seldom really necessary, because it is often a
better alternative to make parameters optional. Cases where an arbitrary number
of arguments are allowed are handled with slurpy parameters instead:

=begin programlisting

    sub mean(*@values) {
        ([+] @values) / @values;
    }

=end programlisting

=head1 Nested Signatures in Multi-dispatch

Chapter A<sec:subs> showed how to use nested signatures to look deeper into data
structures and extract parts of them. In the context of multiple dispatch,
nested signatures take on a second task: they act as constraints to distinguish
between the candidates. This means that it is possible to dispatch based upon
the shape of a data structure. This brings Perl 6 a lot of the expressive power
provided by pattern matching in various functional languages.

Some algorithms have very tidy and natural expressions with this feature,
especially those which recurse to a simple base case.  Consider quicksort.  The
base case is that of the empty list, which trivially sorts to the empty list.
A Perl 6 version might be:

=begin programlisting

    multi quicksort([]) { () }

=end programlisting

The C<[]> declares an empty nested signature for the first positional
parameter.  Additionally, it requires that the first positional parameter be an
indexable item--anything that would match the C<@> sigil.  The signature will
only match if the multi has a single parameter which is an empty list.

The other case is a list which contains at least one value--the pivot--and
possibly other values to partition according to the pivot.  The rest of
quicksort is a couple of recursive calls to sort both partitions:

=begin programlisting

    multi quicksort([$pivot, *@rest]) {
        my @before = @rest.grep({ $_ <= $pivot });
        my @after  = @rest.grep({ $_ >  $pivot });

        return quicksort(@before), $pivot, quicksort(@after);
    }

=end programlisting

=head1 Protos

X<protos>
X<functions, protos>

You have two options to write multi subs: either you start every candidate with
C<multi sub ...> or C<multi ...>, or you declare once and for all that the
compiler shall view every sub of a given name as a multi candidate.  Do the
latter by installing a I<proto> routine:

=begin programlisting

    proto to-json($) { ... }       # literal ... here

    # automatically a multi
    sub to-json(Bool $d) { $d ?? 'true' !! 'false' }

=end programlisting

Nearly all Perl 6 built-in functions and operators export a proto definition,
which prevents accidental overriding of built-insN<One of the very rare
exceptions is the smart match operator C<< infix:<~~> >> which is not easily
overloadable.  Instead it redispatches to overloadable multi methods.>.

=begin sidebar

To hide all candidates of a multi and replace them by another sub, declare it
as C<only sub YourSub>.  At the time of writing, only Rakudo supports this..

=end sidebar

=head1 Toying with the candidate list

Each multi dispatch builds a list of candidates, all of which satisfy the
nominal type constraints. For a normal sub or method call, the dispatcher
invokes the first candidate which passes any additional constraint checks.

X<callsame>
X<callwith>

A routine can choose to delegate its work to other candidates in that list.
The C<callsame> primitive calls the next candidate, passing along the arguments
received.  The C<callwith> primitive calls the next candidate with different
(and provided) arguments.  After the called routine has done its work, the
callee can continue its work.

If there's no further work to do, the routine can decide to hand control
completely to the next candidate by calling C<nextsame> or C<nextwith>.  The
former reuses the argument list and the latter allows the use of a different
argument list.  This delegation is common in object destructors, where each
subclass may perform some cleanup for its own particular data.  After it
finishes its work, it can delegate to its parent class meethod by calling
C<nextsame>.

=head1 Multiple MAIN subs

C<MAIN> routines can also be multis. That way it is easy to add separate code
for each action that the script can perform.

=begin programlisting

    # file calc.pl
    multi MAIN('add', $x, $y)  { say $x + $y }
    multi MAIN('div', $x, $y)  { say $x / $y }
    multi MAIN('mult', $x, $y) { say $x * $y }

=end programlisting

Example calls to this script:

=begin screen

    $ perl6 calc.pl add 3 5
    8
    $ perl6 calc.pl mult 3 5
    15
    $ perl6 calc.pl
    Usage:
    calc.pl add x y
    or
    calc.pl div x y
    or
    calc.pl mult x y

=end screen

Here the multi dispatcher selects the routine based on the value of the first
argument.