Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: Bob's 'Self-aggrandizing ignorant' Count: Was: What databases have taught me

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

From: David Barrett-Lennard <davidbl_at_iinet.net.au>
Date: 30 Jun 2006 22:01:34 -0700
Message-ID: <1151730094.249905.222170@b68g2000cwa.googlegroups.com>


Bob Badour wrote:
> 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.
> >
> > Yes
> >
> > Note that predictability depends on the problem you're trying to solve,
> > not on how you solve it.
>
> 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.

I was thinking in terms of the two programmers being given an identical requirements specification, and they both manage to write a program in the respective computational models without any errors. The predictability of the output is clearly just a function of the original requirements.

Of course the interesting question for us all is whether one solution is more natural, simpler or less likely to hide bugs.

>
>
> >>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.
> >
> > Agreed.
> >
> >
> >>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.
> >
> > Yes, this is both a good characterisation of OO, and of the types of
> > problems it is good at solving.
> >
> >
> >>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.
> >
> > I try to.
>
> 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?

Not in the general case. That's undecidable. However there are certainly a number of techniques to help formulate proofs of correctness of state machines. The OO community needs to investigate these.

We also need to know and document the known pitfalls. I hate the way OO designs can look correct yet hide subtle errors. One that comes to mind is the problem of dirty reads with the observer pattern. Most OO programmers aren't even aware of that lurking problem.

>
> > 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.
Yes. An interesting challenge for the OO camp is to find specific examples of algorithms that are very difficult to express in declarative ways.

>
> > 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.
> >
> > Agreed
> >
> >
> >>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.
> >
> > Yes, all that is usually true.
> >
> >
> >>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.
> >
> > Yes, the OO programmer is working at a lower level. Rather like a
> > human compiler!
>
> 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.

The challenge for the OO camp, is to find examples where the engineering of a tailored solution is so hard that it can't be automated. ie that it really requires human innovation.

The challenge for the non-OO camp is to build better programming tools that put the OO programmers out of a job!

>
> >>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.
> >
> > I agree.
> >
> > However, in certain domains I choose C++. I may spend lots of time
> > away from the code editor developing highly tailored imperative
> > algorithms that are provably correct, and then carefully implement to
> > get the best possible performance. This can be justified in some
> > areas of systems programming where you are confident that the problem
> > is well defined, you've done a proper analysis, and your tailored
> > solution will stand the test of time.
>
> 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?

Good questions!

> >>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.
> >
> > Spot on.
> >
> > I agree with all that you say, and think there are lots of OO
> > programmers who need a good swift kick up the backside.
> >
> > However, I don't think declarative approaches will ever completely
> > displace imperative approaches. But let's see more declarative code
> > than we have now.
>
> 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.

I admit that these terminology distinctions haven't occurred to me, and I probably use these terms too liberally.

In what sense do you distinguish imperative from procedural? According to Wikipedia...

Imperative programming : describes computation in terms of a program state and statements that change the program state

Procedural programming : is sometimes used as a synonym for imperative programming (specifying the steps the program must take to reach the desired state), but can also refer (as in this article) to a programming paradigm based upon the concept of the procedure call.

IMO, the following are the most common, basic types of programming

1.  Imperative programming  (which encompasses procedural programming)
2.  Functional programming
3.  Logic programming

"Declarative" refers to whether the program describes what something is like, rather than how to create it. This is more likely to happen in functional programming and logic programming.

Are you using "declarative" in the sense of using state to represent information, rather than executable code? A good example is where an OpenGL drawing can be achieved by statements that directly issue the drawing commands, versus a scene graph that simply represents what needs to be drawn using state, and a general purpose engine has to walk over the scene graph in order to issue the drawing commands.

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

Cheers,
David Barrett-Lennard Received on Sat Jul 01 2006 - 00:01:34 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US