Re: left-to-right (was In-Out Parameters for functions)

[Stephen Leake <Stephe.Leake@nasa.gov>]

Dmitry A.Kazakov <mailbox@dmitry-kazakov.de> writes:

> On 26 Feb 2004 23:58:22 -0500, Stephen Leake <Stephe.Leake@nasa.gov>
> wrote:
> 
> >Dmitry A.Kazakov <mailbox@dmitry-kazakov.de> writes:
> >
> >> The question is what gets lost if an evaluation order is fixed. I gave
> >> an example earlier:
> >> 
> >> for I in A'Range loop
> >>    Sum := Sum + A (I) + B (B'First + I - A'First);
> >>    ...
> >> 
> >> Here with left-to-right order the compiler cannot optimize neither the
> >> array index of B, 
> >
> >What do you mean by "optimize" in this sentence? the array index of B
> >is B'First + I - A'First. It must be computed before B(). In what way
> >would this be done differently by a "real Ada" compiler vs a
> >"left-to-right" Ada compiler?
> 
> A left-to-right compiler shall first evaluate B'First + I, then
> decrement it by A'First.
> 
> What I would expect from a good compiler is factoring out the cycle
> constant B'First - A'First and omitting all index checks for B when
> A'Length = B'Length. I am not sure if that will be possible for a
> strict left-to-right compiler without dealing with program
> semantics.

Ok. That is a good example.

So, Hymen; we now have (at least) two good examples of optimizations
that are useful, but would not be possible if the language required
right-to-left parameter evaluation.

Do you agree the cost of changing is to right-to-left is not worth the
gain?

> <snip>
> It is a pity that Robert Dewar isn't here.

Yes!

> >> Well, these optimizations could be made possible if the compiler
> >> might prove that the result does not depend on the order. That
> >> could be quite difficult to formally define, especially regarding
> >> numeric exceptions and floating-point accuracy stuff. Even more
> >> difficult it would be check.
> >
> >That is _precisely_ the point. Since it is difficult to formally
> >define and check the meaning of "does not depend on order", why do we
> >expect people to be able to do it? 
> 
> Exactly, they should not! People have to write programs so that they
> would be valid for any allowed order. If they don't the code is
> broken. In my view it is broken *even* if the language defined
> implicit order is the one assumed by the programmer.
> 
> My point is: either 1) the order is specified explicitly by the
> programmer, or 2) the code is valid for any order.

Hmm. You missed my point. Let me try again.

You have made two statements:

1) "the programmer must ensure the code is valid for any order of
   evaluation".

2) "it is difficult to check if things do depend on order of
   evaluation"

The second is paraphrased, but I believe it captures what you said
above.

These statements seem at odds, to me. You are requiring the programmer
to do something that is difficult. 

> >> But finally, if all that could be achived, then the compiler will be
> >> capable to simply detect that different orders give different
> >> results, and threat it as an error. Much better than fixing an
> >> arbitrary order!
> >
> >Why is that better? The goal is to have code that works (meaning
> >produces correct results :), on all compilers/platforms.
> 
> But the code has some semantics it implements, at least I hope it is
> so (:-)). This semantics is either order-dependent or not. That does
> not depend on platform. The goal is to implement that semantics. The
> rest does Ada.

Right. And _if_ the semantics happens to be order-dependent, then to
be portable, the same order must be used on every compiler/platform.
That is not possible in Ada 95; it would be possible in "left-to-right
Ada 95".

> > If I only
> >have to prove that one evaluation order is correct, that is easier
> >than if I have to think about many evaluation orders.
> 
> True. Weaker the precondition, harder to write the code. It is quite
> easy to write sqrt provided that the only valid value of the argument
> is 0. Alas, that would be not what people understand under sqrt. From
> software design point of view it is always worth to try to write
> order-independent code, like one with a weakest precondition. The
> opposite should be treated rather as an exception.

You are assuming the consequence of this argument :).

The point is that (perhaps) it is _not_ always worth writing
order-independent code.

So we need to talk about why you believe this to be the case - we
cannot simply say "yes, you are right".

> >But you haven't answered my question. Is there, in actual fact, any
> >compiler that actually does these optimizations?
> 
> Randy Brukardt gave one example. However I would like to stress that
> optimization and implementation freedom is only one, though important
> argument. Software design practice is no less important. Fixing order
> not imposed by the semantics, and thus an arbitrary order, is that
> sort of premature optimization Knuth wrote about. My concern is that
> fixing an arbitrary order would bless bad software design in favor of
> getting results now.

But it is only bad _because_ it prevents optimization. At least, that
is the only argument I have heard so far. You do _not_ give a
different argument in this paragraph; you just repeat the optimization
one.

What _other_ reason is there?

Software design practices such as "write order-independent code" are
useful simplifications of complex arguments; they allow programmers to
get on with day-to-day work without spending lots of time thinking
about arcane compiler implementation issues :). 

However, in _this_ discussion, we are trying to elucidate the complex
argument behind this particular software design practice, in order to
decide if it is still valid.

> >> >Ada is supposed to be about clear, unsurprising code. Subtle order
> >> >issues are just that - "subtle". If the language _could_ make them a
> >> >non-issue, at very little cost, I think it _should_.
> >> 
> >> Right, the present situation is not good. But IMO the solution lies in
> >> introducing formally pure functions and imposing limitations on use of
> >> impure functions (and procedures with results) in expressions.
> >
> >That's way more work than simply requiring left-to-right, and
> >therefore far less likely to happen.
> 
> AFAIK Ravescar profile would be a part of the standard. 

Yes, the Ravenscar profile will (probably :) be standardized in Ada
0Y. But that will be as an restriction pragma, allowing users to
choose a subset of Ada.

> A time may come when some SPARK ideas will be evaluated too.

If you mean that the SPARK language will be added as another optional
Ada standard, I doubt it. SPARK may become a standard on its own.

-- 
-- Stephe