Does Python's defaultdict violate the LSP?

Question

I believe, in Python defaultdict inherited from dict violates Liskov Substitution Principle. defaultdict doesn't raise KeyError while x in d is still False, for instance.

Is that so? If it is, why developer decided to make such a sacrifice?

Answer 1

At first sight, yes

At first sight it seems to violate the Liskov Substitution Principle:

If S is a subtype of T, then objects of type T in a program may be replaced with objects of type S without altering any of the desirable properties of that program

If you have a program written for a dict dictionary, that should look for words read in a stream, and do something if the words are not found (aka KeyError occurs), the same program would not work with a defaultdict because this would never cause a KeyError to happen (which is an expected invariant for dict).

Here we could open a debate, that only the Python designers could close:

• To be fully compliant with the LSP, they should have created an abstract_dict that defines the shared interface, but makes no claim on the behavior in case of a missing key. Then they should have made dict, defaultdict and ordereddict inherit from abstract_dict. You would then use the three types of dictionnary in the same manner, but knowing that they are "sibbligns", you would not expect that they guarantee the same behavior. But you already know that from the current documentation, don't you ?
• As the abstract_dict would not be very useful in the library, and as many of the methods certainly have the same implementation, the designers chose the inheritance. The idea is to reuse an implementation. Of course this kind of reuse violates the LSP. I suppose they have carefully evaluated the risks. But what's the risk for you if you knowingly choose defaultdict, because you prefer working with empty values instead of KeyError ?
• I suppose they have also compared the potential risks with the benefits: if in future, new features would be added to dict, this inheritance model would ensure that defaultdict would remain consistent at a lesser cost.

But in looking in depth, defaultdict is fully LSP compliant

First sights can mislead. In fact semantically speaking a defaultdict is-a dict. Parameters and return values are the same. Behavior is exactly the same for all programs that verify existence of the key (aka key in d) before trying to address it.

Even more, if you look closely at the documentation, for dict, it is said:

d[key]

Return the item of d with key key. Raises a KeyError if key is not in the map.

If a subclass of dict defines a method __missing__() and key is not present, the d[key] operation calls that method with the key key as argument. The d[key] operation then returns or raises whatever is returned or raised by the __missing__(key) call. No other operations or methods invoke __missing__(). If __missing__() is not defined, KeyError is raised. __missing__() must be a method; it cannot be an instance variable:

This means that you can't assume KeyError when you use dict: you have to assume that a different value could be returned or error raised. The claimed invariant is more complex, and it is defined in such a manner that it really covers the behavior of defaultdict.

By the way, defaultdict seems to have its properties by using the __missing__() method. And by the way, if no factory is provided in its constructor, it will raise a KeyError as dict would (see documentation).

So it seems to me that it's fully compliant.

Answer 2

LSP does not mean a subclass should behave exactly like it's superclass in any piece of code that accepts the superclass(and therefore also the subclass). This would make polymorphism much less useful - after all, you subclass because you want to change the behavior. Rather, LSP means that a subclass may replace it's superclass without altering the desired properties of the code that accepts it. In other words, if someone wrote a code that accepts the superclass, it must also work as intended when receiving the subclass.

Now, pragmatism is more important than blindly following best practices. Here is a function that may work on dict but fail on defaultdict with the same values:

def foo(dct):
    try:
        _ = dct[12]
        assert 12 in dct
    except KeyError:
        pass

So in theory the LSP is broken, but pragmatically - who would write such code? Writing a function that works on the superclass but not on it's subclasses is always possible(assert type(arg) == superclass) but that's not the typical code that people write. With dictionaries, you would either:

• Access the member and if it doesn't exist, catch a KeyError and do some other thing. With defaultdict, you simply do the original thing with the default value.
• Check if the member is in the dict. In that case, defaultdict will behave like an ordinary dict.
• Use .get to pick your own default value. Actually, this one is broken in Python2(it'll use the defaultdict's default instead of the one you specified), but in Python3 it again works like a regular dict.

You don't usually use these methods to validate each other - you pick the one that best fits your piece of code and use it. So if your code worked with dict, and you are not intentionally trying to break it for defaultdict - it should also work and do as intended with defaultdict.

Answer 3

Yes, it violates LSP. This is one reason why inheritance (and nominal sub-typing in general) is dangerous: developers usually get it wrong. As for why it was made this way: you'd have to ask the developers.