Luke Palmer > Class-Multimethods-Pure-0.13 > Class::Multimethods::Pure

Download:
Class-Multimethods-Pure-0.13.tar.gz

Dependencies

Annotate this POD

View/Report Bugs
Module Version: 0.13   Source  

NAME ^

Class::Multimethods::Pure - Method-ordered multimethod dispatch

SYNOPSIS ^

    use Class::Multimethods::Pure;

    package A;
        sub magic { rand() > 0.5 }
    package B;
        use base 'A';
    package C;
        use base 'A';
    
    BEGIN {
        multi foo => ('A', 'A') => sub {
            "Generic catch-all";
        };

        multi foo => ('A', 'B') => sub {
            "More specific";
        };
        
        multi foo => (subtype('A', sub { $_[0]->magic }), 'A') => sub { 
            "This gets called half the time instead of catch-all";
        };

        multi foo => (any('B', 'C'), 'A') => sub {
            "Accepts B or C as the first argument, but not A"
        };
    }

DESCRIPTION ^

Introduciton to Multimethods

When you see the perl expression:

    $animal->speak;

You're asking for speak to be performed on $animal, based on $animal's current type. For instance, if $animal were a Tiger, it would say "Roar", whereas if $animal were a Dog, it would say "Woof". The information of the current type of $animal need not be known by the caller, which is what makes this mechanism powerful.

Now consider a space-shooter game. You want to create a routine collide that does something based on the types of two arguments. For instance, if a Bullet hits a Ship, you want to deliver some damage, but if a Ship hits an Asteroid, you want it to bounce off. You could write it like this:

    sub collide {
        my ($a, $b) = @_;
        if ($a->isa('Bullet') && $b->isa('Ship')) {...}
        elsif ($a->isa('Ship') && $b->isa('Asteroid')) {...}
        ...
    }

Just as you could have written speak that way. But, above being ugly, this prohibits the easy addition of new types. You first have to create the type in one file, and then remember to add it to this list.

However, there is an analog to methods for multiple arguments, called multimethods. This allows the logic for a routine that dispatches on multiple arguments to be spread out, so that you can include the relevant logic for the routine in the file for the type you just added.

Usage

You can define multimethods with the "multi" declarator:

    use Class::Multimethods::Pure;

    multi collide => ('Bullet', 'Ship') => sub {
        my ($a, $b) = @_;  ...
    };

    multi collide => ('Ship', 'Asteroid') => sub {
        my ($a, $b) = @_;  ...
    };

It is usually wise to put such declarations within a BEGIN block, so they behave more like Perl treats subs (you can call them without parentheses and you can use them before you define them).

If you think BEGIN looks ugly, then you can define them inline as you use the module:

    use Class::Multimethods::Pure
        multi => collide => ('Bullet', 'Ship') => sub {...};

But you miss out on a couple of perks if you do that. See "Special Types" below.

After these are declared, you can call collide like a regular subroutine:

    collide($ship, $asteroid);

If you defined any variant of a multimethod within a package, then the multi can also be called as a method on any object of that package (and any package derived from it). It will be passed as the first argument.

    $ship->collide($asteroid);  # same as above

If you want to allow a multi to be called as a method on some package without defining any variants in that package, use the null declaration:

    multi 'collide';
    # or
    use Class::Multimethods::Pure multi => collide;

This is also used to import a particular multi into your scope without defining any variants there.

All multis are global; that is, collide always refers to the same multi, no matter where/how it is defined. Allowing scoped multis is on the TODO list. But you still have to import it (as shown above) to use it.

Non-package Types

In addition to any package name, there are a few special names that represent unblessed references. These are the strings returned by ref when given an unblessed reference. For the record:

    SCALAR
    ARRAY
    HASH
    CODE
    REF
    GLOB
    LVALUE
    IO
    FORMAT
    Regexp

For example:

    multi pretty => (Any) => sub { $_[0] };
    multi pretty => ('ARRAY') => sub {
        "[ " . join(', ', map { pretty($_) } @{$_[0]}) . " ]";
    };
    multi pretty => ('HASH')  => sub {
        my $hash = shift;
        "{ " . join(', ', 
                map { "$_ => " . pretty($hash->{$_}) } keys %$hash)
        . " }";
    };

Special Types

There are several types which don't refer to any package. These are Junctive types, Any, and Subtypes.

Junctive types represent combinations of types. any('Ship', 'Asteroid') represents an object that is of either (or both) of the classes Ship and Asteroid. all('Horse', 'Bird') represents an object that is of both types Horse and Bird (probably some sort of pegasus). Finally, none('Dog') represents an object that is not a Dog (or anything derived from Dog).

For example:

    multi fly => ('Horse') => sub { die "Horses don't fly!" };
    multi fly => ('Bird')  => sub { "Flap flap chirp" };
    multi fly => (all('Horse', 'Bird')) => sub { "Flap flap whinee" };

The Any type represents anything at all, object or not. Use it like so:

    multi fly => (Any) => sub { die "Most things can't fly." };

Note that it is not a string. If you give it the string "Any", it will refer to the Any package, which generally doesn't exist. Any is a function that takes no arguments and returns an Any type object.

Finally, there is a subtype function which allows you to specify constrained types. It takes two arguments: another type and a code reference. The code reference is called on the argument that is being tested for that type (after checking that the first argument---the base type---is satisfied), and if it returns true, then the argument is of that type. For example:

    my $ZeroOne = subtype(Any, sub { $_[0] < 2 });

We have just defined a type object that is only true when its argument is less than two and placed it in the type variable $ZeroOne. Now we can define the Fibonacci sequence function:

    multi fibo => (Any) => sub { fibo($_[0]-1) + fibo($_[0]-2) };
    multi fibo => ($ZeroOne) => sub { 1 };

Of course, we didn't have to use a type variable; we could have just put the subtype call right where $ZeroOne appears in the definition.

Consider the follwing declarations:

    multi describe => (subtype(Any, sub { $_[0] > 10 })) => sub {
        "Big";
    };
    multi describe => (subtype(Any, sub { $_[0] == 42 })) => sub {
        "Forty-two";
    };

Calling describe(42) causes an ambiguity error, stating that both variants of describe match. We can clearly see that the latter is more specific than the former (see "Semantics" for a precise definition of how this relates to dispatch), but getting the computer to see that involves solving the halting problem.

So we have to make explicit the relationships between the two subtypes, using type variables:

    my $Big      = subtype(Any,  sub { $_[0] > 10 });
    my $FortyTwo = subtype($Big, sub { $_[0] == 42 });
    multi describe => ($Big) => sub {
        "Big";
    };
    multi describe => ($FortyTwo) => sub {
        "Forty-two";
    };

Here we have specified that $FortyTwo is more specific than $Big, since it is a subtype of $Big. Now calling describe(42) results in "Forty-two".

In order to get the definitions of all, any, none, Any, and subtype, you need to import them from the module. This happens by default if you use the module with no arguments. If you only want to export some of these, use the import command:

    use Class::Multimethods::Pure import => [qw<Any subtype>];

This will accept a null list for you folks who don't like to import anything.

Semantics

I've put off explaining the method for determing which method to call until now. That's mostly because it will either do exactly what you want, or yell at you for being ambiguous[1]. I'll take a moment to define it precisely and mathematically, and then explain what that means for Mere Mortals.

First, think of a class simply as the set of all of its possible instances. When you say Foo is derived from Bar, you're saying that "anything that is a Foo is also a Bar", and therefore that Foo is a subset of Bar.

Now define a partial order < on the variants of a multimethod. This will represent the relationship "is more specific than". This is defined as follows:

Variant A < variant B if and only if

A particular argument list matches a variant A if:

In other words, we define "is more specific than" in the most conservative possible terms. One method is more specific than the other only when all of its parameters are either equal or more specific.

A couple of notes:

[1] Unlike Manhattan Distance as implemented by Class::Multimethods, which does what you want more often, but does what you don't want sometimes without saying a word.

Dispatch Straegties (and speed)

Class::Multimethods::Pure currently has three different strategies it can use for dispatch, named Cores. If you're having issues with speed, you might want to play around with the different cores (or write a new one and send it to me :-). The three cores are:

Class::Multimethods::Pure::Method::Slow

This is the default core. It implements the algorithm described above in an obvious and straightforward way: it loops through all the defined variants and sees which ones are compatible with your argument list, eliminates dominated methods, and returns. The performance of this core can be miserable, especially if you have many variants. However, if you only have two or three variants, it might the best one for your job.

Class::Multimethods::Pure::Method::DumbCache

This core implements the semantics above by asking the slow core what it would do, then caching the result based on the ref type of the arguments. It can guzzle memory if you pass many different types into the multi. For example, even if you only have one variant (A,A), but you subclass A n times and pass instances of the subclass into the multi instead, the DumbCache core will use memory proportional to n squared. If all your variants have the same arity, they don't use junctions or subtypes, and you're sure that the number of subclasses of the classes defined in the variants is bounded (and small), then this will be the fastest core.

Class::Multimethods::Pure::Method::DecisionTree

This core implements the semantics above by building a decision tree of type membership checks. That is, it does all its logic (like the Slow core) by asking whether arguments are of type X, without any magic caching or ref checking or anything. It also minimizes the numbers of such checks necessary in the worst case. It takes some time to compile the multimethod the first time you dispatch to it after a change. If you don't meet the conditions for DumbCache to be efficient, and you are not making frequent changes to the dispatch table (almost nobody does), then this is going to be the fastest core.

To enable a different core for all multimethods, set $Class::Multimethods::Pure::DEFAULT_CORE to the desired core. For example:

    use Class::Multimethods::Pure;
    $Class::Multimethods::Pure::DEFAULT_CORE = 'DecisionTree';

(If the name given to core is not already a class, then the module will try prepending Class::Multimethods::Pure::Method. I suppose you could get in trouble if you happened to have a package named Slow, DumbCache, DecisionTree in your program. When in doubt, fully qualify.)

A more courteous and versatile approach is to specify the core as an option to the method definition; i.e.:

    use Class::Multimethods::Pure foo => ('A', 'B'),
                                 -Core => 'DecisionTree',
                                  sub {...}

or:

    multi foo => ('A', 'B'), -Core => 'DecisionTree', sub {
        ...
    };

You may also set options separately from definiton, like:

    use Class::Multimethods::Pure 'foo', -Core => 'DecisionTree';

or:

    multi 'foo', -Core => 'DecisionTree';

which sets the core but defines no variant.

Combinator Factoring

One of the things that I find myself wanting to do most when working with multimethods is to have combinator types. These are types that simply call the multimethod again for some list of aggregated objects and perform some operation on them (like a Junction). They're easy to make if they're by themselves.

    multi foo => ('Junction', 'Object') => sub {...}
    multi foo => ('Object', 'Junction') => sub {...}
    multi foo => ('Junction', 'Junction') => sub {...}

However, you find yourself in a major pickle if you want to have more of them. For instance:

    multi foo => ('Kunction', 'Object') => sub {...}
    multi foo => ('Object', 'Kunction') => sub {...}
    multi foo => ('Kunction', 'Kunction') => sub {...}

Now they're both combinators, but the module yells at you if you pass (Kunction, Junction), because there are two methods that would satisfy that.

The way to define precedence with these combinators is similar to the way you define precedence in a recursive descent grammar. You create a cascade of empty classes at the top of your heirarchy, and derive each of your generics from a different one of those:

    package AnyObject;
    package JunctionObject;
        use base 'AnyObject';
    package KunctionObject;
        use base 'JunctionObject';
    package Object;
        use base 'KunctionObject';
        # derive all other classes from Object
    
    package Junction;
        use base 'JunctionObject';
        ...
    package Kunction;
        use base 'KunctionObject';
        ...

Now define your multis using these:

    multi foo => ('Junction', 'JunctionObject') => {...}
    multi foo => ('JunctionObject', 'Junction') => {...}
    multi foo => ('Junction', 'Junction') => {...}
    multi foo => ('Kunction', 'KunctionObject') => {...}
    multi foo => ('KunctionObject', 'Kunction') => {...}
    multi foo => ('Kunction', 'Kunction') => {...}

Then the upper one (Junction in this case) will get threaded first, because a Junction is not a KunctionObject, so it doesn't fit in the latter three methods.

Extending

Class::Multimethods::Pure was written to be extended in many ways, but with a focus on adding new types of, er, types. Let's say you want to add Perl 6-ish roles to the Class::Multimethods::Pure dispatcher. You need to do four things:

After you have defined these, you have fulfilled the Class::Multimethods::Pure::Type interface, and now you can pass an object of type My::Role to multi() and it will be dispatched using the pure-ordered scheme. It is nice to give the user a concise constructor for your object type.

You can also automatically promote strings into objects by defining variants on the (unary) multimethod $Class::Multimethods::Pure::Type::PROMOTE. So to promote strings that happen to be the names of roles, do:

    $Class::Multimethods::Pure::Type::PROMOTE->add_variant(
        [ Class::Multimethods::Pure::Type::Subtype->new(
            Class::Multimethods::Pure::Type::Any->new,
            sub { is_a_role_name($_[0]) }) 
        ] => 
            sub { My::Role->new($_[0]) });

Now when you pass strings to "multi", if is_a_role_name returns true on them, they will be promoted to a My::Role object.

AUTHOR ^

Luke Palmer <lrpalmer@gmail.com>

COPYRIGHT ^

Copyright (C) 2005 by Luke Palmer (lrpalmer@gmail.com)

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.5 or, at your option, any later version of Perl 5 you may have available.

syntax highlighting: