Re: Liskov Substitution Principle and Abstract Factories

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

Date: Fri, 14 Jan 2005 11:57:13 +0100

On Thu, 13 Jan 2005 18:17:36 -0000, Mark Nicholls wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> news:fwowg4yqpybz.1g0qhrqzzwigk.dlg@40tude.net...
>> On Thu, 13 Jan 2005 15:36:31 -0000, Mark Nicholls wrote:
>>
>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
>>> news:1bnewz2zpdx0o.611uno3swovd$.dlg@40tude.net...
>>>> On Thu, 13 Jan 2005 11:17:13 -0000, Mark Nicholls wrote:
>>>>
>>>> OO is not equivalent to prefix notation. To put it clear:
>>>>
>>>> F is a method of X = the subroutine F has at least one dispatching
>>>> parameter or result. Period.
>>>
>>> "one dispatching parameter" ?
>>
>> [in C++ only one 1st parameter of a virtual function is dispatching.
>> Virtual functions dispatch when called (on a reference X.f() or pointer
>> X->f()). The actual type is determined by the vtab pointer. vtab is the
>> dispatching table of the corresponding polymorphic function. Because C++
>> has single dispatch, its dispatching tables are vectors. In general case
>> they are n-dimensioned matrices, where n is the number of dispatching
>> parameters.]
>
> this is what I need to absorb.....to be I see v-tables...your saying in
> general they are matrices?
>
> clunk, clunk, churn churn.
>
> so
> the 'function' call
>
> void foo(int, char,double)
>
> is dispatched via a three dimensional set of function pointers?

Yes. int, char, double have type tags which are used as indices for the
matrix, if you mean how that could be implemented.

> then how do you get to methods?
>
> in C++
>
> void foo(int, char,double)
>
> maps to
>
> int::foo(char,double)
>
> and in a sense that would seem central to OO modeling i.e. you attach
> methods to classes, not to cross products of classes.

But that's obviously wrong. Methods are attached to tuples of types not to
singular types. Otherwise you will never get arithmetic operations,
assignment, equality etc right.

> how do you do a class diagram if the methods do not belong to a specific
> class, but to a cross product of them?

I do not put methods in types anyway when I draw a diagram. To it is
relationships between types is of the major interests. Then you can still
place a method in a type box if it dispatches on this type, just do not
forget that it may also appear in some other boxes.

>>>>>>> if it does that you *know* (well almost) that P is a member of that
>>>>>>> set.....isn't that the basis of design by contract.
>>>>>>
>>>>>> It is, but how do I know it?
>>>>>
>>>>> many contracts are provable.
>>>>> most software is statistically 'provable'...i.e. testing. The compiler does
>>>>> generally prove alot.
>>>>> So if I can say
>>>>>
>>>>> p(A subtype B) = 0.99
>>>>>
>>>>> I can very dubiously say
>>>>>
>>>>> p(LSP(A,B,{programs containing A}) = true) = approx 0.99 (I accept
>>>>> this is highly dubious, there are all sorts of assumptions).
>>>>
>>>> First, what is p? Definitely it is not Pr (probability). And if that were
>>>> Pr, then what could it mean? You know any Pr not equal to 1 guaranties
>>>> nothing. However, statistic cannot be applied here. It is not a stochastic
>>>> thing. The program is either wrong or not (conditionally to the
>>>> requirements given).
>>>> So a bug is either here or not. Consider a statistical
>>>> experiment: you run the program 1000 times with the same data and see how
>>>> many times the bug shows itself. Nonsense. The only random thing lies
>>>> outside, in our perception of a program and its validness. That can be
>>>> considered as random variables. But that has nothing to do with the program
>>>> itself. It is psychotherapy, at best.
>>>
>>> If we cannot logically prove correctness, then we can only statistically
>>> define it.
>>
>> How? To define something statistically you have to present the space of
>> elementary outcomes. What are elementary outcomes? Failed program runs?
>
> it could be the expected value of 'success' over the cross product of
> inputs.
>
> success would be if expected behaviour = contracted behaviour.

Those are not random! For each input the program either fails or not, it is
deterministic.

> you would then have to throw some spurious assumptions at this to enable you
> to approximate that....but that's statistics.
>
> If I build a bridge I am not sure it will stand, but I may be 99.999% sure
> it will.....and then the wind blows in a specific direction, at a specific
> speed and we discover that it resonates, and falls down.

The laws of physics describing behavior of a construction have statistical
nature. This is why one can talk about Pr (bridge will stand). The laws of
Boolean algebra have nothing to do with statistics. So Pr (program is
valid) is sheer nonsense. It is like to talks about Pr (2+2=4).

>>>...that's the difference between maths and physics/engineering.
>>>
>>> not ideal....no....but this is the reality.
>>
>> You cannot apply any theory without reasonable justification.
>
> I have no model as yet.
>
> naively
>
> if a program worked yesterday, and last week, and for the last 3 years, you
> would expect it to work tomorrow.

On different data? Come on, it is like to expect that if test A passed then
the test B would too. OK, it is in human's nature to hope in that, but it
has nothing to do with the reality.

> It is not proof, but you do this every day, you have a model in your head
> that says so.

Right. This is what I meant. The randomness lies in our heads, not in the
software. So the "theory" describes not the distribution of faults, but the
distribution of our beliefs in the software. Good to fake up our customers,
but no other use. Just psychotherapy, as I said before.

> If you can produce a reasonable subset of the space of inputs, and relate
> those to the set of inputs likely to happen in a given program, then you
> have the basis for a statistical indicator.

Huh. To do this you have to exactly know how the program behaves. But this
is what you are trying to describe! Otherwise, I would claim that the
program behaves independently on different inputs. But how can you imply
any program behavior on untested inputs? That's the first question. The
second question is how do you know that the produced subset of inputs
reflects the customer's set of inputs? We know too well that all programs
are used in a way nobody (either programmer or customer) predicted during
development.

>>> I cannot verify the implementation without looking at it!
>>
>> But contract is less than semantics. Otherwise, there were no need in
>> programmers!
>
> I can verify that a set of contracts are consistent.
>
> I need to look at the implementations to verify that the implementations
> satisfy the contracts....thus can I not claim that the set as a whole
> satisfy the contract.

OK, but DbC assumes that you start with contracts. Implementations come
afterwards. But the problems with substitutability appear long before that.
You put down the contracts, everything seems to be OK, and then oops,
circle cannot be resized!

>> This is what polymorphic programs are. You have some polymorphic Pi defined
>> on the class A'Class. The class includes A, B and all other derived types.
>> P2 is defined on A'Class. It has an implementation for A and another for B.
>> P1 is also polymorphic, but we didn't override it for B, so B uses the
>> implementation given for A.
>
> I think I'm catching on, are you viewing P as a polymorhic type as well as
> A?

The polymorphic type is A'Class = { x | x in descendant of A }. In the
terminology I use polymorphic type = class.

Virtual = dispatching = dynamically polymorphic P1 and P2 are defined on
A'Class, not on A or B. A::P1 and B::P1i are parts of P1.

>>>> Nope. char is not substitutable for int. Consider a program that reads ints
>>>> from a file. Substitute char and you will have range error. It is a common
>>>> error. To judge about substitutability you have consider mappings
>>>> char<->int and the parameter modes of each given method (that includes the
>>>> results as well).
>>>
>>> ! aren't you just saying
>>>
>>> LSP(int,char, {set of programs using int}) = false
>>> LSP(char,int, {set of programs using char}) = false as well!
>>>
>>> um, could we define a char in such a way that it would though.
>>
>> It would useless then. But for a given set of int-programs we could have
>> char substitutable. We just cannot do it for all int-programs,
>> indiscriminately.
>
> not with this, can we not define char, and the set of P operating on it,
> s.t. we could substitute int.
>
> heres a start
>
> P1 = {}.....success!
>
> P2;
>
> void Print()
> {
> char c = 1;
> print c;
> }
>
> is that not success;
>
> I have a set of 2 programs.
>
> if that worked I could probably create a whole load of programs by
> induction.
> Find an orthogonal basis for the behaviour of those programs, and I have an
> n dimensions space.
>
> but now your going to tell me that P2 doesn't work.

It works, but already + will not:

char c = 1;

c = c + 256;

And yes you can present a set of working Pi, but it would not help. Because
let somebody have written P, is P in {Pi}? It is undecidable.

In my perception the very idea of LSP was to provide a framework for
program construction which would not let us leave {Pi}. So were the
definition of how to create new types, the statements about pre- and
postconditions etc.

>>> it may still be of practical use.....if the problem of identifying the set
>>> of non halting substitutions is not halting.
>>
>> Yes we should approach it from the other end, constructively, step by step.
>> Everything that is provable should flow into the language design in the
>> form of language constructs. The unknown rest will always be, but more and
>> more routine software design will fall into your safe set S. That's the
>> program for the future.
>>
>
> It's unnerving like incompleteness........(which I also fail to understand
> to the point of almost not believing).
>
> but
>
> LSP(A,B,{}) = true....so I know something.

Compare, I have to implement sine. Well, sin (0) = 0. I know something.
Moreover I know sin (Pi) = 0. Does it help me much? 

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