Re: and then

Re: and then

[Robert Firth]

In article <19930406.143008.278@almaden.ibm.com> jnestoriak@vnet.IBM.COM writes
:
>At a recent code inspection, someone suggested that I convert a
>series of and's to and then's "for performance".  I expect that

Don't do it.  The short-circuit forms "and then" and "or else" are
there to allow you to state that the two conditions must be tested
in the order in which they are written, eg

	if I in A'Range and then A(I) = 0 then ...

where the code would be incorrect with just "and".  Using them when
they are not necessary is just going to give you, or someone else,
one more maintenance headache.

Re: and then

[Charles H. Sampson]

In article <19930406.143008.278@almaden.ibm.com> jnestoriak@vnet.IBM.COM writes
:
>At a recent code inspection, someone suggested that I convert a
>series of and's to and then's "for performance".  I expect that
>90+% of the time all the conditions will be true anyway.  But is
>it really true that and then will get better performance than
>and?  I realize this is probably a compiler dependant question.
>Also, I question the value of doing such a thing styllistically.
>Any opinions?

     My style is to use the boolean operators generally, reserving the
short-circuit forms to document that the second operand should not be eval-
uated under some circumstances.

     Unfortunately, that style can conflict with efficiency considerations. 
Ada compiler writers appear to have abdicated their responsibility and make
no attempt to determine when boolean operations can be optimized as short-
circuit.  (Somebody contradict me, please.)  They apparently feel that if
the programmer wants short-circuit he can ask for it.  In addition, there
are cases when it is unreasonable to expect such an optimization; when the
second operand contains a function reference, for example.

     That said, I still use my style when coding and look for bottlenecks
during testing if performance is poor.  If efficiency requires that I use
an unnecessary short-circuit form, I document that fact in the code.

                                   Charlie

Re: and then

[Ray Harwood -- Data Basix: (602)721-1988]

In article <19930406.143008.278@almaden.ibm.com>, jnestoriak@vnet.IBM.COM
writes...
>At a recent code inspection, someone suggested that I convert a
>series of and's to and then's "for performance".  I expect that
>90+% of the time all the conditions will be true anyway.  But is
>it really true that and then will get better performance than
>and?  I realize this is probably a compiler dependant question.
>Also, I question the value of doing such a thing styllistically.
>Any opinions?

There is certainly nothing "wrong" with the short ciruit forms... please note
this discussion applies to both AND THEN and OR ELSE.  Indeed, as a contractor
of Ada software testing, I try to convince my clients that short circuit forms
should ALWAYS be used, unless there is a compelling reason to REQUIRE the
evaluation of each and every boolean term in an expression!  

My suggestion:  *Always* put the most commonly FALSE term at the BEGINNING of a
string of AND THENs, and continue in decreasing order of frequency.  That way
as soon as the code runs across a FALSE term, the entire expression is declared
FALSE and the appropriate action taken without further needless evaluation. 
This is PARTICULARLY efficient if there are multiple FUNCTION calls in the
boolean expression; saving the overhead of just a few calls (especially, for
example, in a loop) is well worth the "headache" of typing a few more
characters.

For OR ELSE, put the most commonly TRUE term at the beginning.  That way, as
soon as the compiler runs across a TRUE term, the entire expression is delcared
TRUE and appropriated action taken.  Note:  There is no "short circuit" form
for XOR... you just can't decide the outcome of an XOR without evaluating both
parts!

Ray
-----
Ray Harwood          | Data Basix              | Adjunct Faculty, East Campus, 
Voice: (602)721-1988 | PO Box 18324            |     Pima Community College
FAX:   (602)721-7240 | Tucson, AZ 85731        | Instructor in Ada and Pascal
           Internet: | rharwood@Data.Basix.COM | rharwood@east.pima.edu
** For info on Data Basix, send EMail with no subject to Info@Data.Basix.COM **

Re: and then

[Mark Lundquist]

In article <1993Apr7.173556.17184@sei.cmu.edu> ae@sei.cmu.edu (Arthur Evans) wr
ites:
>In connection with a discussion of Ada's short-circuit control forms,
>sampson@nosc.mil (Charles H. Sampson) says
    Ada compiler writers appear to have abdicated their responsibility
    and make no attempt to determine when boolean operations can be
    optimized as short-circuit.

  Well, I'm not surprised that they make no such attempt, but it's not
  because they have abdicated any responsibility.  ARM 4.5(5) says of
  expressions involving 'and' and 'or':
     The operands ... are evaluated in some order that is not defined by
     the language (but before application of the corresponding operator).
  In other words, both operands MUST be evaluated.  That requirement is
  not unreasonable given the availability of the short-circuit forms.
>
 

I don't think it means anything MUST be evaluated.  If you write

	if TRUE and TRUE then
		do_something;
	end if;

are you saying the RM says that code must be generated to evaluate
the operands and apply the operator?

The RM is not talking about implementation, it is specifying the
*logical* semantics of these operators.

Re: and then

[enterpoop.mit.edu!usc!cs.utexas.edu!mars.tsd.arlut.utexas.edu!gardner]

sampson@nosc.mil (Charles H. Sampson) writes:

>In article <19930406.143008.278@almaden.ibm.com> jnestoriak@vnet.IBM.COM write
s:
>>At a recent code inspection, someone suggested that I convert a
>>series of and's to and then's "for performance".  I expect that
>>90+% of the time all the conditions will be true anyway.  But is
>>it really true that and then will get better performance than
>>and?  I realize this is probably a compiler dependant question.
>>Also, I question the value of doing such a thing styllistically.
>>Any opinions?

>     My style is to use the boolean operators generally, reserving the
>short-circuit forms to document that the second operand should not be eval-
>uated under some circumstances.

I humbly suggest that you change your perspective.  When I encounter a
non-short-ciruit of the boolean operators I ask why both expressions
_must_ be evaluated; i.e., the short-circuit forms are the default and
the other forms are used only when both expressions must be evaluated.

Also, I avoid writing functions that have side effects.  Since (as
best I can reason at this early hour) both expressions need to be
evaluated only when both have side effects, I rarely use the
non-short-circuit forms.

Re: and then

[Christopher J. Henrich]

In article <1993Apr7.162133.3564@nosc.mil> sampson@nosc.mil (Charles H. Sampson
) writes:
>     My style is to use the boolean operators generally, reserving the
>short-circuit forms to document that the second operand should not be eval-
>uated under some circumstances.
>
>     Unfortunately, that style can conflict with efficiency considerations. 
>Ada compiler writers appear to have abdicated their responsibility and make
>no attempt to determine when boolean operations can be optimized as short-
>circuit.  (Somebody contradict me, please.)  
All right....

The C3Ada compiler, which runs on the Series 3200 machines produced
by Concurrent Computer Corporation, does optimize AND into AND THEN;
likewise, OR into OR ELSE.  As you point out, this is legal only if
the operands are free of side effects - basically, calls to user
defined functions.  And there are circumstances where the
transformation, though legal, is not optimal, such as

   FLAG1 := FLAG2 and FLAG3;

The compiler tries to avoid doing the transformation in such cases.

>... [T]here are cases when it is unreasonable to expect such an optimization; 
> when the
>second operand contains a function reference, for example.
>
>     That said, I still use my style when coding and look for bottlenecks
>during testing if performance is poor.  If efficiency requires that I use
>an unnecessary short-circuit form, I document that fact in the code.
>
>                                   Charlie
>

Regards,
Chris Henrich

Re: and then

[Charles H. Sampson]

In article <1993Apr7.173556.17184@sei.cmu.edu> ae@sei.cmu.edu (Arthur Evans) wr
ites:
>In connection with a discussion of Ada's short-circuit control forms,
>sampson@nosc.mil (Charles H. Sampson) says
>    Ada compiler writers appear to have abdicated their responsibility
>    and make no attempt to determine when boolean operations can be
>    optimized as short-circuit.
>
>Well, I'm not surprised that they make no such attempt, but it's not
>because they have abdicated any responsibility.  ARM 4.5(5) says of
>expressions involving 'and' and 'or':
>    The operands ... are evaluated in some order that is not defined by
>    the language (but before application of the corresponding operator).
>In other words, both operands MUST be evaluated.  That requirement is
>not unreasonable given the availability of the short-circuit forms.

     The nature of optimization is to generate code other than the obvious
_provided the semantics of the program are unchanged_.  (Ada is one of the
few languages to insist on that.)  Furthermore, a general rule in compiler
writing is "no harm, no foul".  If a programmer writes

                            if X > 1 and Y > 1

I find it hard to believe that any protest would be raised if it were dis-
covered (by reading the generated code) that the compiler had optimized
this as

                         if X > 1 and then Y > 1 .

     A large percentage of boolean expressions that contain a binary opera-
tor are of such simple forms and are worthy of optimization, in my opinion. 
When you look at something like

                          if X > 1 and X * Y < 4

it gets more complicated because of the possibility that NUMERIC_ERROR
might be raised.  It appears to me that the letter of 11.6(4) would allow
short-circuit in this case, but I'm not sure that that's the spirit of this
paragraph.  Whatever it might be, I would still initially write the above
form and even write such things as

                          if X > 1 and F(X) < 5 ,

which only a heroic optimizer could decide anything about, and change to
short-circuit only if execution was unacceptable and tuning analysis showed
that this statement was part of the problem.  The last form clearly indi-
cates to the maintainer that evaluation of F(X) is not dependent on X being
larger than 1.  If forced to change to short-circuit, I would add comments
stating this non-dependency.

                                   Charlie

P. S. I've just received information that the Verdix compilers now do such
transformations when they can verify that the semantics are unchanged.

Re: and then

[Art Duncan]

I think the question of "and then" was discussed in this group
about a year ago.  One question was whether or not an expression like

	if X /= 0 and Y/X > 3 then
	  ...
	end if;

should raise an exception if X = 0. If "and" is optimized to "and then"
it will not. However, the prevailing wisdom at that time was that the
above expression should raise an exception when X = 0.

There is also a matter of uniformity of the language. If B1, B2, and B3
are boolean vectors of the same dimension, the expression

	B1 and B2 and B3

will (and should) and them all together.

There is also the phrase " ... and the operands of an expression that does
not contain a short-circuit control form, are evaluated in SOME order that
is not defined by the language." This means that it is perfectly legal for
the compiler to generate code that evaluates

	X/Y > 3

before evaluating

	X /= 0

The term "some order" is used frequently in the LRM, with the implication
that any expression that depends, for its meaning, on the order of
evaluation is erroneous. Thus, if one wishes to force the order of
evaluation, the only linguistically correct method is to use the
short circuit forms.

Cheers,

	- Art Duncan
	  General Electric Company
	  Corporate Research and Development
	  Schenectady, NY 12301
	  duncan@crd.ge.com

Re: and then

[Alex Blakemore]

jnestoriak@vnet.IBM.COM writes:
>> At a recent code inspection, someone suggested that I convert a
>> series of and's to and then's "for performance".  

firth@sei.cmu.edu (Robert Firth) writes:
> Don't do it.  The short-circuit forms "and then" and "or else" are
> there to allow you to state that the two conditions must be tested
> in the order in which they are written ...
> where the code would be incorrect with just "and".  

for the most part, I agree, but you should consider the case
where one branch is much more expensive than the other to compute
and its in a tight loop, frequently called primitive or other
time critical situation.

a frequent candidate is a condition combining a boolean variable or simple
expression with a complex function call.  then it may well be worth
the short circuit operator.

  if boolean_variable and then complex_function (.. lots of expensive args) the
n

you cant rely on compiler optimizations to get the same effect unfortunately
since the function must be called in case it raises an exception
to maintain portablility (I believe).
-- 
---------------------------------------------------
Alex Blakemore alex@cs.umd.edu   NeXT mail accepted

Re: and then

[Andrew Dunstan,,2285592,]

>From article <1993Apr7.162133.3564@nosc.mil>, by sampson@nosc.mil (Charles H. 
Sampson):
[ should we always use short-circuit boolean forms?]
> 
>      My style is to use the boolean operators generally, reserving the
> short-circuit forms to document that the second operand should not be eval-
> uated under some circumstances.
> 

Your style is correct. Your reservations (see below) are not. Still,
it's better to do the right thing for the wrong reason than the other
way around :-)


>      Unfortunately, that style can conflict with efficiency considerations. 
> Ada compiler writers appear to have abdicated their responsibility and make
> no attempt to determine when boolean operations can be optimized as short-
> circuit.  (Somebody contradict me, please.)  They apparently feel that if
	     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 
	     OK.

> the programmer wants short-circuit he can ask for it.  In addition, there
> are cases when it is unreasonable to expect such an optimization; when the
> second operand contains a function reference, for example.
> 

The LRM (4.5.5) says: the operands of an expression that does not
contain a short-circuit control form are evaluated in some order that
is not defined by the language (but before application of the
corresponding operator).

So, the compiler writers are correct in not attempting to cast
non-short circuit forms to short-circuit evaluation. 

There could well be cases where evaluation of both operands is wanted
(if evaluation of one or both has a desired side-effect). If so,
"optimising" evaluation of one away is highly undesirable.

Leaving the order undefined also ALLOWS the compiler writer the chance
to optimise the order of evaluation.

In summary, if you want short-circuit, ask for it. If not, let the
compiler do the evaluation of both operands the best way it can.

#  Andrew Dunstan                   #   There's nothing good or bad   #
#  net:                             #                                 #
#    adunstan@steptoe.adl.csa.oz.au #   but thinking makes it so.     #
#  or: andrewd@cs.adelaide.edu.au   #                                 #
 
#  Andrew Dunstan                   #   There's nothing good or bad   #
#  net:                             #                                 #
#    adunstan@steptoe.adl.csa.oz.au #   but thinking makes it so.     #
#  or: andrewd@cs.adelaide.edu.au   #                                 #

Re: and then

[Dan Rittersdorf]

In article <1993Apr7.162133.3564@nosc.mil> sampson@nosc.mil (Charles H. Sampson
) writes:
>
>     Unfortunately, that style can conflict with efficiency considerations. 
>Ada compiler writers appear to have abdicated their responsibility and make
>no attempt to determine when boolean operations can be optimized as short-
>circuit.  (Somebody contradict me, please.)  They apparently feel that if
>the programmer wants short-circuit he can ask for it.  In addition, there
>are cases when it is unreasonable to expect such an optimization; when the
>second operand contains a function reference, for example.
>
>                                   Charlie


   Charlie,

      Some vendors, especially those that have concentrated on excellent
   optimization, like (blatant plug alert) Harris, do make this 
   optimization when it can be determined that the operands of
   the boolean operator have no side effects.  Someone else also stated
   that the LRM requires the evaluation of the operands, but I think
   several people have done a good job of arguing that one to the
   ground, so I won't.

      I find it odd, though, that you feel a vendor has some *responsibility*
   to provide this optimization.  Each possible optimization has a cost and 
   a benefit -- to the vendor and the user, and each vendor decides what 
   optimizations they can afford to provide, given the benefit (profit)
   that can be obtained.  That's business.  If a vendor decides that benefits
   of providing short circuit boolean optimizations don't outweigh their
   investment, they may well decide not to provide it.  They have no 
   responsibility to provide it -- just the option.  If you want it, 
   let your vendor know.  They can't know what the customer wants if the
   customer doesn't tell them.  If they're unresponsive, remember that 
   they still have to weigh the benefit to their entire user community
   against the cost to the same.  Sometimes one user's request can't be
   granted if the impact to the entire user community would be deemed
   too great (for example, if the requested optimization were to require
   adding a new, time consuming pass to the compiler which would increase
   everybody's compile times).

      Note: I'm not implying that the short circuit optimization would
   require a cost of that magnitude -- those are separate examples...)

      The language provides two forms of the operators, and one requires
   short circuiting.  If that's what you want, say so; compilers don't have
   dwim switches yet.  If you don't care, use the general form of the 
   operator, but in doing so, you inform the compiler that short circuiting is 
   NOT required, so don't be surprised if you don't get it.

      I hope this doesn't sound like a flamer -- if so, my apologies.  I just
   wanted to provide a vendor perspective on the issue.  And you did ask for
   contradictions...  :-)

-- 
-danr
______________________________________________________________________________
  Dan Rittersdorf                             danr@ada1.ssd.csd.harris.com
  Harris Corporation, Computer Systems Division, Fort Lauderdale, FL 33309
  Michigan Address:                     233 Pippin Drive, Sparta, MI 49345
______________________________________________________________________________

Re: and then

[Dave Bashford]

In article <1q29bd$7d8@huon.itd.adelaide.edu.au> andrewd@cs.adelaide.edu.au wri
tes:
>From article <1993Apr7.162133.3564@nosc.mil>, by sampson@nosc.mil (Charles H. 
Sampson):
>
>[ should we always use short-circuit boolean forms?]
>
>So, the compiler writers are correct in not attempting to cast
>non-short circuit forms to short-circuit evaluation. 
>
>There could well be cases where evaluation of both operands is wanted
>(if evaluation of one or both has a desired side-effect). If so,
>"optimising" evaluation of one away is highly undesirable.

I can't believe my eyes - "desired side-effect" in Ada ? Several people
have mentioned side-effects as a reason not to optimize boolean
expressions.  I thought one of the guiding principles of good s/w
engineering was to minimize or eliminate side-effects. The only reason
I can think of not to optimize to short circuit forms is to catch
undesired side-effects.

I would've thought that with the number of purists out there, as the
height of the flames on this news group would suggest, someone would've
mentioned this before ?

Are there "desired side-effects" ?

Should compilers optimize when, because of poor programming, the
behaviour of the program might change ?  ("poor programming" is too
strong, read "less than ideal programming") Apparently, the LRM says
no.  I don't remember the specific reference, but it says something
about "optimizing should never change the semantics of the program."
-- 

db
bashford@srs.loral.com (Dave Bashford, Sunnyvale, CA)

Re: and then

[Charles H. Sampson]

In article <1993Apr9.180808.19494@scf.loral.com> bashford@srs.loral.com (Dave B
ashford) writes:
>In article <1q29bd$7d8@huon.itd.adelaide.edu.au> andrewd@cs.adelaide.edu.au wr
ites:
>>There could well be cases where evaluation of both operands is wanted
>>(if evaluation of one or both has a desired side-effect). If so,
>>"optimising" evaluation of one away is highly undesirable.
>
>I can't believe my eyes - "desired side-effect" in Ada ? Several people
>have mentioned side-effects as a reason not to optimize boolean
>expressions.  I thought one of the guiding principles of good s/w
>engineering was to minimize or eliminate side-effects. The only reason
>I can think of not to optimize to short circuit forms is to catch
>undesired side-effects.
>
> ...
>
>Are there "desired side-effects" ?

     I assume you're referring to side effects of function references. 
Procedures almost always have desirable side effects.

     In the original requirements for Ada (Steelman), functions were not
allowed to have side effects.  At least one of the candidate languages,
Blue if I remember correctly, took a stab at prohibiting them with rules
about exactly what kind of code a function could and could not contain. 
Somewhere along the way the requirement vanished, either by explicit action
or benign neglect, probably because the requirement was considered draconi-
an.  By that time I was pretty far out of the loop.

     Back to the question.  In my programming style, a function is a sub-
program whose _primary_ purpose is the calculation of a single value and a
procedure is a subprogram whose _primary_ purpose is performing an action.
(There's an unfortunate grey area in applying these rules.)  This allows
for functions that have side effects and procedures that have only one
formal parameter, of mode OUT.  I tend to minimize the side effects of
functions, but I don't rule them out.

     For example, in processing a character stream, I prefer to have a
function named Next_character that returns the next character from the
stream and moves the stream cursor so that character becomes the previous
character, rather than a procedure named Get.

                                   Charlie

Re: and then

[munnari.oz.au!yoyo.aarnet.edu.au!news.adelaide.edu.au!usenet]

>From article <1993Apr9.180808.19494@scf.loral.com>, by bashford@srs.loral.com 
(Dave Bashford):
> In article <1q29bd$7d8@huon.itd.adelaide.edu.au> andrewd@cs.adelaide.edu.au w
rites:
>>From article <1993Apr7.162133.3564@nosc.mil>, by sampson@nosc.mil (Charles H.
 Sampson):
>>
>>
>>There could well be cases where evaluation of both operands is wanted
>>(if evaluation of one or both has a desired side-effect). If so,
>>"optimising" evaluation of one away is highly undesirable.
> 
> I can't believe my eyes - "desired side-effect" in Ada ? Several people
> have mentioned side-effects as a reason not to optimize boolean
> expressions.  I thought one of the guiding principles of good s/w
> engineering was to minimize or eliminate side-effects. The only reason
> I can think of not to optimize to short circuit forms is to catch
> undesired side-effects.
> 
> Are there "desired side-effects" ?
> 

Certainly. One classic example should suffice. Since Ada does not have
"own" variables, a random number generator function in Ada will
normally have the desired side-effect of changing its seed. 

Of this would best be done by hiding the seed in a package, where
nothing but the function could change the seed, but that is another
issue. Ada is NOT a functional language - it is procedural, and
side-effects are common. 

None of this is to deny that over-use of side effects is bad practice.
It is, and as a teacher I have tried to encourage students to avoid
side-effects wherever possible. (Note the qualification).

Interestingly, functions in protected objects in Ada9X are to be
prohibited from having side-effects which alter the protected data
(thus permitting the optimisation of allowing several such functions
to be active at one time).

#  Andrew Dunstan                   #   There's nothing good or bad   #
#  net:                             #                                 #
#    adunstan@steptoe.adl.csa.oz.au #   but thinking makes it so.     #
#  or: andrewd@cs.adelaide.edu.au   #                                 #

Re: and then

[Dik T. Winter]

In article <1q3vtq$2lt@travis.csd.harris.com> danr@ada1.ssd.csd.harris.com (Dan
 Rittersdorf) writes:
 > In article <1993Apr7.162133.3564@nosc.mil> sampson@nosc.mil (Charles H. Samp
son) writes:
...
 > >                                                       In addition, there
 > >are cases when it is unreasonable to expect such an optimization; when the
 > >second operand contains a function reference, for example.

There are other possibilities.  Short-circuiting may make the program
actually slower (jumps take time and sometimes a lot).
 > >
 >       I find it odd, though, that you feel a vendor has some *responsibility
*
 >    to provide this optimization.

There is of course no such *responsibility*, it is merely a question of
quality.  Especially as I prefer conditional tests in non-short-circuited
form if it does not matter.  In that case a good compiler would find what
is most efficient, short-circuiting or not.  Short-circuiting should only
be used where it matters for the logic of the program (e.g. the second
operand becomes invalid).
-- 
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland
home: bovenover 215, 1025 jn  amsterdam, nederland; e-mail: dik@cwi.nl

Re: and then

[Dik T. Winter]

In article <1993Apr10.010355.4244@nosc.mil> sampson@nosc.mil (Charles H. Sampso
n) writes:
 >      In the original requirements for Ada (Steelman), functions were not
 > allowed to have side effects.  At least one of the candidate languages,
 > Blue if I remember correctly, took a stab at prohibiting them with rules
 > about exactly what kind of code a function could and could not contain. 
 > Somewhere along the way the requirement vanished, either by explicit action
 > or benign neglect, probably because the requirement was considered draconi-
 > an.  By that time I was pretty far out of the loop.

The requirements vanished gradually.  At one point there was not a dichotomy
but a trichotomy: functions (pure, no side effects), procedures (pure) and
value-returning procedures.  For optimization purposes this is the best, but
value-returning procedures fell out and functions with side-effects came in.

The basic reason for the shift to value-returning procedures was that it is
impossible to write such a basic thing as a random number generator without
side-effects.
-- 
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland
home: bovenover 215, 1025 jn  amsterdam, nederland; e-mail: dik@cwi.nl

Re: and then

[Alex Blakemore]

In article <1993Apr9.180808.19494@scf.loral.com> bashford@srs.loral.com (Dave B
ashford) writes:

> I can't believe my eyes - "desired side-effect" in Ada ?
> The only reason I can think of not to optimize to short circuit forms is to c
atch
> undesired side-effects.

typically I agree
but what's important is to have the same behavior on different systems so 
if a function may raise an excepion - it should be called just in case.

> Are there "desired side-effects" ?
 
sometimes:

  one class of beneficial side affect doesnt effect semantics but may
affect performance - .e.g. data structures that reorganize on queries
to optimize requests for recently visited info - akin to caching

  somtimes a side effect is intended every time a function is evaluated:
such as in a pseudo-random number generator or a lexical scanner perhaps
but its by far the exception and should be documented.

> Should compilers optimize when, because of poor programming, the
> behaviour of the program might change ?

this caused a lot of debate in the Ada9X forum in the case when 
certain range checks could be safely eliminated (optimized away) 
without changing the semantics _except_ in the erroneous case
where a variable is referenced before being initialized.

If I understand the new 9X proposal, they have a reasonable solution.
-- 
---------------------------------------------------
Alex Blakemore alex@cs.umd.edu   NeXT mail accepted

Re: and then

[Michael Feldman]

In article <1993Apr10.010355.4244@nosc.mil> sampson@nosc.mil (Charles H. Sampso
n) writes:
>
>     Back to the question.  In my programming style, a function is a sub-
>program whose _primary_ purpose is the calculation of a single value and a
>procedure is a subprogram whose _primary_ purpose is performing an action.
>(There's an unfortunate grey area in applying these rules.)  This allows
>for functions that have side effects and procedures that have only one
>formal parameter, of mode OUT.  I tend to minimize the side effects of
>functions, but I don't rule them out.
>
>     For example, in processing a character stream, I prefer to have a
>function named Next_character that returns the next character from the
>stream and moves the stream cursor so that character becomes the previous
>character, rather than a procedure named Get.
>
There's a more obvious example. Ada does not provide static local storage -
all local objects are automatic and get blown off the stack when the
block in which they are declared goes out-of-scope.

Consider how to write a pseudo-random number generator, or any other
similar function that needs one or more state variables. (In case
pseudo-random numbers are not your career, we can summarize it by saying
that the function needs to remember what it did last time").

The canonical Ada way to do this is to export the function from a package, 
hiding the state variable in the package body. This state variable is never 
seen by a client, so it's protected from outside damage, but it is still a 
nonlocal reference for the function, in other words a side effect.

Calling this function, say, 

  FUNCTION PseudoRandom(N: Natural) RETURN Natural;

then each successive call of PseudoRandom(M) returns a number in 0..M.

I claim that 

  X := PseudoRandom(10) - PseudoRandom(10);

will store different values in X depending upon whether the first
or the second call (left side or right side) is evaluated first.

Side effects are a two-edged sword: Ada rules make them sometimes
unavoidable, but they are dangerous nonetheless. And one had better
have one's eyes open. If it is important that the left side be evaluated
first, better declare Temp and write

  Temp := PseudoRandom(10);
  X := Temp - PseudoRandom(10);

Mike Feldman

PS - no, they are not changing this in 9X...

Re: and then

[cis.ohio-state.edu!zaphod.mps.ohio-state.edu!howland.reston.ans.net!noc.n]

In article <1993Apr8.122125.24053@titan.tsd.arlut.utexas.edu> 
  gardner@tsd.arlut.utexas.edu (Don Gardner) writes:

>sampson@nosc.mil (Charles H. Sampson) writes:
>>     My style is to use the boolean operators generally, reserving the
>>short-circuit forms to document that the second operand should not be eval-
>>uated under some circumstances.
>
>I humbly suggest that you change your perspective.  When I encounter a
>non-short-ciruit of the boolean operators I ask why both expressions
>_must_ be evaluated; i.e., the short-circuit forms are the default and
>the other forms are used only when both expressions must be evaluated.
>
>Also, I avoid writing functions that have side effects.  Since (as
>best I can reason at this early hour) both expressions need to be
>evaluated only when both have side effects, I rarely use the
>non-short-circuit forms.

I tend to agree with Don Gardner -- that is, use short-circuit
forms unless it is clear that the non-short-circuit form
is more efficient or semantically required.  However, I have heard heated
and somewhat convincing arguments on either side of this.  The
argument generally seems to reflect the orientation of the
debater, more than any absolute better or worse.  

Personally, I tend to like to have a lot of control over what code gets
generated.  I rely on the optimizer to eliminate common subexpressions,
perform decent global register allocation, and handle all instruction
scheduling.  I don't rely on the optimizer to do much more than that.
This reflects my general suspicion of optimizers (being a compiler
writer myself ;-), and my many years of doing machine-level programming.
I "think" in terms of "and then" and "or else" -- they just seem more
natural in general.  I reserve "and" and "or" for combining boolean
flags.

Some arguments on the other side are: you shouldn't worry about such
low-level efficiency concerns before getting the algorithm right;
you shouldn't presume you know better than the optimizer what is the best
way to evaluate the expression; and you shouldn't sully up a generally 
abstract algorithm with low-level concerns about best order of evaluation.

Certainly on some architectures (e.g. the 680x0), one can compute a 
boolean value without a branch (using the SETx instructions),
and hence it is only the "and then" that forces use of a pipeline-breaking
conditional branch.  However, on some other architectures, something
compiled as:

   if X < Y and then Y < Z then ...

will require, on average, fewer conditional branches than something
compiled as:

   if X < Y and Y < Z then ...

Given the equivalence in the absence of side-effects, a clever optimizer
(is that an oxymoron? ;-) could choose to generate code either way, 
given either version written in the source.

So if you really believe in your optimizer, it shouldn't make any
difference at all!  If you don't believe in your optimizer,
and the expressions are at all complicated, then it seems prudent
to make the decision yourself which is "more efficient" (unfortunately,
this can be target dependent) or "more readable" or "more natural,"
depending which is more important in the current context.

Personally, since I find "and then" and "or else" both
natural and readable, I rarely end up with just "and" or "or" 
unless the situation is special in some way.  However, those
coming to Ada from Pascal (rather than C, for example) might
find "and then" and "or else" both ugly and unreadable, and hence
their bias would be the other way.

In any case, if the efficiency of your system is at the level
where "and" vs. "and then" is critical, then either you
have done an incredibly good job already of choosing the ultimate
algorithm, or you are running extremely close to the edge.

On the other hand, if for the given target and the given
optimizer, you are wasting several cycles every time you write
"and" rather than "and then," I can sympathize with a reviewer
who would rather see "and then."  However, you should probably
double check that "and then" is really more efficient on
your architecture and with the given optimizer.  It may be
that more and more optimizers are performing the permitted 
transformations between "and" and "and then" (ideally both
ways), so you should then pick a uniform style for your
projects, reserving one of the two to signify that the situation
is somehow "special" (as defined by your project) and use
the other of the two systematically in all other situations.

In a big project, uniformity and readability often outweigh
micro-optimization.  The real efficiency gains come from 
"macro-optimization" via good design, good algorithms, 
and good data structures.

S. Tucker Taft    stt@inmet.com
Intermetrics, Inc.
Cambridge, MA  02138

Re: and then

[Charles H. Sampson]

In article <1q3vtq$2lt@travis.csd.harris.com> danr@ada1.ssd.csd.harris.com (Dan
 Rittersdorf) writes:
>In article <1993Apr7.162133.3564@nosc.mil> sampson@nosc.mil (me) writes:
>>
>>     Unfortunately, that style can conflict with efficiency considerations. 
>>Ada compiler writers appear to have abdicated their responsibility and make
>>no attempt to determine when boolean operations can be optimized as short-
>>circuit.  (Somebody contradict me, please.)  They apparently feel that if
>>the programmer wants short-circuit he can ask for it.  In addition, there
>>are cases when it is unreasonable to expect such an optimization; when the
>>second operand contains a function reference, for example.
>
>      Some vendors, especially those that have concentrated on excellent
>   optimization, like (blatant plug alert) Harris, do make this 
>   optimization when it can be determined that the operands of
>   the boolean operator have no side effects.  Someone else also stated
>   that the LRM requires the evaluation of the operands, but I think
>   several people have done a good job of arguing that one to the
>   ground, so I won't.
>
>      I find it odd, though, that you feel a vendor has some *responsibility*
>   to provide this optimization.  Each possible optimization has a cost and 
>   a benefit -- to the vendor and the user, and each vendor decides what 
>   optimizations they can afford to provide, given the benefit (profit)
>   that can be obtained.  That's business.  If a vendor decides that benefits
>   of providing short circuit boolean optimizations don't outweigh their
>   investment, they may well decide not to provide it.  They have no 
>   responsibility to provide it -- just the option.  If you want it, 
>   let your vendor know.  They can't know what the customer wants if the
>   customer doesn't tell them.  If they're unresponsive, remember that 
>   they still have to weigh the benefit to their entire user community
>   against the cost to the same.  Sometimes one user's request can't be
>   granted if the impact to the entire user community would be deemed
>   too great (for example, if the requested optimization were to require
>   adding a new, time consuming pass to the compiler which would increase
>   everybody's compile times).

     These are all good points and I find it difficult to argue with them. 
I will explain a bit what I meant by "abdicating responsibility".

     In the pre-Ada world, not so long ago, evaluating boolean expressions
in short-circuit form was so common that I doubt that many compiler writers
considered it to be an optimization.  I certainly didn't for the compiler I
worked on.  It was just considered code generation, in roughly the same bag
of tricks as a decent register assignment algorithm.  In the FORTRAN world,
short-circuit was common but not universal, which had interesting impact on
FORTRAN's vaunted transportability.

     Then along came Ada, which specified precisely the semantics of bool-
ean expressions.  As I have looked at code from a number of Ada compilers
and not seen any short-circuit, I leaped to the conclusion that the imple-
menter were saying something like, "Heck, it's easy to do short-circuit,
but first we have to verify that we're not changing the semantics.  Forget
it.  If the programmer wants short-circuit he can ask for it."  I consider
it a "responsibility" of Ada compiler writers to generate code roughly as
good as the code for similar constructs in other languages, provided the
LRM doesn't prevent it, therefore roughly as good as a FORTRAN compiler. 
Certainly that "responsibility" is not a moral imperative; it's tempered by
all of the considerations stated by Mr. Rittersdorf.

     I'm happy to report that a number of implementors have responded to my
request to be contradicted.  Apparently many have now decided to do the
extra work required to implement this "optimization".

                                   Charlie