Implement 'multi'-method dispatch as a module

[masak]

With the case statements of #34, we could implement multi subs/methods/macros in a cool way: by processing all multi declarations after parsing (using watcher/walker macros, presumably), and building a synthetic routine to stand in for all the multi variants.

To make this concrete, here's a Perl 6 implementation of rock-paper-scissors:

enum Hand <Rock Paper Scissors>;

multi infix:<beats>(Paper, Rock) { True }
multi infix:<beats>(Rock, Scissors) { True }
multi infix:<beats>(Scissors, Paper) { True }
multi infix:<beats>($, $) { False }

my $p1 = Hand.roll;
say "Player 1 chooses {$p1}";

my $p2 = Hand.roll;
say "Player 2 chooses {$p2}";

say do {
    when $p1 beats $p2 { "Player 1 wins!" }
    when $p2 beats $p1 { "Player 2 wins!" }
    default { "It's a tie!" }
};

Here would be the corresponding 007 implementation:

enum Hand { Rock | Paper | Scissors }

multi sub infix:<beats>(L: Paper, R: Rock) { return True }
multi sub infix:<beats>(L: Rock, R: Scissors) { return True }
multi sub infix:<beats>(L: Scissors, R: Paper) { return True }
multi sub infix:<beats>(L, R) { return False }

my p1 = Hand.roll();  # assumes EnumType.roll()
say("Player 1 chooses " ~ p1);

my p2 = Hand.roll();
say("Player 2 chooses " ~ p2);

if p1 beats p2 {
    say("Player 1 wins!");
}
else if p2 beats p1 {
    say("Player 2 wins!");
}
else {
    say("It's a tie!");
}

And here would be what the macro transformation makes of it afterward:

enum Hand { Rock | Paper | Scissors }

sub ⟦sym0⟧(L: Paper, R: Rock) { return True }
sub ⟦sym1⟧(L: Rock, R: Scissors) { return True }
sub ⟦sym2⟧(L: Scissors, R: Paper) { return True }
sub ⟦sym3⟧(L, R) { return False }

sub infix:<beats>(L: Hand, R: Hand) {
    return case (L, R) {
        | (Paper, Rock): ⟦sym0⟧(L, R)
        | (Rock, Scissors): ⟦sym1⟧(L, R)
        | (Scissors, Paper): ⟦sym2⟧(L, R)
        | otherwise: ⟦sym3⟧(L, R)
    }
}

my p1 = Hand.roll();  # assumes EnumType.roll()
say("Player 1 chooses " ~ p1);

my p2 = Hand.roll();
say("Player 2 chooses " ~ p2);

if p1 beats p2 {
    say("Player 1 wins!");
}
else if p2 beats p1 {
    say("Player 2 wins!");
}
else {
    say("It's a tie!");
}

In other words, the macro would turn the multis into a case statement.

A couple of quick notes:

• Consider symbols conjectural. We don't have them yet and I don't know if we will get them. The mechanism (make up an un-nameable name) is the important part.
• There's an implicit process of "unification" which is used to reduce all the multi signatures into a single signature of the dispatcher. It contains lot of interesting logic, and it's similar in spirit to the type matching of case. Crucially, it will need to keep track of (combinations of) parameters that aren't covered by a multi.
• Ordering is important. Also, the unification algorithm will need to yell in the case of statically-detectable ties.

Overall, I feel this one is a very high goal to achieve for 007, but having it would be so cool. It would put the usefulness of macros in 007 beyond any shred of a doubt. Also, this particular one brings together the "generate, analyze, and typecheck code" slogan into a single use case.

[vendethiel]

How do you know when the user is done defining the multi?

[vendethiel]

Also, can you use a multi sub in the middle of the cases?

[masak]

How do you know when the user is done defining the multi?

I think this macro will end up wanting to process the entire compunit once it's finished parsing. (Known in Perl 6 as "CHECK time".)

Well, there are some things we can do as we parse along (for example, install the subs behind the multi variants, and collect their symbols and their signatures), but the final generation will have to happen at CHECK time. It's not the first issue that hints at us wanting to be able to install macros during that phase.

Also, can you use a multi sub in the middle of the cases?

I don't think I understand the question, but let me try anyway: the case expression is code-generated by the macro. All it does is basically delegate to one of the installed subs. Which means that the case structure remains simple; all it ever contains is a bunch of function calls.

[masak]

I like this issue even more when I realize that it's sort of the coming-together of #33, #34, and #112. I'm going to think of those three issues, and this one, as the "happy family" from now on. If we can get these four to actually work, then 007 will have succeeded, forever.

[vendethiel]

Let me rephrase my poor sentence.

multi f(Int, Int) {}
f(x, y);
multi f(Str, Str) {}

• Does it "just work" by virtue of multi installing a stub?
• does the name not exist before all cases are declared? (Probably doesn't make sense)
• do you see all the variants correctly, not only those declared before the call?
• what about the same piece of code, but f() called at other times? (And by other times, I mean things like... Macros!)

[vendethiel]

The biggest thing coming to mind: "how far is 007 from being usable to define a CLOS-like" (Common Lisp's Object System, first defined as a set of macros)

[masak]

multi f(Int, Int) {}
f(x, y);
multi f(Str, Str) {}

Doesn't seem like a problem to me. Here's the order things happen:

• Parsing
  • First multi parses. A sub ⟦sym0⟧ gets emitted.
  • The call to f parses. Since f is not declared, this postponed check gets queued up for later checking of f.
  • Second multi parses. A sub ⟦sym1⟧ gets emitted.
• CHECK time
  • The multi macro (handwave) emits the dispatcher sub f into the top scope where the multi variants were declared.
  • The postponed check triggers. f is now declared, and it's a Val::Sub, so everyone survives.
• Runtime
  • f gets called.

[masak]

The biggest thing coming to mind: "how far is 007 from being usable to define a CLOS-like" (Common Lisp's Object System, first defined as a set of macros)

I wish I knew enough about CLOS to answer that. :smile:

What I can say is that I am putting some thought into the MOP. It doesn't need to be spectacular or very flexible for 007 to do what it should, but I would like to get it mostly right.

[masak]

Another option would be to inline the multi variants directly into the dispatch routine. That would probably look better on the call stack as well.

Just have to make sure to insert explicit returns. And possibly do alpha renaming.

[vendethiel]

The first metaobject protocol was in the Smalltalk object-oriented programming language developed at Xerox PARC. The Common Lisp Object System (CLOS) came later and was influenced by the Smalltalk protocol.

There's some prior art we could look at...

[masak]

I just found this implementation of multi-method dispatch in Python. It looks terribly sane. I'd like to reduce the scope of this issue a little bit and have us implement it like that first, as a module, and then maybe later expand things to be handled/defined using macros.

[vendethiel]

Interesting macro impl (sweet.js) that does both this and destructuring: https://github.com/natefaubion/sparkler/blob/master/README.md

[masak]

Wow. I really need to have a closer look at sweet.js.

[masak]

Nothing is set in stone yet, but if #490 goes through, we can immediately close this issue.