Re: Liskov Substitution Principle and Abstract Factories

From: Dmitry A. Kazakov (mailbox_at_dmitry-kazakov.de)
Date: 01/31/05 

Date: Mon, 31 Jan 2005 20:18:21 +0100

On Mon, 31 Jan 2005 11:29:29 -0000, Mark Nicholls wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> news:19vwsmqqlh9an$.fx35qrjdr600$.dlg@40tude.net...
>> On Sun, 30 Jan 2005 16:37:22 -0000, Mark Nicholls wrote:
>>
>>> as what?....I'm really not with you....If I say my fuse has blow on my
>>> computer, is it just intuition to believe that the computer wont work?
>>
>> No, it is an inference from a model of the computer. That model, somewhere
>> in it, has rules like blown fuse => no power.
>
> What if I don't know the model explicitly, but notice everytime, for
> everyone I know, fuse blown means electical equipment does not work.....does
> this now qualify as 'intuition'.

It means that you just have created a model in your head.

>> A savage could come to the conculsion that the computer
>> does not work because he cannot feel any breeze blowing from the fan. He
>> would try to rotate the fan to get the computer work (having fed and given
>> drink to it first.)
>
> and you would seem to simply shrug your shoulders and say "there was a bang
> and it's stopped, I can infer no correlation".....I'll go with the savage.

I'll go to a repair shop.

>>>> No it is not. You have no right to take objects outside the set of
>>>> elementary outcomes. In discrete case (we don't want to go into Lebesque
>>>> integrals), there must be S={si}. Your X and Y should be subsets of S. I.e.
>>>> X={s1, s123, s40}. Y={s2, s40}. Your example above is illegal. Z={s1,
>>>> {s1,s2}} is not a subset of S.
>>>
>>> I then fail to see how one would ever formulate a model with multiple random
>>> variables and look at the correlations between them.....for this is all I am
>>> suggesting.
>>
>> Surely you can. A random variable is just a function that maps S to R. You
>> can have any of them.
>
> I had Yi = Xi....you objected.....

Because it wasn't clear if X and Y map from the same S.
 
>>>> See: http://en.wikipedia.org/wiki/Probability_space
>>>
>>> OK...
>>>
>>> the set S is the cross product between { 1,2,3,4,5,6 } x { 1 dog, 2 dogs, 3
>>> dogs, 4 dogs, 5 dogs, 6 dogs }
>>
>> How 1 dog and 2 dogs are related? You should have empty intersection of 1
>> dog and 2 dogs. There is a suspicion that it is not so. I would take
>> individual dogs instead.
>
> your having a laugh with me aren't you.....
>
> the set S is the cross product between { 1,2,3,4,5,6 } x { "dog1", "dog2",
> "dog3", "dog4", "dog5", "dog6" }

>>> with the obvious probality function
>>> p(i,,j dogs) = 0 if i!=j
>>> p(i,,j dogs) = 1/6 if i=j
>>
>> I cannot decipher this.
>
> its a probability distribution....of two directly correlated events.
>
>> S is a set of pairs. The probability has to be defined for each pair:
>>
>> Pr((x, y)), where x in X={1,...,6 }, y in Y={1 dog,...,6 dogs }
>
> yes....S = <x,y>, x member { 1,2,3,4,5,6 } , y member { "dog1", "dog2",
> "dog3", "dog4", "dog5", "dog6" }.
>
> I've done that bit.
>
> so you should now understand
>
> p(i,,j dogs) = 0 if i!=j
> p(i,,j dogs) = 1/6 if i=j

No. I cannot understand the notation "i comma comma j dogs".

>>> Is that OK now? (I must admit to finding this mildly bamboozling, I do not
>>> believe I am doing anything particularly wrong or obtuse)
>>>
>>> So when I say p(x=i) I am saying p(x member {i,j} for some j).
>>
>> x=i has to denote a subset of S. For example all pairs such that the first
>> element is i.
>
> ! thats what I wrote
>
> "x member {i,j} for some j"

So you meant

   Pr ({ (i, dogj) | i=j })?

If so then provided that the distribution is even and each of 36 elementary
outcomes has the probability 1/36

   Pr ({ (i, dogj) | i=j }) = 6/36 = 1/6 (6 diagonal elements)
   Pr ({ (i, dogj) | i#j }) = 1 - 6/36 = 5/6 (30 non-diagonal elements)

>>>> The function = has to be defined on whole C. What does it return for 0+i
>>>> and 0+2i?
>>>
>>> it does not matter!
>>>
>>> because 0+i, and 0+2i will never occur in an execution of P....P is
>>> closed...all instances of R in execution of P will be mapped to x+0i.
>>
>> If other values of C never occur then C is R.
>
> yes in P.......C is R in execution of P.....thus we can guarentee
> substitution!

Yes, as I said, it is reflexive.

>> Do you mean:
>>
>> #define Complex Real ?
>>
>> It makes no sense.
>
> it makes sense.....and it works!
>
> now try making it more interesting and see when it stops working.

It stops immediately.

>> A program P has inputs and outputs. It is a black box, what happens inside
>> it is no matter.
>
> it's no matter, if you choose it to be of no matter. If I construct a
> P....it's implementation is quite explicit....if I want to derive rules of
> construction, it's insides are of paramount importance.

Maybe, but it has nothing to do with substitution.

>> CD would be a subtype of DVD if your DVD player could play both.
>
> mine can!

See, it has input and output.

>> Now you
>> propose to open the cover and do what? Anyway the warranty is over! (:-))
>
> not with this.

OK, then glue down its tray and remove the output sockets. It might nicely
serve as a weight for aerobics...

>>>> P must have parameters to talk about
>>>> substitution. Or formally, the theorem we consider as a subject of
>>>> substitution has to have at least one quantor. As in the theorem I
>>>> mentioned before:
>>>
>>> the parameter is the type....not the object.
>>>
>>> i.e. the program is
>>>
>>> void main(void)
>>> {
>>> A p = new A();
>>> }
>>>
>>> yet we can talk about parametising the program P with type A........in fact
>>> am I not just talking about paramerised types?
>>
>> 1. The program main does nothing. Consuming CPU time and memory are
>> irrelevant side effects. A good compiler could safely replace it with NOOP.
>
> it could throw an exception....

That is not the part of the contract, so it may not. Otherwise, it is
invalid.

> I should declare 'globals' i.e. things like cout.....it's important for the
> moment that there are no in parameters.
>
> so maybe
>
> void (out A a)....

OK, now you can talk about out-substitutability. Then the following might
be important, if you don't override [but inherit via composition with type
conversion = mapping] then:

1. a generalization has no problems with out-substitutability.
2. a specialization has no problems with in-substitutability.

It seems that you are aiming at 1.

>> 2. Parametrizing program is formally the following: instead of a function
>>
>> P : Input -> Output
>>
>> you have
>>
>> P : Input x Parameter_Set -> Output
>>
>> No magic, there is still one program. That in the case of templates, the
>> compiler could generate for each value of Parameter_Set a separate piece of
>> code is no matter.
>
> What's Parameter_Set?

Generic parameters. For example: { type Real, type Complex }

> exceptions......and if I add all the other stuff....cout....it's fine until
> I add input parameters.

+ and allow user overridings. That means that Complex can safely inherit
Real.Get_Value but constructing a composition:

Complex.Get_Value = To_Compex o Real.Get_Value

Because To_Complex is defined on whole Real this composition always exists.

Still it may violate LSP, if that is defined as behavior [the original
definition, BTW]. The behavior might assume that Get_Value can read complex
numbers as well, if the result is expected to be a complex number. You
managed to re-use Get_Value of Real but it does not what it is supposed to
do. [ That happens because Get_Value is polymorphic and so it is in fact
defined on the class Real'Class and thus its contract is formulated for the
whole class. ]

>> For a function over the space R^n it is very different:
>>
>> f : R^n -> R^n
>> f' : R^n -> R^n x R^n
>>
>> There is no way to express dx/dy in R^n, because you cannot divide vectors.
>> But you well can complex numbers. The fact that division cannot be defined
>> in a vector space differentiates it form a field. Space is not a field.
>
> yes, but I can map the components of v to R....do my maths in R and map back
> to a v.
>
> though I can no longer remeber the point.

The point is that C is not a 2D space, it is a field.

>>>> The mapping should have some
>>>> *sense* for the program semantics.
>>>
>>> a+ib ---> a.......the sense is it is a projection onto the real line......
>>
>> Exactly! My program needs complex numbers and you offer me ones mapped to
>> the real line!
>
> P doesn't P needs real numbers....it doesn't give a monkeys whether they are
> secrety complex, or some extension of vectors.

If P needs real numbers, then it cannot work with the complex ones. Complex
is not a label, it is a property.

>>>> 2. It cannot effect P anyway, nobody will substitute Complex there because
>>>> P uses operations meanigless for complex numbers. So better make Preal and
>>>> leave sqrt alone!
>>>
>>> If this is the case...then (at least I have) learnt something....so that
>>> would be a good point.
>>> Do I have to duplicate all operators......I don't think I do....sqrt is
>>> hard....how about square?
>>
>> Square is an inverse of sqrt. Take one brick out and the building will
>> collapse.
>
> I agree that is the fear.....does it though ?
>
> RealSquare is inverse of R:RealSqrt in all R in P.
> ComplexSquare is inverse of C:RealSqrt in all C in P..................
> (remember I preserved RealSqrt)
> ComplexSquare is inverse of C:ComplexSqrt in all C in any new P
>
> so can I simply override Real:square with complex:square....and get away
> with it (remember the C's in P's are really just a+0i)?
>
> i.e. C's in P with use 'realsqrt' and 'complexsquare'.......can I express a
> problem in the C's of P that make statements about them different that using
> 'realsqrt' and 'realsquare'....I can't see one....

Consider the program:

function Test (X : Number) return Boolean is
begin
   return sqrt (X) * sqrt (X) = X;
end Test;

Test (-1+0i) = True
Test (-1) = exception

The corresponding theorem is:

forall x in Numeric_Set there is y in Numeric_Set such that y*y=x

This theorem is wrong with Numeric_Set = Real and true Numeric_Set =
Complex.

>>>> That is cut-and-paste. The above are two different programs: P1 and P2. One
>>>> cannot talk about any substitutability there. See above.
>>>
>>> it is !
>>>
>>> and does cut and paste and relable work?......yes!......so thats a start.
>>>
>>> if we go
>>>
>>> P(<A>)
>>> {
>>> <A> a = <A>.CreateNew(); // note this looks like a factory!!!!
>>> }
>>>
>>> then it's some sort of parametised class.......which is much more than cut
>>> and paste......yet this is what I'm talking about.
>>
>> See above. P does nothing!
>
> so make it do something then........let it be
>
> P(<A>,stdout out)
> {
> <A> a = <A>.CreateNew(); // note this looks like a factory!!!!
> out.print(a.ToString());
> }
>
> and ?

So you can talk about P defined on the set of all possible <A>. Then you
can consider some subset of <A> called T and observe/specifiy/imagine what
P does on T. Then take another subset S (of <A>) and ask whether P works on
S as it does on T. If it does, then S is LSP-substitutable for T in P.

>>>> Actually we can talk about types. When you write program Foo(int X); you
>>>> talk about int.
>>>
>>> I agree, but you difficult sentences i.e. there does not exist a x in R s.t.
>>> x*x <0.........seems somehow irrelevant to writing P......don't ask me why,
>>> I am simpy saying there may be a set of sentences that cause problems....but
>>> if we don't actually need them, then we don't have a problem......i.e. like
>>> Russels paradox......
>>
>> It is not a paradox. A theorem T is irrelevant to the semantics of your
>> concrete P if P does not imply T.
>
> what if P relies on T?

In which sense? If an implementation (proof) of P uses T then it is no
matter, because there might be another proof that does not use T. But if
P=>T and T=false, then P=false. So P should not imply T to be independent
on it.

>> It is a very common problem in
>> mathematics since Euclid's times: which part of geometry relies on the
>> postulate about parallel lines? These questions can be asked, they have
>> answers, but they are damn difficult questions.
>
> not really with this.

There are theorems in Euclidean geometry that cannot be proved without
using this axiom. There are some that can be. Among them there are ones
true in Riemann geometry as well. A "Riemann's object" is substitutable
into Euclidean geometry no longer you are trying to apply the axiom about
parallel lines to it. 

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