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?

  • 1
    Only the developer who "made the sacrifice" could tell you why. – Robert Harvey Sep 27 '16 at 22:56
  • 5
    It's a principle, not a <deleted> law. – David Hammen Sep 27 '16 at 23:48
  • 2
    I'm with @David Hammen. Should we scrap Python cause it violates one of the more "fine print" aspects of the LSP? Many language designers (see Java Collections) chose to violate strict LSP so they could get work done. – user949300 Sep 28 '16 at 1:10
  • 1
    @user949300 There is an ocean of difference between scrapping Python and asking why a specific choice was made that seems to go against common wisdom. – gardenhead Sep 28 '16 at 2:44
up vote 10 down vote accepted

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.

  • 2
    That entire paragraph is the documentation for d[key]. You don't get to stop reading at the first period just because they didn't phrase it as "does x unless y then does z" – StarWeaver Sep 28 '16 at 0:59
  • 2
    @gardenhead, on what criteria is __missing__ part of the implementation instead of the interface? – Winston Ewert Sep 28 '16 at 2:05
  • 3
    You could still assume a KeyError will be raised if a queried element doesn't exist; defaultdict just makes sure that condition never exists in its world. – Blrfl Sep 28 '16 at 9:26
  • 3
    to rephrase what @Blrfl said: a default dict always contains the keys you ask it about. – Caleth Sep 28 '16 at 16:01
  • 4
    Good lord. I had no idea you could practice language law in the context of Python until now. – Josh Caswell Sep 28 '16 at 17:16

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.

  • “who would write such code” — People use except KeyError on a regular basis though it's not correct as @Christophe explained. – Vadim Pushtaev Sep 28 '16 at 7:46
  • 1
    @Christophe referred to the docs that said a dict subclass may override __missing__ to change the behavior when the key you look for is not in the dictionary. This means that using except KeyError: to check whether or not the dictionary contains the item is incorrect, since a subclass(like defaultdict) may decide to change that behavior. However, people don't(at least they shouldn't) use expect KeyError: for this purpose - if they want to check the existence they have the in operator. – Idan Arye Sep 28 '16 at 13:34
  • When people use KeyError it's not to check for the existence, but to specify the behavior when the key is missing. "Get the value for that key and do X with it, but if that key is not in the dictionary do Y instead". defaultdict should not break that code. True, it won't do Y, but it will return a default value that will be used when doing X. – Idan Arye Sep 28 '16 at 13:34
  • I'm pretty sure I saw except KeyError where x in d should be for dozens of times. – Vadim Pushtaev Sep 28 '16 at 13:44
  • 1
    There should be a limit to how much effort one has to make to be compatible with crappy code... – Idan Arye Sep 28 '16 at 14:07

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.

  • Downvoter care to share? – gardenhead Sep 28 '16 at 2:41

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.