Undecidability of Liskov Substitution Principle

#81 04-26-2007, 05:12 AM

On 23 Apr, 20:26, Universe <universe353-goo...{}yahoo.com> wrote:
> On Apr 20, 12:02 pm, Mark Nicholls <Nicholls.M...{}mtvne.com> wrote:
>
>
>
>
>
> > On 20 Apr, 14:17, Mark Nicholls <Nicholls.M...{}mtvne.com> wrote:
>
> > > On 19 Apr, 21:37, Universe <universe353-goo...{}yahoo.com> wrote:
>
> > > > On Apr 19, 9:39 am, Mark Nicholls <Nicholls.M...{}mtvne.com> wrote:
>
> > > > > forall contexts X = Y....is pretty strong.....too strong for my tastes
> > > > > (in terms of being useful)...my question was whether Elliott meant
> > > > > "forall context X = Y"....or just "some context X=Y".
>
> > > > > I tend to mean
>
> > > > > forall contexts X < Y....when I say subtype.
>
> > > > For me it's "for *some context* X = Y" (or "for some context S = T" to
> > > > use Liskov symbols). With "context" defined as *the conditions
> > > > surrounding the attempt to substitute one thing for another*.
> > > > Certainly there are situations where the the conditions surrounding
> > > > the attempt to substitute one thing for another do *not* allow S to be
> > > > substituted for T. I.e. there is no absolute notion of what it means
> > > > for two things to be equivalent and thus substitutable for one
> > > > another, it's all relative to the circumstances. In context A, S = T,
> > > > in context B, S =\= T. So the term "LSP compliant" is not absolute,
> > > > but relative.
>
> > > > Elliott
>
> > > You seem to be saying rougly what Steve is...which is fine, I bow to
> > > your superiour knowledge of LSP....but to me there is quite clearly an
> > > "absolute notion of what it means for two things to be equivalent and
> > > thus substitutable for one
> > > another"....I do not dispute the relative notion as well....but it
> > > seems a little weak....I want (my compiler) to know absolutely whether
> > > something is substitutable or not.- Hide quoted text -
>
> > > - Show quoted text -
>
> > This is a little unclear....currenlty compilers tend to allow
> > substitution without reference to context...so basically the relative
> > notion of substitutability is 'correct' but if I'm designing code for
> > tools now, I want the tool to enforce substitutability as much as
> > possible...the relative notion doesn't really help.- Hide quoted text -
>
> > - Show quoted text -
>
> I use the relative to make the point that where one type Y is
> substitutable type X depends on context, that Y is not substitutable
> for X in all programs (nor necessarily in all places in the same
> program). However for every context (place) substitutability should
> be absolute in the sense that for each context the appropriate basis
> for substitutability should be well defined and enforced.
>

But you accept the point that some types are substitutable in all
contexts? (in addition to a trivial 'clone')

Your tone implies you don't accept it, if so can you
demonstrate.....it may highlight a different nuance of our
interpretation of 'type' as well as 'subtype'.

#82 04-26-2007, 07:02 AM

On 23 Apr, 20:26, Universe <universe353-goo...{}yahoo.com> wrote:
> On Apr 20, 12:02 pm, Mark Nicholls <Nicholls.M...{}mtvne.com> wrote:
>
>
>
>
>
> > On 20 Apr, 14:17, Mark Nicholls <Nicholls.M...{}mtvne.com> wrote:
>
> > > On 19 Apr, 21:37, Universe <universe353-goo...{}yahoo.com> wrote:
>
> > > > On Apr 19, 9:39 am, Mark Nicholls <Nicholls.M...{}mtvne.com> wrote:
>
> > > > > forall contexts X = Y....is pretty strong.....too strong for my tastes
> > > > > (in terms of being useful)...my question was whether Elliott meant
> > > > > "forall context X = Y"....or just "some context X=Y".
>
> > > > > I tend to mean
>
> > > > > forall contexts X < Y....when I say subtype.
>
> > > > For me it's "for *some context* X = Y" (or "for some context S = T" to
> > > > use Liskov symbols). With "context" defined as *the conditions
> > > > surrounding the attempt to substitute one thing for another*.
> > > > Certainly there are situations where the the conditions surrounding
> > > > the attempt to substitute one thing for another do *not* allow S to be
> > > > substituted for T. I.e. there is no absolute notion of what it means
> > > > for two things to be equivalent and thus substitutable for one
> > > > another, it's all relative to the circumstances. In context A, S = T,
> > > > in context B, S =\= T. So the term "LSP compliant" is not absolute,
> > > > but relative.
>
> > > > Elliott
>
> > > You seem to be saying rougly what Steve is...which is fine, I bow to
> > > your superiour knowledge of LSP....but to me there is quite clearly an
> > > "absolute notion of what it means for two things to be equivalent and
> > > thus substitutable for one
> > > another"....I do not dispute the relative notion as well....but it
> > > seems a little weak....I want (my compiler) to know absolutely whether
> > > something is substitutable or not.- Hide quoted text -
>
> > > - Show quoted text -
>
> > This is a little unclear....currenlty compilers tend to allow
> > substitution without reference to context...so basically the relative
> > notion of substitutability is 'correct' but if I'm designing code for
> > tools now, I want the tool to enforce substitutability as much as
> > possible...the relative notion doesn't really help.- Hide quoted text -
>
> > - Show quoted text -
>
> I use the relative to make the point that where one type Y is
> substitutable type X depends on context, that Y is not substitutable
> for X in all programs (nor necessarily in all places in the same
> program). However for every context (place) substitutability should
> be absolute in the sense that for each context the appropriate basis
> for substitutability should be well defined and enforced.
>
> Elliott
> ---
> OO uses object abstractions and their interaction to reduce complexity.- Hide quoted text -
>
> - Show quoted text -

I'm sure I replied to this.....maybe I'm loosing it....

do you accept that there exists some non trivial types A,B where A
substitutable for B in all contexts?

I'm not saying your wrong, but I think there may underlie a slightly
different interpretation of 'type'.

#83 04-26-2007, 10:54 AM

On Apr 26, 5:11 am, Nicholls.M...{}mtvne.com wrote:
> On 23 Apr, 20:26, Universe <universe353-goo...{}yahoo.com> wrote:
>
>
>
>
>
> > On Apr 20, 12:02 pm, Mark Nicholls <Nicholls.M...{}mtvne.com> wrote:
>
> > > On 20 Apr, 14:17, Mark Nicholls <Nicholls.M...{}mtvne.com> wrote:
>
> > > > On 19 Apr, 21:37, Universe <universe353-goo...{}yahoo.com> wrote:
>
> > > > > On Apr 19, 9:39 am, Mark Nicholls <Nicholls.M...{}mtvne.com> wrote:
>
> > > > > > forall contexts X = Y....is pretty strong.....too strong for my tastes
> > > > > > (in terms of being useful)...my question was whether Elliott meant
> > > > > > "forall context X = Y"....or just "some context X=Y".
>
> > > > > > I tend to mean
>
> > > > > > forall contexts X < Y....when I say subtype.
>
> > > > > For me it's "for *some context* X = Y" (or "for some context S = T" to
> > > > > use Liskov symbols). With "context" defined as *the conditions
> > > > > surrounding the attempt to substitute one thing for another*.
> > > > > Certainly there are situations where the the conditions surrounding
> > > > > the attempt to substitute one thing for another do *not* allow S to be
> > > > > substituted for T. I.e. there is no absolute notion of what it means
> > > > > for two things to be equivalent and thus substitutable for one
> > > > > another, it's all relative to the circumstances. In context A, S = T,
> > > > > in context B, S =\= T. So the term "LSP compliant" is not absolute,
> > > > > but relative.
>
> > > > > Elliott
>
> > > > You seem to be saying rougly what Steve is...which is fine, I bow to
> > > > your superiour knowledge of LSP....but to me there is quite clearly an
> > > > "absolute notion of what it means for two things to be equivalent and
> > > > thus substitutable for one
> > > > another"....I do not dispute the relative notion as well....but it
> > > > seems a little weak....I want (my compiler) to know absolutely whether
> > > > something is substitutable or not.- Hide quoted text -
>
> > > > - Show quoted text -
>
> > > This is a little unclear....currenlty compilers tend to allow
> > > substitution without reference to context...so basically the relative
> > > notion of substitutability is 'correct' but if I'm designing code for
> > > tools now, I want the tool to enforce substitutability as much as
> > > possible...the relative notion doesn't really help.- Hide quoted text -
>
> > > - Show quoted text -
>
> > I use the relative to make the point that where one type Y is
> > substitutable [for] type X depends on context, that Y is not substitutable
> > for X in all programs (nor necessarily in all places in the same
> > program). However for every context (place) substitutability should
> > be absolute in the sense that for each context the appropriate basis
> > for substitutability should be well defined and enforced.
>
> But you accept the point that some types are substitutable in all
> contexts? (in addition to a trivial 'clone')

Doubtful, but there may be. Taking "all contexts" to mean, "all
programs and all sites in all programs", I seriously doubt if there
are any 2 types that are always substitutable for each other.

> Your tone implies you don't accept it, if so can you
> demonstrate.....it may highlight a different nuance of our
> interpretation of 'type' as well as 'subtype'.- Hide quoted text -

A Car type (class) containing leather seats and a Bus type (class)
without leather seats that are substitutable in a program context as
both being a Vehicle type (class) in one program are not substitutable
for one another in a program context that requires its substitutable
types to share possession of leather seats as a commonality.

Elliott
---
OO uses object abstractions and their interaction to simulate domains
as machines in order to reduce complexity.

#84 04-29-2007, 02:42 PM

On 26 Apr, 15:54, Universe <universe353-goo...{}yahoo.com> wrote:
> On Apr 26, 5:11 am, Nicholls.M...{}mtvne.com wrote:
>
>
>
>
>
> > On 23 Apr, 20:26, Universe <universe353-goo...{}yahoo.com> wrote:
>
> > > On Apr 20, 12:02 pm, Mark Nicholls <Nicholls.M...{}mtvne.com> wrote:
>
> > > > On 20 Apr, 14:17, Mark Nicholls <Nicholls.M...{}mtvne.com> wrote:
>
> > > > > On 19 Apr, 21:37, Universe <universe353-goo...{}yahoo.com> wrote:
>
> > > > > > On Apr 19, 9:39 am, Mark Nicholls <Nicholls.M...{}mtvne.com> wrote:
>
> > > > > > > forall contexts X = Y....is pretty strong.....too strong for my tastes
> > > > > > > (in terms of being useful)...my question was whether Elliott meant
> > > > > > > "forall context X = Y"....or just "some context X=Y".
>
> > > > > > > I tend to mean
>
> > > > > > > forall contexts X < Y....when I say subtype.
>
> > > > > > For me it's "for *some context* X = Y" (or "for some context S = T" to
> > > > > > use Liskov symbols). With "context" defined as *the conditions
> > > > > > surrounding the attempt to substitute one thing for another*.
> > > > > > Certainly there are situations where the the conditions surrounding
> > > > > > the attempt to substitute one thing for another do *not* allow S to be
> > > > > > substituted for T. I.e. there is no absolute notion of what it means
> > > > > > for two things to be equivalent and thus substitutable for one
> > > > > > another, it's all relative to the circumstances. In context A, S = T,
> > > > > > in context B, S =\= T. So the term "LSP compliant" is not absolute,
> > > > > > but relative.
>
> > > > > > Elliott
>
> > > > > You seem to be saying rougly what Steve is...which is fine, I bow to
> > > > > your superiour knowledge of LSP....but to me there is quite clearly an
> > > > > "absolute notion of what it means for two things to be equivalent and
> > > > > thus substitutable for one
> > > > > another"....I do not dispute the relative notion as well....but it
> > > > > seems a little weak....I want (my compiler) to know absolutely whether
> > > > > something is substitutable or not.- Hide quoted text -
>
> > > > > - Show quoted text -
>
> > > > This is a little unclear....currenlty compilers tend to allow
> > > > substitution without reference to context...so basically the relative
> > > > notion of substitutability is 'correct' but if I'm designing code for
> > > > tools now, I want the tool to enforce substitutability as much as
> > > > possible...the relative notion doesn't really help.- Hide quoted text -
>
> > > > - Show quoted text -
>
> > > I use the relative to make the point that where one type Y is
> > > substitutable [for] type X depends on context, that Y is not substitutable
> > > for X in all programs (nor necessarily in all places in the same
> > > program). However for every context (place) substitutability should
> > > be absolute in the sense that for each context the appropriate basis
> > > for substitutability should be well defined and enforced.
>
> > But you accept the point that some types are substitutable in all
> > contexts? (in addition to a trivial 'clone')
>
> Doubtful, but there may be. Taking "all contexts" to mean, "all
> programs and all sites in all programs", I seriously doubt if there
> are any 2 types that are always substitutable for each other.
>
> > Your tone implies you don't accept it, if so can you
> > demonstrate.....it may highlight a different nuance of our
> > interpretation of 'type' as well as 'subtype'.- Hide quoted text -
>
> A Car type (class) containing leather seats and a Bus type (class)
> without leather seats that are substitutable in a program context as
> both being a Vehicle type (class) in one program are not substitutable
> for one another in a program context that requires its substitutable
> types to share possession of leather seats as a commonality.

These are clearly not universally substitutable for each other....but
Car & Vehicle, and Bus & Vehicle would clearly seem to be universally
substituble (one way).

>
> Elliott
> ---
> OO uses object abstractions and their interaction to simulate domains
> as machines in order to reduce complexity.- Hide quoted text -
>
> - Show quoted text -

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode