Circle-ellipse problem

From Wikipedia, the free encyclopedia

 This article does not cite any references or sources. (January 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

The circle-ellipse problem in software development (sometimes known as the square-rectangle problem) illustrates a number of pitfalls which can arise when using subtype polymorphism in object modelling. The issues are most commonly encountered when using object-oriented programming.

The problem concerns what subtyping/inheritance relationship should exist between classes which represent circles and ellipses. More generally, the problem illustrates the difficulties which can occur when a base class contains methods which mutate an object in a manner which might invalidate a (stronger) invariant found in a derived class, causing the Liskov substitution principle to be violated.

The existence of the circle-ellipse problem is sometimes used to criticize object-oriented programming. It may also imply that hierarchical taxonomies are difficult to make universal, implying that situational classification systems may be more practical.


Contents

[edit] The problem

It is a central tenet of object-oriented analysis and design that subtype polymorphism, which is implemented in most OO languages via inheritance, should be used to model object types which are subsets of each other; this is commonly referred to as the is-a relationship. In the present example, the set of circles is a subset of the set of ellipses; circles can be defined as ellipses whose major and minor axes are the same length. Thus, code written in an OOPL which models shapes will frequently choose to make class Circle as a sub-class of class Ellipse, i.e. inheriting from it.

If the classes are immutable, there is no problem with this state of affairs. Circles satisfy all invariants of ellipses; and an (immutable) circle can be used in any context where an immutable ellipse is expected. The relationship satisfies the Liskov substitution principle. Ellipse could have a method stretchX (integer Factor) which alters the length of one of its axes, but not the other, and returns the result in a new Ellipse object. This would cause no problem for Circle::stretchX, as it could return a new Ellipse just as the Ellipse::stretchX does (whilst remaining unaltered itself).

But some OO designs encourage the use of mutators, methods which modify instances of the class. A sub-class has to provide support for all behaviour supported by the super-class; subclasses must implement any mutators defined in a base class. In the present case, the method Ellipse::stretchX alters the length of one of its axes in place. If Circle inherits from Ellipse, it must also have a method stretchX, but the result of this method would be to change a circle into something which is no longer a circle. The Circle class can not simultaneously satisfy its own invariant, and the behavioral requirements of the Ellipse::stretchX method.

A related problem with this inheritance arises when we consider the implementation. An ellipse requires more state to describe than a circle does, as the former needs attributes to specify the length and rotation of the major and minor axes; whereas a circle needs only a radius. It may be possible to avoid this if the language (such as Eiffel) makes constant values of a class, functions without arguments and data members interchangeable.

Some authors have suggested reversing the relationship between circle and ellipse, on the grounds that an ellipse is a circle with additional capabilities. Unfortunately, ellipses fail to satisfy many of the invariants of circles; if Circle has a method radius, Ellipse will now have to provide it as well.

The problem is sometimes expressed in statements such as "a Circle is not a sort of Ellipse". This looks confusingly like the absurd "a circle is not a sort of ellipse", and sounds identical, so it is unhelpful. What is actually meant is "an OO-model of a circle should not be a sort of OO-model of an ellipse".

[edit] Analysis

The problem arises when a super-class's methods are incompatible with a sub-class's. For example, parameters of method stretch(X,Y) of Ellipse do not need to have the same values, but X!=Y is not acceptable for class Circle.

Indeed, a circle is a special ellipse in which the two foci coincide (i.e., are the same point), thus intuitively the class Circle is usually designed as sub-class of the class Ellipse. However, the usage-incompatible methods will cause unexpected results.

For example, if there is another method flatten(rate) of class Ellipse:

Ellipse::flatten(rate){
   stretch(1,1/rate);
}

Since Circle is sub-class of Ellipse, it should be able to "flatten". But after "flatten", the circle object is no longer circle, thus will fail at the circle-specific methods such as Circle::getRadius().

[edit] Possible solutions

One may solve the problem by changing one's model, or perhaps using a different language, which could be a (not yet implemented) extension of an existing language or use a different paradigm. Exactly which option is appropriate will depend on who wrote Circle and who wrote Ellipse. If the same author is designing them both from scratch, then they will be able to define the interface to handle this situation. If the Ellipse object was already written, and cannot be changed, then the options are more limited.

[edit] Change the model

[edit] Return success or failure value

Allow the objects to return a 'success' or 'failure' value for each modifier. This is usually done in the case of file I/O, but can also be helpful here. Now, Ellipse.stretchX works, and returns 'true', while Circle.stretchX simply returns 'false'. This is in general good practice, but may require that the original author of ellipse anticipated such a problem, and defined the mutators as returning a value.

Alternately, Circle.stretchX could throw an exception (but depending on the language, this may also require that the original author of ellipse declare that it may throw an exception).

[edit] Return the new value of X

This is a similar solution to the above, but is slightly more powerful. Ellipse.stretchX now returns the new value of its X dimension. This is more powerful because it also allows the Ellipse class to limit its X dimension to a maximum if it wants. Now, Circle.stretchX simply returns its current radius.

[edit] Maintain the aspect ratio

If the interface definition for Ellipse states only that "stretchX modifies the X axis", and does not state "and nothing else will change", then Circle could simply force the X and Y dimensions to be the same. Circle.stretchX and Circle.stretchY both modify both the X and Y size.

Circle::stretchX(x) {xSize = ySize = x;}
Circle::stretchY(y) {xSize = ySize = y;}

[edit] Convert the Circle into an Ellipse

If Circle.stretchX is called, then Circle changes itself into an Ellipse. This may be dangerous, however, if some other function is expecting it to be a Circle. Both classes must also be the same size.

[edit] Limit the interfaces

In some cases it may be possible to argue that not all theoretically defined methods are necessary. This is only applicable in a limited number of cases, and makes re-use of the model harder.

[edit] Make all instances constant

One can change the model so that instances of the classes represent constant values (i.e. they are immutable). This is exactly the implementation that is used in purely functional programming.

In this case methods such as stretchX must be changed to yield a new instance, rather than modifying the instance they act on. This means that it is no longer a problem to define Circle.stretchX, and the inheritance reflects the mathematical relationship between circles and ellipses.

A disadvantage is that changing the value of an instance then requires an assignment, which is inconvenient and prone to programming errors, e.g.
Orbit(planet[i]) := Orbit(planet[i]).stretchX.

A second disadvantage is that such an assignment conceptually involves a temporary value, which could reduce performance and be difficult to optimise.

[edit] Factor out modifiers

One can define a new class MutableEllipse, and put the modifiers from Ellipse in it. The Circle only inherits queries from Ellipse.

This has a disadvantage of introducing an extra class where all we really want to do is specify that Circle does not inherit modifiers from Ellipse.

[edit] Impose pre-conditions on modifiers

One can specify that Ellipse.stretchX is only allowed on instances satisfying Ellipse.stretchable, and will otherwise throw an exception.

This allows us to implement Circle.stretchX, but makes it harder to check at compile-time that calls will be valid at run-time. It also introduces methods whose sole purpose is to solve this problem, which makes the model less clear.

[edit] Drop all inheritance relationships

This solves the problem at a stroke, and may sometimes be a reasonable approach.

The disadvantage is that one can no longer use circles where ellipses are expected.

However, an acceptable workaround may be to add a method Circle.toEllipse() which would instantiate and return a mutable ellipse object using the circle's current state. The caveat is that mutations performed on this new ellipse would not affect the original circle, and vice versa.

[edit] Change the language

Some of the above approaches suggest proposals to modify OO languages.

[edit] Support the value/variable distinction

One could change the language so that all methods must be defined to provide new values, a sort of value-oriented programming.

An essential part of the OO approach is, however, that variables can refer to different instances, and instances can take on different values. This suffers from the previously described problem with assignments, so it is desirable to have a compact way of expressing modification, e.g. Orbit(planet[i]) :. stretchX.

[edit] Support query-only inheritance

A syntax to specify that a class only inherits the queries of another would obviate the syntactic overhead of the solution Factor out modifiers, e.g. class Circle : const Ellipse .

[edit] Change the paradigm

The most radical approach is to use a different language paradigm, such as a functional language, where there are no variables, and the problem cannot arise.

Not many functional languages support inheritance/sub-typing.[citation needed] A discussion of the relative advantages and disadvantages of OO and functional languages would exceed the remit of this article.

[edit] See also

[edit] External links