scientific publications on the "Square-rectangle problem"?

[tonydee]

* Stefan Ram:











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]

Indeed .




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



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]

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]

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]

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]

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]

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.

Having read Stefan's comments elsethread, I think I finally get it.

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]

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.

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.

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.

Having read Stefan's comments elsethread, I think I finally get it.

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.