Circle And Ellipse Problem

Also known as SquareAndRectangleProblem.

If we have an application that uses circles and ellipses (e.g. a graphics program), should we have two classes Circle and Ellipse? Which should inherit from which, if at all? A circle is a special kind of ellipse, viz. one where the two foci coincide. But if an Ellipse is mutable, a Circle is mutable too, and can be made a non-circle.

Or should we only have an Ellipse? But if we then create an Ellipse that happens to represent a circle, we cannot ask it for its radius, because Ellipse has no radius() method.

(If I misrepresented or obfuscated the problem, please reformulate. -- MarnixKlooster)

[I wrote this for SquareAndRectangleProblem, but I'm sure you can live with it]

Is a square a rectangle? Yes, sure. But a rectangle can be a square, so we could run into problems.

The discussion below tries to solve this problem, but it doesn't quite succeed. Because - the real problem is: The view of "a square" and "a rectangle" as objects is the result of a deep-seating CulturalAssumption we are not really aware of. In our western society, we tend to see everything as an object - we call this objectification. Examples are pretty much all abstract concepts. Our languages reflects this: It require us to use nouns, like in It rains. But, as SquareAndRectangleProblem illustrates, from time to time we run into, well, problems. What exactly is this it in it rains? We invent an it, just because our language requires us to do so. The interesting thing is: ObjectOrientedLanguages do that too!

So what is "a square"? Now we can see it as an object, but we don't have to, and let's try to avoid it. What we really want to express is that an object has a certain shape. Or, to avoid the noun and the "is a": Is shaped in a certain fashion. So "being square" and "being rectangular" are really just properties, or states, and not objects. "Being square" implies "being rectangular", but that is really all that puts them in a relationship. No "is a", no "has a".

So this renders the whole SquareAndRectangleProblem discussion pointless? Not at all. It shows that our tendency to objectify has its limitations, and, most importantly, that our natural language doesn't really help in modeling. Because our language itself is already modeled, and seldomly in the most appropriate way.

-- AndreasHaferburg?

I question the degree to which linguistic conventions in the West affect this particular problem in ComputerScience. True, the phrase "it rains" requires a dummy subject in English, where the equivalent phrase in, say, Cantonese, "lohk seui" (literally "down water") does not. But Chinese programmers seem to not have any edge in solving the CircleAndEllipseProblem.

It seems that the CecilLanguage is well suited for solving this problem through its PredicateClasses. Loosely speaking, this is a kind of dynamic inheritance, where an instance can inherit from a class higher or lower in the inheritance graph when its state changes.

In this example, Ellipse would be a regular class, and Circle would be a predicate class. The declaration of Circle would say that any instance of Ellipse also inherits from Circle when the two foci coincide. If the object is in that state it can use all methods from Circle, in addition to those of Ellipse. When it changes states to represent a non-circle, only the Ellipse methods are available.

Obviously, this semantics involves run-time checks. But it allows for a very clear expression of programmer intent.

See http://groups.google.com/group/comp.object/browse_thread/thread/e2564d10b4ba52/28e32827634edb22?lnk=st&q=circle+ellipse+cecil+comp.object&rnum=3&hl=en#28e32827634edb22 and other articles on news:comp.object mentioning Cecil for details.

-- MarnixKlooster

From ValueObjectsShouldBeImmutable:

It is interesting to note that the classic CircleAndEllipseProblem is a variation on the same theme. Ellipses that can be modified really represent the mathematical notion of a family of ellipses rather than a single concrete instance. -- MichaelFeathers

So you seem to be saying: don't create mutable ellipses. But aren't there cases where a mutable ellipse really is the clearest way to express the programmer's intention? -- MarnixKlooster

Mutable ellipses are okay. I'm just saying that there is more than one definition of ellipse and it trips us. The issue is just understanding that they are very different from concrete ellipses and circles.

Imagine a point in space and then imagine, one at a time, all the possible ellipses that can be centered on that point. Now try this for circles. Stepping back for a moment, what can we say are the properties that hold true for all of those instances? I can't think of many other than center position and a bounding rectangle. Perhaps a method that returns the eccentricity. Those things could go in a common base class. For mutable things the properties and methods of the class should work over all instances.

It seems that coming up with properties and methods is a process of figuring out what is immutable in an abstraction. If we have a class which defines concrete ellipses with fixed foci, it is a ValueObject just like a date. Going further, a class definition itself is a ValueObject. It is the fixed part of the abstraction. This is true, except in languages with metaclasses that you can modify. -- MichaelFeathers

ContextSensitiveSubtyping has an answer that says, you can't answer the question until you add more information to the question. -- AlistairCockburn

So, type is a heavily overloaded concept! I think that most of the confusion comes from failing to recognize that the type system of Java (and similar) languages can only model a portion of the concept of 'type' as it is used in human language, or even in its mathematical/logical/philosophical usages.

In common usage, things maintain their identity as they change, and in changing, they may change type, possibly to something unrelated to the previous type. As Michael Feathers points out above, the mathematical point of view is more as though every possible thing exists, immutable and eternal, and change involves replacing one such object with another to create a new context.

Java has a static type system with mutable objects, which is clearly at odds with both points of view. An elliptical object may become circular, but it doesn't become a object of class circle.

The fact is that type safety and polymorphism simply are not entirely compatible. Java offers one valid compromise - just don't expect inheritance with static typing to be able to model everything you mean when you talk about type.

-- AndyRaybould

Read-Only Circle is a subtype of Read-Only Ellipse.
Write-Only Ellipse is a subtype of Write-Only Circle.
Read-Write Circle And Read-Write Ellipses have no typing relationship.
Read-Write Circle is a subtype of both Read-Only Circle and Write-Only Circle
- and hence Read-Only Ellipse.
Read-Write Ellipse is a subtype of both Read-Only Ellipse and Write-Only Ellipse
- and hence Write-Only Circle.

Note that the first relationship is the only one that would be relevant in Maths or a functional OOP language.

Comments?

-- MatthewTuck

Let me try this one more time, and be as crass as I possibly can be:

Nothing is a subtype of anything!

The word subtype is a misnomer as it is usually used. It isn't anything. The Java code fragment

 return ( argument.getClass().getName() );

makes a mess of your neat subtyping hierarchy above. As it says in ContextSensitiveSubtyping and ConstructiveDeconstructionOfSubtyping? (http://alistair.cockburn.us/crystal/articles/cdos/constructivedesconstructionofsubtyping.htm),

: "...subtyping cannot be expressed as the binary relation between two types, subtype(S, T), but must be expressed with respect to the range of usage permitted in the operating environment, subtype(S, T, EP)... literature on subtyping discusses assertions, "S is a subtype of T" as if such an assertion can be pronounced true or false for all programs. Most authors assume that, in principle, such an assertion is possible.... "
: "..."Is a circle a subtype of an ellipse?", "Is a working person a subtype of a person?"
: "...Those questions cannot be answered as phrased (this should not be a surprise to the reader). They cannot be answered when given the abstract definition of all items. In fact, they cannot be answered even when given concrete mplementations in any mathematical or executable language (this should be a surprise to the reader). They cannot be answered except in the context of an interpreting environment, where the usage of the items is known. "
: "...A subtype is not a subtype in a reflective environment."

-- AlistairCockburn

Alistair, I will try to read your paper to get a better idea of where you are coming from. But in the mean time ...

I don't see any way that your reflective statement makes a "mess" of a subtyping hierarchy. Reflection is a powerful tool and can certainly subvert type systems, but that doesn't make it any less a type system. If anything it means reflection could well be a bad thing, not subtyping.

But in the end, if a programmer wants to do silly things like the above, there's little that can be done.

I don't consider a typing system to be a sort of security against other people so much as a security against my own mistakes, and I'm hardly going to write something like that, so perhaps that matters more to you than to me.

-- MatthewTuck

Just to kick you in the noggin', consider C++ whose strong typing is eradicated and supplanted with weak sub-typing in the magic template syntax. That is, while a given type A may nto be a sub-type of type B or vice versa, if the set-intersect of properties between A and B is a (possibly improper) superset of the required type-form inside the template, they both are weak-subtypes of the template parameter. Huh? The template defines what you need, and any class that implements those needs will "fit." Is this what you were getting at, Alistair?

By the way, while the concept of (sub)typing is irrelevant to most programmers, I don't think it should be. Behaving like the Smalltalk Collection hierarchy--that is overriding functional super-class methods with self messageNotUnderstood--is not acceptable unless you know what your doing; and you probably don't if you're doing junk like that. -- SunirShah

I'm really only a supporter of passive reflection, that is looking at a type or implementation. What you describe about C++, namely its template mechanism, is what I call coincidental compilation, where two things can match just because they have the same names. I don't like this, and that's also why I don't like active reflection (such as the ability to call a method through reflective means), for the same reasons. Maybe I'm not up with all the reflective literature, but I've never seen a use of it.

I should make a point here that I believe a name is not a type. A name is a property of a type. A name could change everywhere and it's still basically the same type. Changing a name should not be able to break things. So basically, this comes down to a C++ language problem, and not a subtyping problem.

-- MatthewTuck

I should probably say that I think the LiskovSubstitutionPrinciple does not have to apply in the face of reflection. If you believe it had to, then there would certainly be no subtyping in a language with it, which I think Alistair might have meant.

Subtyping is meant to describe a concept with a use, as are reflection and LSP. If you try to combine them in that way the concept of subtype does becomes useless, but if you amend LSP it is still a useful concept.

-- MatthewTuck

As I see it, the confusion is with the word "ISA".

Mathematicians say that a Circle ISA Ellipse, because a Circle has all the constraints of an Ellipse, plus more.

Computer Scientists say that an Ellipse ISA Circle, because an Ellipse has all the functionality of a Circle, plus more.

 class Circle {
double height;
Point center;
 };

 class Ellipse : public Circle {
double width;
 };

This gives both Circle and Ellipse the appropriate behaviors. So what's the problem? -- AndyJewell

Mathematicians use computers too. -- BrianEwins

Actually, ellipses don't have radii. If you draw a right angle triangle with one side along the axis of an ellipse, the triangle will not be circumscribed by the ellipse (unless the ellipse happens to be a circle at the time). Computer scientists use ISA for substitution of properties. Mathematicians use ISA for substitution in proofs and definitions. One is "internal" substitution or LiskovSubstitution the other is "external" or contextual substitution. -- SunirShah

I disagree with you here. Ellipses do have radii, and they have two foci each. The distance from one focus to a point on the ellipse plus the distance from that point to the other focus, remains constant - see http://mathworld.wolfram.com/Ellipse.html. So a circle is an ellipse with the foci coinciding. I'll give a CircleAndEllipseExample, and even though I'm afraid I might be ArguingWithGhosts, could people try to shoot holes in it? I won't be so arrogant to say there is no problem, or that I've solved it, but I don't see what would be wrong with my example or why people would want to make Ellipse a subclass of Circle. -- AalbertTorsius

Matthew, when you write these phrases,

: "Reflection is a powerful tool and can certainly subvert type systems, but that doesn't make it any less a type system. If anything it means reflection could well be a bad thing, not subtyping. But in the end, if a programmer wants to do silly things like the above, there's little that can be done."

you are starting off assuming that subtyping is good. I am challenging that it even means anything, well before we get around to discussing whether it is good.

There is very wonderful code out there that makes use of reflection, and plays havoc with standard subtyping structures. My point in the paper, when you get around to reading it, is the word subtyping has different meanings in different environments, and reflective environments make a mess of it.

Good or bad? Let's first discover what it means, then run that discussion. But I can't start from assuming it's good, and then start to work out what it might mean that preserves goodness.

-- AlistairCockburn

Above AlistairCockburn writes

: "...A subtype is not a subtype in a reflective environment."

And he's wrong. The subtyping relation holds even in a reflective environment. The difference from non-reflective environments is that in reflective environments types don't coincide with classes.

-- MichaelSchuerig

None of the argument revolves around "classes." The entirety of the argument revolves around the association of the property of "substitutability" with the word "subtype." The word class is a RedHerring.

Alistair, do I read you correctly when I say that even the term "object" we use is wrong - that we should be really doing subjective programming? I.e. that isn't not the type/class/object, but where, by who and how is it used? I think it would even cover the reflection.. (haven't read your paper yet). -- VladEnder

The mathematical definition of subtypes seems to come into play with prototype systems (sorry, not familiar enough with this site to give the right WikiWord), wherein your object is a bird because it has wings and flies rather than it being a bird and so has wings and flies. You could even define bird and airplane identically there (has wings and flies), except that birds breathe and airplanes take jet fuel... but an object which has wings, flies, breathes, and takes jet fuel, could be both a bird and an airplane. -- RobRix

How can anyone say what "should" be without knowing how circle and ellipse are used? It's the use that determines how they work, not finding an absolute frame of reference and pontificating on what should be. Everyone can play that game and everyone will be equally right and wrong.

DateAndDarwensTypeSystem handles this problem in an interesting manner - a circle is a subtype of an ellipse. In their type system (defined in TheThirdManifesto), all objects are immutable (ValueObjects) though they do support the concept of "update operators", which take a ReferenceParameter? to a variable defined elsewhere and update it. If you were to call a "set_major_axis" operator on a variable that happened to be of type circle (the variable; not the value pointing to it), that would fail.

TemporalClassesAndIdentity

One problem that OO languages have is representing classes that change behavior and attributes over time. The id of the object remains the same, but behaviour and attributes are different. It is a variant on the circle ellipse problem.

Q: Is integer vs float a case of circle vs elipse?

A (sort of): Be careful of your terminology. The set of (mathematical) integers is a proper subset of the set of rationals, so in that sense maybe. The set of ints in CeeLanguage is not a subset of the set of floats; assuming 32-bit ints and single-precision IeeeSevenFiftyFour floating point numbers. As "float" (floating point) is not a mathematical construct but an approximatation of the reals which is popular on computer systems, I wasn't entirely sure what you meant.

Assuming the mathematical integers and rationals (or reals) are meant - in this case it's clear that the ints are a subset of the rationals. One complication which numbers don't have is that numbers are considered to be immutable; they don't have mutator methods which change their state. You wouldn't send the number 5 a message and tell it to take its square root - the square root operator returns a different number. With the CircleAndEllipseProblem, it is assumed that the circles and ellipses in question are mutable - one can stretch them, rotate them, translate them, etc... otherwise there would be no problem. (Circle would be a subtype of Ellipse).

The difference might be subtle

You point out the difference between dealing with mutable versus immutable types. Here is my attempt at arguing that the difference has no bearing on CircleAndEllipseProblem. I need to assume that we are working within a statically typed language, say C++.

Mutable types: Suppose I have an Ellipse object, and I call ScaleHorizontal(0.5) on it. It just so happens that this results in a perfect Circle. The Ellipse now conceptually represents a Circle. Its type is still Ellipse, however. The Ellipse object can't spontaneously decide to change its type to Circle, since that would upset the caller.

Immutable types: Now let's suppose I have a Real object, and I call Multiply(2) on it. It just so happens that this results in a perfect Integer. Number objects are immutable. So now we have a different situation than the above. What kind of object should Multiply() return? We'd like it to return an Integer, since the result conceptually is an integer. However, since we are working with statically typed objects, Real.Multiply can't choose at runtime which type to return. It must be declared to return either Integer or Real.

In both cases, we know the "natural" type of the result, but we can't act on it because of the static typing.

Again, you're confusing the mathematical concept of "integer" and "real" with how they get implemented on hardware. Agreed, "ints" in C/C++/Java are not subtypes of "floats" (nor is the reverse true); the two have incompatible implementations, and there are quantities that one can represent and the other cannot.

However, if your language had a Rational type and an Integer type; both of which could store an arbitrary rational number (or integer, respectively - subject only to memory limits), then Rational.Multiply (Rational) should return a Rational - multiplying rationals is closed under multiplication. Likewise, Integer.Multiply (Integer) could, using contravariance, return an integer.

At any rate, in your example above - it should return a Real; as valid integers are also valid reals. Just because a function is declared to return an object of type Foo doesn't mean it cannot return a subtype.

No, I don't think I'm confusing the mathematical concepts with the programming concepts. In an earlier comment I used the term float. You brought up a valid point that float means a programming concept, and basically suggested using the term real instead. In my reply, that is just what I did. I spoke of some abstract type called Real, and I didn't suggest that it was implemented with floating point numbers, IeeeSevenFiftyFour or otherwise. I also spoke of an abstract type called Integer. Note, again, that I didn't refer to a particular implementation, TwosComplement?, 32-bit, or anything of that sort.

According to your argument, we should have only Ellipse objects. Since all circles are also valid Ellipses, there is no need for the Circle abstract data type. Is that what you intended to say?

Not at all... that would lead to the ThereAreNoTypes argument, which I think is a swamp. :) The integers exist, there are many operations on integers which produce integers, and operations on integers which produce integers can be safely declared to return integers. However, some operations on integers - division, for example - don't necessarily produce integers; division of integers should produce a rational. That rational, of course, may have a denominator of 1, making it also an integer. But such division can return things that aren't integers, so having division of integers return integers all the time is inappropriate. (Unless you do what many languages do -redefine integer division so it returns the floor of the quotient, which is an integer).

If they are immutable, all circles are ellipses - that just happen to have major and minor axes of the same length. In addition, circle-specific concepts (like the radius) can be introduced. In which case, circle is a (proper) subtype of ellipse. The fly in the ointment is - again - when one tries to mutate ellipses; if one mutates a circle then the circle invariant is no longer satisfied.

The set of (mathematical) integers is a proper subset of the set of rationals.

The set of ints in CeeLanguage *is* a subset of the set of doubles - IeeeSevenFiftyFour double precision floating point numbers can exactly represent any 32-bit int. In fact, IEEE754 double precision can handle integers exactly up to (but not including) 2^53+1.

This is one of the reasons

some mathematicians always use doubles by default, and
many programming language (such as MatLab) don't support single-precision floats. (Using single-precision floats is an optimization - get it working with doubles first, then OptimizeLater).
LuaLanguage supports only one type of number - by default these are double precision floating point numbers.

When you have a subtype that takes an object out of the traditional domain of the base type, then the LiskovSubsitutability? gets turned upside-down - so instead, the more complex, powerful class must be used as the base instead of the subclass. Normally, with containers, read-only containers are Covariant (the subclass can be substituted) and write-only containers are Contravariant (the base-classes can be substituted). Now, consider that all value-types are read-only - by this logic, an Integer is a subtype of Real, and a Circle is a subtype of Ellipse (since they're Covariant) in the case of value-types. In the trivial case, you implement this by making Circle an Ellipse in which the constructor provides only a single "radius" instead of the two Ellipse values, and then you provide functionality that assumes this is staying as-is for the new, Circle-specific reading methods. To optimize the circle later so that it is no longer just an ellipse where the height/width are forced equal, you create an IEllipse interface that both circle and ellipse implement, and factor out the common code into an abstract base class, and then inherit the circle and the ellipse both from the abstract base and both implement IEllipse... but that's an implementation detail. The point is that, if you make them immutable objects, the circle can be an ellipse.

Consider than normally a subtype provides extra operations onto a base-type - but in this case, the subtype actually constrained into a smaller domain than the base-type. While that means that all the read operations are still valid (since the reading interface of the subtype is fully functional - a circle can still provide answers to all the questions you could ask an ellipse), only the write-operations are invalid. Hence, the rule is this: if you have an environment where class "A" has a wider domain than "B", but "B" should be substitutable for "A", then "A" must be immutable and "B" must subtype "A". A non-obvious part of the "immutable, value-type" behaviour is that in impure Clone()-style operations that are being provided by the interface of "A", then "B" must return an "A" in cases where it can't return a "B" that satisfies its construction constraints. For example, consider if the Ellipse has a "StretchHorizontal?" method that returns a new Ellipse with a new width - logically, one cannot StretchHorizontal? a circle - so the circle must also return a new Ellipse (unless the StretchHorizontal? coefficient is 1.0, where it can return a Circle... possibly itself since it's immutable and aliasing is not a problem).

The only way to have the small-domain class be the base of the wide-domain class is if you design the base class as having the same (or similar) interface as the subclass, without any concepts that the subclass can't express. For example, you could have a tree like this (showing methods only)

Class Whole {flooredMagnitudeMinimumOne()}

Class Number : Whole {flooredMagnitude()}

Class Integer : Number {floor()}

Class Rational : Integer {nearestRational()}

Class Real : Rational {value()}

The idea is that every method on the base class is still a valid operation on the subclasses. Real can still implement a concept of "flooredMagnitudeMinimumOne()"... which just happens to be the only concept that a Whole number can express. So the subclasses interfaces still satisfy the base-class interfaces. Of course, for implementation's sake, very little of the functionality will be inherited in this model, while in the reversed model you could inherit the functionality (although it would be sub-optimal, just as it would be sub-optimal to use Reals that have been constrained to only be constructed as Integers).

Many CAD programs and geometry teachers define a "curve" as "a straight or curved line". This emphasizes that a straight line is a kind of curve.

I think the CircleAndEllipseProblem is just another natural language problem. Let's rename the Ellipse class to ScalableEllipse?. After all, this name is even a closer description of what the class is all about. All of a sudden, it becomes very clear that a Circle is NOT a subtype of a ScalableEllipse?. Maybe a ScalableCircle? would be a fine subtype, but then everybody immediately realizes that such a class is a logical contradiction.

I can write a HashTable implementation and name it Ellipse. Then I can write an AWT component and name it Circle. Why not? But it is clear that this Circle is not a subtype of Ellipse. A class name is worthless on its own. A class named Circle or Ellipse does not immediately get all the properties of any mathematical object that, by chance, has the same name.

To go even further, mathematicians tell us that an Ellipse has several properties. One of these properties is that a Circle is a special Ellipse. But I never read from anywhere that an ellipse or a circle was supposed to be scalable. Therefore, the Ellipse class we're talking about has nothing to do with the mathematical Ellipse, and the discussion is pointless.

-- PhilippeDetournay

Sort of kind of, but those observations can be sharpened further. One of the more insightful commentaries I've seen is in the multiple sequential sections of the C++ FAQ on the topic. I was amused by one section titled "But I have a Ph.D. in Mathematics, and I'm sure a Circle is a kind of an Ellipse! Does this mean Marshall Cline is stupid? Or that C++ is stupid? Or that OO is stupid?} See e.g. http://www.parashift.com/c++-faq-lite/proper-inheritance.html#faq-21.6

There is a simple engineering point of view--you don't want every instance of circle carrying the data overhead of an ellipse or, to take it to its logical conclusion, of a conic section. Efficiency dictates that an ellipse be a subcless of circle. We're all engineers, aren't we? -- mt

We're not all engineers.
Sometimes engineers do things that aren't the RightThing(tm) in the name of efficiency.
It's worth knowing what the RightThing is before compromising on it.

This looks like PrematureOptimization to me : moving data to the superclass just to gain some memory or efficiency has nothing to do with OO. In any case, if you really want to factorize the common data, then create a new class called EllipticParameters? or ConicCoefficients? that contains any relevant information, and put a reference to some instance of it within your Ellipse or Circle class. But keep it private.

-- PhilippeDetournay

I strongly agree. The issue is about inheritance, not about efficiency. Efficiency doesn't necessarily arise here at all, and if it did, there are zillions of ways to address that. Inheritance on the other hand is primarily about the semantic model, so that would be putting the cart before the horse in any case.

The issue here (and its resolution) can be stated very simply. Inheritance is not always a valid way to implement subtypes. In particular, if inheritance causes the LiskovSubstitutionPrinciple to be violated (i.e. if a subclass breaks a promise made by a parent class), then inheritance cannot properly implement a subtype.

For CircleAndEllipseProblem, if Ellipse promises to allow eccentricity to be changed (e.g. via a set_size(X, Y) method), then Circle cannot inherit from Ellipse, since Circle cannot fulfill the promise to assymetrically set_size(X, Y).

Similarly the other way around, e.g. if Circle advertises a get_radius() method, then Ellipse cannot inherit from Circle, since it cannot fulfill the promise to return a radius (since that presumes symmetry).

That's thinking like a mathematician. Of course an ellipse can respond to a radius request. We don't discover these things, we invent them. An engineer asks what it means in the subject domain and produces an appropriate result--which might be NaN, throwing an exception, the average distance from a focus to the perimiter, or a solution to A=pi*r^2. Who cares, as long as it's documented? Am I the only one whose factorial function returns (-!x) for (!-x)?

I hope so, especially if you call your function "factorial". By all means call it something else and document its behaviour, but I'd be pretty annoyed to use code that had a function square that returned x^3.
- That's an irrelevant comparison. I'm sure you have a point. Care to try again?
I thought it was clear. If the function you call factorial returns -6 when given -3, your function is not what it claims to be. That's similar to implementing a function called square and having it return 8 when given 2, or 27 when given 3.
The definition of factorial is other than the one your function implements. I've simply given a more extreme example of what you've done.
You ask:

"Who cares, as long as it's documented?"

: Function names, class names, method names, etc, are all part of the documentation. If you call something an ellipse it should behave like an ellipse. If you call something a factorial function it should behave like a factorial function. If your factorial function returns something other than the generally accepted definition, your documentation does not match your code.

Proverb: "When the documentation and code don't agree, they are probably both wrong."

A similar situation crops up with any implementation of the GoF Composite pattern. Use a list method on an atomic item or vice-versa and the method throws an exception--you're supposed to check what you got before using it. The thing is that this stuff solves problems in the real world. That's all it needs to do.

In any case, you don't want all your circles carrying the baggage needed to handle ellipses, so if one is to be a subclass of the other (rather than both being subclasses of something else) it's most efficient if the ellipse is a subclass of the circle. --mt

That merely misunderstands the intent of that one sentence, which would better be phrased "if it cannot fulfill the promise to return a radius (e.g. since that presumes symmetry)". With that paraphrase, your objection goes away; it is then already covered by my paragraph below (if there are no contract violations, then there's no problem inheriting in either order that makes sense for the problem domain; there's then no absolute answer either way, but no problem, either, so no need for an absolute answer).
This isn't about mathematics/looking at things as a mathematician rather than in a real world sense; circles and ellipses are just an example. One could also paraphrase it in terms of mammals and duck billed platypus, or anything else that potentially violates a promise made by a superclass.
The C++ FAQ I already referenced covers this nicely, and despite the source, applies equally to inheritance in Java, no need to ignore it just because one doesn't care about C++. The SubTypingAndSubClassing page I mention below also covers it.
CircleAndEllipseProblem can't be solved by ad hoc intuition; everyone's is different. It can be resolved more formally, as tersely outlined above, by looking at contract violations by subclasses, which is a question of when subclassing allows IS-A-KIND-OF subtyping, and when subclassing cannot function that way.
The point raised here can't be ducked by appealing to "engineering is just about getting things done any way you can", either, because that's precisely the point. If you don't take into account subclassing vs subtyping in terms of promises broken by subclasses, then eventually here and there you will run into real world problems where the class hierarchy just doesn't work well, and will have to solve each such occasion in some ad hoc way that often involves painful trial and error repeated refactoring. That's not much fun.

A quote from that FAQ: "Here are the two most common traps new OO/C++ programmers regularly fall into. They attempt to use coding hacks to cover up a broken design, e.g., they might redefine Circle::setSize(x,y) to throw an exception, call abort(), choose the average of the two parameters, or to be a no-op. Unfortunately all these hacks will surprise users, since users are expecting width() == x and height() == y. The one thing you must not do is surprise your users."

An unfortunate phrasing, actually, since programmers who've been doing OO for a long time often make some form of one of those same mistakes. The CircleAndEllipseProblem is notorious for provoking controversy where it really should not.

Sometimes programmers wonder, "why should I care whether a superclass promise is broken? Will it hurt the classes' feelings or something? Who died and made the LiskovSubstitutionPrinciple boss?" But that's forgetting that a promise made by a superclass is made to human users who depend on what the superclass is promising, and who certainly shouldn't be forced to examine each of the (sometimes hundreds or more) descendent subclass documentation (if any) to see whether they fulfill or break the superclass promise. Thus they're saying, "don't surprise your users". The rest follows.

For some purposes, there may not be any contract violations, in which case you can go ahead and have either inherit from the other as best fits the problem domain. Definitely take a look at SubTypingAndSubClassing.

It's important to note that the point is that ItDepends, and that looking for contract violations gives a way to solve the problem for an individual problem, and that there isn't an absolute answer appropriate for all programs, merely some ways to go wrong. -- DougMerritt

Precisely! And as MichaelFeathers states further along, discovering the invariants of the abstraction is the key to formulating useful abstractions. (I paraphrase somewhat.) And (I would add) in order to discover the invariants of the abstraction one must understand the context in which that abstraction is used, or is to be used; and furthermore, one must understand the set of transformations under which the invariants are to be preserved. -- JohnReynoldsTheStudent

Now, consider a type, Integer, and another type (which may or may not be a sub-type), Odd_Integer. Integer uses a method which employs a unary operator, <incrementByOne>, where, <incrementByOne> is guaranteed to yield another object of the same type, viz. Integer. Odd_Integer, however, (seemingly) breaks the contract, in that <incrementByOne> does not yield another object of the same type, viz. Odd_Integer (although it does yield an object of type Integer). The "problem" can be resolved by defining an abstract method for the abstract type Integer, to wit, the unary operator <successorOf>; for the base type, Integer, the interpretation of <successorOf> is identical to <incrementByOne>, whereas for derived types, such as Odd_Integer, <successorOf> has an interpretation which is specific to the derived type. Would this qualify as an example of syntactic sub-typing? Or what?

-- JohnReynoldsTheStudent

I tend to ChooseSuperClassesByRefactoring.

How can refactoring determine which Super Classes (Abstract Classes) the application will need, or will be useful in eliminating duplication? Let us revert for the moment to discussing Types rather than Classes, since Types seem to be the salient issue here. If <successorOf> is the only abstract method of abstractInteger that is of concern to the application then both Odd_Integer and Even_Integer, and every other sub-set of the domain value-set of abstractInteger, could be regarded as a concrete instantiation (or if you will) sub-type of abstractInteger. If dyadic operator <+> (ordinary integer addition) is also to be a requisite method of the concrete instantiations of abstractInteger, then clearly Even_Integer is a valid sub-type of Integer, but Odd_Integer is not (the sum of two odd integers is not odd). On the other hand, if (only) dyadic operator <*> (ordinary integer multiplication) is to be a requisite method of the concrete instantiations of abstractInteger, then clearly Odd_Integer is a valid sub-type of Integer, but Even_Integer may not be (because the even integers lack a multiplicative identity, namely unity). If both <+> and <*> operator methods are to be required in the concrete instantiations of abstractInteger, and if all of the postulates of ordinary integer arithmetic are to apply, then clearly neither Odd_Integer nor Even_Integer are valid sub-types of abstractInteger. Note, however, that abstractInteger could itself be a valid instantiation of abstractCommutativeRing.

-- JohnReynoldsTheStudent

I've been an OO programmer for over 15 years. When extreme programming came along, it changed many people's approach to design, mine included. I now do very little design up front - most of my design is done after the fact, as part of refactoring. I will try to address your (quite interesting) question, first from my point of view...

The computer doesn't care about superclasses or supertypes - an application will work the same if all methods are in instantiated classes, or some methods are in abstract classes.
So I start by putting all my methods in the concrete classes that my application actually needs (I either actually do it, or just "pretend" to do it). Then I make superclasses into which I promote methods, in order to remove duplication.
I choose superclasses that eliminate existing duplication, not anticipated duplication. I attempt to use a decent name for my superclasses, but I don't always succeed.
I think you are talking about computer science and I am talking about software engineering - Unfortunately, I don't know the difference between types and classes - I only work with classes.
Therefore, there is a good chance that my code will end up being theoretically "wrong". It will, however, have no duplication, and it will pass all of its tests.''

Now, I will attempt to answer your question from your point of view. You asked "How does refactoring determine which superclasses the application will need...", and then go on to give examples of "good" abstract class / concrete class relationships.

The answer is, it doesn't. Refactoring alone isn't good enough to do what you are asking. It doesn't produce theoretically correct class hierarchies. I am not asking it to. My refactoring just produces class hierarchies that remove duplication.
I guess what I am trying to say is that my code does not end up being theoretically correct. It just has no duplication, and it passes all my tests.

So the answer to the original question seems to be:

have separate 2 classes that do not inherit from each other.

MatthewTuck had a very good answer that involved quite a few more classes with a sort of structured non-hierarchy, which was compatible with LiskovSubstitutionPrinciple.

They are different shapes after all. Next the discussion will go down the circles are a special case of regular polygons, but elipses are a special case of irregular polygons.

Neither circles nore ellipses are special cases of polygons, but both are special cases of closed, non-intersecting free-form curves in two dimensions (over which the 'area' concept is well defined), which themselves are special cases of all closed free-form curves in two dimensions, which themselves are special cases of all free-form curves in two dimensions including the open ones, which themselves are special cases of free-form curves in higher dimensions. Polygons are also special cases of closed free-form curves in two dimensions, including both Squares and Rectangles for which this problem has also been described. I imagine that fitting all these things into a sort of pseudo-hierarchical structure would be rather difficult, but doable.

This is where a prototype model comes in really handy. Suppose you start out with an ellipse object. You can ask it to set its foci to the same value, and upon completion of that method, you have a circle. As in, a proper circle typed object. You can ask it for its radius if you desire.

Looking at this thing functionally might provide a bit more clarity in semantics:

  data Ellipse = Ellipse { origin :: Point; focusA :: Int; focusB :: Int; };
  data Circle = Circle { origin :: Point; radius :: Int };

  setFocusA e@(Ellipse o _ b) f = if b == f
                                   then Circle o f
                                   else Ellipse o f b

  setFocusB e@(Ellipse o a _) f = if a == f
                                   then Circle o f
                                   else Ellipse o a f

  setFocusA c@(Circle o r) f = if r == f
                                then c
                                else Ellipse o f r

  setFocusB c@(Circle o r) f = if r == f
                                then c
                                else Ellipse o r f

See SubTypingAndSubClassing and InheritanceIsNotSubtyping.

See LimitsOfHierarchies, DependentTyping

Some interest in AugustZeroFive and DecemberZeroFive

CategoryPolymorphism