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

From: Stephen Leake (Stephe.Leake_at_nasa.gov)
Date: 02/27/04

  • Next message: Jeff C,: "Re: c2ada" 
    Date: 27 Feb 2004 09:07:12 -0500
To: comp.lang.ada@ada-france.org

    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
  • Next message: Jeff C,: "Re: c2ada"

    Relevant Pages

    • Re: Brian Kernighan, maybe Im not worthy, maybe Im scum
      ... what experienced programmers do, ... the compiler doesn't have the free pass to /assume/ that the function ... Nobody has recommended doing all optimization by hand to my knowledge. ... Compiler behavior in optimization simply has no place in a language ...
      (comp.programming)
    • Re: GNAT Optimization of Constant Expressions
      ... Ada, so I surmised that the constant math expressions in the code ... below were being precomputed by the compiler in C and Fortran, ... the compiler has to do a loop-hoisting optimization in order to ... I suspect that from your results, Gnat ...
      (comp.lang.ada)
    • Re: Interesting article by Randall Hyde
      ... >> language, not the code that the compiler generates. ... *what* code the compiler generates is up to the implementor. ... > I didn't see anything under "Optimization". ... > Perhaps because I'm not a long-experience `c` programmer, ...
      (comp.lang.asm.x86)
    • Re: Syntax for user-defined infix operators
      ... Maybe for Ada this are counterexamples, but for Seed7 they are not. ... easy to see why a compiler complains. ... It would only bother the programmer and make the program less readable, ...
      (comp.lang.misc)
    • Re: Certified C compilers for safety-critical embedded systems
      ... wrong with running 'lint' or whatever in addition to the compiler. ... to perform the checks that are routinely done by Ada compilers. ... The average C programmer is not. ... > be used in a safety critical environment I think things would change. ...
      (comp.lang.ada)