Re: Let's not BE NP-hard, shall we...?

[Ian McIntosh <ianm@xxxxxxxxxx>]

I think I understood your point about explicitly versus effectively, and we mostly agree. I just don't agree with Dan that order of evaluation is just "effectively not specified" in Fortran, or with you that the order is always "explicitly unspecified". I believe the truth is between.

I apologize to you and anyone else who felt misled. It was not deliberate. Let me say it a different way that I hope is clearer.


The Fortran standard does NOT leave the order of evaluation of an _expression_ implicitly or effectively unspecified just by not specifying it. It also does NOT explicitly specify that the order of evaluation is always unspecified. It is deliberately more selective.

The standard explicitly specifies when the order of evaluation IS specified (by the programmer using parentheses in an _expression_). As you say, "the significance of parentheses is specified", and it is that they control the order of evaluation. (See below for wording in one version of the standard. Others are equivalent.)

The standard explicitly specifies when the order is UNspecified (by the programmer omitting parentheses), and it explicitly specifies that the order is always UNspecified in some contexts like calls to impure functions.

Forall statements are interesting: The iterations "may be done in any order" but within each iteration "each statement ... is executed in sequence", and impure functions are disallowed in them. So their ordering is partly explicitly unspecified but partly explicitly specified, in addition to the normal rules.

All that gives the programmer the ability to control the order when it is believed to be important, and gives the compiler the ability to improve the performance when the user allows.

Controlling the order is not trivial. It requires being careful to add parentheses in many places. If performance matters more than repeatability, it also involves thinking about where to add them and where not too, and can be a maintenance headache. (Did the author omit a pair deliberately? Or is it a bug?)

The rules allow different compilers, or different versions of the same compiler, or the same compiler used with different options to make different choices that produce different results. But they explicitly require a program using parentheses everywhere and avoiding specified undefined usage to have its operations done in close enough to the same order to produce repeatable results on different systems using equivalent floating point hardware and libraries. (Libraries differ enough that perfect portability is generally impossible.)

Also the standard implicitly does not explicitly specify the effect of using multiple threads because those are not in the language (excluding High Performance Fortran and CoArray Fortran, and OpenMP and other extensions that dictate or imply the use of threads), but the explicitly specified specification and explicitly specified unspecification still apply (although that doesn't mean they're totally followed).

- Ian McIntosh IBM Canada Lab Compiler Back End Support and Development



From the September 2002 committee draft, because it's handiest.

7.1.8.2 Integrity of parentheses

The sections that follow state certain conditions under which a processor may evaluate an _expression_ that is different from the one specified by applying the rules given in 7.1.1 and 7.2. However, any _expression_ in parentheses shall be treated as a data entity.

NOTE 7.16
For example, in evaluating the _expression_ A + (B - C) where A, B, and C are of numeric types, the difference of B and C shall be evaluated before the addition operation is performed; the processor shall not evaluate the mathematically equivalent _expression_ (A + B) - C.

A brief extract from 7.1.8.3:

7.1.8.3 Evaluation of numeric intrinsic operations

The rules given in 7.2.1 specify the interpretation of a numeric intrinsic operation. Once the interpretation has been established in accordance with those rules, the processor may evaluate any mathematically equivalent _expression_, provided that the integrity of parentheses is not violated.

Two expressions of a numeric type are mathematically equivalent if, for all possible values of their primaries, their mathematical values are equal. However, mathematically equivalent expressions of numeric type may produce different computational results.

That's followed by 1 1/2 pages describing allowed and some disallowed differences.

"N.M. Maclaren" ---08/04/2011 06:35:43 PM---On Aug 4 2011, Ian McIntosh wrote: >NM>

From:	"N.M. Maclaren" <nmm1@xxxxxxxxx>
To:	Ian McIntosh/Toronto/IBM@IBMCA
Date:	08/04/2011 06:35 PM
Subject:	Re: Let's not BE NP-hard, shall we...?

---

On Aug 4 2011, Ian McIntosh wrote:
>NM>
>NM> DZ >		 		  I am aware that Fortran specifies that the order of
>NM> DZ >		 		  evaluation is effectively NOT specified.  I am also
>NM> DZ >		 		  aware that, while it IS specified in C, it is also
>NM> DZ >		 		  routinely ignored.
>NM>
>NM> That's misleading.  It is EXPLICITLY unspecified for Fortran,
>
>The truth is in between.  The Fortran standard is more complicated than
>either specified or unspecified.
>
>Within an _expression_, the standard lets the programmer use parentheses to
>explicitly partially specify the evaluation order or leave it unspecified.
>In other situations it is partly unspecified.

I am afraid that you have missed my point, and I feel that you are
being a bit misleading.  My point was that, not just is it effectively
unspecified, it is EXPLICITLY unspecified.  Only the significance of
parentheses is specified, and that does NOT include the parentheses
around the arguments in function calls.

Also, your examples with function calls may confuse people who are not
Fortran experts.  Unlike in C, whether impure function calls are completely
undefined behaviour or have a more constrained set of possibilities has
been a matter of debate for at least 40 years.  And the attitude of WG5
is a lot harder to that one than it was 40 years ago.  In particular,
even the following statement is dubious:

.        f(g(x),h(x))      has an unspecified order between the g and h
>function calls (and if either changes x or a global variable read by the
>other, or does I/O, it can affect the result).
>but splitting the last one into three statements
>        t1 = g(x)
>        t2 = h(x)
>        f(t1,t2)                 has a specified order.

However, this is not an appropriate forum to discuss that particularly
arcane and controversial aspect of the Fortran standard!  Nor, for that
matter, the equally arcane but entirely different way that C has related
ambiguities, which are subtly different between C90, C99 and C1X.


Regards,
Nick Maclaren.