Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Do I understand correctly that Liskov Substitution Principle cannot be observed in languages where objects can inspect themselves, like what is usual in duck typed languages?

For example, in Ruby, if a class B inherits from a class A, then for every object x of A, x.class is going to return A, but if x is an object of B, x.class is not going to return A.

Here is a statement of LSP:

Let q(x) be a property provable about objects x of type T. Then q(y) should be provable for objects y of type S where S is a subtype of T.

So in Ruby, for example,

class T; end
class S < T; end

violate LSP in this form, as witnessed by the property q(x) = x.class.name == 'T'


Addition. If the answer is "yes" (LSP incompatible with introspection), then my other question would be: is there some modified "weak" form of LSP which can possibly hold for a dynamic language, possibly under some additional conditions and with only special types of properties.


Update. For reference, here is another formulation of LSP that I've found on the web:

Functions that use pointers or references to base classes must be able to use objects of derived classes without knowing it.

And another:

If S is a declared subtype of T, objects of type S should behave as objects of type T are expected to behave, if they are treated as objects of type T.

The last one is annotated with:

Note that the LSP is all about expected behaviour of objects. One can only follow the LSP if one is clear about what the expected behaviour of objects is.

This seems to be weaker than the original one, and might be possible to observe, but I would like to see it formalized, in particular explained who decides what the expected behavior is.

Is then LSP not a property of a pair of classes in a programming language, but of a pair of classes together with a given set of properties, satisfied by the ancestor class? Practically, would this mean that to construct a subclass (descendant class) respecting LSP, all possible uses of the ancestor class have to be known? According to LSP, the ancestor class is supposed to be replaceable with any descendant class, right?


Update. I have already accepted the answer, but i would like to add one more concrete example from Ruby to illustrate the question. In Ruby, each class is a module in the sense that Class class is a descendant of Module class. However:

class C; end
C.is_a?(Module) # => true
C.class # => Class
Class.superclass # => Module

module M; end
M.class # => Module

o = Object.new

o.extend(M) # ok
o.extend(C) # => TypeError: wrong argument type Class (expected Module)
share|improve this question
2  
Almost all modern languages provide some degree of introspection, so the question is not really specific to Ruby. –  Joachim Sauer Jul 30 '12 at 10:13
    
I understand, i gave Ruby just as an example. I do not know, maybe in some other languages with introspection there are some "weak forms" of LSP, but, if i understood the principle correctly, it is incompatible with introspection. –  Alexey Jul 30 '12 at 10:29
    
I've removed "Ruby" from title. –  Alexey Jul 30 '12 at 10:42
2  
The short answer is they're compatible. Here's a blog post that I mostly agree with: Liskov Substitution Principle for Duck Typing –  K.Steff Jul 30 '12 at 15:06
2  
@Alexey Properties in this context are invariants of an object. For example, immutable objects have the property that their values do not change. If you look at good unit tests, they should test exactly for these properties. –  K.Steff Jul 30 '12 at 15:23

6 Answers 6

up vote 26 down vote accepted

Here's the actual principle:

Let q(x) be a property provable about objects x of type T. Then q(y) should be provable for objects y of type S where S is a subtype of T.

And the excellent wikipedia summary:

It states that, in a computer program, if S is a subtype of T, then objects of type T 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.).

And some relevant quotes from the paper:

What is needed is a stronger requirement that constrains the behavior of sub-types: properties that can be proved using the specification of an object’s presumed type should hold even though the object is actually a member of a subtype of that type...

A type specification includes the following information:
- The type’s name;
- A description of the type's value space;
- For each of the type's methods:
--- Its name;
--- Its signature (including signaled exceptions);
--- Its behavior in terms of pre-conditions and post-conditions.

So on to the question:

Do I understand correctly that Liskov Substitution Principle cannot be observed in languages where objects can inspect themselves, like what is usual in duck typed languages?

No.

A.class returns a class.
B.class returns a class.

Since you can make the same call on the more specific type and get a compatible result, LSP holds. The issue is that with dynamic languages, you can still call things on the result expecting them to be there.

But let's consider a statically, structural (duck) typed language. In this case, A.class would return a type with a constraint that it must be A or a subtype of A. This provides the static guarantee that any subtype of A must provide a method T.class whose result is a type that satisfies that constraint.

This provides a stronger assertion that LSP holds in languages that support duck typing, and that any violation of LSP in something like Ruby occurs more due to normal dynamic misuse than a language design incompatibility.

share|improve this answer
1  
"Since you can make the same call on the more specific type and get a compatible result, LSP holds". LSP holds if the results are identical, if i understood it correctly. Maybe there can be some "week" form of LSP with respect to given constraints, requiring instead of all properties that only the given constraints be satisfied. In any case, i would appreciate any reference. –  Alexey Jul 30 '12 at 13:11
    
@Alexey edited to include what LSP means. If I can use B where I expect A, then LSP holds. I'm curious how you think Ruby's .class possibly violates that. –  Telastyn Jul 30 '12 at 13:21
    
Telastyn, thank you for the edit, but can you please give me a reference other than Wikipedia summary, which goes there even before the actual one-line definition? The .class in Ruby violates LSP because, if your program contains, for example fail unless x.class == A, it will pass for x of class A, but fail for x of class B. –  Alexey Jul 30 '12 at 13:32
3  
@Alexey - If your program contains fail unless x.foo == 42 and a subtype returns 0 that's the same thing. This isn't a failure of LSP, it's the normal operation of your program. Polymorphism isn't a violation of LSP. –  Telastyn Jul 30 '12 at 13:44
6  
@Alexey: if you write something that depends on x.class == A, then it is your code that violates LSP, not the language. It is possible to write code that violates LSP in almost every programming language. –  Andres F. Jul 30 '12 at 17:42

In the context of LSP a "property" is something that can be observed on a type (or an object). In particular it talks about a "provable property".

Such a "property" could the existence of a foo() method that has no return value (and follows the contract set in its documentation).

Make sure you don't confuse this term with "property" as in "class is a property of every object in Ruby". Such a "property" can be a "LSP property", but it's not automatically the same!

Now the answer to your questions depends a lot on how stringent you define "property". If you say "the property of class A is that .class will return the type of the object", then B actually does have that property.

If, however, you define the "property" to be ".class returns A", then obviously B does not have that property.

However, the second definition isn't very useful, as you've essentially found a round-about way to declare a constant.

share|improve this answer
    
I can only think of one definition of a "property" of a program: for a given input it returns a given value, or, more generally, when used as a block in another program, that other program for a given input will return a given values. With this definition, i do not see what it means that ".class will return the type of the object". If it means that x.class == x.class, this is not an interesting property. –  Alexey Jul 30 '12 at 10:23
1  
@Alexey: I've updated my question with a clarification on what "property" means in the context of LSP. –  Joachim Sauer Jul 30 '12 at 11:03
2  
@Alexey: looking into the paper I don't find a specific definition or "property". That's probably because the term is used in the general CS sense "something that can be observed/proven about some object". It has nothing to do with the other meaing "a field of an object". –  Joachim Sauer Jul 30 '12 at 11:47
4  
@Alexey: I don't know what more I can tell you. I use the definition of "a property is some quality or attriute of an object". "color" is a property of a physical, visible object. "density" is a property of a material. "having a specified method" is a property of a class/object. –  Joachim Sauer Jul 30 '12 at 12:13
3  
@Alexey: I think you're throwing baby with the bathwater: Just because for some properties the LSP can't be made to hold doesn't mean that it's useless or "doesn't hold in any language". But that discussion would go to far here. –  Joachim Sauer Jul 30 '12 at 12:22

As I understand it, there's nothing about introspection that would be incompatible with the LSP. Basically, as long as an object supports the same methods as another, the two should be interchangable. That is, if your code expects an Address object, then it doesn't matter if it's a CustomerAddress or a WarehouseAddress, as long as both provide (e.g.) getStreetAddress(), getCityName(), getRegion() and getPostalCode(). You could certainly create some kind of decorator that takes a different type of object and uses introspection to provide the required methods (e.g., a DestinationAddress class that takes a Shipment object and presents the ship-to address as an Address), but it's not required and certainly wouldn't prevent the LSP from being applied.

share|improve this answer
2  
@Alexey: The objects are "the same" if they support the same methods. This means the same name, same number and type of arguments, same return type and same side-effects (as long as they are visible to the calling code). The methods may behave completely differently, but as long as they honor the contract, that's OK. –  TMN Jul 30 '12 at 13:27
1  
@Alexey: but why would I have such a contract? What actual use does that contract fulfill? If I had such a contract I could simply replace every occurance of x.class.name with 'A' , effectively making x.class.name useless. –  Joachim Sauer Jul 30 '12 at 14:09
1  
@Alexey: again: just because you can define a contract that can't be fullfilled by extending another class doesn't break LSP. It just means you've build an un-extendable class. If I define a method to "return if the provided code block ends in finite time" then I also have a contract that can't be fulfilled. It doesn't mean that programming is useless. –  Joachim Sauer Jul 30 '12 at 14:34
2  
@Alexey trying to determine if x.class.name == 'A' is an anti-pattern in duck typing: after all, duck typing comes from "If it quacks and walks like a duck, it's a duck". So if it behaves like A and honors the contracts that A put forth, it's an A instance –  K.Steff Jul 30 '12 at 15:02
1  
@Alexey You've been presented with clear definitions. An object's class isn't part of its behavior or contract or whatever you want to call it. You are equivocating "property" with "object field, such as x.myField", which as has been pointed out, it is NOT the same. In this context, a property is more like a mathematical property, like type invariants. Furthermore, it's an anti-pattern to check for the exact type if you want duck typing. So, what is your problem with LSP and duck typing, again? ;) –  Andres F. Jul 30 '12 at 21:13

To quote Wikipedia's article on LSP, "substitutability is a principle in object-oriented programming." It is a principle and part of the design of your program. If you write code that depends on x.class == A, then it is your code that is violating LSP. Note this kind of broken code is also possible in Java, no duck typing necessary.

Nothing in duck typing inherently breaks LSP. Only if you misuse it, as in your example.

Additional thought: doesn't explicitly checking for an object's class defeat the purpose of duck typing, anyway?

share|improve this answer
    
Andres, can you give your definition of LSP, please? –  Alexey Jul 30 '12 at 18:15
1  
@Alexey The precise definition of LSP is stated in Wikipedia in terms of subtypes. The informal definition is Liskov's notion of a behavioral subtype defines a notion of substitutability for mutable objects; that is, 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 (e.g., correctness).. The exact class of an object is NOT one of "the desirable properties of the program"; otherwise it would run contrary to not only duck typing but of subtyping in general, Java's flavor included. –  Andres F. Jul 30 '12 at 18:34
2  
@Alexey Also note that your example of x.class == A violates both LSP and duck typing. No sense in using duck typing if you're going to check for the actual types. –  Andres F. Jul 30 '12 at 18:35
    
Andres, this definition is not precise enough for me to understand. Which program, a given one, or any? What is a desirable property? If the class is in a library, different applications may consider different properties desirable. A do not see how the line of code could violate LSP, because i thought that LSP was a property of a pair of classes in a given programming language: either (A, B) satisfy LSP or not. If LSP depends on the code used elsewhere, it is not explained what code is allowed. I hope to find something here: cse.ohio-state.edu/~neelam/courses/788/lwb.pdf –  Alexey Jul 30 '12 at 19:05
2  
@Alexey LSP holds (or doesn't) for a specific design. It is something to look for in a design; it's not a property of a language in general. It doesn't get any more precise than the actual definition: Let q(x) be a property provable about objects x of type T. Then q(y) should be provable for objects y of type S where S is a subtype of T. It's obvious that x.class is not one of the interesting properties here; otherwise Java's polymorphism wouldn't work either. There is nothing inherent to duck typing in your "x.class problem". Do you agree so far? –  Andres F. Jul 30 '12 at 19:40

After looking through Barbara Liskov's original paper, I've found how to complete the Wikipedia definition so that LSP indeed could be satisfied in almost any language.

First of all, the word "provable" is important in the definition. It is not explained in the Wikipedia article, and "constraints" are mentioned elsewhere without reference to it.

Here is the first important quote from the paper:

What is needed is a stronger requirement that constrains the behavior of sub-types: properties that can be proved using the specification of an object’s presumed type should hold even though the object is actually a member of a subtype of that type...

And here is the second, explaining what a type specification is:

A type specification includes the following information:

  • The type’s name;
  • A description of the type's value space;
  • For each of the type's methods:
    • Its name;
    • Its signature (including signaled exceptions);
    • Its behavior in terms of pre-conditions and post-conditions.

So, LSP only makes sense with respect to given type specifications, and for an appropriate type specification (for the empty one for example), it can be satisfied in probably any language.

I consider Telastyn's answer to be the closest to what I was looking for because the "constraints" were mentioned explicitly.

share|improve this answer
    
Telastyn, if you could add these quotes to your answer, i would prefer to accept yours than my own. –  Alexey Jul 31 '12 at 17:55
2  
the markup isn't quite the same, and I changed a little of the emphesis, but the quotes were included. –  Telastyn Jul 31 '12 at 19:24
    
Sorry, Joachim Sauer already mentioned "provable" properties, which you disliked. In general, you've merely restated existing answers. Honestly, I don't know what you're looking for... –  Andres F. Jul 31 '12 at 23:36
    
No, it was not explained "provable from what?". The property x.class.name = 'A' is provable for all x of class A if you allow too much knowledge. The type specification was not defined, and its exact relation with LSP was not either, though informally some indications were given. I have already found what i was looking for in Liskov's paper and answered my question above. –  Alexey Jul 31 '12 at 23:47

In short no. In your example x has a property "class", but the result of x.class is a value. There is a difference, it's the same one as with variables and values and pointers, the map is not the territory.

Suppose you have a class Door, which contains a property Width, and two subtypes; LargeDoor and SmallDoor. LargeDoor has a Width of 48, SmallDoor has a Width of 36 and for the base class it picks a random value when instantiated.

If your program checks for width and does nothing when it is less than 48, that does not mean the object fails the LSP -- how could it, the base object itself could fail!

share|improve this answer
    
Whether your example fails LSP or not depends, in general, on the Door class specification. It is possible that it never fails, because a random attribute is a rather special kind of an attribute, and maybe it is formally impossible to state a post-condition that the width is random. With Ruby class method/attribute there is no such issue: one can state a post-condition for class that, when combined with name afterwards, it returns the string 'A'. In the syntax of Liskov's paper, it would be something like class = proc() returns(Class) ensures result.name = 'A'. –  Alexey Aug 1 '12 at 8:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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