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

# scientific publications on the "Square-rectangle problem"?

tonydee
Guest
Posts: n/a

 02-03-2010
On Feb 2, 1:47*am, "Alf P. Steinbach" <(E-Mail Removed)> wrote:
> * Stefan Ram:
>
>
>
> > (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.

>

>
> > * * * 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#.
>
> Cheers,
>
> - Alf

Hi Alf,

I would agree that the problem only arises for mutable values, but I
wouldn't agree that the problem is _about_ constness/mutability.
Still, enforced constness may be a legitimate solution, encouraging
robust usage... whether it's actually more natural and intuitive for
developers may depend upon their educational background and
experience....

I do hope you'll have time to put your articles back online....

> For C++ the only such support is half hidden and
> very limited, namely co-variance for pointer or reference function results.

Good point - an explicit way to mark "out" parameter would be great.
Tuples and structs help somewhat but can be clumsy.

Regards,
Tony

Nilone
Guest
Posts: n/a

 02-03-2010
On Feb 3, 9:23*am, tonydee <(E-Mail Removed)> wrote:
> 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.

I understood R to refer specifically to ellipse stores. A method
which modifies an ellipse store cannot operate on circle stores, since
mutator methods aren't inherited covariantly *in subtyping*. They are
in OO inheritance, which is one of the reasons OO inheritance isn't
subtyping. Another is dynamic dispatch.

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

OO inheritance isn't subtyping.

Stefan Ram
Guest
Posts: n/a

 02-03-2010
http://www.velocityreviews.com/forums/(E-Mail Removed)-berlin.de (Stefan Ram) writes:
>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)

This can also be put in this wording:

Let us call 0 and 1 »small values«.

Let us call a function that accepts a small value as an
argument a »small function«, while a function that accepts
any int argument an is called an »int function«.

Then we have:

Every small value is an int value.

Every int function is a small function.

(Note the interchange of directions.)

Now, when we have a store, it can be set to a value:

store.set( value )

The set-function of a small store is a small function,
the set-function of an int store is an int function.

So the contravariance actually only holds for the
set functions of a storage object, while the get functions
(which return the stored value) are covariant.

So to avoid confusion one needs to talk about values
and functions.

Whole interfaces (i.e., sets of functions) might not be
covariant or contravariant, but a mixture of both
(with regard to a value type).

Philip Potter
Guest
Posts: n/a

 02-03-2010
On 03/02/2010 05:02, Stefan Ram wrote:
> 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.)

My problem isn't that a rectangle store can't store a square -- it can
-- it's that a rectangle store is able to store things other than a
square, while a square store promises to only hold squares.

Imagine a function 'void f (SquareStore &x)' which takes a reference to
a square store, and expects that store to come preloaded with a square
value. It will throw an exception if the store is empty, but it assumes
that if the store is not empty then it contains a square value.

Now, suppose I call that function with a rectangle store instead. That
function now has a rectangle value where it was expecting a square value.

These statements are contradictory, and one has to go:

* A rectangle store makes every promise that a square store makes.
* A square store will only ever hold a square.
* A rectangle store can store non-square rectangles.

Phil

Stefan Ram
Guest
Posts: n/a

 02-03-2010
Philip Potter <(E-Mail Removed)> writes:
>My problem isn't that a rectangle store can't store a square -- it can
>-- it's that a rectangle store is able to store things other than a
>square, while a square store promises to only hold squares.

I see. That is an other meaning than the one I had in mind.

Nilone
Guest
Posts: n/a

 02-03-2010
On Feb 3, 11:31*am, Philip Potter <(E-Mail Removed)> wrote:
> On 03/02/2010 05:02, Stefan Ram wrote:
>
>
>
>
>
> > 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.)

>
> My problem isn't that a rectangle store can't store a square -- it can
> -- it's that a rectangle store is able to store things other than a
> square, while a square store promises to only hold squares.
>
> Imagine a function 'void f (SquareStore &x)' which takes a reference to
> a square store, and expects that store to come preloaded with a square
> value. It will throw an exception if the store is empty, but it assumes
> that if the store is not empty then it contains a square value.
>
> Now, suppose I call that function with a rectangle store instead. That
> function now has a rectangle value where it was expecting a square value.
>
> These statements are contradictory, and one has to go:
>
> * A rectangle store makes every promise that a square store makes.
> * A square store will only ever hold a square.
> * A rectangle store can store non-square rectangles.
>
> Phil- Hide quoted text -
>
> - Show quoted text -

Since the parameter is in/out, arguments would have to comply with the
intersection of covariant inheritance of value properties and
contravariant inheritance of variable mutators, i.e. you could only
pass a square store and not a rectangle store.

A pure in-parameter would be able to accept any square value including
values of subtypes of square.

A pure out-parameter would be able to accept any square store
including stores of supertypes of square.

As for the contradictory statements, a rectangle store promises to
store square values, just like a square store does. Whether the value
in it is a square or a rectangle isn't a property of the store, but of
the value itself.

Philip Potter
Guest
Posts: n/a

 02-03-2010
On 03/02/2010 10:09, Nilone wrote:
> On Feb 3, 11:31 am, Philip Potter <(E-Mail Removed)> wrote:
>> My problem isn't that a rectangle store can't store a square -- it can
>> -- it's that a rectangle store is able to store things other than a
>> square, while a square store promises to only hold squares.
>>
>> Imagine a function 'void f (SquareStore &x)' which takes a reference to
>> a square store, and expects that store to come preloaded with a square
>> value. It will throw an exception if the store is empty, but it assumes
>> that if the store is not empty then it contains a square value.
>>
>> Now, suppose I call that function with a rectangle store instead. That
>> function now has a rectangle value where it was expecting a square value.
>>
>> These statements are contradictory, and one has to go:
>>
>> * A rectangle store makes every promise that a square store makes.
>> * A square store will only ever hold a square.
>> * A rectangle store can store non-square rectangles.
>>

> Since the parameter is in/out, arguments would have to comply with the
> intersection of covariant inheritance of value properties and
> contravariant inheritance of variable mutators, i.e. you could only
> pass a square store and not a rectangle store.

Which parameter is in/out? A slight variation, 'void f (const
SquareStore &x)', has the same problem, but it's definitely not in/out
wrt to the function.

If you're talking about in/out wrt the store itself, I'm afraid that any
definition of "store" which doesn't let you put things in and take
things out is not one I'm willing to accept.

> A pure in-parameter would be able to accept any square value including
> values of subtypes of square.
>
> A pure out-parameter would be able to accept any square store
> including stores of supertypes of square.

If this is the problem, how would you prevent a SquareStore being used
as an in/out parameter?

> As for the contradictory statements, a rectangle store promises to
> store square values, just like a square store does. Whether the value
> in it is a square or a rectangle isn't a property of the store, but of
> the value itself.

What you say is true, but it leaves out the fact that a square store is
guaranteed to give me a square out of it, while a rectangle store makes
no such promise.

These are guaranteed:

* A rectangle store can accept any square value
* A square store will only emit rectangle values

BUT these are not guaranteed:

* A square store can accept any rectangle value
* A rectangle store will only emit square values

If the stores are write-only, a rectangle store is (substitutable for) a
square store. Code that wants to stuff a square somewhere can use either.

If the stores are read-only, a square store is (substitutable for) a
rectangle store. Code that wants to get a rectangle value can use either.

But if (for some reason) you expect both behaviours, then there is no
simple relationship between square store and rectangle store, and that
is my problem with Stefan's original post.

The key thing for me in the Square-Rectangle problem, and the thing that
this analysis doesn't really cover, is Liskov substitutability. A
derived class must keep all the promises a base class makes. The problem
only arises if a Rectangle makes a promise a Square can't keep, or vice
versa. If this is the case, then Rectangle and Square cannot be directly
descended from each other, though they might be siblings.

Phil

Nilone
Guest
Posts: n/a

 02-03-2010
On Feb 3, 1:43*pm, Philip Potter <(E-Mail Removed)> wrote:
> On 03/02/2010 10:09, Nilone wrote:
>
>
>
>
>
> > On Feb 3, 11:31 am, Philip Potter <(E-Mail Removed)> wrote:
> >> My problem isn't that a rectangle store can't store a square -- it can
> >> -- it's that a rectangle store is able to store things other than a
> >> square, while a square store promises to only hold squares.

>
> >> Imagine a function 'void f (SquareStore &x)' which takes a reference to
> >> a square store, and expects that store to come preloaded with a square
> >> value. It will throw an exception if the store is empty, but it assumes
> >> that if the store is not empty then it contains a square value.

>
> >> Now, suppose I call that function with a rectangle store instead. That
> >> function now has a rectangle value where it was expecting a square value.

>
> >> These statements are contradictory, and one has to go:

>
> >> * A rectangle store makes every promise that a square store makes.
> >> * A square store will only ever hold a square.
> >> * A rectangle store can store non-square rectangles.

>
> > Since the parameter is in/out, arguments would have to comply with the
> > intersection of covariant inheritance of value properties and
> > contravariant inheritance of variable mutators, i.e. you could only
> > pass a square store and not a rectangle store.

>
> Which parameter is in/out? A slight variation, 'void f (const
> SquareStore &x)', has the same problem, but it's definitely not in/out
> wrt to the function.

I was describing an ideal subtyping language, not C++. My apologies
for not being explicit.

>
> If you're talking about in/out wrt the store itself, I'm afraid that any
> definition of "store" which doesn't let you put things in and take
> things out is not one I'm willing to accept.

I wouldn't accept such a store either. I was only talking about
restrictions on accessing a store polymorphically.

>
> > A pure in-parameter would be able to accept any square value including
> > values of subtypes of square.

>
> > A pure out-parameter would be able to accept any square store
> > including stores of supertypes of square.

>
> If this is the problem, how would you prevent a SquareStore being used
> as an in/out parameter?

It's not a problem, and in general, I wouldn't want to prevent any
store being used as an in/out parameter. I was just trying to express
what you described more clearly in the remainder of your post.

>
> > As for the contradictory statements, a rectangle store promises to
> > store square values, just like a square store does. *Whether the value
> > in it is a square or a rectangle isn't a property of the store, but of
> > the value itself.

>
> What you say is true, but it leaves out the fact that a square store is
> guaranteed to give me a square out of it, while a rectangle store makes
> no such promise.
>
>
> These are guaranteed:
>
> * A rectangle store can accept any square value
> * A square store will only emit rectangle values
>
> BUT these are not guaranteed:
>
> * A square store can accept any rectangle value
> * A rectangle store will only emit square values
>
> If the stores are write-only, a rectangle store is (substitutable for) a
> square store. Code that wants to stuff a square somewhere can use either.
>
> If the stores are read-only, a square store is (substitutable for) a
> rectangle store. Code that wants to get a rectangle value can use either.

I agree completely up to this point.

>
> But if (for some reason) you expect both behaviours, then there is no
> simple relationship between square store and rectangle store, and that
> is my problem with Stefan's original post.

If you want to do both, then the store must be exactly of the expected
type. Stefan's original post distinguished writing the store from
reading a value, whereas we're now talking both of writing and reading
the store.

The reason for the difference is to express the fact that properties
of the value relate to the value, not the store. I tend to prefer
that style myself.

>
> The key thing for me in the Square-Rectangle problem, and the thing that
> this analysis doesn't really cover, is Liskov substitutability. A
> derived class must keep all the promises a base class makes. The problem
> only arises if a Rectangle makes a promise a Square can't keep, or vice
> versa. If this is the case, then Rectangle and Square cannot be directly
> descended from each other, though they might be siblings.

I currently believe the inability of current OO languages to enforce
LSP is due to a broken inheritance model.