The logic is built to essentially check if there is an equality between the two signatures, and break the equality iff only one of the two has varargs.

This ensures that your example is not broken, aka

In [6]: from plum import Signature

In [7]:  Signature(int) == Signature(int, varargs=int)
False

@PhilipVinc This is super interesting! I've taken some time to think about your approach, to try to really understand what is going on.

Define varargs as the corresponding infinite set of signatures:

(float, *int) = {(float), (float, int), (float, int, int), ...}

To fix #117, we wish to define an order such that (float, *int) < (float, Number).

For two signatures S and T, let S <= T if (1) S and T contain an equal number of types and (2) the types in S are subtypes of the correspond types in T.

Since (float, *int) is defined as a set of signature, we wish to extend <= to collections of signatures such that (float, *int) < (float, Number) holds. We do this in two steps.

For a collection of signatures {S1, S2, ...} and a single signature T, let {S1, S2, ...} <= T if one of the following is true: S1 <= T, S2 <= T, et cetera. This models the desired condition.

For two collections of signatures {S1, S2, ...} and {T1, T2, ...}, let {S1, S2, ...} <= {T1, T2, ...} if all of the following are true: {S1, S2, ...} <= T1, {S1, S2, ...} <= T2, et cetera.

In words, {S1, S2, ...} <= {T1, T2, ...} if, for every Ti, Sj <= Ti for some Sj. That is, every element in {T1, T2, ...} is preceded by some element in {S1, S2, ...}.

We now investigate whether this is a partial order. We desire a partial order, because then equality means that things are really equal (anti-symmetry).

It is true that {S1, S2, ...} <= {S1, S2, ...}, so the relation is reflexive.

Suppose that {S1, S2, ...} <= {T1, T2, ...} <= {U1, U2, ...}. For every Ui, Tj <= Ui for some Tj. For that Tj, Sk <= Tj for that Sk. Hence, by transitivity of <= for single signatures, for every Ui, Sk <= Ui for some Sk, meaning that {S1, S2, ...} <= {U1, U2, ...}.

For anti-symmetry, we assume that {S1, S2, ...} <= {T1, T2, ...} and {T1, T2, ...} <= {S1, S2, ...}. If {T1, T2, ...} = {S1, S2, ...}, then the relation would be anti-symmetric . Unfortunately, note that {(int)} == {(int), (Number)}, because {(int)} <= {(int), (Number)} and {(int), (Number)} <= {(int)}, so I do not think anti-symmetry holds.

However, if we restrict ourselves to collections of signatures where every two different signatures have a different number of types, then I think anti-symmetry does hold!

Therefore, the proposed relation is indeed a partial order if we consider sets of signatures a where every two different signatures have a different number of types. Note that this includes (1) singular signatures like {(S)} and (2) varargs.

A few sanity checks:

1. (int, *int) <= (int, *Number) is indeed true: for every (int, Number, ..., Number), (int, int, ..., int) precedes it.
2. (int, *Number) <= (int, *int) is false.
3. (int) <= (int, *int) is also false, because e.g. (int, int) is not preceded by (int).

I think that the above formalisation corresponds to your implementation. Would you agree? If so, then it might be nice to document this.

All in all, super good find!!! If you agree that the above is consistent with your implementation, I might have a little think about whether the logic can be simplified. Otherwise, I'm super happy to merge this!

1 and 2 pass the tests in the PR.

3 I disagree (or maybe Julia disagrees). quoting you

Considering (int) <= (int, *int), I think this should be True because...

For a collection of signatures {S1, S2, ...} and a single signature T, let {S1, S2, ...} <= T if one of the following is true: S1 <= T, S2 <= T, et cetera. This models the desired condition.

then I have (int,) <= {(int,), (int, int), ...} which is {True, False} therefore true according to your condition.

However, if we now inquire about (int, *int) <= (int) we get {(int,), (int, int), ...} <= (int,) therefore {True, False} therefore True as well.

This would mean that (int) == (int, *int) but I explicitly break this case by ensuring that when we have an equality among two signatures where one has a varargs (or, using your formalism, when we have an equality among a set of signatures and a single signature) I forcibly break this equality and define that the smallest set is the smaller.

Which is what the following test testifies.

In [7]:  Signature(int) == Signature(int, varargs=int)
False

--

EDIT: I think you formalised what I have brutally implemented and was thinking about in much rougher terms. Thank you! now what you say is cleaner to me as well. Apart from this latter point, I agree wholly with your discussion.

therefore true according to your condition.

I think that's the other condition, right? I think you have a set on the right.

{(int)} <= {(int), (int, int), (int, int, int), ...} if, for every (int, ..., int), it is preceded by (int). This is not true. Therefore, at least according to the proposed formalism, we would find that (int, int*) < (int).

Argh, maybe what I wrote down isn't quite right after all. However, your implementation does seem to do the right thing. I'll sleep on it and get back to this tomorrow!

@PhilipVinc, after thinking about it a bit more, I think trying to define a partial order directly which does what you implement might not be the right way to think about this. Rather, the correct approach might to, first, define an "initial" partial order; and, second, break ties, exactly like you're doing in the implementation.

What got me worried initially about this construction is that, if we break ties in the wrong way, the relation might no longer be a partial order.

Just a very quick sketch. Define varargs as the corresponding infinite set of signatures:

(float, *int) = {(float), (float, int), (float, int, int), ...}

For two signatures S and T, let S <= T if (1) S and T contain an equal number of types and (2) the types in S are subtypes of the correspond types in T.

For collections of signatures, we now define two relations: <=1 and <=2. Intuitively, <=1 should roughly be the implementation with

        # If this signature has variable arguments, but the other does not, then this
        # signature cannot be possibly smaller.
        if self.has_varargs and not other.has_varargs:
            return False

commented out and before your addition.

How does <=1 behave? This actually is not clear to me, but I have one proposal.

Because the lines are commented out, I think <=1 is not the subset relation <=s, where {S1, S2, ...} <=s {T1, T2, ...} if every Si preceeds some Tj.

Rather, let {S1, S2, ...} <=1 {T1, T2, ...} if some Si preceeds some Tj.

This is a very weak relation, because it equates too many things. For example,

(int) ==1 (int, *int) ==1 (int, *Number)

Let's call a collection of things equated by <=1 an equivalence class. Let the equivalence class of {S1, S2, ...} be [{S1, S2, ...}].

I now believe it is true that, if we only consider collections of signatures which are (1) singular or (2) varargs expansions, the elements in every equivalence class only differ by their varargs.

We now proceed to "breaking these ties." Formally, this corresponds to defining an additional partial order <=e which operates within equivalence classes.

Specifically, let {S1, S2, ...} <=2 {T1, T2, ...} whenever

1. if [{S1, S2, ...}] != [{T1, T2, ...}], we have [{S1, S2, ...}] <=1 [{T1, T2, ...}] (equal to {S1, S2, ...} <=1 {T1, T2, ...});
2. and if [{S1, S2, ...}] == [{T1, T2, ...}], we have {S1, S2, ...} <=e {T1, T2, ...}.

I think this is still a partial order, because reflexivity and anti-symmetry only have to be verified within equivalence classes and thus follow from <=e. Transitivity would have to be more carefully verified, but also holds, I think.

Since the things within an equivalence class only differ by their varargs, define the following partial order: first comes no varargs, and then order by varargs type. This fully defines <=2.

If this is right, we might be able to simplify the logic in the following way:

        # If the number of types of the signatures are unequal, then the signature
        # with the fewer number of types must be expanded using variable arguments.
        if not (
            len(self.types) == len(other.types)
            or (len(self.types) > len(other.types) and other.has_varargs)
            or (len(self.types) < len(other.types) and self.has_varargs)
        ):
            return False

        # Expand the types and compare.
        self_types = self.expand_varargs(len(other.types))
        other_types = other.expand_varargs(len(self.types))
        initial_partial_order = all(
            [
                beartype.door.TypeHint(x) <= beartype.door.TypeHint(y)
                for x, y in zip(self_types, other_types)
            ]
        )

        if initial_partial_order:
            same_equivalence_class = all(
                [
                    beartype.door.TypeHint(x) == beartype.door.TypeHint(y)
                    for x, y in zip(self_types, other_types)
                ]
            )

            if same_equivalence_class:
                if not self.has_varargs and not other.has_varargs:
                    # They are the same signature!
                    return True
                if self.has_varargs ^ other.has_varargs:
                    # The smallest is the one without varargs.
                    return other.has_varargs
                else:
                    return (
                        beartype.door.TypeHint(self.varargs)
                        <= beartype.door.TypeHint(other.varargs)
                    )
            else:
                return initial_partial_order
        else:
            return initial_partial_order

This fails three tests, but I'm wondering if that is actually right:

================================================== FAILURES ==================================================
______________________________________________ test_comparison _______________________________________________

    def test_comparison():
        # Variable arguments shortcuts:
        assert not Sig(varargs=int) <= Sig()
        assert not Sig(varargs=Num) <= Sig(varargs=int)

        # Expandability shortcuts:
        assert not Sig(int) <= Sig(int, int)
        assert not Sig(int) <= Sig(int, int, varargs=int)
        assert not Sig(int, int, varargs=int) <= Sig(int)

        # Test expansion:
        assert Sig(varargs=int) <= Sig(Re, varargs=Re)
        assert Sig(int, varargs=int) <= Sig(Re, varargs=Re)
        assert Sig(int, int, varargs=int) <= Sig(Re, varargs=Re)

        assert not Sig(varargs=Num) <= Sig(Re, varargs=Re)
        assert not Sig(Num, varargs=int) <= Sig(Re, varargs=Re)
>       assert not Sig(int, int, varargs=Num) <= Sig(Re, varargs=Re)
E       assert not Signature(int, int, varargs=numbers.Number) <= Signature(numbers.Real, varargs=numbers.Real)
E        +  where Signature(int, int, varargs=numbers.Number) = Sig(int, int, varargs=Num)
E        +  and   Signature(numbers.Real, varargs=numbers.Real) = Sig(Re, varargs=Re)

tests/test_signature.py:144: AssertionError
________________________________________________ test_varargs ________________________________________________

    def test_varargs():
        assert f() == "fallback"
        assert f(Num()) == "number"
        assert f(Num(), object) == "fallback"
        assert f(object, Num()) == "fallback"
        assert f(Num(), Num()) == "two numbers"
        assert f(Num(), Num(), Num()) == "two or more numbers"
        with pytest.raises(LookupError):
>           f(Rat(), Rat(), Rat())
E           Failed: DID NOT RAISE <class 'LookupError'>

tests/advanced/test_cases.py:201: Failed
________________________________________________ test_varargs ________________________________________________

    def test_varargs():
        assert f() == "fallback"
        assert f(Num()) == "number"
        assert f(Num(), object) == "fallback"
        assert f(object, Num()) == "fallback"
        assert f(Num(), Num()) == "two numbers"
        assert f(Num(), Num(), Num()) == "two or more numbers"
        with pytest.raises(LookupError):
>           f(Rat(), Rat(), Rat())
E           Failed: DID NOT RAISE <class 'LookupError'>

tests/advanced/test_correctness.py:203: Failed
========================================== short test summary info ===========================================
FAILED tests/test_signature.py::test_comparison - assert not Signature(int, int, varargs=numbers.Number) <=...
FAILED tests/advanced/test_cases.py::test_varargs - Failed: DID NOT RAISE <class 'LookupError'>
FAILED tests/advanced/test_correctness.py::test_varargs - Failed: DID NOT RAISE <class 'LookupError'>
===================== 3 failed, 151 passed, 3 skipped, 5 deselected, 1 xfailed in 0.58s ======================

Will continue later!

@PhilipVinc Please ignore the previous message. I think the failing tests prove that whatever I tried to do there doesn't work.

What I'm having trouble fully understanding is that

>>> Signature(int, varargs=Number) <= Signature(int)
False

>>> Signature(int, varargs=Number) <= Signature(Number)
True

How does one interpret this? I guess this means that

Signature(int) < Signature(int, varargs=object) < Signature(Number)

meaning that adding varargs makes things strictly larger, but the signature always remains strictly smaller than any superclass? Ok, I think that makes sense. Is that also your interpretation?

If I try a more complicated scenario, things do really seem to check out, so I do think you've got it right:

from plum import dispatch
from numbers import Number


@dispatch
def f(*xs: int):
    return "ints"


@dispatch
def f(*xs: Number):
    return "nums"


@dispatch
def f(x: int):
    return "int"


@dispatch
def f(x: int, y: int):
    return "two ints"


@dispatch
def f(x: Number):
    return "num"


@dispatch
def f(x: Number, y: Number):
    return "two nums"


@dispatch
def f(x: int, *ys: int):
    return "int and ints"


@dispatch
def f(x: int, *ys: Number):
    return "int and nums"


@dispatch
def f(x: Number, *ys: int):
    return "num and ints"


@dispatch
def f(x: Number, *ys: Number):
    return "num and nums"


assert f(1) == "int"
assert f(1, 1) == "two ints"
assert f(1, 1, 1) == "int and ints"

assert f(1.0) == "num"
assert f(1.0, 1.0) == "two nums"
assert f(1.0, 1.0, 1.0) == "num and nums"

assert f(1, 1.0) == "int and nums"
assert f(1.0, 1) == "num and ints"

assert f(1, 1, 1.0) == "int and nums"
assert f(1.0, 1.0, 1) == "num and nums"
assert f(1, 1.0, 1.0) == "int and nums"
assert f(1.0, 1, 1) == "num and ints"

I have to say it's a bit tough for me to follow what you were saying... I mean, I do understand the math/logic but the bigger picture I fail to grasp. Do you have something I could read to build up some culture about such things like partial/total order etc etc?

Anyhow, my brutal physicist self was simply trying to match what Julia does

julia> test(x::Int, b::Number...)=1
test (generic function with 1 method)

julia> test(x::Int) = 2
test (generic function with 2 methods)

julia> test(1)
2

and

julia> test(x::Int, b::Number...)=1
test (generic function with 1 method)

julia> test(x::Number) = 2
test (generic function with 2 methods)

julia> test(1)
1

My intuitive understanding (I would love to be able to formulate it better, but I miss the language) is that

• This makes sense from a dispatch point of view. Because I want the most specific signature, and if there is a choice between a varargs and a non-varargs version I want the non varargs because it's more specific in some sense.
• If I interpret vararg signature as a set of signatures for which the <= relationship wrt another signature to be defined as s1 <= {s2} == any(s1 <= s2_i for s2_i in s2) (where <= is here defined as the logic as it, where the vararg statement disappears because I compare 'expanded' signatures) then I would get an equality between Sig(int)and Sig(int, *int).
• The equality that arises from the definition above feels wrong, and my intuition suggests me that a vararg object should be strictly larger than a non varargs object so I brutally define, only in this case Sig(int) < Sig(int, *int) to break the equatlity.

About

Signature(int) < Signature(int, varargs=object) < Signature(Number)

meaning that adding varargs makes things strictly larger, but the signature always remains strictly smaller than any superclass? Ok, I think that makes sense. Is that also your interpretation?

Yes, this is the hierarchy that arises. I think this makes sense because Signature(int, varargs=object) here is effectively Signature(int) * where the star simply says that this object behaves as Signature(int) when compared against everything except Signature(int) itself, in which case it should test larger.

By the way, I'm looking at how Julia does it (see to https://github.com/JeffBezanson/phdthesis/blob/master/main.pdf in practice, sec 4.3.2) and the relevant rules are

• Union type A is more specific than B if some element of A is more specific than B, and B is not more specific than any element of A.
• Non-union type A is more specific than union type B if it is more specific than some element of B.

those two roughly corresponds to my any rule if we interpret types with varargs as some sort of union type...

Also, see page 126, the code listing. Roughly it says

function issub(a::TagT , b::TagT , env)
    ... some early logic
    va , vb = a.vararg , b.vararg
    la , lb = length(a.params), length(b.params)
    ai = bi = 1
    .......... # some logic that should break out early if a > b
    return (la==lb && va==vb) || (vb && (la>= (va ? lb : lb -1)))

look at the return statement: it says if the length is the same and both are varargs, then return True, but otherwise return a is smaller than b if b is varargs and a is not, which matches my logic.

Note: I found out about Jeff bezanson's thesis only after I started writing the message above, and will maybe read it in following days. Now that I found a version of how sub typing relationship can be handled, maybe one day I could try to write something that could handle parametric types as well!

By the way, the picture I outline above I have no idea how it turns out in case of multiple inheritance. As this is something that can arise in python, it would be interesting to reflect how to expand @JeffBezanson work in the case where multiple inheritance is allowed, and see if we can get all of this into python.

I'm increasingly sure that Beartype won't be enough for us in the case of parametric signatures (eg (Array[T], Array[T]) where T<: ...) and we would have to at least partially introduce our own logic there. But if we can get everything right I think it would be a great advancement.

Oh god, I would love that.

Nevertheless, @wesselb , I am increasingly convinced that this PR is correct (as far as what we have been discussing) and can be merged.

EDIT: Ah, and please excuse my brutal language. I'm just a physicist who tries to talk about programming languages.

I have to say it's a bit tough for me to follow what you were saying... I mean, I do understand the math/logic but the bigger picture I fail to grasp. Do you have something I could read to build up some culture about such things like partial/total order etc etc?

Sorry, I'm entirely aware that I'm doing a lot of rambling here! The fact that I'm having to appeal to these concepts just demonstrates that I don't quite fully understand what's going on. 😅 I actually think Wikipedia is not a bad source to read up on partial/total orders, equivalence classes, and partitions.

By the way, I'm looking at how Julia does it (see to https://github.com/JeffBezanson/phdthesis/blob/master/main.pdf in practice, sec 4.3.2) and the relevant rules are

Ahhh, this is super interesting. Thanks for linking @JeffBezanson's thesis! I'm definitely going to have a closer look.

look at the return statement: it says if the length is the same and both are varargs, then return True, but otherwise return a is smaller than b if b is varargs and a is not, which matches my logic.

That's an awesome find. Yes, I'm also becoming more and more convinced that your implementation is right.

Oh god, I would love that.

This would be so nice. It seems like a very challenging task, but I would absolutely love that too.

Before we merge this, there is just one more perspective that I would like to discuss. I unfortunately might also have found another case where we diverge from Julia, even after your changes. :(

(I'm sorry for possibly overanalysing this. I just want to be absolutely sure that this is right and that I understand what's going on.)

So far, we've attempted to interpret signatures with varargs like (int, *int) as collections of signatures. However, what if this interpretation is wrong and overcomplicating the matter?

When a non-varargs signature of length n is compared with a varargs signature, perhaps the right interpretation is that the comparison simply interprets the varargs signature as a signature of length n. I mean, it's obvious that this is going on because of the varargs expansion, but I think it is worthwhile to emphasise this: the comparison completely ignores the "union-nature" of varargs signatures and simply considers them signatures of the appropriate length. (With the additional nuance that adding varargs makes things slightly bigger!)

Although this interpretation seems to make sense, you do you run into situations like this:

>>> Signature(int) < Signature(int, varargs=Number) < Signature(Number, Number)
True

>>> Signature(int) <= Signature(Number, Number)
False

Clearly, if <= were a partial order, this shouldn't be possible. Therefore, if the implementation you've converged onto is right, I think your earlier suspicion that using a partial order is too restrictive might be true.

In practice, when we use <=, we first check compatibility with the provided arguments. Importantly, this compatibility check eliminates all non-varargs signatures with a different number of types, so we can never arrive at the above contradition: we simply never consider Signature(int) and Signature(Number, Number) simultaneously.

When we compare non-varargs against non-varargs and non-varargs against varargs, things appear to make sense. So far so good. Unfortunately, when comparing varargs against varargs, things again become a little strange:

>>> class A: pass

>>> class B: pass

>>> Signature(int, varargs=A) <= Signature(Number) <= Signature(Number, varargs=B)
True

>>> Signature(int, varargs=A) <= Signature(Number, varargs=B)
False

Whereas the first inequality treats the signatures as one-argument signatures, the latter inequality treats the varargs signatures as unions and (I think) implements the subset relation, which is why it returns False. Unlike the previous situation, I think this situation can occur in practice and might lead to problems. For example, consider the following snippet:

from plum import dispatch
from numbers import Number


class A:
    pass


class B:
    pass


@dispatch
def f(x: int, *a: A):
    return "int"


@dispatch
def f(x: Number, *a: B):
    return "num"


f(1)
# AmbiguousLookupError: For function `f`, `(1,)` is ambiguous among the following:
#   Signature(int, varargs=__main__.A, implementation=<function f at 0x7f9db14011f0>) (precedence: 0)
#   Signature(numbers.Number, varargs=__main__.B, implementation=<function f at 0x7f9d703b2f70>) (precedence: 0)

In comparison, Julia does get this right:

julia> struct A
       end

julia> struct B
       end

julia> f(x::Int, a::A...) = "a"
f (generic function with 1 method)

julia> f(x::Real, b::B...) = "b"
f (generic function with 2 methods)

julia> f(1)
"a"

julia> f(1.0)
"b"

What I suspect might need to happen is the following: when two varargs signatures are compared, they need to be "contextualised" to a given number of types.

Ok, enough analysis. Onto a more concrete proposal. What if we got rid of __le__ and instead implemented the following:

def is_subsig(s1: Signature, s2: Signature, n: int):
    ...

In practice, n would derive from the number of arguments supplied. For every n, it would implement a valid partial order. The implementation of is_subsig would what you have right now, but it would treat two varargs signatures differently: simply expand them according to n and compare.

Hey @wesselb !
I think your analysis above was entirely right, so I got back to thinking a bit more about this.

I came to the conclusion that implementing correctly rules #3 and #4 from Jeff's thesis would solve those issues, and therefore got around to that the rules are respectively

• 3. If some element of tuple type A is more specific than its corresponding element in tuple type B, and no element of B is more specific than its corresponding element in A, then A is more specific
• 4. A variadic type is less specific than an otherwise equal non-variadic type.

He also understands varargs (variadic types) as sets.

Look at the implementation, which I tried to document extensively. Of course I added all tests that we discussed, and everything passes so I hope that it is correct this time...

@wesselb between this and the other PR, as you have little time, I'd prefer you review this one because it's blocking my next release of netket...

@PhilipVinc that sounds good! Let me first focus on this then so we can get it merged asap.

EDIT: Please ignore the second part of the message before the edit. I haven't yet had my morning coffee...

@PhilipVinc, I might have found an edge case that doesn't work after all:

from plum import dispatch


class A:
    pass


class B:
    pass


@dispatch
def f(x: int, *ys: A):
    return "int and As"


@dispatch
def f(x: int, *ys: B):
    return "int and Bs"


print(f(1, A()))  # int and As :)
print(f(1, B()))  # int and Bs :)
print(f(1))  # int and Bs :( I think this should raise an ambiguity error.

I'm starting to suspect that comparing two varargs signatures in a vacuum, so without additional context, is ill-defined. E.g., whereas (int, *A) is more specific than (int, *B) depends on how many arguments you're considering: for one argument, they are equally specific; but for two or more arguments, neither is more specific.

I'm therefore thinking that we might need to rethink the approach. For comparing two varargs, we might need two modes of comparison:

1. When defining methods, I think it makes sense to use the subset relation. This relation should be used to see whether e.g. a method is redefined.

2. When running the resolver to see which signature is most specific, when comparing two varargs signatures, perhaps the comparison should take into account how many arguments you're considering.

Thanks!
So... indeed you are right.
But I don't think the issue stems from that (or maybe it's just that I don't particularly like the approach because it makes signatures not really comparable in a vacuum, which I believe should hold...)

I think the issue here stems from the fact that:

• Everywhere we check for the subset relationship ⊆ between signatures implemented through __le__
• The equality (the bar below ⊆) is unimportant at resolution-level for all non-varargs signatures because if two signatures are identical we never compare them, because we do not allow two identical signatures in the method table.
  • Note that, if for any reason we had two identical signatures in resolution , the logic

          new_candidates = [
              c for c in candidates if not method.signature < c.signature
          ]

    would keep both of them thus causing an ambiguity error

However when introducing varargs in the mix...

• We still check for ⊆ relationship, but now we have Sig(int, *A) ⊆ Sig(int, *B) and Sig(int, *B) ⊆ Sig(int, *A), according to all the blabla above
• However, Sig(int, *A) != Sig(int, *B) so python will verify that Sig(int, *A) < Sig(int, *B) and Sig(int, *A) < Sig(int, *B)
• Because of this, the logic new_candidates = [c for c in candidates if not method.signature < c.signature] will not add both signatures to the list of candidates, and we don't get a resolution error...

I think it's because we are checking for equality, but equality is not the right concept here.

Ok, ignore what I said above.

I think the underlying reason is that at some point we want to check that Sig(int, *A) ⊂ Sig(int, *B), which is implemented as Sig(int, *A) < Sig(int, *B).

This calls into Comparable meta class, where it is defined to be

    def __lt__(self, other):
        return self <= other and self != other

but I believe this is wrong, because this leads to the fact that since Sig(int, *A) ≠ Sig(int, *B) and Sig(int, *A) <= Sig(int, *B) and Sig(int, *B) <= Sig(int, *A) then we have that Sig(int, *A) < Sig(int, *B) and Sig(int, *B) < Sig(int, *A).

Instead, if we define

    def __lt__(self, other):
        return self <= other and not other <= self

we automatically break this and obtain what I believe it to be the correct subset relationship Sig(int, *A) ⊆ Sig(int, *B) and Sig(int, *B) ⊆ Sig(int, *A) but Sig(int, *A) ⊄ Sig(int, *B) and Sig(int, *B) ⊄ Sig(int, *A)

Does this make any sense?
(By the way, making this change does indeed fix also your edge case without breaking anything)

This calls into Comparable meta class, where it is defined to be (...) but I believe this is wrong,

Hmm, I'm confused about this. Mathematically, I believe that x < y if and only if both x <= y and x != y.

Given a non-strict partial order <=, I believe the current implementation is the usual way to derive the strict inequality < from the non-strict inequality. See e.g. this Wikipedia entry.

Instead, if we define (...)

Right, your definition makes sense too. In fact, I think that mathematically

x < y    <=>    x <= y and x != y    <=>    x <= y and not (y <= x)

I'm a little worried about making subtle changes like this, because it suggests that we're not working with a partial order anymore, as for a partial order the two definitions should be equivalent.

Taking a step back, I can't seem to resolve the following issue.

What we want is to determine whether e.g.(int, *A) is more specific than (int, *B). Since they should be equally specific for one argument and not comparable for two arguments, it doesn't matter which <= we implement, because it will always get one of the two cases wrong.

To me this suggests that attempting to directly compare (int, *A) and (int, *B) without further context simply cannot work. @PhilipVinc, what do you think about this argument?

If we want to follow Julia's playbook, that won't work because we are comparing signatures, not signatures for a certain length.

Using your suggestion of expanding the varargs to the correct size, the example below should raise an Ambiguity error, but that is not correct because the second signature is strictly more precise than the first.

julia> f(x::Int, y::Number...) = 1
f (generic function with 1 method)

julia> f(x::Int, y::Int...) = 2
f (generic function with 2 methods)

julia> f(1)
2

Another case where comparing without the varargs would lead to wrong results is this example.

julia> g(x::Number, y::Int...) = 1
g (generic function with 1 method)

julia> g(x::Int, y::Number...) = 2
g (generic function with 2 methods)

julia> g(1)
ERROR: MethodError: g(::Int64) is ambiguous.

I just added those two more test cases and the PR as it stands (changing the definition of less) passes them. It is not at all obvious to me how to do it with the approach you propose.

Hey @PhilipVinc! Apologies for the delay. I was offline for a few days due to personal circumstances.

I've thought about it a bit more, and perhaps there is a simpler solution.

When we're determining which signature is most specific for some given arguments, first we expand all candidate varargs signatures to the right length, but we retain the varargs. (So this sense of "expansion" is a little different from earlier use, where we discard the varargs.) More specifically, this step would be done at the beginning of the resolve function.

I think that this, combined with implementing the subset relation for comparing two varargs signatures, might get it right! In particular, I think that this should work correctly in your two examples.

What do you think?

When we're determining which signature is most specific for some given arguments, first we expand all candidate varargs signatures to the right length, but we retain the varargs. (So this sense of "expansion" is a little different from earlier use, where we discard the varargs.) More specifically, this step would be done at the beginning of the resolve function.

Maybe yes... though we would have to special case cases like (int, *int) and (int, int, *int) when calling with (1,1) because the latter is more specialised but this approach would compare them equal...

I will spend the next hour of train to think about this, but it's really unclear to me how to do it this way

@PhilipVinc Wouldn't (int, *int) always have precedence over (int, int, *int), so you wouldn't be able to ever call the latter?

Actually, with the subset relation, the two would actually be equal, so defining one would overwrite the other. In that case, you would never have to compare them.

EDIT: No, hold on. Of course they are not equal, since only the former can accept one argument. Would it be reasonable to raise an ambiguity error for (1, 1)? I'm actually not what the rules here should be.

Well, no. The latter is the most specific, at least according to the set of rules that Julia follows .
We can decide to deviate

julia> f(x::Int, y::Int...) = 1
f (generic function with 1 method)

julia> f(x::Int, y::Int, z::Int...) = 2
f (generic function with 2 methods)

julia> f(1,1)
2

julia> f(1,1,3)
2

@PhilipVinc Hmm, you're completely right. This might turn out to be complicated than anticipated.

I think I'm convinced that two varargs signatures cannot be compared in isolation, by the following earlier argumentation. However, you've also convinced me that the proposed solution is not fully consistent with Julia either.

It seems that the edge case could be addressed by considering the general subset relation in the case of equality. That is, expand and keep varargs, and compare. Of non-equality, things are OK. If equality, check subset relation in in pre-expansion form. This is starting to sound a little complicated. I'm not sure.

Hey @wesselb , a while ago I had to vendor plum into netket (with this PR merged) as this was blocking us from some updates.

Do you see any way forward to getting this PR (or some PR that makes the included test cases) pass, such that we can stop venturing Plum?

A particularly nasty test case that we would like to pass is the following, which should not raise an Ambiguous error...

In [1]: from plum import dispatch
In [2]: from numbers import Number
In [3]: @dispatch
   ...: def f(x: int, y: Number):
   ...:     return 1
   ...: @dispatch
   ...: def f(x: int, *y: int):
   ...:     return 2
   ...: f(1, 1)
---------------------------------------------------------------------------
AmbiguousLookupError                      Traceback (most recent call last)
Cell In[5], line 1
----> 1 f(1, 1)

    [... skipping hidden 4 frame]

File ~/Dropbox/Ricerca/Codes/Python/plum/plum/resolver.py:334, in Resolver.resolve(self, target)
    331     return candidates[precedences.index(max_precendence)]
    332 else:
    333     # Could not resolve the ambiguity, so error.
--> 334     raise AmbiguousLookupError(self.function_name, target, candidates)

AmbiguousLookupError: `f(1, 1)` is ambiguous.

Candidates:
   f(x: int, y: numbers.Number)
       <function f at 0x10323f2e0> @ /<ipython-input-3-370890474f21>:1
   f(x: int, *y: int)
       <function f at 0x10323fec0> @ /<ipython-input-3-370890474f21>:4

Hey @PhilipVinc! I think this extensive issue has shown that a general solution is complicated and perhaps not feasible, so it might sense to go with something that works better than what we now have, even if it is a general solution.

Let me go over this thread once more to again fully understand the situation, since it's been a while. After I've convinced myself that this is an extension of what we currently have without any unintended breaking behaviour (I think that's the case, just need to remind myself), I'm happy to merge this.

I'm preoccupied until mid next week, but should then be able to look at this, so we should be able to merge this on the very short term!

Closing in favour of #151