TITLE

Objects : Native support for multimethods

VERSION

  Maintainer: Damian Conway <damian@conway.org>
  Date: 18 September 2000
  Last Modified: 25 Sep 2000
  Mailing List: perl6-language-objects@perl.org
  Number: 256
  Version: 2
  Status: Frozen

ABSTRACT

This RFC proposes that Perl natively support multiply dispatched subroutines (multimethods).

DESCRIPTION

Multimethods solve a class of problems in which objects of two or more hierarchies must interact polymorphically, but where the nature of the interaction is determined by the run-time type of both (all) the objects.

Theoretical model

It is proposed that calls to certain (explicitly marked) subroutines be dispatched using a different mechanism from that used for regular Perl 5 subroutines, or that used for Perl 5 methods.

These explicitly marked subroutines would share the same name, but provide unique parameter lists. Collectively all marked subroutines with the same name but different parameters lists would be known as a multimethod, with each individual subroutine known as a variant of the multimethod.

The new dispatch mechanism would look at the classes or types of each argument to the subroutine (by calling ref on each) and determine the "closest" matching variant of the multimethod, according to the parameter types specified in the variants' parameter list.

The result would subsume the behaviour of function overloading (e.g. in C++) but in a more sophisticated manner, since multimethods take the run-time inheritance relationships of each argument into account. Another way of thinking of the mechanism is that it would perform polymorphic dispatch on every argument of a multimethod, not just on the first.

Defining multimethods

A single variant of a multimethod would be defined by specifying a subroutine with a full parameter list (as per RFC 128), and appending the attribute :multi. Two or more such subroutines could be defined with the same name, in the same package namespace, provide they were both defined with the :multi attribute, and their parameter lists were not identical.

For example:

	package LargeNum;
	package LargeInt;    use base 'LargeNum';
	package LargeFloat;  use base 'LargeNum';

	package LargeMath;

        sub divide(LargeInt $a, LargeInt $b) : multi {
		...
	}

        sub divide(LargeInt $a, LargeFloat $b) : multi {
		...
	}

This creates a (single) multimethod called LargeMath::divide with two variants. If the multimethod is called with two references to LargeInt objects as arguments:

	$x = LargeInt->new(1234567890);
	$y = LargeInt->new(9876543210);
	$quotient = divide($x, $y);

then the first variant is invoked. If the multimethod is called with a LargeInt reference and a LargeFloat reference:

	$x = LargeInt->new(1234567890);
	$y = LargeFloat->new(9876543210.12345);
	$quotient = divide($x, $y);

then the second variant is called.

Calling the multimethod with any other combination of LargeNum-derived reference arguments (e.g. a reference to a LargeFloat and a reference to a LargeInt, or two LargeFloat references) results in an exception being thrown, with the message:

	No viable candidate for call to multimethod divide

To avoid this, a "catch-all" variant could be specified:

	sub divide(LargeNum $b, LargeNum $b) : multi {
		...
	}

Now, calling divide with (for example) a LargeFloat reference and a LargeInt reference causes this third variant to be invoked. That's because a LargeFloat is-a LargeNum (so the first argument is compatible with the first parameter), and a LargeInt is-a LargeNum too (so the second argument is compatible with the second parameter). Note that adding this third variant doesn't affect calls to the other two, since multiple dispatch always selects the nearest match.

Finding the "nearest" multimethod

The usefulness of multiple dispatch depends on how intelligently the dispatcher decides which variant of a multimethod is "nearest" to a given set of arguments. That decision process is called dispatch resolution, and it is proposed that it be done (or appear to be done, modulo optimization) like this:

If the types of the arguments given (as determined by applying ref to each in turn) exactly match the set of parameter types specified in any variant of the multimethod, that variant is immediately called.

Otherwise, the dispatch mechanism compiles a list of viable targets. A viable target is a variant of the multimethod with the same number of parameters as there were arguments passed. In addition, for each parameter the specified parameter type must be a base class of the actual type of the corresponding argument in the actual call (i.e. each argument must belong to a subclass of the corresponding parameter type).

If there is only one viable target, it is called immediately. If there are no viable targets, an exception is thrown indicating that the multimethod can't handle the specific set of arguments. (but see "Handling dispatch failure" below).

Otherwise, the dispatch mechanism examines each viable target and computes its inheritance distance from the actual set of arguments. The inheritance distance from a single argument to the corresponding parameter is the number of inheritance steps between their respective classes (working up the tree from argument to parameter). If there's no inheritance path between them, the distance is infinite. The inheritance distance for a set of arguments is just the sum of their individual inheritance distances.

The dispatch mechanism then chooses the viable target with the smallest inheritance distance as the actual target. If more than one viable target has the same smallest distance, the call is ambiguous. In that case, the dispatch process fails and an exception is thrown (but see "Handling dispatch failure" below) If there's only a single actual target, its identity is cached (to accelerate subsequent dispatching), and then the actual target is invoked.

Handling built-in types

Because the multiple dispatch mechanism applies ref to determine the type of each argument, it is indifferent to whether those arguments are references to blessed objects, or just regular Perl data types. That means that multimethod variants can also be defined to process built-in data types:

        sub stringify(ARRAY $a) : multi {
                my @arg = map { stringify $_ } @a;
                return  "[" . join(", ",@a) . "]";
        }

        sub stringify(HASH $h) : multi {
                my %arg = map { stringify $_ } %h;
                return  "{" . join(", ", map( "$_=>$h{$_}", keys %h) ) . "}";
        }

        sub stringify(CODE $c) : multi {
                return "sub {???}";
        }

        sub stringify(Regexp $r) : multi {
                return "qr/$r/";
        }

        sub stringify(UNIVERSAL $r) : multi {   # *any* type of object
                return $obj->stringify()
			if $obj->can('stringify');
                return "???";
        }

        sub stringify($scalar) : multi {        # catch-all if ref() eq ""
                return qq{'$scalar'};
        }


        # and later...

        print stringify([1,2,3]);
        print stringify({a=>1,b=>[1,2,3],c=>MyClass->new(),d=>qr/#.*/});
        print stringify(42);

Notes:

In the above example, stringify is used recursively in processing the contents of arrays and hashes. This ensures that nested components (as in the second of the "and later..." examples) are correctly stringified. This indicates some of the polymorphic power of multimethods, in that the single map-ped call to stringify suffices to correctly stringify every array element and hash entry, no matter what type that nested element or entry is.
The parameter type UNIVERSAL provides a means of writing a single variant that captures references to any blessed object, since every blessed object automatically inherits from UNIVERSAL.
A variant whose argument is untyped (i.e. the last variant in the above example) represents a "catch-all" case, which in this particular case would receive all calls to stringify which had non-reference scalar arguments. If the stringify(UNIVERSAL) variant did not exist, the untyped variant would also receive all calls with blessed objects as arguments.

Handling dispatch failure

It's relatively easy to set up a multimethod such that particular combinations of argument types cannot be correctly dispatched. For example, consider the following variants of a multimethod called put_peg:

        package RoundPeg;     use base 'Peg';
        package SquareHole;   use base 'Hole';

        sub put_peg(RoundPeg,Hole) : multi {
                print "round peg in generic hole\n"
        }

        sub put_peg(Peg,SquareHole) : multi {
                print "generic peg in square hole\n"
        }

        sub put_peg(Peg,Hole) : multi {
                print "generic peg in generic hole\n"
        }

If put_peg is called like this:

        my $peg  = RoundPeg->new();
        my $hole = SquareHole->new();

        put_peg($peg, $hole);

then the call can't be dispatched, because there's no way to decide between the variants (RoundPeg,Hole) and (Peg,SquareHole), each of which is the same inheritance distance (i.e. 1 derivation) from the actual arguments.

The response to this situation (proposed above) is to throw an exception like this:

        Cannot resolve call to multimethod put_peg(RoundPeg,SquareHole).
        The multimethods:
                put_peg(RoundPeg,Hole)
                put_peg(Peg,SquareHole)
        are equally viable

This is the obvious behaviour, since the case truly is ambiguous.

Some languages (e.g. CLOS) take a different approach -- breaking the tie by a recount on the inheritance distance of each argument starting from the left. In this example, that would mean that the call would be dispatched to put_peg(RoundPeg,Hole), since the left-most parameter of that variant is a "closer" match than the left-most parameter of the put_peg(Peg,SquareHole) variant.

In the author's opinion, this approach is appalling, since it favours one parameter above all others for no better reason than it comes first in the argument list. But there is no reason why pegs should be more significant than holes. Moreover, arbitrarily resolving the dispatch in this way will often mask a fundamental design flaw in the multimethod.

However, experience indicates that sometimes the more specialized variants of a multimethod are only provided as optimizations, and a more general variant (in this case, the (Peg,Hole) variant) would suffice as a default where such an ambiguity exists. It is proposed that an additional parameterized attribute -- :default(ambiguous) -- be provided so that one particular multimethod can be nominated as the dispatch recipient in cases of ambiguity:

        sub put_peg(Peg,Hole) : multi default(ambiguous) {
                print "some kinda peg in some kinda hole\n"
        }

Now, whenever a call to put_peg can't be dispatched because it's ambiguous, this default variant will be called, rather than throwing an exception.

Multiple dispatch can also fail if there are no suitable variants available to handle a particular call. For example:

        my $peg  = JPEG->new();
        my $hole = Loophole->new();

        put_peg($peg, $hole);

which, it is proposed above, would normally produce the exception:

        No viable candidate for call to multimethod put_peg(JPEG,Loophole)

The classes JPEG and Loophole aren't in the Peg and Hole hierarchies, so there's no inheritance path back to a more general (Peg,Hole) variant.

It is proposed that the :default attribute might also take an parameter failure, which would indicate that the attributed variant should be called when dispatch fails to find any suitable variant:

        sub put_peg(@args) : multi default(failure) {
		print "Unknown kinda peg in unknown kinda hole\n";
        }

It is further proposed that a single variant could cover both types of default behaviour, if it were specified with just the (unparameterized) default attribute:

        sub put_peg(@args) : multi default {
		print "Any kinda peg in any kinda hole\n";
        }

Multimethod redispatch

It is further proposed that the semantics of the proposed NEXT pseudoclass (RFC 190) be extended to cover redispatch of multimethods.

Specifically, it is proposed that within a multimethod variant, any call of the form &NEXT::foo; to the same multimethod would cause the dispatch mechanism to resume its dispatch process at the next most viable candidate(s) and thus select the next closest variant.

For example, given the following multimethods:

        package Object;
        package HardObject;     use base 'Object';
        package SoftObject;     use base 'Object';

	package Simulation;

        sub collide(Object $obj1, Object $obj2) {
                print STDLOG "$obj1->{id} collided with $obj2->{id}";
        }

        sub collide(HardObject $obj1, HardObject $obj2) {
                print "crunch!";
                &NEXT::collide;         
        }

        sub collide(SoftObject $obj1, SoftObject $obj2) {
                print "gloop!";
                &NEXT::collide;
        }

In this case, if one of the two more specialized collision variants is called, the more general variant that logs all collisions would also be invoked (and passed the same arguments).

MIGRATION ISSUES

None.

IMPLEMENTATION

See the Class::Multimethods module.

REFERENCES

"Object Oriented Perl", Chapter 13.

RFC 128: Subroutines: Extend subroutine contexts to include name parameters and lazy arguments

RFC 190 : NEXT pseudoclass for method redispatch

This file is part of the Perl 6 Archive