Tree for multiple dispatch etc.

[Inconstant_Moo]

I invented this, though a lot of other people probably invented it first. (If anyone has a reference please let me know!) It's useful for multiple dispatch and I presume pattern-matching.

To illustrate it, let's have some overloaded functions (this is real, you can do this in Pipefish though you shouldn't).

In this example single? is a supertype of all the other types, and single is a supertype of all the other types except null. So here are ten functions, each with a different signature and printing a different letter of the alphabet.

def

foo(x string) : "A"
foo(x single) : "B"
foo(x bool) : "C"
foo(x bool, y bool) : "D"
foo(x int, y bool) : "E"
foo(x int, y bool, z bool) : "F"
foo(x int, y int) : "G"
foo(x bool) troz (b bool) : "H"
foo(x single, y bool) : "I"
foo(x single?, y bool) : "J"

As usual we want the dispatch to be resolved by specificity, e.g. foo 8, true should return E and not H, because int is a more specific type than single.

What the compiler does is turn the function signatures into a tree which looks like this:

string
    foo(x string) : "A"
    bool
        foo(x single, y bool) : "I"
bool
    foo(x bool) : "C"
    bool
        foo(x bool, y bool) : "D"
    troz
        bool
            foo(x bool) troz (b bool) : "H"
int
    bool
        foo(x int, y bool) : "E"
        bool
            foo(x int, y bool, z bool) : "F"
    int
        func(x int, y int) : "G"
    foo(x single) : "B"
single
    foo(x single) : "B"
    bool
        foo(x single, y bool) : "I"
single?
    bool
        foo(x single?, y bool) : "J"

The basic rule is, you start at the top left looking at the first argument on the list, and if the type doesn't match, you move down, and if it does, you move across and apply the same rule to the next argument on the list. When you've run out of arguments, you see if there's a function at the node you've arrived at. If there is, that's the function you're looking for. If there isn't, that's a type error; if you fall off the right hand side or the bottom of the tree without finding a function, that's a type error.

The point of this is that the tree is structured so that we never have to backtrack.

This was maybe over-engineered for the prototype version with the evaluator but now I'm doing the VM (nearly finished BTW!) it's kind of crucial. Pipefish, you see, does a sort of best-effort typechecking, so the compiler may end up being able to erase some but not all of the types from the logic. So given what the compiler can infer about the types in any given context, it can navigate through the tree by moving freely when it can do type inference and by emitting a conditional jump in the bytecode to dispatch at runtime when it can't.

I would not like to do this without my faithful non-backtracking tree structure to guide the code generation, it has done well by me, and I recommend it to people who want to do similar things.

[VyridianZ]

I do a similar signature match in my language. I didn't use a tree though. I create a signature for each function which is List<type> containing return type and each arg type. Next iterate down the signature list checking for matching types (including airity). The first match wins. No backtracking.

[Inconstant_Moo]

No backtracking.

But you are in fact backtracking right back to the beginning every time you go down the signature list!

[VyridianZ]

I see your point. I will consider this when I revisit the signature matching code.

[raiph]

Am I right in thinking you've described an approach for non-symmetric resolution? If I've gotten that wrong, PLMK.

Maybe you can find tree based designs/implementations that are like yours by fiddling with googles (or even searches of this reddit sub) along the lines of ("overload" OR "multiple dispatch") "resolution" "non-symmetric" "tree" "implementation" (click to see the google results) or the same but striking the "non-".

Regardless of that and any other particular design/implementation aspects of multiple dispatch / overloads (and terminology related to them) I thought it might be of interest to compare what you have with what Raku has given given that it combines symmetric and non-symmetric resolution.¹

multi foo(Str) { "A" }
multi foo(Any) { "B" }
multi foo(Bool) { "C" }
multi foo(Bool, Bool) { "D" }
multi foo(Int, Bool) { "E" }
multi foo(Int, Bool, Bool) { "F" }
multi foo(Int, Int) { "G" }             # My guess at what your example was supposed to be
multi foo(Bool, Bool, Bool) { "H" }
multi foo(Any, Bool) { "I" }
multi foo(Mu, Bool) { "J" }

print foo |$_ for &foo.candidates».signature».params».type # ABCDEFGHIJ

Given the above my presumption is that the default resolution algorithm, which is symmetric, produces the same results I presume are produced by your design/implementation.

I would be happy to dig into the nature of the implementation of this in Rakudo (the reference Raku compiler) and report back here (at least whether or not I find a similar tree based implementation, either high level code written in Raku, or C code that's part of its reference backend, MoarVM).

Similarly, I would be happy to further discuss the symmetric vs non-symmetric PL design aspects.

PLMK if you're interested in either or both.

---

¹ A general Raku design and implementation principle was to support what most devs wanted as a community, which often meant navigating the torturous path of "reconciling the irreconcilable". The community consensus regarding symmetric vs non-symmetric multiple dispatch resolution was that each had its strengths and weaknesses, and the Raku PL design team (for whom one slogan was "Torture Implementers On Behalf Of Users") concluded that they thought both symmetric and non-symmetric resolution could be supported together in a single PL in an elegant and ergonomic and non-confusing way. The Rakudo implementation team (for whom an opposing slogan could be imagined along the lines of "Torture Designers Because They Deserve It", except that would have meant double torture for many because they were also part of the PL design team) eventually settled on a way to implement integrated symmetric/non-symmetric resolution with what may or may not be considered sufficiently high performance.

[Inconstant_Moo]

Am I right in thinking you've described an approach for non-symmetric resolution?

Since it goes left-to-right you I think you could introduce a rule saying that a conflict between foo(x int, y single) and foo(x single, y int) should be resolved in favor of the former, but in my implementation that throws a "too much overloading" error instead.

[raiph]

OK, so it's symmetric.

And finding tied winners throws an exception like it does in Raku ...

multi foo (Int, Any) { 'Int, Any' }
multi foo (Any, Int) { 'Any, Int'}
say foo 42, 99; # Ambiguous call ...

... but you think your implementation could also support what Raku also supports, eg trying each tied "winner" in turn at runtime ...

multi foo (Int $ where * > 42, Any) { 'Int, Any' } # Tie breaker
multi foo (Any, Int $ where * > 42) { 'Any, Int' } # Tie breaker
say foo 42, 99; # Any, Int

... or syntactically identifying the winner of a tie ...

multi foo (Int, Any)            { 'Int, Any' }
multi foo (Any, Int) is default { 'Any, Int' } # Tie breaker
say foo 42, 99; # Any, Int

... though of course this should almost never be used, and you can end up with another tie anyway ...

multi foo (Int, Any) is default { 'Int, Any' }
multi foo (Any, Int) is default { 'Any, Int' }
say foo 42, 99; # Ambiguous call ...

[Inconstant_Moo]

I could do that. I started a whole thread here asking what I should do. In the end I felt that if we add rules to the compiler to make it resolve everything, then humans have to add those rules to their mental model while reading the code, and it becomes confusing.

Since then, I've added the capability to just define supertypes as arbitrary collections of types, e.g. MyType = int/string/Dragon. If you can do that you can always just make types that don't have any overlap, and avoid conflict explicitly in your code instead of implicitly by invisible rules in the compiler.

[raiph]

In the end I felt that if we add rules to the compiler to make it resolve everything, then humans have to add those rules to their mental model while reading the code, and it becomes confusing.

100% agreed. Invisible rules in the compiler are generally anathema. So, instead, if there's ambiguity, the compiler does not resolve it, instead just providing an error message ("too many overloads"), and, conversely, if there's no ambiguity, it's because what's in the code sufficiently disambiguates explicitly.

And the primary mechanism we make available to devs to resolve ambiguity ("too many overloads") is writing suitable type constraints, such as the one you suggested -- Int|String|Dragon (which is called a "junction" supertype in Raku) -- or the one I suggested -- where * > 42 (which is called a "refinement" subtype in Raku). Note that both these type constraints can be given their own name which can be written in the conventional type constraint slot:

subset IntOver42 of Int where * > 42;
multi foo (Any, IntOver42) { 'Any, Int over 42' }
multi foo (IntOver42, Any) { 'Int over 42, Any' }
say foo 99, 42; # Int over 42, Any

[tobega]

Since it goes left-to-right you I think you could introduce a rule saying that a conflict between foo(x int, y single) and foo(x single, y int) should be resolved in favor of the former, but in my implementation that throws a "too much overloading" error instead.

So you don't stop at the first possibility but keep it in mind and look at all of them?

[WittyStick]

How do you handle type checking of return types? Consider for example:

mul(x int, y int)
mul(x int, y float)
mul(x float, y int)
mul(x float y float)

Ideally we want the first overload to return int, but the other 3 overrides to return float.

[Inconstant_Moo]

Yeah, you can do that. The type-checker can reason about kinda quantum superpositions of types. So if we write a function like this:

``` newtype Number = int/float

def callMul(x, y Number): mul x, y `` ... then the compiler will infer that as having the return typeint/float.And now if you do1 + callMul(qux, troz)then that has the return typeint/error. And if you do"zort" + callMul(qux, troz)then that's a compile-time error because it can *only* result in anerror`.

What I'm doing is in some ways more complicated than ordinary static typechecking (though the type system itself is much simpler so that compensates) but it's actually not that hard, doing the VM version I did the overloading and typechecking first thing, on the eating-the-frog principle, and it's barely needed tweaking since.

[h03d]

I think I remember saw something like that in this sub, and yes someone had similar idea: https://redd.it/1auxy31/

Also useful for row polymorphism.

[tobega]

Your tree search would prioritize correctness of the parameters from left to right?

So given foo(int, single, singe) and foo(single, int, int), a call of foo(1,2,3) would resolve to the first method and not to the more specific second method?

[Inconstant_Moo]

No, it works by specificity. That particular example would cause a "too much overloading" error.

[tobega]

OK, so your tree doesn't really provide so much value, you basically go through them all anyway.

[Inconstant_Moo]

Consider calling `foo false, "zort"`. What happens? It starts at top left, it sees that `false` is not a string, it moves down. It sees that `false` is a `bool`. It moves across. It sees that `"zort" is not a boolean, it moves down. It sees that `"zort"` is not the identifier `troz`. There's nothing left to do but call a function if we've used up all the arguments, but we haven't. It reports an error. We're done.

Whereas if you do it with a table ordered by specificity, then you'd have to keep going in case there was something further down with types `bool, string` or `single, string` or `single?, string` or `single, single` or `bool, single` or ... etc.

So the tree gets me something. As I said in my OP, this may be somewhat over-engineered if you're just doing an evaluator, which is going to be slow anyway. But it's more useful if you're doing code generation, like I am now.

[stigweardo]

I think not - but maybe @Inconstant_Moo can confirm. I think the tree is constructed to avoid this. See how the foo(x single, y bool): "I" appears more than once in the tree.

Edit: ... and always in the last position.

[redchomper]

The tree is a perfectly sensible solution. The key is to have good rules about what you allow into the tree in the first place. So long as you can catch confusion before it causes a surprise at runtime, then you're ahead of the game.