The Liskov Substitution Principle (LSP) in duck typed programming languages

November 8, 2010 at 10:16 am 2 comments


This article is the follow up to a Twitter conversation in which at least @johanneslink, @jasongorman, @leiderleider and @berndschiffer were involved. The question was if the Liskov Substitution Principle would apply if you don’t use inheritance. I had to stop participating in the Twitter conversation since 140 character messages are just too short to explain my point of view. Here is the longer version:

The Liskov Substitution Principle
The Liskov Substitution Principle (LSP): “[…] states that, if S is a subtype of T, then objects of type T in a computer program may be replaced with objects of type S (i.e., objects of type S may be substituted for objects of type T), without altering any of the desirable properties of that program (correctness, task performed, etc.).” (Source: Wikipedia).
The more formal definition of the LSP is: “Let q(x) be a property provable about objects x of type T. Then q(y) should be true for objects y of type S where S is a subtype of T.” (Source: Wikipedia).
And to be complete, here is the definition of subtype: “In programming language theory, subtyping or subtype polymorphism is a form of type polymorphism in which a subtype is a datatype that is related to another datatype (the supertype) by some notion of substitutability, meaning that program constructs, typically subroutines or functions, written to operate on elements of the supertype can also operate on elements of the subtype.” (Source: Wikipedia).

While subtype and LSP sound similar, there is a difference: The subtype relation normally is interpreted as a syntactical property. If the required methods are available on an object, everything is valid. The Liskov Substitution Principle goes beyond that and adds a requirement on the semantics of the methods.

Example (in pseudo code)

class A {

    public void m() { ... do something ... }

}

class B extends A {

    public void m() { 
        throw new Exception();
    }

}

In this case B is a subtype of A. B has the same methods as A. But the LSP may be violated. If the clients of A expect m to not throw an exception, B’s implementation of m breaks the LSP. Regarding the formal definition of the LSP (“Let q(x) be a property provable about objects x of type T.”). The property q would be that the execution of m won’t throw an exception. This property is true for A’s implementation of m but not for B’s implementation of m. Therefore you shouldn’t use objects of class B where a client expects objects of class A. While that would be syntactically correct it isn’t semantically valid.

The Liskov Substitution Principle in class typed languages
In most statically typed object-oriented languages (like C++, Java, C#) the subtype relation is defined by inheritance between classes. When a class B inherits from a class A the defined type B is a subtype of A. The example above showed that the LSP may be violated due to specific method implementations provided by B.
Some languages (like Java) provide an interface concept. Interfaces only define the signature of methods but don’t provide method implementations. Classes implement interfaces and provide the method implementations. With interfaces the LSP is still a useful concept. The clients of an Interface C rely on a certain behaviour of the objects implementing the interface. Again the clients of C may assume that m won’t throw exceptions.

interface C {

    public void m();

}

class A implements C {

    public void m() {
        throw new Exception();
    }

}

In the example code A’s implementation of m will break the LSP.

These situations are clear and well understood. But what happens in programming languages with duck typing (like Ruby)?

The Liskov Substitution Principle in duck typed languages
In programming languages with duck typing (e.g. Ruby, Python, Smalltalk) classes don’t really define types. There is no type checking when assigning objects to variables or passing objects as method arguments. There is a kind of type checking when a method is called. It is checked that the method exists with a matching number of parameters.
Since classes don’t define types, inheritance in duck typed languages has nothing to do with the subtype relation or the LSP.
In a way clients define interfaces in an implicit way. Let’s look at an example:

def my_method1(a) do
    a.m1()
    a.m2()
    my_method2(a)
end

def my_method2(a) do
  a.m3()
end

Calling my_method1 with an object a will succeed if the object a provides the three methods m1, m2 and m3. This is the implicit interface the object a needs to implement. And with this implicit interface comes the clients expectation about the behaviour of m1, m2 and m3. That’s just the same as with the Java interface. If an object b provides m1, m2 and m3 but doesn’t fit the expected behaviour, the LSP is violated.

Conclusion
The LSP isn’t tied to inheritance or class based typing. It applies to duck types languages as well as to systems without inheritance. LSP is a concept that applies to all kinds of polymorphism. Only if you don’t use polymorphism of all you don’t need to care about the LSP.

Entry filed under: #. Tags: .

ScrumBut auf den XP-Days Germany Train the Trainers: “Training from the back of the room”

2 Comments Add your own

  • […] This post was mentioned on Twitter by Stefan Roock, Florian. Florian said: Summed up my thoughts very nicely!😉 @stefanroock blogged about Liskov Substitution Principle in duck typed languages: http://bit.ly/bxcvDh […]

  • 2. Paul King  |  November 8, 2010 at 11:56 am

    I would argue that LSP may even be of interest where no explicit polymorphism is apparent. When working out what allowable refactorings I may apply to a program which will allow it to work on all existing input data, the usual ideas about weaker pre and stronger post still apply. They give me the guidance that I need to make the refactorings. In some sense, the new program is a polymorphic variation of the old one but I may have no apparent polymorphism in either program.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed



%d bloggers like this: