Undecidability of Liskov Substitution Principle

On Mar 22, 9:35 am, "H. S. Lahman" <h.lah...{}verizon.net> wrote:

> Recognizing LSP problems is a matter of DbC contracts with
> the supertype. If those are properly defined it is usually
> fairly easy to determine if a candidate implementation
> violates them.

Wouldn't at least part of the "contract" between a candindate subtype
and the supertype be that it actually IS a subtype? And assuring that
is what the author claims is non-trivial and undecidable, if the
values of the candidate subtype implementation are allowed to override
some of the supertype's values, as they generally are in OO languages:

http://okmij.org/ftp/Computation/Sub...ences.html#LSP

<n.torrey.pines{}> wrote:
> Wouldn't at least part of the "contract" between a candindate subtype
> and the supertype be that it actually IS a subtype? And assuring that
> is what the author claims is non-trivial and undecidable, if the
> values of the candidate subtype implementation are allowed to override
> some of the supertype's values, as they generally are in OO languages:

As I mentioned, *assuring* that is not difficult at all. *Deciding* it
is impossible. This is an important distinction.

--
Chris Smith

n.torrey.pines{} wrote:

> On Mar 22, 9:35 am, "H. S. Lahman" <h.lah...{}verizon.net> wrote:
>
> > Recognizing LSP problems is a matter of DbC contracts with
> > the supertype. If those are properly defined it is usually
> > fairly easy to determine if a candidate implementation
> > violates them.
>
> Wouldn't at least part of the "contract" between a candindate subtype
> and the supertype be that it actually IS a subtype?

The question is, how do you know if it IS a subtype? Read the LSP paper
for the answer.

On Mar 23, 6:56 pm, Chris Smith <cdsm...{}twu.net> wrote:
> <n.torrey.pi...{}> wrote:
> > Wouldn't at least part of the "contract" between a candindate subtype
> > and the supertype be that it actually IS a subtype? And assuring that
> > is what the author claims is non-trivial and undecidable, if the
> > values of the candidate subtype implementation are allowed to override
> > some of the supertype's values, as they generally are in OO languages:
>
> As I mentioned, *assuring* that is not difficult at all. *Deciding* it
> is impossible. This is an important distinction.

I agree with what you wrote earlier (in principle). You just dislike
my choice of words, but I think I was clear, given the context. I was
replying to H.S. who wrote "recognizing LSP problems is easy". I take
that to mean "deciding when some type S, claimed to be a subtype of T,
is in fact its subtype is easy", same as "assuring that some type S,
claimed to be a subtype of T, is in fact its subtype is easy".

You mentioned type systems that would prevent you from using a value X
as type T, unless that value was a subtype S of type T. I'm curious -
would such type system be substantially more permissive (with respect
to subtyping) than the BRules from the article?

Responding to N.torrey.pines...

>>Recognizing LSP problems is a matter of DbC contracts with
>>the supertype. If those are properly defined it is usually
>>fairly easy to determine if a candidate implementation
>>violates them.
>
>
> Wouldn't at least part of the "contract" between a candindate subtype
> and the supertype be that it actually IS a subtype? And assuring that
> is what the author claims is non-trivial and undecidable, if the
> values of the candidate subtype implementation are allowed to override
> some of the supertype's values, as they generally are in OO languages:

Since this was posted to comp.object I have assumed we are talking about
an OO context. In that case, I agree with Daniel T.'s original post. If
LSP is not honored, then it is not a valid OO subtype.

Also in an OO context there are two relevant DbC contracts: Between the
client and the subtype (i.e., direct access of the subtype properties)
and between the client and the supertype (i.e., direct access of the
supertype properties). IOW, there is no relevant contract between the
supertype and the subtype. The only contract that is relevant to LSP is
the supertype contract because it is only though that contract that
types can be substituted for the client.

My assertion is that if that supertype contract is rigorously defined in
a DbC sense for the client, then it should be relatively simple to
determine if the subtype implementation honors that contract. In
principle it is exactly the same as determining if any procedure in a
FORTRAN program fulfills its DbC contract. If it does honor the contract
for all superclass properties, it is a valid OO subtype. If it doesn't,
it isn't a valid OO subtype.

Note that implementation overrides are not directly relevant. An object
instantiating an OO generalization is always a leaf object and one is
only concerned with the property implementations that the leaf object
actually has. Implementation overrides are simply a mechanism for
determining what property implementations it actually has based upon
inheritance rules. IOW, all we care about is whether the implementation
the leaf subtype object actually has is compliant with the supertype
contract (regardless of how many levels and overrides there may be in
the generalization between the invoked supertype and the leaf subtype).

[BTW, implementation inheritance overrides is one of those things that
seemed like a good idea at the time but turned out badly. That is
because such overrides effectively add another dimension to inheritance
rules so that in practice there are all sorts of new ways to break
existing clients by reorganizing the tree during <careless> maintenance.
So in modern OOA/D practice implementation overrides are usually
regarded as a no-no.]


*************
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl{}pathfindermda.com
Pathfinder Solutions
http://www.pathfindermda.com
blog: http://pathfinderpeople.blogs.com/hslahman
"Model-Based Translation: The Next Step in Agile Development". Email
info{}pathfindermda.com for your copy.
Pathfinder is hiring:
http://www.pathfindermda.com/about_us/careers_pos3.php.
(888)OOA-PATH

On Sat, 24 Mar 2007 22:03:04 GMT, H. S. Lahman wrote:

> If LSP is not honored, then it is not a valid OO subtype.

"LSP-subtype" you mean. "OO subtype" is much too wide.

> Also in an OO context there are two relevant DbC contracts: Between the
> client and the subtype (i.e., direct access of the subtype properties)
> and between the client and the supertype (i.e., direct access of the
> supertype properties).

Why is it two? It is one contract here, of the type. [De]composition of the
contracts is secondary. And the idea that a type may have different(?)
contracts between "clients" and other animals (types?, values?, contexts?)
is not in LSP spirit.

However, such anarchy of contracts [maybe contradicting each other] could
be a way out. Though that might kill the very notion of type, and its
subtypes as well.

> IOW, there is no relevant contract between the
> supertype and the subtype. The only contract that is relevant to LSP is
> the supertype contract because it is only though that contract that
> types can be substituted for the client.

Subtyping is just a binary relation defined on types which has some
intuitive properties all people could agree on, like reflexivity and
transitivity. LSP-subtyping is one of many possible subtypings.

> [BTW, implementation inheritance overrides is one of those things that
> seemed like a good idea at the time but turned out badly.

It is just a mechanism of defining a polymorphic subprogram body. This
mechanics is not the issue with LSP. The issue is that in numerous trivial
cases no any LSP-conform body exists. Whatever way one would use to define
it: inherit, override, rewrite it all from scratch, everything will be
wrong.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

On 24 Mar, 00:30, n.torrey.pi...{} wrote:
> On Mar 22, 9:35 am, "H. S. Lahman" <h.lah...{}verizon.net> wrote:
>
> > Recognizing LSP problems is a matter of DbC contracts with
> > the supertype. If those are properly defined it is usually
> > fairly easy to determine if a candidate implementation
> > violates them.
>
> Wouldn't at least part of the "contract" between a candindate subtype
> and the supertype be that it actually IS a subtype? And assuring that
> is what the author claims is non-trivial and undecidable, if the
> values of the candidate subtype implementation are allowed to override
> some of the supertype's values, as they generally are in OO languages:
>
> http://okmij.org/ftp/Computation/Sub...ences.html#LSP

There's more than one way of setting it up.

If type A is declared to be a subtype of type B, then the question is
obviously simple.

A subtype B -> A subtype B

the undecidability is for 2 arbritary types....if I don't know if A is
a subtype of B then how can I tell, sometimes it's obvious...but not
always? you are correct in saying "Wouldn't at least part of the
"contract" between a candindate subtype and the supertype be that it
actually IS a subtype?"....this is usually the case in most
OOP's.....but is not the general case, statically defining type
hierarchies is a special case, which makes the quesion easy.

In most OOP's the programmer explicitly declares the type tree, the
compiler then just either uses to validate substitutability (and force
the user to jump over some hurdles in order to implement these
types...i.e. you said it implements a method XYZ....so you have to do
so). (Most OOP's types are very weak, much weaker than the 'real'
types that exist largely in the programmers head).

Responding to Kazakov...

>>If LSP is not honored, then it is not a valid OO subtype.
>
>
> "LSP-subtype" you mean. "OO subtype" is much too wide.

Because it is an OO context one is <presumably> interested in how LSP is
applied to OO subtyping. For example, in an OO context the relevant LSP
contract is between client and supertype or subtype rather than between
supertype and subtype.

>>Also in an OO context there are two relevant DbC contracts: Between the
>>client and the subtype (i.e., direct access of the subtype properties)
>>and between the client and the supertype (i.e., direct access of the
>>supertype properties).
>
>
> Why is it two? It is one contract here, of the type. [De]composition of the
> contracts is secondary. And the idea that a type may have different(?)
> contracts between "clients" and other animals (types?, values?, contexts?)
> is not in LSP spirit.

The contract with the subtype is different because it can access
properties that are not available for a supertype contract. In addition
the subtype contract is usually limited to the specific implementation
and does not support the implementations of peer subtypes. IOW, the
supertype contract is more general because it must support
substitutability while the subtype contract does not.

>>IOW, there is no relevant contract between the
>>supertype and the subtype. The only contract that is relevant to LSP is
>>the supertype contract because it is only though that contract that
>>types can be substituted for the client.
>
>
> Subtyping is just a binary relation defined on types which has some
> intuitive properties all people could agree on, like reflexivity and
> transitivity. LSP-subtyping is one of many possible subtypings.

I'm afraid you've lost me. You seem to view LSP as a form of subtyping.
It is just a criterion that defines valid substitutability among subtypes.

>>[BTW, implementation inheritance overrides is one of those things that
>>seemed like a good idea at the time but turned out badly.
>
>
> It is just a mechanism of defining a polymorphic subprogram body. This
> mechanics is not the issue with LSP. The issue is that in numerous trivial
> cases no any LSP-conform body exists. Whatever way one would use to define
> it: inherit, override, rewrite it all from scratch, everything will be
> wrong.

I agree and said so in the elided text. My point here was that
implementation overrides are no longer considered a good idea in OOA/D
so one shouldn't be using them. One reason for that is that they open up
more opportunities for violating LSP.


*************
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl{}pathfindermda.com
Pathfinder Solutions
http://www.pathfindermda.com
blog: http://pathfinderpeople.blogs.com/hslahman
"Model-Based Translation: The Next Step in Agile Development". Email
info{}pathfindermda.com for your copy.
Pathfinder is hiring:
http://www.pathfindermda.com/about_us/careers_pos3.php.
(888)OOA-PATH

On Sun, 25 Mar 2007 14:39:54 GMT, H. S. Lahman wrote:

> Responding to Kazakov...
>
>>>If LSP is not honored, then it is not a valid OO subtype.
>>
>> "LSP-subtype" you mean. "OO subtype" is much too wide.
>
> Because it is an OO context one is <presumably> interested in how LSP is
> applied to OO subtyping.

OK, but "OO subtyping" needs to be defined, and that might turn quite hard
to do so that everybody could agree on the meaning of. That's for one. Then
we would need to proceed to "valid" OO subtypes, which would be even
harder. So I prefer not to do any interpolations and stay by not LSP <=>
not an LSP subtype.

>> Why is it two? It is one contract here, of the type. [De]composition of the
>> contracts is secondary. And the idea that a type may have different(?)
>> contracts between "clients" and other animals (types?, values?, contexts?)
>> is not in LSP spirit.
>
> The contract with the subtype is different because it can access
> properties that are not available for a supertype contract.

These are parts of one type contract. But we seem to disagree in just
wording.

>>>IOW, there is no relevant contract between the
>>>supertype and the subtype. The only contract that is relevant to LSP is
>>>the supertype contract because it is only though that contract that
>>>types can be substituted for the client.
>>
>> Subtyping is just a binary relation defined on types which has some
>> intuitive properties all people could agree on, like reflexivity and
>> transitivity. LSP-subtyping is one of many possible subtypings.
>
> I'm afraid you've lost me. You seem to view LSP as a form of subtyping.

Depends on the context. LSP is a principle, which (if useful) should induce
a notion of subtyping. At least Liskov tried to promote such a notion.
Solely as a principle, a gesture programmer's of good-will, it would be
uninteresting: honor LSP and your father and your mother... (:-))

> It is just a criterion that defines valid substitutability among subtypes.

It is imprecise. Actually [absolute] LSP-conformity is a sufficient but not
necessary condition of substitutability.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

On 25 Mar, 16:56, "Dmitry A. Kazakov" <mail...{}dmitry-kazakov.de>
wrote:
> On Sun, 25 Mar 2007 14:39:54 GMT, H. S. Lahman wrote:
> > Responding to Kazakov...
>
> >>>If LSP is not honored, then it is not a valid OO subtype.
>
> >> "LSP-subtype" you mean. "OO subtype" is much too wide.
>
> > Because it is an OO context one is <presumably> interested in how LSP is
> > applied to OO subtyping.
>
> OK, but "OO subtyping" needs to be defined, and that might turn quite hard
> to do so that everybody could agree on the meaning of. That's for one. Then
> we would need to proceed to "valid" OO subtypes, which would be even
> harder. So I prefer not to do any interpolations and stay by not LSP <=>
> not an LSP subtype.
>
> >> Why is it two? It is one contract here, of the type. [De]composition of the
> >> contracts is secondary. And the idea that a type may have different(?)
> >> contracts between "clients" and other animals (types?, values?, contexts?)
> >> is not in LSP spirit.
>
> > The contract with the subtype is different because it can access
> > properties that are not available for a supertype contract.
>
> These are parts of one type contract. But we seem to disagree in just
> wording.
>
> >>>IOW, there is no relevant contract between the
> >>>supertype and the subtype. The only contract that is relevant to LSP is
> >>>the supertype contract because it is only though that contract that
> >>>types can be substituted for the client.
>
> >> Subtyping is just a binary relation defined on types which has some
> >> intuitive properties all people could agree on, like reflexivity and
> >> transitivity. LSP-subtyping is one of many possible subtypings.
>
> > I'm afraid you've lost me. You seem to view LSP as a form of subtyping.
>
> Depends on the context. LSP is a principle, which (if useful) should induce
> a notion of subtyping. At least Liskov tried to promote such a notion.
> Solely as a principle, a gesture programmer's of good-will, it would be
> uninteresting: honor LSP and your father and your mother... (:-))
>
> > It is just a criterion that defines valid substitutability among subtypes.
>
> It is imprecise. Actually [absolute] LSP-conformity is a sufficient but not
> necessary condition of substitutability.
>

Can you clarify....what do you mean by "absolute"....(I tend to use it
to mean effectively behaviourally indistinguishable...but I don't
think you mean this.)

Can you give an example of something that does not satisfy LSP but is
substitutable....I'm not picking holes....it's an interesting
subject....and I know it's at the mercy of everyone using the same
words to mean something slightly different.