= Name
MMD revisted - a proposal for a new set of multimethod dispatch semantics for
Perl 6 and Parrot.
= Features
It is our belief that SMD (that is, traditional single method dispatch like we
have in Perl 5) in Perl 6 is entirely unnecessary, and can be implemented with
MMD, to result in a less confusing dispatch system, consistent semantics, and
easier extendability.
* All methods are MMD
** It might be a good idea to warn if two methods are in the same declaration block (i.e., not under different `is extended` decls), but don't have the now weak `multi` keyword in front of them.
* Every MMD method belongs to all the classes of it's invocants
* All MMDs can be dispatched with the following syntaxes:
** `multimethod($invocant)` - iff the $invocant's class is known at compile time
*** If all methods are also put in a global namespace `method($invocant)` is ok, even without compile time knowlege
** `multimethod($invocant, $invocant)` - ditto, for at least one inv
** `multimethod $invocant, $invocant: $arg`
** `$invocant.multimethod`
** An additional syntax might be a good idea.
== Symmetrical Invocants
Lets pretend we have `link`:
method link(Foo $foo, Bar $bar) { ... }
A method which is symmetrical between all it's invocants, i.e., does not care
what order they come in should have a way to say so.
method link(Bar $bar, Foo $foo) { link($foo, $bar) }; # silly
A nice syntax is needed to say that "the following params are unordered".
= Dispatch
== Method Lookup
* All dispatching is based on a short name lookup in all the classes of all the invocants,
** Method signatures are collected, and then sorted
* Signatures know to explode themselves, into applicable classes/roles
** This is how the initial set is found
* Each signature is a pattern
** It matches on the params
** Non matching patterns are expunged from the list
== Pattern Matching
Methods are all pattern matched, up to where { } clauses. These are delayed
till we have to decide on a single candidate, and evaluated one at a time, on
our sorted candidate list. This makes sure we don't waste too much time on
where { } evaluation, and that their order is sensible.
== Signature Ordering
We need a consistent set of rules to order method signatures.
=== Requirements
* Mostly sane
** doesn't need to always DWIM, consistency is more important
* Simple
** easy to remember
** easy to predict
* Mostly stable
** A simple change should not affect many things
The comparison of signatures is between their individual params.
==== Shape
It is assumed that by this stage only signatures with a similar shape have been
retained.
We now know where each arg will go in each method, if it ends up going there.
We base our comparison on this, comparing each arg's candidate parameter
against the others for that arg and making a decision.
==== Origin
Each method has an origin - the place where it was looked up from. This is any
namespace it exists in. Imported methods' "origin" is
If the origin classes or roles of the method are all the exact class (not
super) of all the invocants, or from roles directly mixed in to the exact
class, this method is preferred.
This is to retain SMD like matching, and to allow users to override the rules
by declaring a method in a specific place. To do this, one must do something like
class Foo { method multifoobar (Foo $foo, Bar $bar:) { } }
class Bar { &multifoobar := Foo::multifoobar }
A syntax to make this operation easy is in order:
class Foo {
method multifoobar :class(Bar|Gorch) { ... }; # ::?CLASS, that is Foo is in there by default
}
Or
class Bar { method multifoobar from Foo; };
==== Lexical Scope
The lexical scope of method definition is searched outwards. All lexical
definitions supercede namespace ones.
==== Slurpy vs. Non-slurpy
The more non-slurpy params before a slurpy a method has, the more "specific" it
is.
That is, if an arg will end up in a slurpy in one sub, and in a non-slurpy in
the other, the non-slurpy wins.
==== Type Prioritization
Scalars or Container values which are strongly typed are compared.
At dispatch time the arguments's type is known. In this way we can determine
which parameter is more "specific".
The argument's type is already known to match both signatures, so we can now
order, by exploding the junctive type of the param:
* If a param does not match the arg's class directly but another candidate does
** Class::Subclass vs. Class when arg is Class::Subclass
* If a param does not match one of the arg's roles directly, but another doesA
** Class vs. Class & Role
** The param with the most direct roles wins
* If a param matches a superclass of another param, it is eliminated
** Class::Subclass vs. Class when arg is Class::Subcass::Subclass
A complete sort between these is made.
For efficiency reasons, the list of candidates could be lazily heap sorted.
This will allow us to not bother sorting bad candidates amongst themselves.
==== Optional Params
If a method has optionals and another doesn't, the strict one is preferred.
If a method has empty optionals, and another has filled optionals, the one with
data is prefered.
If two methods have empty optionals, the arity of all the optionals together is
compared numerically.
==== Where Clauses
Any param with a where clause is preferred to a similar param without one.
==== Rule Ordering
The above rules are not yet ordered. We will define this later in more detail.
=== Tie Breaking
* Methods defined early in a file precede functions later in a file
* Methods from files loaded late precede methods from files loaded early.
=== The Dispatch
When our method candidates are sorted, the where clauses if at all are tried in
order, till we find a candidate that passes. We're done.
If we do not find such a method, we raise a fatal error, that the method was not found.
=== First Class Code Signatures
Given a good API into first class signatures, it should be easy to write the
dispatcher in Perl 6, and also implement other dispatch schemes for alternative
meta models.
class Perl6::Class {
method dispatch ($short_name, @invocants, @args) {
( # find the method
@invocants».can($short_name) ==> uniq ==> # get all method candidates
map { $_.meta.signature.bind(@invocants, @args) } ==> # try to bind them
sort { } ==> # compare the binding according to the rules
first { all($_.where_clauses».eval) } # try the where clauses
).invoke(@invocants, @args); # invoke our chosen meth
}
}
== An Example
http://svn.openfoundry.org/pugs/modules/Class-Events/lib/Class/Events.pm
This module uses very elegant aspects of MMD.
It introduces a generic event dispatching system, between listener and
publisher objects.
On top it new event types can be implemented. In the code a named event type is
implemented:
$publisher_obj.add_subscriber("event_name", $subscriber_obj);
# ...
$?SELF.notify("event_name");
The beauty of MMD is that it lets `get_subscriptions`, `notify`,
`add_subscriber` and `remove_subscriber` to be written concisely and clearl for
the generic and the specific version, allowing the use of hash lookup for named
events, and a generic container and matcher for other events, with no clash.
Look into the two definitions of get_subscriptions and the way the optimized
version is automatically used even from a tricky context.
Also look into the way that several versions of `notify` give a polymorphic,
intuitive interface to choose the simplest version for the user.
Also notice the way this extra functionality is appended, without the original
Class::Events framework being aware of such changes.
= The Ruby Way
Ruby defines an implicit kernel singleton. Since in Perl 6 everything is really
an object, but we can ignore that, perhaps it's suitable to copy this paradgim.
With regular subroutine dispatch implemented as MMD on a hidden thing, we can
really say this is MMD on nothing. It doesn't set $?SELF, or any of that.
Not much should change, except there will be only one way to match params, and
that way will be useful.
== Everything Is An Invocant
In the authors' opinion for consistency it is crucial that everything is an
invocant.
The main maintenance advantage of MMD is it's ability to make control flow
appendable by making invocation level switch statements a declarative pattern
matching language.
class Dog {
method bark {
.bark("woof!");
}
method bark (String $sound) {
say $sound
};
}
This should be a valid use for MMD in Perl 6. It is much like functional
pattern matching, only without the constructor reversal logic. This is due to
the fact that in Perl 6 constructors are actions, not declarations.
Instead of unpacking we have the possibility of where clauses, that can take
apart our possibly bound parameters, and do the logic themselves.
Ofcourse, we do have a subset of this logic for the primitive containers, in
the form of hash and array unpacking, but that isn't quite the same thing.
= MMD, JIT, Psyco, Zero Dispatch, between Perl 6 and Parrot
This is the grand unified scheme for dispatching at the machine level as
offerred here should give us a very optimized form of MMD execution.
It fits well into the scheme like this:
* JIT is used to delay the dispatch and it's compilation
** Since Perl is dynamic this allows us to have as much knowlege as possible
** If the dispatchee, that is the invocant, is strongly typed in the calling context, the method that applied to it is jumped to directly on subsequent calls
* Psyco like ideas are incorperated to the scheme to generate highly optimized code for specific instances. An MMD on numerical looking types could be several bits of generated code, each one JIT'd into the best possible assembly for the platform, to deal with ints, floats, etc.
* Closed classes allow us to omit cache validation checks before using cached dispatches
== The pipeline
After the compiler does the minimum it can to validate the AST in it's
serialized form - the source code, interpretation begins.
This is done by pulling instructions. The pipeline is basically
* AST to byte code compiler (this step might not be necessary by now)
* MMD exploder (it's crucial that this is JIT, due to the size cost)
* Byte code optimizer
* Arch Specific byte code optimizer
* JIT opcode translator
The latter two are obviously highly coupled, and pretty generic.
Any code that has gotten to this stage is imply executed as machine language.
== MMD explosions
When an MMD method is about to be dispatched, it's args are already known. At
this stage, the method is duplicated, with a staticly typed signature matching
the arguments.
This version of the method is subject to type inferrence in a language where
this might pay off.
This code is then passed to the byte code optimizer, which may do away with
certain constructs that are not necessary due to the local lack of
polymorphism, and so on, down to machine level.
If a version is already in the dispatch table, and matches exactly, it is used.
Furthermore, if the calling code has enough type information to know which MMD
to use in advance, this version can be jumped to directly.
When the original MMD has been exploded entirely, meaning that no argument
combination needs to be compiled anymore, the original version can be masked,
and various assumptions can be made.
Furthermore, methods called from an exploded method should be jumped to
directly, since complete type safety is assured.
== Control Over Optimization
The following parameters should be entirely under the control of the user
*running* the code.
Since the cost/gain ratios of die-hard optimizations are hard to predict, it
may be completely undesirable to optimize this way, and it may be desirable to
optimize only certain bits of code this way.
=== Forefitting compilation
Since compilation is expensive, a good time to start JITTing this way is after
runtime-in-compilation has finished, plus 1-2 CPU seconds.
Statistically, startup configurations should have finished by then, and in a
long running application most subsequent code will be reused.
Furthermore,
=== LRU expunging
Little used MMDs take up space. For a complex method a set of "popular"
invocation styles may be determined by using pragmas, runtime statistics, data
from previous runs, and so forth.
=== Cost Thresholds
A cost threshold could be determined, wheras partial optimization happens, on
the generic version first, then on the byte code of the exploded version, and
so forth, perhaps given a minimum *commulitive* cost of the function.
If overall a function is taking a significant amount of time (not a call to a
function, obviously), it is a good candidate for optimization.
=== Factors for Default Option Selection
* Context
** mod_parrot or equiv
** command line
* Code size
** Huge code probably does a lot
* Runtime
** Maybe after a while it pays to change our stragegy
* Pragmas and options
** In the host language's format
*** use less 'ram' might cause optimized versions to be thrown away if not used enough
** In the environment variables
* History
** Based on % of time spent optimizing in the last N CPU seconds
*** If we have something to do
*** We optimize more aggressively
*** Or decrease aggressiveness
**** We can always optimize more later
=== Example
sub factorial (0) { 1 }
sub factorial ($n) {
$n * factorial($n + 1);
}
# built ins, presumably hand coded
method infix:<*> (Int, Int);
method infix:<*> (Num, Num); # abstract
method infix:<-> (Int, Int);
method infix:<*> (Num, Num);
my $object = Foo.new; # does Num
factorial($object);
factorial(10);
Lets look at the dispatches.
==== `factorial($object)`
MMD is invoked on `$object` with short name `factorial`. Our permissive version
is found.
We explode it into
sub factorial (Foo $n) {
$n * factorial($n - 1);
}
We now expand the two sides `&infix:<*>`. To do this, we need to invoke another
factorial, whose argument is the result of `$n + 1`.
We now invoke MMD on `&infix:<->`, and find that it's implemented in the role
Num, as a forceful numification (assume it's built into class Foo), which maps
to a builtin subtraction operation.
That's our best match.
Pretend our addition yielded 2. Now we feed this 2, an Int, into factorial.
This does a new MMD invocation, and this time
method sub factorial (Int $n) {
$n * factorial($n - 1);
}
Is exploded.
Note that there are no branches, and since `&infix:<-> (Int $x, Int $y) returns
Int` it is a recursive function.
Our current version of factorial on Ints is already very efficient, since it
can be jitted down to very simple math operations on machine registers with
native integers, as all the math ops have been hard coded to call their Int
manifestations. We'll see how that's done in a second. The biggest overhead is
the subsequent MMD on `factorial(1)`.
We already know how to do this, but now we reach `factorial(0)`. Since we have
a match, we explode it into
method factorial (Int 0) { 1 }
Now we have deriviatives of all the generic `factorial` multimethods for Int
types. We can therefor generate a simplified conditional instead of the call to
MMD factorial($n):
method factorial ($n) {
$n * given (n - 1) {
when 0 { factorial_Int_0($n) } # may even be inlined to 1
default { factorial_Int_n($n) }
}
}
With brutal enough optimization we may notice that all our operations are 100% primitive:
* factorial_Int_0 is constant
* infix:<*> and infix:<+> are internal
* factorial_Int_n is the only weird thing
** but it's ourselves, so it's also pure
In this case the behavior is entirely predictable, and no branches, except for
the one we generated, or side effects will happen.
Since we don't need to preserve generic behavior, we can even optimize the
call, to be something like (in very old, somehwat improvised x86 assembler):
mov AX, [ ... add of param ... ]
mov CX, 0
X001: push AX
dec AX ; this is kind of silly, but it looks like a call
inc CX ; i doubt an optimizer is smart enough to make it better
cmp AX, 0 ; this is our branch
jne X001
X002: pop BX
mul AX, BX ; i forget it's behavior
; also catch integer overflow, and redispatch here
; integer overflow catching is in fact a part of every
; builtin MMD on Ints. If these were int32s, otoh ;-)
jump_if_integer_overflow OVERFLOW_HANDLER ; yadda yadda
dec CX ; again with the call emulation stupidity
jnz X002
mov [ ... return addr ... ], AX
In other words, extra book keeping can be optimized away, since we know that
*this* variation of `factorial` is completely safe.
Perhaps smart enough branch identification the decrements and increments could
be trapped, and reorganized. Maybe a rule book can be matched on it for some
really extreme behavior. We should look to the Psyco peoples' work for
guidance.
== Currying Multi Methods
With the dispatch model illustrated above currying no longer requires explicit
typing, to disambiguate. This is as opposed to the demonstration in S06.
== Chat between nothingmuch and autrijus for reference
[16:39] nothingmuch: for the type being passed into it at the moment
[16:39] nothingmuch: ofcourse, now the parts of the optimization pipeline can assume things about this invocation
[16:40] nothingmuch: so a factorial (n) { factorial(n-1) * n };
[16:40] nothingmuch: factorial (0) { 1 };
[16:40] nothingmuch: this MMD can be optimizes with the knowlege that n is now an int
[16:40] nothingmuch: when we try to dispatch factorial(10);
[16:41] nothingmuch: if it looks like it's going to pay off, our generic unroller will notice that 10 is an int and factorial, * and - are all applied on ints
[16:41] autrijus: er, hi.
[16:41] nothingmuch: at this level a tail optimization can be figured out
[16:41] nothingmuch: not too expensively
[16:41] nothingmuch: since it's all opcodes with a safe type
[16:41] nothingmuch: then our arch unroller will know what kind of unrolling is cheap on this platform
[16:42] nothingmuch: depending on whether we optimize for size or speed or whatever
[16:42] nothingmuch: and then our JIT opcode table will take that code and produce machine code
[16:42] nothingmuch: and overall the steps to get into something that is a very tight, register based assembler loop is not very complicated
[16:42] nothingmuch: and although hard to match, it only needs to happen once
[16:42] nothingmuch: and when it happens the search space is usually constrained anyway
[16:43] nothingmuch: what do you think?
[16:43] nothingmuch: as a side note, MMD is very very very cool to append definitions
[16:43] nothingmuch: see Class::Events
[16:43] nothingmuch: and how get_subscriptions is optimized for a special case
[16:43] nothingmuch: without introducing cruft
[16:43] nothingmuch: if only it was the default
[16:44] nothingmuch: anyway, please comment, i need another brain for this
[16:44] nothingmuch: if it makes sense, I'd like to write up a One True MMD way for perl 6, encapsulating this mess
[16:44] nothingmuch: and encapsulating Class::Event's style
[16:44] nothingmuch: but retaining compatibility with what we have already
[16:47] autrijus: I confess I know nothing about Parrot JIT, or JIT in general.
[16:47] autrijus: I'm still trying to digest this
[16:47] nothingmuch: JIT is really just a pipeline:
[16:47] nothingmuch: take generic opcodes
[16:47] nothingmuch: which are written in say, C
[16:47] autrijus: are you saying that
[16:47] nothingmuch: and if you know how for your platform
[16:47] autrijus: MMD is to be resolved at runtime
[16:47] nothingmuch: convert them to real machine optcodes
[16:47] autrijus: but as part of the JIT pipeline
[16:47] nothingmuch: no, not at all =)
[16:47] nothingmuch: well, yes
[16:47] nothingmuch: but actually no
[16:48] nothingmuch: the dispatch itself is eliminated as much as possible
[16:48] nothingmuch: by precalculating (the compiler's job) what can be ommitted
[16:48] autrijus: ...
[16:48] nothingmuch: if you have a known type
[16:48] nothingmuch: function(5);
[16:48] nothingmuch: you know that's an int
[16:48] nothingmuch: you never need to dispatch it as a non int
[16:48] nothingmuch: but the generic version is kept, since this is only usage
[16:49] nothingmuch: the JIT compiled version will be jumped to directly
[16:49] nothingmuch: however, function (int x) { } does not need any generic version at all
[16:49] nothingmuch: since the compiler must catch improper use
[16:49] nothingmuch: if it cannot catch improper use, then it will generate a fallback MMD
[16:49] nothingmuch: which will really be a guard
[16:49] nothingmuch: this way true MMD can be avoided
[16:49] nothingmuch: by JITting it
[16:50] autrijus: I think I understand.
[16:50] nothingmuch: since JIT is in effect, we can know as much as possible too
[16:50] autrijus: this is all at VM level right?
[16:50] nothingmuch: yes
[16:50] nothingmuch: this entire process is on the compiled byte code
[16:50] autrijus: can you look at how parrot's mmd already works?
[16:50] nothingmuch: the compiler simply has to provides the things to MMD on
[16:50] autrijus: and augment/compare its design
[16:50] nothingmuch: i will read up on it
[16:50] nothingmuch: yes, i'll try
[16:50] autrijus: that way I can bring your proposal to Leo
[16:51] nothingmuch: but first, i have to bike while there is light
[16:51] autrijus: because that's ultimately what needs to happen for pugs/parrot to run
[16:51] autrijus: okay. take care!
[16:51] nothingmuch: true
[16:51] nothingmuch: anyway, we'll see later
[16:51] nothingmuch: i just wanted another person churning the idea
[16:51] autrijus: thanks for sharing this with me :)
[16:51] nothingmuch: and not saying "no stupid"
[16:51] autrijus: I'll try to read up too
[16:51] nothingmuch: i
[16:51] nothingmuch: i'll spam stevan too
[16:51] nothingmuch: and part of my grand master plan is to bring this up with my MMD proposal
[16:52] nothingmuch: to prove that I thought about it, and that I"m not just bullcrapping the "it could be optimized" argument
[16:52] nothingmuch: anywho, please do read Class::Events
[16:52] nothingmuch: i think it's some of the most beautiful code i've ever written
[16:52] autrijus: ok. what do you need for me to make it ext/ ?
[16:52] nothingmuch: it's concise, efficient, and extensible
[16:52] nothingmuch: i need delegation
[16:52] autrijus: just "handles" ?
[16:52] autrijus: that's all?
[16:52] nothingmuch: and I need 'role foo is extended { }'
[16:52] nothingmuch: and true MMD
[16:53] autrijus: what does "is extended" mean?
[16:53] nothingmuch: for example, see the way that 'method notify' is appended to Class::Events::Publisher
[16:53] nothingmuch: bassically it means 'glue this def to the end of the class'
[16:53] nothingmuch: in perl 5 it's not necessary
[16:53] autrijus: and how is pugs mmd currently failing?
[16:53] nothingmuch: you could no-op it for now
[16:53] nothingmuch: i don't know, I haven't used pugs mmd yet
[16:53] nothingmuch: anyway, the nice examples in Class::Events are two fold: the way that get_notification optimizes for named events
[16:54] autrijus: pugsmmd should just work
[16:54] autrijus: "is extended" is noop
[16:54] autrijus: (for now)
[16:54] autrijus: so you just need delegation. good
[16:54] nothingmuch: and the way named events get a pretty syntax, which will make it all efficient too
[16:54] nothingmuch: huraah!
[16:54] nothingmuch: and this delegation is a simple form, btw
[16:54] nothingmuch: anyway, i'm off,it's already 17:00
[16:54] autrijus: I'm a bit uncomfortable seeing it in modules/ :)
[16:54] nothingmuch: but I shall return energized and motivatred
[16:54] autrijus: please write some t/
[16:54] nothingmuch: i will do that soon
[16:54] autrijus: and I'll see about delegation
[16:54] nothingmuch: ti's not even valid perl yet
[16:54] autrijus: nod. cool, take care, see you in a bit
[16:55] nothingmuch: it's just been a very busy weekend, and I didn't want to keep that to myself alone