False positive when checking parameter with Callable

[ericv8v9s]

Here's an example:

from typing import Callable
from overrides import override

class X: pass
class Y(X): pass
# X > Y
# Expected: ((Y) -> None) > ((X) -> None)

class A:
	def f(self, o: Callable[[X], None]) -> None:
		pass

class B(A):
	@override
	def f(self, o: Callable[[Y], None]) -> None:
		pass

Running this, I get:

$ python stuff.py
Traceback (most recent call last):
  File "/home/user/tmp/stuff.py", line 13, in <module>
    class B(A):
  File "/home/user/tmp/stuff.py", line 14, in B
    @override
     ^^^^^^^^
  File "/home/user/storage/misc/jupyter/lib/python3.11/site-packages/overrides/overrides.py", line 143, in override
    return _overrides(method, check_signature, check_at_runtime)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/user/storage/misc/jupyter/lib/python3.11/site-packages/overrides/overrides.py", line 170, in _overrides
    _validate_method(method, super_class, check_signature)
  File "/home/user/storage/misc/jupyter/lib/python3.11/site-packages/overrides/overrides.py", line 189, in _validate_method
    ensure_signature_is_compatible(super_method, method, is_static)
  File "/home/user/storage/misc/jupyter/lib/python3.11/site-packages/overrides/signature.py", line 103, in ensure_signature_is_compatible
    ensure_all_kwargs_defined_in_sub(
  File "/home/user/storage/misc/jupyter/lib/python3.11/site-packages/overrides/signature.py", line 164, in ensure_all_kwargs_defined_in_sub
    raise TypeError(
TypeError: `B.f: o must be a supertype of `typing.Callable[[__main__.X], NoneType]` but is `typing.Callable[[__main__.Y], NoneType]`

But as I understand it, Callable parameters are contravariant, and thus Callable[[Y], None] is a super type of Callable[[X], None].

mypy seems to agree:

$ mypy stuff.py
Success: no issues found in 1 source file

[mkorpela]

In general, when we override a method in a subclass, the principle of substitutability must hold. This principle, also known as Liskov Substitution Principle (LSP), is fundamental in object-oriented programming and type theory.

Specifically, in the context of method overriding:

1. The input parameters (arguments) of the overriding method in the subclass can be the same as or wider (more general) than those in the overridden method of the superclass. This is known as contravariance of method arguments.

2. The return type of the overriding method in the subclass can be the same as or narrower (more specific) than that in the overridden method of the superclass. This is known as covariance of return types.

In your case, the types in the parameter are inverted. You're passing Callable[[X], None] in class A and Callable[[Y], None] in class B, where Y is a subclass of X. This contradicts the principle of contravariance for method arguments.

Therefore, your example doesn't comply with Liskov's Substitution Principle, which is likely to cause a TypeError when trying to override the function f in class B.

To correct this, you would want to ensure the principle of contravariance for method arguments. So, class A should take Callable[[Y], None] and class B should take Callable[[X], None], as X is a wider type compared to Y. This allows any function that can handle X to be passed in, ensuring substitutability when going from A to B.

Here is the corrected code:

from typing import Callable
from overrides import override

class X: pass
class Y(X): pass

class A:
	def f(self, o: Callable[[Y], None]) -> None:
		pass

class B(A):
	@override
	def f(self, o: Callable[[X], None]) -> None:
		pass

Please note that the actual functionality of the classes and methods isn't defined in the code you provided, so my advice is based on type theory and the Liskov Substitution Principle, and not on the specifics of the functionality.

[mkorpela]

Yeah GPT-4 wrote that.. I think it is also correct the callables should be the otherway. Wider argument type is accepted but your making it stricter.

[mkorpela]

I’ll close this for now. I can open it again if more evidence comes in.

[ericv8v9s]

Thanks for getting back.

I agree with the theory you (or rather GPT-4) wrote, but I still think the correction is actually exactly backwards. Let's say we have these toy objects:

a = A()
b = B()
takes_x = lambda x: None  # Callable[[X], None]
takes_y = lambda y: None  # Callable[[Y], None]

And if B is a subtype of A, then we would expect its instances to be able to be used as if they were instances of A (at least in terms of type). But if A and B were defined using the "corrected" declarations, we would have

a.f(takes_x)  # works as expected, Callable[[X], None] can be invoked to take Y
a.f(takes_y)  # works
b.f(takes_x)  # works
b.f(takes_y)  # should work according to subsitution principle, but argument type is incompatible

Because in B.f (which was declared to take a Callable[[X], None]), we would be trying to use takes_y as if it takes X, but it doesn't.

On the other hand, if A and B were defined as given in my original example:

a.f(takes_x)  # works, argument type is exact match
a.f(takes_y)  # does not work AS EXPECTED, A is a super type of B
b.f(takes_x)  # works, takes_x can accept instances of Y for its argument
b.f(takes_y)  # works, argument type is exact match

[mkorpela]

Lets use a bit more specific example.

Class X we will call Animal and the subclass Y we will call Dog.

Class A we will call AnimalHerd and B we will call DogHerd.

The method f we will call feed_animals and the argument o we will call feed function.

In your example your stating that the feed_animals of the DogHerd should be able to close the feed function to only take in Dogs.

This is not possible. The super class of Animal for example is allowed to use it to feed for example Zepras.. this means that the DogHerd function signature should allow that too.

I think what you are looking for might be generics https://mypy.readthedocs.io/en/stable/generics.html

[mkorpela]

More specifically feed(animal: Dog) is not a super type of feed(animal:Animal).

[ericv8v9s]

More specifically feed(animal: Dog) is not a super type of feed(animal:Animal).

My whole argument is pretty much just the opposite of that: feed(animal: Dog) is a super type of feed(animal: Animal). Function parameter types are contravariant, no?

Let's consider the LSP applied on these two objects:

feed_any_animal: Callable[[Animal], None]
feed_only_dogs: Callable[[Dog], None]

Subtype Requirement: Let ϕ(x) be a property provable about objects x of type T. Then ϕ(y) should be true for objects y of type S where S is a subtype of T.

So something that works on a supertype should also work on the subtype.

In our case, we are dealing with functions, and specifically we only care about passing things into them, so that "something that works" or ϕ means "function accepts the argument we passed in".

If we suppose feed_any_animal is a supertype of feed_only_dogs as you proposed, then the requirement doesn't hold: we can give Dogs to feed_any_animal, and also Snakes, Tigers, etc., but the subtype can only accept Dogs.

On the other hand, if we say feed_only_dogs is a supertype of feed_any_animal, then everything works out: the supertype feed_only_dogs only accepts Dogs, while its subtype feed_any_animal can feed Dogs and a bunch of other things.

---

As to the issue you pointed out:

In your example your stating that the feed_animals of the DogHerd should be able to close the feed function to only take in Dogs.

This is not possible. The super class of Animal for example is allowed to use it to feed for example Zepras.. this means that the DogHerd function signature should allow that too.

I don't think that's an issue at all. It should be possible, and that the parent class can't use the feed function from its children is exactly how it's supposed to be.

Suppose our feed_animals method didn't take in functions and instead accepts Fruits, for example. And I assume the following setup is agreeable (to you and me, but maybe not the dogs who now have to eat fruits):

class Fruit: pass
class Apple(Fruit): pass

class AnimalHerd:
	def feed_animals(self, fruit: Apple): pass
class DogHerd:
	def feed_animals(self, fruit: Fruit): # bark and protest

Fruit is the supertype of Apple, so the override is correct and all is well. But it still means if DogHerd were to store a Banana passed to it, it's parent AnimalHerd can do nothing with that Banana.

[mkorpela]

Quoting the all mighty AI: ” The input parameters (arguments) of the overriding method in the subclass can be the same as or wider (more general) than those in the overridden method of the superclass. This is known as contravariance of method arguments.”

[ericv8v9s]

That's... I agree with that... The parameter in the subclass should be a supertype of whatever is in the parent, right? I'm saying that when that parameter itself is a Callable[[Dog], None], that's a supertype of Callable[[Animal], None].

[mkorpela]

Unfortunately it is not.
You can not substitute Callable animal with Callable dog

[ericv8v9s]

It is! I just walked through the substitution principle in my previous comment. Everything you can pass to a Callable dog, you can pass to a Callable Animal. It's the other way around that doesn't work.

[ericv8v9s]

Would this make more sense?

class Food: pass
class DogFood(Food): pass

class AnimalHerd:
	def feed_animals(self, bucket: list[Food]): pass
class DogHerd:
	def feed_animals(self, bucket: list[DogFood]): pass

We pass a bucket to feed_animals and it'll fill it with food. We can then get back our buckets and go to feed the animals.

It's the same thing with Callable[[T], None]. Our buckets here only takes stuff into it, which makes the T in list[T] contravariant. That's why we can write list[DogFood] in the subclass, because in this case list[DogFood] is a supertype of list[Food] (anything you can put in a DogFood bucket, you can also put in a Food bucket).

[mkorpela]

Really stupid for me to continue. But for educational purposes please check for example https://docs.oracle.com/javase/tutorial/java/generics/inheritance.html

[ericv8v9s]

You keep giving me references I already agree with...

Yes, if my example was talking about lists in the abstract, and their parameter types were invariant, then indeed list[Food] and list[DogFood] are incompatible. They would have nothing to do with each other.

But that's not the case. In feed_animals(self, bucket: list[Food]), I'm using the bucket strictly to put stuff into it, same way the parameters of a Callable object can only go in.

Those Callable object are the feed functions that were used as arguments to feed_animals a few examples ago. If we write out the types for those feed functions in Java, it would look like

class Food {}
class DogFood extends Food {}

// Java's Callable[..., None]
Consumer<? super Food> feed_food = (food) -> {};
Consumer<? super DogFood> feed_dog_food = (food) -> {};

// feed_food = feed_dog_food;  // does not compile: incompatible types
feed_dog_food = feed_food;

We have the wild cards because Java uses use-site variance, and we have to explicitly write out the contravariant property of function parameter types. Python uses declare-site variance, and that property is built in to Callable.

Notice that we can assign feed_food of type Consumer<? super Food> to a variable declared to be Consumer<? super DogFood>, because the latter is a supertype of the former. If you try to assign the other way, the compiler will error.

[mkorpela]

So your main argument is that a callable c1 taking in argument of type A that is a subclass of B is a super class of callable c2 that is taking in argument of type B?

[mkorpela]

You're correct that function parameter types are contravariant. However, it's important to understand what this means. When we say function parameter types are contravariant, it means that if B is a subtype of A, then a function that accepts an A can be replaced with a function that accepts a B (not the other way around). In other words, the function that accepts the more general type is considered the "super type" when comparing functions.

So in the case of feed_any_animal: Callable[[Animal], None] and feed_only_dogs: Callable[[Dog], None], feed_any_animal is the super type of feed_only_dogs. That's because feed_any_animal can replace feed_only_dogs in any code that uses feed_only_dogs without causing a type error.

To understand why, consider the following scenario:

Let's say we have a function that calls feed_only_dogs:

def take_dog_to_dinner(feed_func: Callable[[Dog], None], dog: Dog):
    feed_func(dog)

You can pass feed_any_animal to this function without any issues:

take_dog_to_dinner(feed_any_animal, Dog())

However, if we have a similar function that calls feed_any_animal:

def take_animal_to_dinner(feed_func: Callable[[Animal], None], animal: Animal):
    feed_func(animal)

You can't pass feed_only_dogs to this function if you're planning to feed an animal that's not a Dog:

take_animal_to_dinner(feed_only_dogs, Cat())  # This would be a problem!

In this sense, feed_any_animal can be used anywhere feed_only_dogs can be used, but the reverse is not true. This is why feed_any_animal is a super type of feed_only_dogs.

---

To your analogy about Fruit and Apple, that example is different from the function example because it deals with return types of methods rather than input parameters. When it comes to return types, it's true that they are covariant, meaning that a function returning a B could be replaced with a function returning an A if B is a subtype of A. That's the opposite of what happens with function parameter types, which are contravariant. So it's not accurate to compare a function's input parameters to a function's return type when discussing covariance and contravariance.

[mkorpela]

I'm trying to come up with a counter example.

[mkorpela]

@ericv8v9s this is pretty difficult actually.

[mkorpela]

@ericv8v9s I think you are correct. This is a bug and I was wrong.

[mkorpela]

The list example fails in mypy:

class Food: pass
class DogFood(Food): pass

class AnimalHerd:
	def feed_animals(self, bucket: list[Food]): pass
class DogHerd(AnimalHerd):
	def feed_animals(self, bucket: list[DogFood]): pass

With

❯ mypy foods.py
foods.py:9: error: Argument 1 of "feed_animals" is incompatible with supertype "AnimalHerd"; supertype defines the argument type as "list[Food]"  [override]
foods.py:9: note: This violates the Liskov substitution principle
foods.py:9: note: See https://mypy.readthedocs.io/en/stable/common_issues.html#incompatible-overrides
Found 1 error in 1 file (checked 1 source file)

In this case AnimalHerd could take in something that is not DogFood and the subclass DogHerd should then be able to take that also in.

But this is not the same case as the Callable that you mentioned.

[mkorpela]

The case of the Callable is pretty interesting and to me very special.

Lets say we have a internal field in the AnimalHerd where we store the feed function.

class AnimalHerd:
  feeder: Optional[Callable[[Animal], None]]
  
  def feed_animals(self, feed: Callable[[Animal], None]) -> None:
      ...
      self.feeder = feed

A field is at the same time an input and an output. This makes the type checking on that level different.

Then let's go to the DogHerd.

class DogHerd(AnimalHerd):
   
   @override
   def feed_animals(self, feed: Callable[[Dog], None]) -> None:
       ...
       self.feeder = feed  # This should in my opinion fail in type checking because one could feed none Dogs to it.
       AnimalHerd.feed_animals(self, feed)  # This should in my opinion also fail because the super class might put there none Dogs.

But those failures should be catched on another level and are not related to inheritance and method overrides..

Yep. Mypy gives error for the assignment:
self.feeder = feed

foods.py:18: error: Incompatible types in assignment (expression has type "Callable[[Dog], None]", variable has type "Callable[[Animal], None] | None")  [assignment]
Found 1 error in 1 file (checked 1 source file)

And for the super class method call:
AnimalHerd.feed_animals(self, feed)

foods.py:18: error: Argument 2 to "feed_animals" of "AnimalHerd" has incompatible type "Callable[[Dog], None]"; expected "Callable[[Animal], None]"  [arg-type]

[mkorpela]

I'm marking this as a bug. Thanks @ericv8v9s for explaining this pretty peculiar case!

[mkorpela]

from typing import List

class Animal: pass
class Dog(Animal): pass

class DogConsumer:
    def consume(self, item: Dog) -> None:
        # Do something with the dog
        pass

class AnimalConsumer(DogConsumer):
    def consume(self, item: Animal) -> None:
        # Do something with the animal
        pass


class AnimalHerd:
    animals: List[Animal]

    def eat_herd(self, consumer: AnimalConsumer) -> None:
        for animal in self.animals:
            consumer.consume(animal)

class DogHerd(AnimalHerd):
    dogs: List[Dog]

    def eat_herd(self, consumer: DogConsumer) -> None:
        for dog in self.dogs:
            consumer.consume(dog)

This is ok for Mypy and for overrides. => Callable is a bug.

[ericv8v9s]

I also just tried with the list example. I can't get it to work with the built-in list (mypy says "Variance of TypeVar "T" incompatible with variance in parent type"), but I don't think the issue is specific to Callable either. I managed to define a custom class that behaves the same way:

from typing import TypeVar, Generic
from overrides import override

class Food: pass
class DogFood(Food): pass

T = TypeVar("T", contravariant=True)
class ContraList(Generic[T]):
	pass

class AnimalHerd:
	def feed_animals(self, bucket: ContraList[Food]): pass
class DogHerd(AnimalHerd):
	@override
	def feed_animals(self, bucket: ContraList[DogFood]): pass

Not that a ContraList would be practically useful... But mypy is happy with that, and the @override is not.

[mkorpela]

Started working on this #114