Re: LSP and subtype

On Wed, 02 Nov 2005 18:06:05 GMT, H. S. Lahman wrote:

> Responding to Kazakov...
>
>> This particular case is still Turing's. Remember your point about
>> functional vs. non-functional requirements? As long as all requirements are
>> non-functional everything stays Turing-complete. Furthermore, I believe it
>> is easy to show that if time is quantized then it will fall back to
>> Turing-completeness.
>
> My point here is that the original Turing Machine was a pure serial
> device; it did not model hardware concurrency. One employs concurrency
> to resolve a nonfunctional requirement on performance. But the
> resolution of functional requirements is not dependent on how fast the
> software runs.

Right. Concurrency is not a functional requirement, so Turing machine
qualifies.

> However, the concurrency solution cannot be directly implemented on a
> Turing Machine. To do concurrency one must supply addition
> infrastructure in the software like time slicing to /emulate/ concurrency.

Which changes nothing. You have timer interrupts and timer counters as the
inputs. It is no different to probability or fuzzines. They all are
examples of non-computable things which number of states is uncontable. Yet
all solutions we are talking about are approximations which use a finite
number of states. Moreover these states are different from the original
ones. Therefore it stays Turing.

> The same thing applies to multi-processors. If the multi-processor
> hardware provides synchronization it would not be a Turing Machine and
> Turing-completeness would be irrelevant. If the hardware does not
> provide synchronization support, then the software must and it can only
> do that as a pure Turing Program if one assumes each processor is an
> independent Turing machine and provides synchronization infrastructure
> in the software.

Observe difference between the following statements:

1. Random generators, clocks etc are not Turing-complete.

2. Programs using the above are not Turing-complete.

Concurrent languages have clock as an atomic building block. Which is truly
atomic because you indeed cannot split it. Clock is a term. Similarly Pr()
Pos() are terms. Even button click is a term, because you cannot look into
a user.

>>>Any "fuzzy" system where a viable computation result is Maybe.
>>
>> No. All they are Turing-complete. "Maybe" is just a value [ maybe X <=>
>> Pos(X)=1 & Nec(X)=0.] It is like probability, which is also just a number,
>> that can be estimated with a desired precision. Only when you liked to deal
>> with "distributions" as a whole, rather than with concrete realizations, or
>> perform fuzzy inference in an exact manner (without defuzzification), then
>> you'd leave discrete computations.
>
> What you are describing is abstraction of a concept that has no direct
> computational representation into a representation that is a direct
> computational representation (i.e., a number). IOW, it is an emulation
> infrastructure that the software developer must provide; it is not
> inherently supported by the Turing Machine. To put it another way, the
> notion of Maybe is not representable as a number until one makes
> specific assumptions about the problem space.

Right. In other words it is the difference between the problem space and
the computation space. Note that the same is true for plain numbers as
well. Software integer is not an integer, it is a model of. Models have no
meanings, they are mappings to meanings. Completeness is relevant because
it limits which mappings might exist. More completeness you have, better
mapping you can achieve.

> BTW, UML can be translated into PC code.

The quantifier should be "forall". "Exists" is not enough.

>>>>Nope. Turing completeness is about a definite class of computational
>>>>problems one can solve.
>>>
>>>A definite class of computational problems that is /defined/ based on
>>>whether they can be solved on a Turing Machine. B-)
>>
>> Exactly my point!
>
> But it's a circular definition!

It is not very good, but it isn't circular. Turing machines are well
formalized. So far we have nothing better than that. Quantuum computing may
overturn our world or not. Or consider, that somebody would manage to
create true AI on Turing-complete basis. That would effectively mean that
there is simply nothing beyond that, because anything else would be
incomputable in absolute (=human) sense.

>>>One can't tell until a Quantum Machine is defined with the same rigor
>>>(and utility) of a Turing Machine. However, once such a definition is
>>>available, a priori I see no bar since UML is independent of the
>>>computing environment. That is, whatever paradigm equivalent to 2GL/3GL
>>>programs that one ends up using for quantum logic, I suspect an OOA
>>>solution will be mappable into it.
>>
>> This is a very strong statement. It is roughly equivalent to saying that
>> you have a universal language for everything. For the start, let's consider
>> mathematics, physics, law, pop-music as computing environments... And there
>> are hard facts against it (Goedel).
>
> How strong is, "I suspect..."? B-)

(:-))

[...]
> On the contrary, I think abstraction is hugely important. Abstraction
> is the reason that 3GL code is portable across different platforms. A
> similar benefit lies at the 4GL level across whole environments. That's
> why I believe defining '4GL' in terms of computing space independence is
> the best way to capture what is probably the most important feature.

I see no significant difference between "platforms" and "computing spaces".
I thought that you meant independence on the mappings computing space ->
problem space. That is what we could flag as an OO philosophy. [ It seems
totally unrealistic to me. ]

>>>>Because it is not! We have clarified that UML is not Turing-complete. That
>>>>explicitly means that there exist problems which cannot be solved in UML.
>>>>Period. A direct implication from this is that if I wished to use UML (as a
>>>>language) to solve such problem I would be forced to look into the blocks.
>>>
>>>Not quite. I said I didn't know whether UML was Turing-complete or not
>>>and, furthermore, that I didn't care because I never have to think about
>>>Turing-completeness at the application development level in UML.
>>
>> You need not to think about it. Or better to say it would be too late to
>> think about it during development, if something went wrong.
>> Turing-completeness is a premise.
>
> And the core of our disagreement is that I see no demonstration that
> such a premise must hold for any level of abstraction beyond 3GLs. I
> see no reason why the 4GL cannot be implemented with the same sorts of
> added-value emulation infrastructures that one would uses to implement
> concurrency or fuzzy logic in a 3GL.

Maybe it can, but I see no reason why 3GL blocks must be considered as
atomic. There is a reason for concurrency, because otherwise it will be
incomputable. But 3GL stuff *is* computable. So what's the gain of not be
able to do something? The only one is to have a weaker language. What for?

>>>In a translation environment it is the job of the transformation engine
>>>to optimize for nonfunctional requirements in the computing environment
>>>in hand.
>>
>> Let's start with functional ones. Turing-completeness is about them.
>
> The functional requirements are all resolved (and validatable) in the
> OOA application model (aka PIM in MDA terms). But they are resolved
> purely in problem space terms, not computing space terms.

Come on, a trivial diagonal proof will show that you cannot do it for any
problem space. So there is a set of spaces you can model. If you start to
analyze what they all have in common, you'll see that it is computability.
That path was already traversed in the last century by Turing and others.
There is no need to do it again.

>>>However, it is a fait accompli that transformation engines do produce
>>>correct code and they do optimize even though the UML model is
>>>essentially devoid of 3GL type systems. So my question still stands:
>>>why would one want to look inside their "blocks"?
>>
>> Because UML cannot describe and then translate: "let M be a square matrix
>> with elements from the field F. Get ^M such that M*^M=I", to *any*
>> computing environment except than maybe the programmer's head! This is what
>> distinguishes UML from programming languages.
>
> We've been here before. You could do it in UML but you wouldn't want to
> because all the manipulations are invariant and defined outside the
> scope of the customer's problem so there are better ways of representing
> raw algorithmic processing.

So? It is even worse. It was:

Customer problem <--> Mathematical problem <--> Software problem

Now you are going to replace it with:

Customer problem <--> Software problem

and describe the whole customer problematic and accompanying theories
directly as a software problem. This is exactly what is called low-level
abstraction: to count fingers without understanding that there are integer
numbers. Additionally, a UML tool or its user should be able to deduce
arithmetic and linear algebra from a concrete customer problem? Come on!

>>>>This cannot be done automatically.
>>>
>>>You keep saying things like this but the fact is that commercial
>>>transformation engines do such optimization once the nonfunctional
>>>requirements are defined. And the resulting code will work correctly.
>>>And they have been doing it for nearly two decades.
>>
>> Yes I do, because it is still unclear which functional requirements qualify
>> here.
>
> All the functional requirements about What the software should do
> qualify for the OOA model.

Fine. Then I can take any computable problem an present it as a functional
requirement. It is equivalent to saying that thing is at least
Turing-complete. q.e.d.

>>>>>The primary goal of the OO paradigm is to provide maintainability.
>>>>
>>>>It is to have better way of handling growing complexity.
>>>
>>>That applies to all software development paradigms; it is like saying
>>>that the most important characteristic of OO programs is that they
>>>should execute correctly.
>>
>> goal /= characteristic of
>
> OK, but it seems to me that whichever view one adopts, it is still a
> generality. Both the OO and FP paradigms evolved from SA/D/P -- albeit
> in quite different ways. Wasn't the goal of both paradigms to provide a
> better way of handling growing complexity?

There could be many solutions of the same problem. Then as I said in my
view the opposition OO vs. FP is a 2.5GL one. It will vanish with the next
generation of languages.

> <aside>
> Not necessarily. Where I worked before retiring we had various
> standards. One was that all date computations would be done using
> reusable binaries (VMS system services on VAXen or predefined commercial
> libraries on Unix or PC boxes). So our entire Y2K validation was
> basically checking with the vendor whether they had done their job and
> we had no problems.
>
> Similarly, we ported about 3 MLOC of complex device driver that used a
> /lot/ of bitwise operations from RSX 16 -> VMS 32 bits in six months
> with about four people. Most of their effort was devoted to converting
> system service calls from RSX to VMS and testing. There were only a
> handful of instances where someone had broken the standard and
> hard-wired a mask. [Of course it helped that we were using BLISS which,
> unlike C, does not leave things like bit field packing as a platform or
> vendor option. B-) (As an Ada Guy, I'm sure you share my view that C's
> legendary portability is pretty much a joke.) As a result the binary
> libraries our software built for customers were completely portable from
> PDP11s to VAXen so the customer's jobs ported without a hitch.]
>
> So I think Y2K and porting examples are weak in this context because the
> impact is more about coding standards, basic good design, and specific
> language support. (Insofar as impact is concerned; I agree there are
> better problem space examples of where impact is vastly different.)
> </aside>

[ These examples do not qualify, because they refer to DEC systems. These
were unique in quality of both the software and hardware design, in all
thinkable respects. DEC Ada 83 and C compilers were legendary for their
excellence. I never used BLISS, though. Porting from RSX to VMS, what a
laughable task! How about porting between two versions of MS Visual C++!
(:-)) ]

>>>That's only true if one needs to make choices among individual
>>>algorithms. If I want to provide a general optimization package, it
>>>would have an assortment of operations research techniques at its
>>>disposal (linear programming, dynamic programming, monte carlo, etc.).
>>>Deciding which approach was the best to use _for a particular problem_
>>>is a complex decision based on the nature of the problem in hand.
>>
>> You cannot *formulate* an optimization problem without types. To optimize
>> something you need at least a space of that something (one type) and goal
>> function (yields another type, ordered, limited on the space, etc).
>
> You're talking to a guy who spent almost a decade doing OR using FORTRAN
> before anyone ever heard of types. B-) The mathematical specifications
> of things like network flow problems was being specified as far back
> back as the '40s and had nothing to do with types because they weren't
> invented yet.

.... as well as programming languages. I didn't mean data types. I meat
types as abstractions. They were well known as mathematical structures like
groups, fields, spaces etc long before programming languages evolved.

> We've been here too. The procedural paradigm is about organizing
> sequences of operations. That has an implied imperative: do This, then
> so This, then ... do This. A primary tool for organizing those
> sequences is functional decomposition where functions are organized
> hierarchically so that high level functions invoke low level functions.
> That hierarchical structure necessarily imposed specification
> dependencies because the higher level functions cannot be specified
> without also specifying all of the descending functions in the call
> stack. That's because the nature of such decomposition means the lower
> level functions are just extensions (subdivisions) of what the higher
> level function does.
>
> The OO paradigm eliminates the hierarchical spaghetti dependencies by
> abstracting objects as identifiable /intrinsic/ properties that are then
> coordinated for the solution by peer-to-peer interactions rather than
> hierarchical interactions. Those communications are based on
> announcement messages (I'm Done) rather than imperatives. But that
> construction paradigm is completely opposite to organizing around
> sequences of operations so the notion of a function as a first class
> object is antithetical to the OO paradigm.

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.

> [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.

>>> It doesn't matter what is /possible/ to
>>>do with a 3GL type system. In the OOA/D paradigm one abstracts problem
>>>space entities, not functions.
>>
>> So? Rename "function" to "entity", what changes?
>
> Semantically I think it is apples and oranges. A function is always an
> operation and it only has one functionality. But an object abstracts a
> problem space entity with identity that has multiple distinct
> properties, only some of which (if any) are opreations. And the object
> may have multiple properties that are distinct operations.

You are mixing objects and abstract types. Object or function, it is the
same abstraction level (2.5GL). Object does not have any operations, same
like a function does not possess any operands. It is the type with has! The
type brings both together.

> All I have been saying is that OOA/D is based upon class systems, not
> type systems. One uses type systems at the 3GL level because they
> provide a very convenient mechanism for mapping abstract concepts
> directly onto procedural block structuring, message passing, and scope.
> OTOH, class systems are much more versatile for mapping to typical
> customer problem spaces, which are usually not organized around Turing
> Machines. Fortuitously, there is an unambiguous mapping between class
> systems and type systems that one can employ when transforming UML to OOPL.

I disagree, of course, but I better restrain myself from starting another
"type vs. class" debate! (:-))

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

Quantcast