Re: Bob's 'Self-aggrandizing ignorant' Count: Was: What databases have taught me

David Barrett-Lennard wrote:

> Bob Badour wrote:
>

>>Adrian Alston wrote:
>>
>>
>>>"Bruno Desthuilliers" <onurb_at_xiludom.gro> wrote in message
>>>news:44a2b543$0$6509$626a54ce_at_news.free.fr...
>>>
>>>
>>>>What bother me here is not about OO being born from needs for simulation
>>>>- FWIW, at least part of Bob's assertion seems perfectly and obviously
>>>>true:
>>>>
>>>><quote>
>>>>(OO) is a
>>>>computational model comprising a collection of features useful for
>>>>constructing large unpredictable state machines from small
>>>>predictable state machines
>>>></quote>
>>>
>>>Hi Bruno and all,
>>>
>>>I have lots of C programming experience but I'm pretty new to OOP can you
>>>please help.
>>>
>>>I can understand how objects are a sort of state machine but I thought OO
>>>programs should be predictable. What's this unpredictable bit about? I know
>>>about simulations but I write regular non-simulation apps. Ok the world
>>>around the program may be hard to predict but just how are my "OO" programs
>>>suppose to be unpredictable?
>>>
>>>Thanks in advance.
>>
>>Keep in mind that this is cross-posted to comp.databases.theory, and I
>>post from the perspective of c.d.t
>>
>>Unless you are writing simulations or chaotic attractors, your programs
>>are supposed to be predictable.

A quibble: the desire for predictability depends on the problem to solve, and the outcome of predictability depends on the proposed solution.

   I'm thinking specifically of an example of
> two programs, one written in C++ (an imperative language that supports
> OO), the other in PROLOG (a declarative language) that both generate
> identical output.

The outcome depends on the program texts (and the program texts for the compilers or interpreters, of course.) Whether they should generate identical output depends on the desires of the program text writers.

>>The unpredictability of simulations comes from the interactions among
>>many interacting state machines, the potentially large set of boundary
>>conditions and sometimes from the complex or chaotic equations used. The
>>whole purpose of the simulation is to discover what would happen in
>>various situations. If that were predictable, one would not need a
>>simulation.

>>When one uses OO, one naturally tends to have interacting state machines
>>and to have more of these than when does not use OO. When one's
>>application is naturally a very large state machine, one can decompose
>>it into smaller state machines as an abstraction technique to break it
>>up into human-manageable chunks.

>>However, if one were truly abstracting a large state machine like that,
>>one would tend to want to prove that the aggregate of the smaller state
>>machines omits no states and introduces no new and unwanted state
>>transitions etc. Nobody, as far as I know, practices OO in this way.

You are the first I have encountered, and I suspect you are from a very select few. Does any theory of state machines exist that facilitates this task?

> The study of (imperative) algorithms is an interesting field. Proving
> algorithms correct can sometimes take pages of formal, inductive
> proofs.

Dijkstra's papers on program structure address this very issue. I assume if you try to prove the correctness of your programs that you apply similar structuring techniques.

   Some concise, useful and powerful algorithms are implicitly
> imperative in nature, and trying to write them in PROLOG seems
> unnatural, inefficient and painful.

I don't necessarily agree with the statement that some algorithms are implicitly imperative or procedural in nature on the basis of possible implementations in PROLOG. Even if they are imperative, this does not preclude declarative solutions because a language can be both imperative and declarative, and one can imagine other non-procedural languages than PROLOG.
> However other algorithms are breathtakingly concise in declarative
> form. Quicksort is one that comes to mind.

I agree.

>>Further, as Dijkstra notes, the tools we use affect the way we think. If
>>one has a tool that makes creating large state machines very easy, one
>>will naturally tend to think of solutions in terms of large state
>>machines and more importantly in terms of state transitions. Focusing on
>>state transitions leads one to take a much more procedural and
>>operational perspective than is often warranted.

>>Declarative techniques allow one to specify solutions closer to the
>>level of intent. A good declarative formalism causes one to think more
>>about "what" than about "how", which naturally separates the concern for
>>correctness from the concern for efficiency. Those of us who understand
>>the relational model and SQL, understand that one can address the
>>concern for efficiency separately, for example by creating indexes, by
>>clustering data, and by automating the translation from the declarative
>>language to the physical hardware.

>>The OO computational model is simply not as amenable to higher order
>>transformations. The executable code more directly reflects the
>>specification. For instance, optimizers do not combine object classes to
>>transform a collection of possibly inefficient state machines into a
>>single more-efficient state machine.

Exactly! He spends much of his intellectual energy performing symbolic transformations (ie. from what to how) that are amenable to automation. What's more, the human mind often finds these transformations tedious and never evolved in the first place to perform them as accurately as a machine would.

>>As Aho et al noted way back when in the dragon book (on compilers),
>>algorithmic replacement arguably offers the greatest opportunity for
>>performance optimization and is almost never done because of the
>>enormous difficulty involved. Thus, if the optimizer could recognize a
>>bubble-sort, it could replace it with a quick-sort. However, I suspect
>>the task of recognizing the equivalence of any two arbitrary algorithms
>>is probably close to the complexity of the halting problem.

Absolutely. I have friends who have done real-time programming where the work had to be completed in assembler and where one had to prove the maximum number of CPU cycles consumed in the worst-case situation did not exceed some threshold.

These observations naturally lead one to two important questions:

1. Can one create a pair of languages where the proofs written in one language establish the correct outcome and where some other language instructs the compiler on how to implement to get the best possible performance?
2. Could one create a compiler to translate proofs as above in 1) into assembler code with an automated proof that the maximum number of CPU cycles consumed in the worst-case situation would not exceed some threshold?

These then lead into a third question: Can one combine the above features in a single product?

>>However, a declarative set-level language specifies what to do at a much
>>higher level often making the similar optimization a task of algorithmic
>>choice rather than algorithmic replacement.

I think you are confusing two distinct dichotomies:

Imperative vs functional
Declarative vs procedural

I am not sure where the declarative vs imperative misconception originated, but sadly, I see it has caught on.

> There seems to be a lack of science going on. For example, what work
> has been done to determine whether a given algorithm is best
> represented declaratively or imperatively?

Since declarative and imperative are not mutually exclusive, one must also consider solutions expressed as both.

   In my (limited) reading on
> comp.object, I haven't seen anyone discuss such an important question.
> Instead everyone seems to hand wave with all too generic, meaningless
> statements.

Indeed. Received on Fri Jun 30 2006 - 23:27:20 CEST