Friday, 2 January 2009

Is a Square a Rectangle?

I pre-ordered the Clojure book today, so I downloaded Clojure and had a peek at something that I know is interesting - "multimethods". I came across the following example statement:

(derive ::square ::rect)

i.e. a Square IS-A Rectangle in the Object-Oriented sense.

This rang a bell for me. Not a nice melodious one, but one that's a little off-key. A good teacher asked some colleagues and me the question "Is a Square a Rectangle?" a few years ago, and the answer wasn't all that clear ti us. But he showed us a realitively easy way to determine to some extent the validity of any IS-A relationship.

I will try and show you this principle by way of actually designing this hierarchy. First we design a simple Rectangle in Ruby:


class RectangleTest < Test::Unit::TestCase
def test_width_height

# Given
r = Rectangle.new(1,1)

# Then
assert_equal 1, r.width
assert_equal 1, r.height

# When
r.width = 5

# Then
assert_equal 5, r.width
assert_equal 1, r.height

# When
r.height = 2

# Then
assert_equal 5, r.width
assert_equal 2, r.height

end
end


If you think it's strange that I use a test as a design, I suggest you read this. I'm not even going to show the implementation since it's so simple. Next we will design our Square class:


class SquareTest < Test::Unit::TestCase
def test_width_height

# Given
s = Square.new(3)

# Then
assert_equal 3, s.width
assert_equal 3, s.height

# When
s.width = 5

# Then
assert_equal 5, s.width
assert_equal 5, s.height

# When
s.height = 2

# Then
assert_equal 2, s.width
assert_equal 2, s.height

end
end


And you can see that we make sure that when either the width or height has been set, we get the same value for both the width and height respectively. The same goes for the single-parameter constructor. Again, the implementation is trivial. 

Now, you might think that this design is OK, but it's not. We have to ensure that our inheritance doesn't break the Liskov Substritution Principle.

From Wikipedia:
"Liskov's notion of 'subtype' is based on the notion of substitutability; 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)."

This means that for our designs, the unit test for the Rectangle should pass when I substitute the Rectangle instance with a Square instance. Will it? No it won't. Because in the rectangle test, we ensure that when the width is set, the height is not affected, and vice versa. Using a Square instance here will break the test.

Another way of looking at it is to think of the contract of the setters, and the pre and post conditions of those contracts. According to the Liskov princple, (again, from Wikipedia):
  • Preconditions cannot be strengthened in a subclass.
  • Postconditions cannot be weakened in a subclass.
If we design the Square to force the width to be set when setting the height (and vice versa), we are weakening the postconditions of the Rectangle methods. I.e. the post condition that states that either the width or height should not be altered when setting the height or width respectively has been weakened.

In conclusion, here we have a Square that is NOT a Rectangle. The lesson to be learnt is that (unfortunately for us), IS-A in the real world or other domains does not necessarily imply IS-A in the OO world! 

P.S. If you remove the setters from the Rectangle, and only allow the fields to be set during construction, there is no violation of the Liskov Substitution Principle :)

14 comments:

Jonas Bandi said...

I think the order of your code examples is backwards. From the explanation I think RectangleTest should come first followed by SquareTest...

Benjamin Nortier said...

Argh! Thanks, you're right. I've fixed the order. I was struggling with the way Blogger decides to destroy my formatting, copy andpasting all over the place...

Skene said...

Hi Ben,

Interesting blog, but I think some clarification is in order. The reason that your square is not the same as your rectangle is that you have added a notion of behaviour that has nothing to do with the geometric concept of square and rectangle. In geometry, there is no notion of changing the width of a shape. If you do, you simply have another shape which is non-identical with the original, i.e. a new shape. Consequently, I think that these primatives would be better modelled using immutable objects, like Java's String class. Whether this is doable in Clojure is unknown to me.

Cheers,
James Skene

Benjamin Nortier said...

@James

Hmmm, that's a very interesting observation! Yes, I agree with you.

It's the shape-changing behaviour that creates the problem. If you removed the shape-changing behaviour, then the inheritance holds.

Your suggestion for immutable objects could very well be a better idea. I'm not trying to comment on the quality of the design, but on the correctness... :)

alexey-rom said...

It is both possible and normal to have immutable objects in Clojure, so this example may well be correct.

keithb said...

James is right that having immutable objects fixes this. Another win for the "functional" style of programming.

We can also look at this as a failure of information hiding: putting in the mutation reveals too much about how these objects are implemented such that they can answer questions like "what is your width".

If we concentrate on what questions an object has to answer in order to be useful in our system, rather than on what "it" "is" then a lot of these issues go away.

Dean said...

Yea, we teach this example a lot in our OO design courses, as it's a great example of the Liskov substitution principle, especially the fact that what's "true" depends on the "contract" between clients and the classes. In this case, if the "contract" allows mutability, then the "is a" relationship doesn't work, BUT if shapes are immutable, then the intuition that a square is a rectangle passes the tests. It's also a great example of using tests as your specifications.

unclebobmartin said...

So, who wants a Rectangle class without a setHeight and setWidth method?

In any case, if you make the objects immutable, you still have the problem that the square inherits too many data variables and functions with names that don't make a lot of sense.

So making the objects immutable only solves one of a plethora of symptoms.

Moral: Class Square is not a square, it's a class. Class Rectangle is not a rectangle, it's a class. A Square is a rectangle, but the class Square is not a class Rectangle.

Or to say this another way, relationships between entities are not shared between the representatives of those entities. The two lawyers representing the parties in a divorce are not themselves getting divorced. Class Rectangle represents a geometric rectangle. Class Square represents a geometric square. The fact that a square is a rectangle does not mean that their respresentatives share the same ISA relationship.

Benjamin Nortier said...

@James

The guys on Reddit like your comment :)
http://www.reddit.com/r/programming/comments/7pe20/21st_century_code_works_is_a_square_a_rectangle/

Paul E Davis said...

Mathematically a square is a rectangle too
:-)
It's a polygon that is "also" a square.

Anyway, very interesting post.

Dantelope said...

It seems that the problem here is the test itself.

A rectangle is a four-sided shape with two sets of equal-length sides and right angles all around.

Since your class does not appear to participate in angular stories, you are left with the length questions.

Since your class specifies one set as "width" and the other as "height", you are left to check these.

However, there is no real test here. Since a rectangle is fully defined by your properties, the only real test for the rectangle is "are the height and width positive integers?". To test whether you can change the length and width and that it sticks is really testing the getters and setters which, if not too trivial for your purposes, must be checked only with immutable objects as indicated in a previous comment -- and the only reason you'd know this is because you know there are subtypes of a rectangle which do not follow this rule.

With the square, you can check that the length and width are equal at all time. Since the setters are undoubtedly going to fix the sides to be all equilateral, it makes sense to test them. And in this case, no immutability is necessary, although should probably be done so for consistency.

DerHeiligste said...

It's possible to reproduce exactly the same problem with immutable squares and rectangles. Let Square and Rectangle be immutable, and replace the setWidth and setHeight methods with withWidth and withHeight methods that return new Rectangles and Squares. A reasonable implementation of Square.withWidth should return another square, so we'd still be breaking the LSP.

dibblego said...

Remove mutability and your point falls to pieces. Consider that for a moment and a bit more. Try to rephrase your point without resorting to mutability.

Notice how a square is indeed a rectangle and there is no convolution about this matter?

dibblego said...

Sorry I hadn't read the comments and realised that others had made a similar point followed by misunderstanding.

What is really happening is a confusion between identity and equivalence.

By the way, who wants a rectangle without setWidth? Skilled programmers, that's who. Take a look at a pure functional language.