Velocity Reviews > C++ > scientific publications on the "Square-rectangle problem"?

scientific publications on the "Square-rectangle problem"?

Philip Potter
Guest
Posts: n/a

 02-02-2010
On 01/02/2010 16:23, Stefan Ram wrote:
> http://www.velocityreviews.com/forums/(E-Mail Removed)-berlin.de (Stefan Ram) writes:
>> 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/Covaria...mputer_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
Guest
Posts: n/a

 02-03-2010
On Feb 2, 1:30*am, (E-Mail Removed)-berlin.de (Stefan Ram) wrote:
> Tony D <(E-Mail Removed)> writes:
> >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.

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
Guest
Posts: n/a

 02-03-2010
tonydee <(E-Mail Removed)> writes:
>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
Guest
Posts: n/a

 02-03-2010
Philip Potter <(E-Mail Removed)> writes:
>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
Guest
Posts: n/a

 02-03-2010
On Feb 3, 1:45*pm, (E-Mail Removed)-berlin.de (Stefan Ram) wrote:
> tonydee <(E-Mail Removed)> writes:
> >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.

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
Guest
Posts: n/a

 02-03-2010
tonydee <(E-Mail Removed)> writes:
>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
Guest
Posts: n/a

 02-03-2010
On Feb 3, 3:50*pm, (E-Mail Removed)-berlin.de (Stefan Ram) wrote:
> tonydee <(E-Mail Removed)> writes:
> >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.

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....

> >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.

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
Guest
Posts: n/a

 02-03-2010
On Feb 1, 6:23*pm, (E-Mail Removed)-berlin.de (Stefan Ram) wrote:
> (E-Mail Removed)-berlin.de (Stefan Ram) writes:
> >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/Covaria...nce_(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
Guest
Posts: n/a

 02-03-2010
On Feb 3, 8:50*am, (E-Mail Removed)-berlin.de (Stefan Ram) wrote:
> tonydee <(E-Mail Removed)> writes:
> >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.

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

tonydee
Guest
Posts: n/a

 02-03-2010
On Feb 3, 4:23*pm, tonydee <(E-Mail Removed)> wrote:
> On Feb 3, 3:50*pm, (E-Mail Removed)-berlin.de (Stefan Ram) wrote:
> > * 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)

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

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Ryan Digital Photography 0 07-15-2007 06:07 AM =?Utf-8?B?UmFtIEsu?= Microsoft Certification 0 04-19-2007 05:56 PM michael_quinlivan@hotmail.com MCSA 3 08-22-2005 09:16 AM BobSam Digital Photography 3 01-04-2005 07:45 AM James Britt Ruby 0 03-07-2004 11:47 PM

Advertisments