Dispatching to list subtypes

[shoyer]

As an (temporary?) alternative to full support for Python typing (#69), I'd like to propose adding multipledispatch.TypedList. The use case here is separate functions for different list subtypes, e.g., lists of strings vs lists of integers. See pydata/xarray#1938 for discussion.

I have an example implementation here and am happy to work on putting together a PR if desired:
https://colab.research.google.com/drive/18zdyUpWLNFzFaz08GUOC5vs1GxE_jHg-#scrollTo=XDL0cBeS-lub

Example usage:

@dispatch(TypedList[int])
def f(args):
  print('integers:', args)

@dispatch(TypedList[str])
def f(args):
  print('strings:', args)

@dispatch(TypedList[str, int])
def f(args):
  print('mixed str-int:', args)

f([1, 2])  # integers: [1, 2]
f([1, 2, 'foo'])  # mixed str-int: [1, 2, 'foo']
f(['foo', 'bar'])  # strings: ['foo', 'bar']
f([[1, 2]])  # NotImplementedError: Could not find signature for f: <TypedList[list]>

The exact public facing API is up for discussion. I'm tentatively calling this TypedList for clarity and to distinguish this from typing.List (this is actually equivalent to typing.List[typing.Union[...]).

[mrocklin]

cc @llllllllll @mariusvniekerk

[hameerabbasi]

I think that for tuples, it might be useful to have Tuple (exact match) and VarTuple (this approach). Tuples are often fixed length.

Edit: Or, more generally, Iterable and VarIterable.

[llllllllll]

I don't like that this merges the idea of typed lists and regular lists. One of the advantages of the implementation in blaze is that it makes the two kinds of dispatches distinct. This is important when working on a large code base with thousands of dispatch definitions, many of them already dispatch on list. The proposed implementation adds ambiguity when you register a dispatch for both list and TypedList. For example, what should the result of the following code be?

@dispatch(TypedList[int])
def f(xs):
    print('typed')


@dispatch(list)
def f(xs):
    print('regular')

f([1, 2, 3])

This currently prints regular; however, if you change the definition order of the two functions you will get typed. I find this confusing given that:

In [11]: issubclass(TypedList[int], list)
Out[11]: False

In [12]: issubclass(list, TypedList[int])
Out[12]: False

Given that we can get the the same auto-boxing behavior with two lines of Python, I am not sure this is a big feature. If anything, it forces us to explicitly register the list instance so we know that this has been done and we understand how dispatching will happen in the future.

Regarding the use of frozenset vs unique: you are correct that the frozenset version will create less classes and probably be a bit faster, but due to how the subclassing machinery works it still produces the correct result.

Finally, the VarArgs object is duck-typed like an immutable list, so it should be usable in almost all cases without worrying about the actual type, this is Python after all.

I would also like to make my stance on typing clear: I don't think that supporting typing style annotations in multipledispatch is a good idea. typing annotations are designed for static analysis tools like mypy, they should not affect the runtime behavior of your program.

[hameerabbasi]

I, on the other hand, support typing. But (on the other hand) Joe is right about overlapping, and how it could be difficult in a large codebase.

I suggest writing a simple decorator on anything that will convert VarArgs/TypedList to List. Should be trivial.

[shoyer]

I'm also happy with a solution based more directly on @llllllllll's VarArgs. It is indeed simple to write a decorator to automatically unwrap dispatched types and to overload list directly, so I'm all for leaving that out of multipledispatch.

The harder part is writing the TypedList/VarArgs type in the first place, which involves some subtlety and metaclasses. Is there support for adding some form of this into multipledispatch?

As for typing, I'll note that there are at least two ways to support it:

1. Types from typing in the @dispatch decorator. This form is very explicit:

@dispatch(List[Union[str, int]])
def f(x):
    ...

2. Automatically extracting types from decorated functions for dispatching (from WIP: Experiment to use pytypes to add support for python type hints #69). This form is much more magical:

@dispatch()
def f(x: List[Union[str, int]])
    ...

I would support version (1) directly in multipledispatch.dispatch if it can be done in a performant way. I'm not opposed to version (2), but it should probably use a separate name, e.g., dispatch_by_type_hints or something similar.

[mrocklin]

Note that multipledispatch does support PEP 484 type hints: #65

[shoyer]

Note that multipledispatch does support PEP 484 type hints: #65

Oh, interesting.

I'm not entirely sure that's a good idea to include for the default dispatch decorator, to be honest :). Types for dispatching with multipledispatch and type checking (e.g., with mypy) have some small but important differences:

• multipledispatch only accepts exact type matches (not even subclasses) for runtime performance (edit: not true)
• type checkers will even introspect values to determine compound types (e.g., List[str]) and have various other small differences from runtime type checking (e.g., integers are valid for float arguments).

I can see cases where I might use different types, e.g., list for multipledispatch but List[str] for type checking.

[llllllllll]

multipledispatch only accepts exact type matches (not even subclasses) for runtime performance

Multiple dispatch supports subclasses correctly. It uses the same linearization algorithm as the Python MRO to partially order the types to search.

[shoyer]

Multiple dispatch supports subclasses correctly. It uses the same linearization algorithm as the Python MRO to partially order the types to search.

Oops, my mistake.

[hameerabbasi]

Subtypes can come in useful. For example, I wouldn't feel okay asking XArray to change its code every time I add a new matrix format. And it will be useful in sparse for checking input arguments are a SparseArray instead of every combination.

In light of @llllllllll's comments, I'm now in favour of @llllllllll's implementation, maybe while adding a simple wrapper that extracts the List from VarArgs so that the function itself doesn't have to be written to extract all the arguments. And possibly a wrapper that converts particular arguments to VarArgs.

[francesco-ballarin]

Hi everybody,
in one library that I am currently developing I had done something similar (typed lists), see e.g. the following tests for the notation

# Test class with list_of inputs
def test_enabled_list_of():
    class E(object):
        @dispatch(list_of(int))
        def __init__(self, arg):
            self.arg = arg[0]
    assert E([1, 2]).arg == 1
    
# Test class with list_of inputs, with multiple types for each list
def test_enabled_list_of_multiple():
    class E(object):
        @dispatch(list_of(float))
        def __init__(self, arg):
            self.arg = arg[0]
            
        @dispatch(list_of((float, int)))
        def __init__(self, arg):
            self.arg = 2*arg[0]
            
        @dispatch(list_of((float, str)))
        def __init__(self, arg):
            self.arg = 3*arg[0]
            
    assert E([1.]).arg == 1. and isinstance(E([1., 2.]).arg, float)
    assert E(["a"]).arg == "aaa"
    assert E([1]).arg == 2 and isinstance(E([1]).arg, int)
    assert E([1., 2.]).arg == 1. and isinstance(E([1., 2.]).arg, float)
    assert E([4., 3]).arg == 8. and isinstance(E([4., 3]).arg, float)
    assert E([4, 3.]).arg == 8 and isinstance(E([4, 3.]).arg, int)
    assert E([2., "a"]).arg == 6. and isinstance(E([2., "a"]).arg, float)
    assert raises(UnavailableSignatureError, lambda: E([object()]))

# Test class with list_of inputs, with multiple types for each list, with ambiguous types
def test_enabled_list_of_multiple_ambiguous():
    class E(object):
        @dispatch(list_of(float))
        def __init__(self, arg):
            self.arg = arg[0]
            
        @dispatch(list_of((float, int)))
        def __init__(self, arg):
            self.arg = 2*arg[0]
            
        @dispatch(list_of((float, int, str)))
        def __init__(self, arg):
            self.arg = 3*arg[0]
    
    try:
        # Ambiguity checking is delayed to the first time the method is evaluated
        E = E(None)
        # The ambiguity for list_of(float) is solved by the first method, however
        # the ambiguity for list_of(int) cannot be solved as both the second and third
        # method could be used for that.
    except AmbiguousSignatureError:
        pass # this has failed has expected
    else:
        raise RuntimeError("This test should have failed due to list_of(int) ambiguity")
        
    # Ambiguity can be fixed by explicitly providing an overloaded method for list_of(int)
    class F(object):
        @dispatch(list_of(float))
        def __init__(self, arg):
            self.arg = arg[0]
            
        @dispatch(list_of(int))
        def __init__(self, arg):
            self.arg = 4*arg[0]
            
        @dispatch(list_of((float, int)))
        def __init__(self, arg):
            self.arg = 2*arg[0]
            
        @dispatch(list_of((float, int, str)))
        def __init__(self, arg):
            self.arg = 3*arg[0]
            
    assert F([1.]).arg == 1. and isinstance(F([1., 2.]).arg, float)
    assert F(["a"]).arg == "aaa"
    assert F([1]).arg == 4 and isinstance(F([1]).arg, int)
    assert F([1., 2.]).arg == 1. and isinstance(F([1., 2.]).arg, float)
    assert F([4., 3]).arg == 8. and isinstance(F([4., 3]).arg, float)
    assert F([4, 3.]).arg == 8 and isinstance(F([4, 3.]).arg, int)
    assert F([2., "a"]).arg == 6. and isinstance(F([2., "a"]).arg, float)

# Test inheritance in combination with list_of
def test_inheritance_for_list_of():
    class A(object):
        pass
    class B(object):
        pass
    class C(A):
        pass
    
    @dispatch(list_of(A))
    def f(x):
        return 'a'

    @dispatch(list_of(B))
    def f(x):
        return 'b'

    assert f([A(), A()]) == 'a'
    assert f([B(), B()]) == 'b'
    assert f([C(), C()]) == 'a'
    assert f([C(), A()]) == 'a'
    assert raises(UnavailableSignatureError, lambda: f(B(), C()))

Right now the code is a bit of hack on top of multipledispatch.
There is definitely some overlapping to PR 69 [*], but I can definitely share the code in a gist if you want to have a look [**]. Let me know.

[*] I created wrapper called list_of instead of using the typing module, which I thought was not available in python 2, and I felt it was closer to the existing multipledispatch notation to have list_of((type1, type2)) rather than List[Union[type1, type2]]. Even though the typing module is probably superior to my approach, maybe some of my test cases could still come useful.

[**] I am proposing a gist and not a PR because in any case the code would need a bit of cleanup

[shoyer]

Finally, the VarArgs object is duck-typed like an immutable list, so it should be usable in almost all cases without worrying about the actual type, this is Python after all.

@llllllllll This is one part that I don't love about your solution, for two reasons:

1. Reliability: relying on duck-typing means VarArgs objects will be used with libraries that weren't built for it. As you note, this usually works, but there are many exceptions where base types (especially tuple) treated differently. Offhand, I can think of examples in NumPy, Dask and Xarray. Even if duck types currently work, relying on that behavior introduces risk of being broken by future releases, since upstream libraries rarely test for full duck-type compatibility.
2. Performance: Casting a list or tuple to VarArgs and then back to a base sequence type (if desired) entails additional overhead, because the the full sequence is copied for each conversion. For long sequences, this overhead could be non-negligible. I would rather only pay the price of iterating over a sequence once, to determine its unique types.

---

So again, I really don't care exactly how we spell this, but clearly there's a strong need. To keep things moving forward, let me make another proposal of what the public API could look like here:

from multipledispatch import dispatch, VarArgs

@dispatch(VarArgs[int])
def f(varargs):
    print('integers:', varargs.value)

@dispatch(VarArgs[str])
def f(varargs):
    print('strings:', varargs.value)

@dispatch(list)
def f(value):
    return f(VarArgs(value))

f([1, 2])  # integers: [1, 2]
f(['foo', 'bar'])  # strings: ['foo', 'bar']
f([[1, 2]])  # NotImplementedError: Could not find signature for f: <VarArgs[list]>

My main goal with this version is to keep things explicit and maintainable. We'll leave syntactic sugar up to downstream libraries:

• Explicit wrapping with VarArgs() is required to wrap a sequence (and infer the combined type)
• Explicit unwrapping with varargs.value is required to pull out the wrapped sequence.
• We only support a single type VarArgs for sequences of values with an inferred type. Downstream libraries can make their own specialized functions for different sequence types if desired.

We do need a metaclass to implement __getitem__ on the VarArgs type, but the usage is pretty tame as far as metaclasses go. This magic also has clear upsides: we need dynamically created classes to make this work at all, and this at least provides a clear baseclass and constructor for the specialized VarArgs types.

[shoyer]

We could easily make VarArgsitself implement the immutable sequence API. But it shouldn't inherit from tuple.

[hameerabbasi]

f([1, 2]) # integers: [1, 2]

Don't you mean f(VarArgs([1, 2]))?