I have a grant from DeepText, a Russian company who have very kindly stepped up to buy 40 hours of my time on Rakudo. We agreed that I would work on Multiple Dispatch. At the moment, there are various Rakudo changes needed before we can actually get all of this in place, some of which Patrick is currently working on and another which needs more discussion between myself and Patrick to work out the exact way forward. I've been holding off work on multiple dispatch waiting for these, but as we're getting really rather close to the time I need to deliver stuff, I really want to start now. I realized (I really should have realized before now, I guess) that there's no reason I can't write PIR tests that will exercise the dispatch algorithm that I will implement, and provide the signature object interface for when we get a final implementation of that into Rakudo. So, I'm now going to follow this approach, and hopefully towards the end of the grant, or during YAPC::EU hacking, we'll push this into Rakudo so everyone can play with it.
I started work on the grant today by gathering all of the bits of the specification together that relate to MMD, and reading through all of them in detail. This post sort of summaries some of the design thinking I've been going through, and after some more of that I'll dig into some implementation. Throughout the whole process, I will work on tests, too. I want an outcome of my work here to be that we have many good tests for multiple dispatch. Of course, I will be writing some to exercise the PMCs from PIR until we get things into Rakudo.
Some general thoughts (I'm writing these because having to write stuff helps me to make sure I understand it, as much as for everyone else to read it, but I hope some folks will find it an interesting read).
1. I will implement the Perl 6 dispatch algorithm by subclassing the Parrot MultiSub PMC, as the Parrot MMD spec recommends. From there, I can override invoke, thus implementing the Perl 6 MMD algorithm.
2. Perl 6 needs to be able to get at the MMD algorithm when not actually invoking in some cases. Therefore, it will not actually be inside invoke, but instead invoke will call some method on the PMC that computes the candidates and hands them back, to make it easy to do this stuff later.
3. We need to actually be able get at the list of all possible candidates to implement some operations, and not just the "winner".
4. Not all parameters may participate in the multiple dispatch, so we need to make sure the ";;" can be "seen" in the dispatch algorithm. so it knows just to consider what comes before the ";;".
5. Before we do any multi-dispatches, and at CHECK time (so we can do this once per compile rather than once per run), we need to perform a topological sort of the candidates. (Note that if the set of possible multis to consider changes at runtime, we will have to re-do the sort. We can still cache it between these events.) I will likely do another post on this sort at some point in the future, but as I see it so far:
For now I'll just point at S12's definition of narrowness, and point out that we only consider class and role types in it - refinement types (those declared with subset) are only used to tie-break later, if we get a tie from the class/role checks.
6. The dispatch algorithm proceeds something like this.
More news as I progress on this grant, and a big thanks to DeepText for the funding!