scientific publications on the "Square-rectangle problem"?

[Leslaw Bieniasz]

Hi,

Are there any scientific publications about the "square-rectangle problem"
(also known as the "circle-ellipse problem")
and its possible treatments in C++?
My search in literature databases does not reveal anything concrete.
I would appreciate pointers to relevant publications, if there are any.

Leslaw

 

[Saeed Amrollahi]

Hi,

Are there any scientific publications about the "square-rectangle problem"
(also known as the "circle-ellipse problem")
and its possible treatments in C++?
My search in literature databases does not reveal anything concrete.
I would appreciate pointers to relevant publications, if there are any.

Leslaw

Hi

I think the following are good:
1. http://parashift.com/c++-faq-lite/proper-inheritance.html#faq-21.6,7,8,9,10,11
2. Kevlin Henney. From Mechanism to Method: Total Ellipse, C/C++
Users Journal March 2001.
http://www.curbralan.com/

Regards,
-- Saeed Amrollahi

 

[Balog Pal]

Are there any scientific publications about the "square-rectangle problem"
(also known as the "circle-ellipse problem")
and its possible treatments in C++?
My search in literature databases does not reveal anything concrete.
I would appreciate pointers to relevant publications, if there are any.

Scott Meyers wrote it as the 'All birds fly. Penguins are birds. Penguins
don't fly. Uh-oh.' problem.

 

[Stefan Ram]

Are there any scientific publications about the
"square-rectangle problem" (also known as the "circle-ellipse
problem")

This has nothing to do whatsoever specifically with C++.

It has been solved by me some years ago - I don't know if
anyone else has published this solution, but I guess so:

This pseudoproblem only comes from the lack of distinction
between a /value/ and a /store/ (i.e., a typed region of storage).

Every square value is a rectangle value.

Every rectangle store is a square store.

(If you remove »value« and »store« from the sentences
above, you will get two contradicting statements.)

These four lines from above are all to be written about
this pseudo-problem. It is this shallow. It does not even
have to do with object-oriented programming, but with
programming in general as soon as typed stores are used.

Most articles on this »problem« do not make this solution clear,
yes, it seems as most authors really are not aware of it
and therefore are a »part of the problem«, not of the solution.

For another example, assume, x e {0,1} and y e {0,1,2,3}
(e = »element of«).

Then, every x is a y, that is x e {0,1,2,3} is always true.
That is,

every x-value is a y-value.

Now, assume, x* s {0,1} and y* s {0,1,2,3}
(s = »is able to store a value from the set ...«).

Then, every y* is an x*, that is y* s {0,1} is always true.
That is,

every x-store is a y-store.

Thus, the general rule is:

Whenever a value set U is a subset of a value set S, then
every U value is an S value, and every S store is a U store.

In C++, an immutable (const) object representing a square or
a rectangle is a »value« in the sense used above, while a
mutable (non-const) object able to store a square value or a
rectangle value is a »store« in the sense used above.

There is another place in C++, where it might have to
be observed (I do not know how this usually is treated in C++):
When U is a subtype of T, then vector<U> will usually /not/ be
a subtype of vector<T>. This is so, because a vector of a type
is not a value of this type, but a store for values of this type.

Citation for this publication:

Stefan Ram, On the Square-Rectangle Problem, Usenet-post
<[email protected]>, 2010.

 

[Tony D]

  This pseudoproblem only comes from the lack of distinction
  between a /value/ and a /store/ (i.e., a typed region of storage).

      Every square    value is a rectangle value.

      Every rectangle store is a square    store.

An elegant observation, but haven't you rather skipped over the
crucial elements: the expectations that come with the terminology,
what functions are appropriate in the interfaces, any inheritance
relationship, justified in terms of implications to correct design and
usage. Personally, I consider the FAQ helpful, but I haven't followed
your link to your complete publication... I'm sure if someone likes
the in-thread summary and is still in need of help of the issue,
they'll do so.

Regards,
Tony

 

[Stefan Ram]

It has been solved by me some years ago - I don't know if
anyone else has published this solution, but I guess so:

I have been looking around and found:

http://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)

Using the terms from this article, I can define a function:

*: T -> T*

that maps a type T of values to a type T* of storage cells
for such values, and the essential assertion then becomes:

* is contravariant.

That is, using »<=« from this article:

square <= rectangle, but
rectangle* <= square*.

So, obviously, many computer scientists are aware of
contravariance - just some authors of web articles about
»the square-rectangle problem« are not.

 

[Stefan Ram]

what functions are appropriate in the interfaces, any inheritance
relationship, justified in terms of implications to correct design and
usage.

Such questions are best discussed given a specific set of
requirements for a programming task.

For example, when someone tells me to write a shape
editor where one can edit rectangles and squares, these
requirements would eventually lead to a class design,
possibly with certain subtype-relationships.

Without specific requirements, we can not derive enough
information from just the words »square« and »rectangle«
to get such a design.

 

[Alf P. Steinbach]

* Stefan Ram:

I have been looking around and found:

http://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)

Using the terms from this article, I can define a function:

*: T -> T*

that maps a type T of values to a type T* of storage cells
for such values, and the essential assertion then becomes:

* is contravariant.

That is, using »<=« from this article:

square <= rectangle, but
rectangle* <= square*.

So, obviously, many computer scientists are aware of
contravariance - just some authors of web articles about
»the square-rectangle problem« are not.

Not sure if I follow the above, it looks like obfuscation.

I discussed the ellipse/circle problem in my "pointers" tutorial, which is now
off-web. Perhaps I should put it on Google docs. Essentially, as you point out,
it is about an immutable-values-view versus a modifiable-variables view.

And yes, understanding it is essential for understanding the Liskov substitution
principle (contra-variance and co-variance), and it ties in with "const" in C++.
It also ties in with "in", "in/out" and "out" in languages that support such,
e.g. the partial support in C#. For C++ the only such support is half hidden and
very limited, namely co-variance for pointer or reference function results.


Cheers,

- Alf

 

[Kaz Kylheku]

Hi,

Are there any scientific publications about the "square-rectangle problem"
(also known as the "circle-ellipse problem")

There is no problem.

The ``problem'' is whether you can model a circle as a subtype of
ellipse.

Doing this is only a problem if you allow mutability, without type
change.

Clearly, in mathematics, a circle is a kind of ellipse. But in
mathematics, we don't change an ellipse into a different ellipse while
lying to ourselves that it's still the same object.

 

[Nilone]

Hi,

Are there any scientific publications about the "square-rectangle problem"
(also known as the "circle-ellipse problem")
and its possible treatments in C++?
My search in literature databases does not reveal anything concrete.
I would appreciate pointers to relevant publications, if there are any.

Leslaw

Look for the following authors: Birkhoff, Cardelli, Cockburn, Date,
Guttag, Halpin, Kay, Liskov, Lispon, and Wing.

Alistair Cockburn has a good page on the topic, and some references
too:

http://alistair.cockburn.us/Constructive+deconstruction+of+subtyping

HTH

 

[Philip Potter]

I have been looking around and found:

http://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)

Using the terms from this article, I can define a function:

*: T -> T*

that maps a type T of values to a type T* of storage cells
for such values, and the essential assertion then becomes:

* is contravariant.

That is, using »<=« from this article:

square <= rectangle, but
rectangle* <= square*.

I agree that a square value is a rectangle value.
I don't agree that a rectangle store is a square store.

Everything that I can say about a rectangle value also applies to square
values, but I can come up with properties about a square store that do
not apply to a rectangle store. In particular:

A square store is guaranteed to hold a square. A rectangle store has no
such guarantee.

A rectangle store which currently holds a nonsquare rectangle is
certainly not useful as a square store.

Therefore, at this level of abstraction, Liskov substitutability is not
satisfied. I can see that perhaps, if you introduce some more conditions
or clarifications, a rectangle store might be considered to be a square
store, but right now neither seems to be an example of the other.

Phil

 

[tonydee]

  Such questions are best discussed given a specific set of
  requirements for a programming task.

  For example, when someone tells me to write a shape
  editor where one can edit rectangles and squares, these
  requirements would eventually lead to a class design,
  possibly with certain subtype-relationships.

  Without specific requirements, we can not derive enough
  information from just the words »square« and »rectangle«
  to get such a design.

Agreed, but is it not the exploration of options and implications in
this space that makes the square/rectangle circle/ellipse problem
space educational?

 

[Stefan Ram]

Agreed, but is it not the exploration of options and implications in
this space that makes the square/rectangle circle/ellipse problem
space educational?

Educational or just entertaining?

Whenever one has a specific assignment, one has a context.

Given just the words one can only use the mathematical
definition, because this is the realm those words come from.
By this, a circle is the set of all points where the
distance from a given point is a given constant while an
ellipse is the set of all points in a plane such that the
sum of the distances to two fixed points is a given constant.

By this definition, every circle is an ellipse, because
here, set theory applies.

So in programming, to come to other conclusions, one needs
to use other meanings of »circle« and »ellipse«, and those
cannot be derived from just those words.

 

[Stefan Ram]

A square store is guaranteed to hold a square. A rectangle store has no
such guarantee.
A rectangle store which currently holds a nonsquare rectangle is
certainly not useful as a square store.

If a rectangle store can store a width and a height, then it
can store a square by storing the width and the height of
the square (which happen to be equal to each other for a square).

Assuming for simplicity rectangles and squares with borders
that are parallel to the axes of the coordinate system, both
have only the width and height as their properties.

(However, you might define some of these terms in other ways,
and then you would be right. So here, everything depends on the
definitions used for these terms.)

 

[tonydee]

  Educational or just entertaining?

  Whenever one has a specific assignment, one has a context.

  Given just the words one can only use the mathematical
  definition, because this is the realm those words come from.

Not so, the words also have meaning in common usage.

  By this, a circle is the set of all points where the
  distance from a given point is a given constant while an
  ellipse is the set of all points in a plane such that the
  sum of the distances to two fixed points is a given constant.

  By this definition, every circle is an ellipse, because
  here, set theory applies.

In common usage, calling something an ellipse may imply it's not
(obviously) simply a circle, in the same way that calling some person
an animal is presumed to be making a point. But I play Devil's
Advocate here... it's only a distraction from the OO modeling issues
that these examples are used to illustrate.

  So in programming, to come to other conclusions, one needs
  to use other meanings of »circle« and »ellipse«, and those
  cannot be derived from just those words.

Not so... the programming issues embrace the definitions you've
provided above - accepting those conclusions. Specifically, they
explore what happens when you map that conclusion most simply/naively
into an object model: a Circle object as a special case (subclass) of
a more general Ellipse. The answer is that you have Circles that
can't do what is reasonable to ask of an Ellipse, namely, alter the
ratio of width to height, without ceasing to be Circles. You hide
form Mrs Liskov spotlight. You can try to mitigate the mess by having
the Circles throw exceptions, return a success indicator, assert or
any other manner of error handling/notification, but someone who knows
they're dealing with an Ellipse may take it for granted that these
fundamental operations are always successful and not even read the
documentation let alone check for and handle failure. It's a bad
design in that what's intuitively certain may not work. That level of
presentation of the problem is not so vague and arbitrary that it is
"best discussed given a specific set of requirements for a programming
task" as you've suggested. That is the starting point for
discussion. If you don't get that far, then you're not addressing
yourself to the same problem. It is from an understanding of that
conflict that alternative modeling can be explored, and that's where
things might get vague - although in practice it's not so difficult to
have a reasonably tight and meaningful discussion around this.

Regards, Tony

 

[Stefan Ram]

explore what happens when you map that conclusion most simply/naively
into an object model: a Circle object as a special case (subclass) of
a more general Ellipse. The answer is that you have Circles that
can't do what is reasonable to ask of an Ellipse, namely, alter the
ratio of width to height, without ceasing to be Circles. You hide

Such an object does not truly model a circle, because a
circle cannot be modified. Instead it seem to model a
circle storage, which is something different from a circle.

The essential property of an ellipse storage is an ellipse
/requirement/: It requires a value to be an ellipse (in order
to become accepted for storage). Since every circle is an
ellipse, every ellipse requirement R also accepts circles. Thus:

x e C ==> x e E (if x is a circle, then x is an ellipse)
R a C <== R a E (if R accepts ellipses, then R accepts circles)

The transition from objects to requirements is what actually
inverts the direction of the arrow above. It happens to apply
to stores, because stores for type T require values to be of type T.

form Mrs Liskov spotlight. You can try to mitigate the mess by having
the Circles throw exceptions, return a success indicator, assert or

You are calling something a »Circle« here, what is really a
»circle storage«. This is like calling a numeric variable a
»number«: It is alright as long as you know that it really is
storage, not a value.

 

[tonydee]

  Such an object does not truly model a circle, because a
  circle cannot be modified.

Indeed .

Instead it seem to model a
  circle storage, which is something different from a circle.
  The essential property of an ellipse storage is an ellipse
  /requirement/: It requires a value to be an ellipse (in order
  to become accepted for storage). Since every circle is an
  ellipse, every ellipse requirement R also accepts circles. Thus:

x e C  ==>  x e E      (if x is a circle, then x is an ellipse)
R a C  <==  R a E      (if R accepts ellipses, then R accepts circles)

  The transition from objects to requirements is what actually
  inverts the direction of the arrow above. It happens to apply
  to stores, because stores for type T require values to be of type T.

The issue is not with storage: an ellipse can store a circle. But
your statement "if R accepts ellipses, then R accepts circles" is
wrong, given a function R that accepts an ellipse by reference and
attempts to change its height:width ratio. That's the flaw in the
naive OO model... itself an important insight, but again -
understanding this is primarily a basis for discussing how to model
Circles and Ellipses in a more inherently robust fashion....

  You are calling something a Circle here, what is really a
  circle storage . This is like calling a numeric variable a
  number : It is alright as long as you know that it really is
  storage, not a value.

Wrong. I clearly defined "Circle" and "Ellipse" above in terms of
naive OO modeling, in which Circle is subclassed from Ellipse and
therefore inherits its Ellipse storage.

Regards,
Tony

 

[Nilone]

  I have been looking around and found:

http://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_...)

  Using the terms from this article, I can define a function:

      *: T -> T*

  that maps a type T of values to a type T* of storage cells
  for such values, and the essential assertion then becomes:

      * is contravariant.

  That is, using <= from this article:

      square     <= rectangle, but
      rectangle* <= square*.

  So, obviously, many computer scientists are aware of
  contravariance - just some authors of web articles about
  the square-rectangle problem are not.

Why do you disable archiving of your posts, Stefan? I think these are
important points.

 

[Nilone]

  Such an object does not truly model a circle, because a
  circle cannot be modified. Instead it seem to model a
  circle storage, which is something different from a circle.

  The essential property of an ellipse storage is an ellipse
  /requirement/: It requires a value to be an ellipse (in order
  to become accepted for storage). Since every circle is an
  ellipse, every ellipse requirement R also accepts circles. Thus:

x e C  ==>  x e E      (if x is a circle, then x is an ellipse)
R a C  <==  R a E      (if R accepts ellipses, then R accepts circles)

  The transition from objects to requirements is what actually
  inverts the direction of the arrow above. It happens to apply
  to stores, because stores for type T require values to be of type T.


  You are calling something a Circle here, what is really a
  circle storage . This is like calling a numeric variable a
  number : It is alright as long as you know that it really is
  storage, not a value.

My apologies for contradicting your archiving wishes by quoting you.
I really do want to keep posts like these around.

 

[tonydee]

Apologies for saying this statement of requirement was wrong...
reading bits of your post piecemeal as I responded, I lost sight of
the fact you'd specifically defined R as a requirement _on the
storage_, and not a more general requirement re functionality/
interface....

That misunderstanding aside, your model seems to do nothing more than
also suggest a "class Circle : public Ellipse" naive modeling. It
only gets interesting in light of the expected set_height_width(...)
or similar member in Ellipse, which by having an error case
necessarily breaks the expectation that the interface be fully
intuitive and safe.

(Personally, I think a "try_to_set_height_width(...)" or similar is a
practical compromise, ensuring client usage is cued to investigate the
potential failure condition....)

(There's also the even more naive model of "class Ellipse : public
Circle", too obviously broken to be interesting).

Regards,
Tony