Re: LSP and subtype

On Sat, 05 Nov 2005 16:43:53 GMT, H. S. Lahman wrote:

> Responding to Kazakov...
>
> Thus to solve a non-Turing problem on a Turing Machine, one needs to
> provide two distinct solutions. The emulation infrastructure solution
> will be general so that, like Turing, it can be used to solve a wide
> variety of customer problems (e.g., any Turing problem also having
> real-time constraints). But it will not be a general emulation solution
> for all non-Turing problems because it needs to be tailored to the kind
> of emulation problem one is trying to solve (e.g., concurrency requires
> a different emulation infrastructure than fuzzy logic).

Yes, the system, considered as a whole, is not Turing. But this is already
abstracted away (I don't consider hybrid systems.) My point is that we
cannot describe incomputable elements in either of nGL. We can describe
some properties of Clock, but that will always be a "computable" part of.
So if somebody replaced Clock with something else having the same
computable part, there would be no way to determine any difference by means
of computation. Turing systems are native solipsists.

Now if we consider a hybrid system consisting of C (computable) and N
(incomputable) parts. If N is fixed, then varying C will draw a circle of
solutions you can achieve. You cannot leave that circle. UML describes the
part C. You can say that UML is independent on N, but this independence is
of the same nature as one of Assembler, being independent from the behavior
of a hardware register it sets to zero. Whether that causes a rocket launch
is outside.

>> Which only means that all these elements are included in the language as
>> terms. This is a flawed approach because there are too many of them, which
>> drives the language to a niche. A true abstraction is achieved *within* the
>> language. This is IMO the essence of languages evolution.
>
> No, they aren't included in UML as terms. That's the whole point of
> being a 4GL. The specific implementation mechanisms are completely
> transparent to the 4GL. The 4GL solution can be unambiguously
> implemented without change using any of them.
>
> 1 attends *
> [Class] ------------------ [Student]
> + subject + name
>
> That 1:* relationship can be unambiguously implemented with literally
> dozens of mechanisms (embedded pointers, pointer arrays, B-Trees, etc.)
> depending upon nonfunctional requirements. If a collection class is
> used, it will probably be in a commercial utility library but whose
> library and what the access syntax must be used is completely
> unspecified by UML.

But the problem to solve is not to represent relationships. It is, "running
a high school" or "social study of 3rd generation immigrant families" etc.
"Student attends class" is a basic statement which helps very little here.
Then diagram is by no means better than declaration of abstract interfaces:

type Student is abstract;
function Get_Name (Student) return Name is abstract;

type Class is abstract;
function Get_Subject (C : Class; S : Student)
return Subject is abstract;

They are equivalent, they both are totally decoupled from any concrete
implementation. This level of abstraction is already achieved by almost all
OO languages.

But that wasn't the point. It was:

1. Can a 4GL exhaustively describe all these embedded pointers, pointer
arrays etc. [~Turing completeness]

2. How readable, maintainable etc this description could be.

The question 2 need to be answered *only* if 1 is yes.

>>>So that OOA model is not inherently a computable solution; only its
>>>implementation in software is.
>>
>> OK, but the question is in added/lost values:
>>
>> 1. Can any interesting computable be exhaustively described in UML?
>> Example: matrix inversion
>
> Yes. For this sort of thing abstract action languages code looks pretty
> much like C code.

Which is bad, because C code is known to be unmaintainable. Then it looks
like machine code insertions. My point is that a truly higher level
languages would need no such insertions.

>> 2. Which incomputable solutions can be?
>> Example: halting problem
>
> Any problem where the OO paradigm is applicable.

Which problems are they? I bet you'll find no one.

> A more interesting question from your perspective would be: Can one
> express a fuzzy logic solution? The answer is Yes.

In general case no. Trivial fuzzy inference: if A and B then C is
incomputable. You have to get some measure of A and B (say possibility),
from that you can evaluate (only estimate, in fact), the measure of C.
Which fundamentally tells you nothing about C. The same situation is true
for probabilities. Let you know that Pr(Coin's head)=0.5, compute if the
coin will fall on the head. Any UML diagram of any size can solve no more
than a Turing machine could. All tricks you can imagine go no further
substitutions of the words in a finite dictionary. That changes nothing.

> True. But there are lots of problems one doesn't want to solve with OO.
> One common class of such problems are pure mathematical computational
> algorithms.

Which would mean that in your view OO is not an answer to the great SW
design challenge. See where 4GLs have led you? (:-))

>> That's easy. I just make one "reflection" step up. You say 1+1 is
>> non-functional? Fine! Let's write a calculator. Here you are, it is
>> functional now.
>
> What does 1+1 have to do with this? That's computable. The
> nonfunctional requirement is computability itself.

No you cannot escape this way, because I can make anything functional. For
computability: the application is a compiler to Turing-machine. The
compiler must reject all incomputable programs. That is a functional
requirement if the language to compile from is stronger than Turing.

>>>>I don't see any difference between a sequence of operations and a sequence
>>>>of messages "I'm done." Both are sequences and both do not answer the
>>>>question "what did you done?" It is the same abstraction level.
>>>
>>>The difference lies in the fact that an I'm Done message implies nothing
>>>at all about what happens next.
>>
>> As well as a return from a subprogram or an end of a rendezvous.
>
> Ah, therein lies the catch. How is the return done? If it is done
> synchronously (i.e., via procedural message passing), then the caller
> necessarily depends on the subprogram doing the Right Thing because it
> uses the result. If it is done be sending a message to announce the
> results to which someone (i.e., someone other than the caller) responds
> with a particular behavior, then it is just an input argument to the new
> behavior. Now both the original caller and the user of the results can
> be fully specified independently of what the subprogram does.

So the only difference is in using the result in a third subroutine? Where
is any problem with that? Either make the parameter object active, or call
the thing from where the result is needed, end of story.

It seems that you associate OO with active objects. BTW, Ada 83 concurrency
design was based on active objects [that time people would say "monitors".]
It is not the whole OO, which is orthogonal in my view to the issue of
functional vs. data decomposition. Anyway, practice showed, that in many
cases active objects were bad, especially because of race conditions and
performance penalties. Then pendulum swung and protected objects came into
light with Ada 95. And it became obvious that neither of paradigms is
universal, either has its weaknesses. One needs both.

>>>>>[Note that hierarchical structure is not a problem if the algorithm
>>>>>doesn't change. Once one gets the solution to work, one never has to
>>>>>touch it again. But when requirements change and force one to
>>>>>reorganize the tree, modify low level services, or change low level
>>>>>sequences for some but not all invocation contexts, things get messy
>>>>>very quickly.]
>>>>
>>>>Same as with messages. Only types decomposition makes difference.
>>>
>>>Not if the messages are peer-to-peer. Then one does not need to
>>>reorganize the decomposition tree; one just sends the message to a
>>>different place.
>>
>> Compare: gotos are good. If something goes wrong one just changes the
>> goto's label.
>
> Nice try. B-) You are correct that gotos provide a very convenient
> means of modifying flow of control, exactly like routing messages. In
> fact, one could construe a goto as a message without a data packet.
>
> However, there are whole a lot more methodological constraints on the
> construction of an OO application that ensure that one doesn't have
> problems.

Methodological constraint? Types give us language constraints, which is
much better. The issue is all about constraints needed to ensure
correctness.

>> Function can be as identifiable as any object. Consider the function Clock.
>
> OK, let's consider Clock as a problem space entity. What is the main
> thing one would expect any Clock to know? Answer: the current time,
> which is a knowledge responsibility, not a behavior.

A call to Clock can be blocking. Consider the requirement:

T1 := Clock;
T2 := Clock;

T1 < T2

To enforce monotonic time an implementation of Clock on a machine with a
low resolution hardware might wait for a next tick to come.

Even more complex behavior would represent Clock in a distributed system
with synchronized partitions.

The point is: to get an object, a function is as good as the object itself.
And from design perspective there is absolutely no difference between
function, constant, literal, constant object.

>>>As
>>>such they have a /collection/ of properties that are intrinsic to the
>>>underlying entity. While objects are abstract because they are
>>>representative, they are not abstract types because every object
>>>represents a unique concrete entity.
>>
>> The properties of an object are determined solely by its type. Type is the
>> word for "collection of properties." Instances of types are objects.
>
> Only if one is mired in the world of 3GLs. B-)) You need to turn that
> definition around. A type -- assuming one has need of one -- is
> determined solely by what an object's properties are. The object exists
> and has properties regardless of whether types are relevant.

Type is an abstraction, an artefact of design. It is the way we perceive
the world. We don't in concrete objects.

> Your notion of type has no meaning in most customer problem spaces. Ask
> a bean-counter what the type is for a T-Account. He won't have any idea
> what you are talking about but he can give you chapter and verse about
> what a T-Acount /is/. And when you try to explain that a type defines
> how one accesses the T-Account you're going to get a /really/ strange look.

Any software object has no meaning except one attached by the designer. He
can map:

1. Individual values. This is the most primitive level

value --> problem space element

2. The second level is to find commonalities between values:

set of values --> subset of problem space

3. The third level is to reflect relations between values in the set:

set of values x set of values --> subset of problem space x subset of
problem space

Note the product operation. A relationship involves at least two sets. The
result is a far more complex structure than just sets. Type is a set of
values + operations.

4. The fourth level is to identify relations between types. Note that at
this level it becomes possible to identify some design problems without
considering the problem space. This is why LSP comes into consideration.
This is a gain, because you cannot analyse the problem space exhaustively.
Even if you could, there would be impossible to ensure that all mappings
are right. At the 4th level you can do some things formally in the solution
space, much lesser than the problem space.

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

Relevant Pages

  • Re: Super Turing Machines
    ... > |>Problem for normal Turing Machines. ... > |>Can anyone provide an example of such a 'Super Turing Machine'? ... Turing introduced the definition of an 'oracle' which can supply on demand ... the formulation of questions of relative rather than absolute computability. ...
    (comp.theory)
  • Re: all the incompleteness proofs are worthless untill...
    ... I suppose I am referring specifically to Turing equivalence, ... computability is not bound by physical constraints. ... cone or the physical universe in some sense as "mathematical objects" ... very pedestrian view on mathematics and logic, ...
    (sci.logic)
  • Re: [PO] Proving a negative is hard
    ... This is just how TMs are defined. ... > Not according to another respondent's direct quote of Turing. ... language given in Davis "Computability and Unsolvability" ... bunch of other independently designed computation models, ...
    (sci.logic)
  • Re: [PO] Proving a negative is hard
    ... This is just how TMs are defined. ... > Not according to another respondent's direct quote of Turing. ... language given in Davis "Computability and Unsolvability" ... bunch of other independently designed computation models, ...
    (comp.theory)