Subject: Revised 'Elemental functions' proposal

From: John Merlin <[email-masked]>
Date: Mon, 31 Aug 92 14:53:13 BST

Here is a modified draft of the 'elemental functions' proposal
(now called 'pure procedures').  It should replace the section
on 'ELEMENTAL Functions' in the document 'Tentative Proposal: 
High Performance Fortran FORALL and INDEPENDENT Proposal', 
24 August (section 1.5.5), which we believe contained some technical
problems which this version hopefully cures.

The intent of this proposal is to define 'pure' (i.e. side-effect
free) functions which may be used freely and safely in FORALL - and
in any normal F90 context - and whose dummy arguments and results
can be array-valued.  A separate aspect of the proposal is that pure
procedures may be used *elementally* (i.e. like F90 elemental
intrinsic procedures) *provided* their arguments and result satisfy 
the additional constraint that they are *scalar*.  This avoids
introducing into Fortran the controversial concept of 'array-of-arrays'
(which Fortran seems to assiduously avoid) present in my original 
proposal, and still allows the flexibility of array-valued functions 
in FORALL.  Furthermore, it does not reduce the functionality
(at least for functions) -- if the programmer wants the effect of
elemental invocation of functions that have array-valued dummy args 
or result, he can obtain this with FORALL.

I commend this proposal to the house!

(BTW, I'm going on holiday now until Sept 21, so won't be able to 
respond to any questions or comments until after the next HPF meeting. 
I hope for good news about 'pure' procedures when I return! :-)
Have a good meeting!)

              John Merlin.
----------------------------------------------------------------------

\subsection{PURE Procedures and Elemental Invocation\protect\footnote{Version 
of August 28, 
1992 - John Merlin, University of Southampton, and Chuck Koelbel, Rice 
University}}

\label{forall-elemental}

The intent of this counter-proposal is to further restrict functions 
called from within FORALL so that they have no side effects.
This is more restrictive than the constraints on function calls in 
section \ref{forall-stmt}; however, the definition is simpler and 
presumably clearer, as well as providing complete security against 
non-deterministic behaviour.

A separate aspect of this proposal is to extend the concept of 
`elemental procedures', which in Fortran~90 are restricted to a subset 
of the intrinsic procedures, so that they can be user-defined.

\subsubsection{General Form of Element Array Assignment}

To the definition of {\it forall-assignment}, add the following:
\begin{quotation}

\noindent Constraint: If any subexpression in {\it expr}, {\it 
array-element}, or {\it array-section} is a {\it function-reference}, 
then the {\it function-name} must be a `pure' function as defined below.
\end{quotation}

\subsubsection{Interpretation of Element Array Assignments}  

Change the paragraphs after the step-by-step interpretation to the 
following:
\begin{quotation}

If the scalar mask expression is omitted, it is as if it were
present with the value true.

The scope of a
{\it subscript-name} is the FORALL statement itself. 

The {\it forall-assignment} must not cause any element of the array
being assigned to be assigned a value more than once.
By the nature of PURE functions, no expression evaluations can 
have any affect on other expressions, either for the same combination of 
{\it subscript-name} values or for a different combination.
\end{quotation}
 
\subsubsection{PURE Procedures}

A `pure' procedure is one which produces no side effects, except for 
assigning to dummy arguments of INTENT (OUT) or (INOUT) in the case of a
`pure' subroutine.
It may be used in any way that a normal procedure of its type may 
be used.
In addition, pure functions may be used in a FORALL statement or construct.
Also, a pure procedure whose dummy arguments (and, in the case of a function,
result) are all scalar may be used `elementally', that is, it may be
applied to conforming array arguments in a similar manner to the elemental
intrinsic procedures defined in Fortran~90.

If a procedure is used in a context that requires it to be pure
(namely, it is used elementally or in a FORALL statement or construct),
then its interface must be explicit, and it must be declared to be pure 
in both its definition and interface.  The form of this declaration is 
a directive preceding the {\it function-stmt\/} or {\it subroutine-stmt\/}:
                                                                 \BNF
pure-directive \IS !HPF$ PURE
                                                                 \FNB

To define pure functions, Rule~R1215 of the Fortran~90 standard is changed 
to:
                                                                 \BNF
function-subprogram \IS [pure-directive]
                        function-stmt
						[specification-part]
						[execution-part]
						[internal-subprogram-part]
						end-function-stmt
                                                                \FNB
with the following additional constraints:

\noindent
Constraint: The dummy arguments of a pure function must have INTENT(IN).

\noindent
Constraint: The local variables of a pure function must not have the SAVE 
attribute.

\noindent
Constraint: A pure function must not contain assignments to global 
data objects.

\noindent
Constraint: A pure function must not contain I/O statements.

\noindent
Constraint: Any procedure called from a pure function must be pure.

\noindent
Constraint: A pure function must not contain data mapping directives.

To assert that a function is pure, a {\it pure-directive\/} must be given.

\vspace*{1ex}

To define pure subroutines, Rule~R1219 is changed to:
                                                                 \BNF
subroutine-subprogram \IS [pure-directive]
                        subroutine-stmt
						[specification-part]
						[execution-part]
						[internal-subprogram-part]
						end-subroutine-stmt
                                                                \FNB
with the following additional constraints:

\noindent
Constraint: The dummy arguments of a pure subroutine must have explicit
INTENT.

\noindent
Constraint: The local variables of a pure subroutine must not have the SAVE 
attribute.

\noindent
Constraint: A pure subroutine must not contain assignments to global 
data objects.

\noindent
Constraint: A pure subroutine must not contain I/O statements.

\noindent
Constraint: Any procedure called from a pure subroutine must be pure.

\noindent
Constraint: A pure subroutine must not contain data mapping directives.

To assert that a subroutine is pure, a {\it pure-directive\/} must be given.
\vspace*{1ex}

To define interface specifications for pure procedures, Rule~R1204 is 
changed to:
                                                                \BNF
interface-body \IS [pure-directive]
                   function-stmt
				   [specification-part]
				   end-function-stmt
			   \OR [pure-directive]
                   subroutine-stmt
				   [specification-part]
				   end-subroutine-stmt
                                                                \FNB

\noindent
Constraint: An {\it interface-body\/} of a pure subroutine must specify
the intents of all dummy arguments.

When applied to a procedure interface body, the {\it pure-directive} asserts 
that the procedure satisfies the constraints required of pure procedures.
Because of the limited information provided by an interface specification,
this assertion can only be checked to a limited extent in this context
(i.e. with respect to argument intent and the absence of data mapping 
directives).

If a procedure is used in a context that requires it to be pure
(namely, it is used elementally or in a FORALL statement or construct),
then its interface must be explicit.  If the interface is provided by 
means of an interface block, the {\it interface-body\/} must contain a 
{\it pure-directive\/}.

If an interface body contains a {\it pure-directive\/}, then the 
corresponding procedure definition must also contain it, though the 
reverse is not true.  When a procedure definition with a {\it pure-directive\/}
is compiled, the compiler may check that it satisfies the necessary 
constraints.

\vspace*{1ex}

To define elemental invocations of pure procedures, the following 
extra constraint is added after Rules R1209 ({\it function-reference\/}) 
and R1210 ({\it call-stmt\/}):
\begin{quotation}

\noindent
Constraint: A non-intrinsic function (subroutine) that is invoked 
elementally must be a pure function (subroutine) with scalar dummy 
arguments (and result), and its interface must be explicit.
\end{quotation}

Additionally, the beginning of section 12.4.3 should be changed to:
\begin{quotation}

A reference to {\em a pure function or\/} an elemental intrinsic function
is an elemental reference if\ldots
\end{quotation}
and the beginning of section 12.4.5 to:
\begin{quotation}

A reference to {\em a pure subroutine or\/} an elemental intrinsic subroutine
is an elemental reference if\ldots
\end{quotation}
(where the additional words are italicised).

\paragraph{Comments}
Detailed comments on pure procedures:
\begin{itemize}
\item The constraints for a pure procedure guarantee freedom from 
side-effects, thus ensuring that it can be invoked concurrently at each 
`element' of an array (where an `element' may itself be a data-structure, 
including an array).

\item An earlier draft of this proposal contained a constraint disallowing 
pure procedures from accessing global data objects, particularly distributed 
data objects.
This constraint has been dropped as inessential to the side-effect freedom 
that the HPF committee requested.
However, it may well be that some machines will have great difficulty 
implementing FORALL without this constraint.\footnote{            %
%
One of us (JHM) is still in favour of this additional constraint for a 
number of reasons: 
(i) aesthetically, it is in keeping with the
nature of a `pure' function, i.e. a function in the mathematical
sense, and in practical terms it imposes no real restrictions on the 
programmer, as global data can be passed-in via the argument list; 
(ii) without this constraint HPF programs can no longer be implemented 
by pure message-passing, or at least not efficiently, i.e. without
sequentialising FORALL statements containing function calls and greatly
complicating their implementation; 
(iii) absence of this restriction may inhibit optimisation of FORALLs
and array assignments, as the optimisation of assigning the {\it expr\/}
directly to the assignment variable rather than to a temporary intermediate 
array may now require interprocedural analysis rather than just local 
analysis.  However, JHM does not want this to be a make-or-break point!}

\item The constraints are such that a compiler cannot deduce from a 
procedure's interface body whether it can validly be used as a pure 
procedure, as that depends partly on its local declarations and internal 
operations.  Hence, it is necessary to use a specifier like `PURE' in the 
interface body to identify such procedures.  The compiler can 
check that the procedure satisfies all the necessary constraints 
when it compiles the procedure itself (provided it also has the `PURE' 
specifier).

\end{itemize}

As well as using pure functions in FORALL, a pure procedure can also be 
used `elementally', provided it satisfies the additional constraint that 
its dummy arguments (and, in the case of a function, its result) are scalar.

Fortran 90 introduces the concept of `elemental procedures',
which are defined for scalar arguments but may also be applied to
conforming array-valued arguments.  
For an elemental function,
each element of the result, if any, is as would have been obtained by
applying the function to corresponding elements of the arguments.
Examples are the mathematical intrinsics, e.g SIN(X).
For an elemental subroutine, the effect on each element of an INTENT(OUT) or 
INTENT(INOUT) array argument is would be obtained by calling the 
subroutine with the corresponding elements of the arguments.
An example is the intrinsic subroutine MVBITS.

However, Fortran~90 restricts the application of elemental
procedures to a subset of the intrinsic procedures --- the programmer
cannot define his own.  Obviously, elemental invocation is equivalent to 
concurrent invocation, so extra constraints beyond those for normal
Fortran procedures are required to allow this to be done safely
(e.g. deterministically).  Appropriate constraints in this case are
the same as those for function calls in FORALL---indeed, the latter are 
virtually equivalent to elemental invocation in an array assignment, 
given the close correspondence between FORALL and array assignment.
Hence, we propose that pure procedures may also be invoked elementally,
subject to the additional constraint that their dummy arguments 
(and, for a function, result) are scalar.

Comment:
\begin{itemize}
	\item The original draft proposed allowing pure procedures 
to be invoked elementally even if their dummy arguments or results 
were array-valued.  These provisions have been dropped to avoid 
promoting storage order to a higher level in Fortran~90
(i.e.\ to avoid introducing the concept of `arrays-if-arrays', 
which Fortran~90 seems to strenuously avoid!)   In practical terms,
the current proposal provides the same functionality as the original 
one for functions, though not for subroutines.  If a programmer wants 
elemental function behaviour, but also wants the `elements' to be
array-valued, this can be achieved using FORALL.
	\item In typical FORALL or elemental usage, a pure procedure 
would be called independently in each process, and its dummy arguments 
would be associated with `elements' local to that process.  
This is the reason for disallowing data mapping directives within the 
bodies of such procedures.
Note that, particularly in elemental invocations, the actual arguments
can be distributed arrays which need not be `co-distributed'; if not,
a typical implementation would in general perform all data communications 
prior to calling the procedure, and would then pass-in the required 
elements locally via its argument list.
\end{itemize}

\paragraph{Uses and MIMD aspects}

\subparagraph{FORALL statements and constructs}

Pure functions may be used in expressions in FORALL statements and 
constructs, unlike general functions.  Because a {\it forall-assignment}
may be an {\it array-assignment} the pure function can have an array result.  
For example, if a certain problem
is data-parallel over a 2d grid, and the data structure at each grid
point is a vector of length 3 (2d QCD?), we could have:
                                                              \CODE
    INTERFACE
!HPF$ PURE
      FUNCTION f (x)
        REAL, DIMENSION(3) :: f, x
      END FUNCTION f
    END INTERFACE
    REAL  v (3,10,10)
    ...
    FORALL (i=1:10, j=1:10)  v(:,i,j) = f (v(:,i,j)) 
                                                              \EDOC

\subparagraph{MIMD parallelism}

A natural way of obtaining some MIMD parallelism is by
means of branches within a pure function which depend on argument 
values.  These branches can be governed by content-based or index-based 
conditionals (the latter in a FORALL context).  For example:
                                                              \CODE
!HPF$ PURE
    FUNCTION f (x, i)
      IF (x > 0) THEN     ! content-based conditional
        ...
      ELSE IF (i==1 .OR. i==n) THEN    ! index-based conditional
        ...
      ENDIF
    END FUNCTION

    ...
    FORALL (i=1:n)  x (i) = f(x(i), i)
    ...
                                                              \EDOC
Content-based conditionals can be exploited generally, including in
array assignments (see below), which may sometimes obviate the need for 
WHERE-ELSEWHERE constructs or sequences of masked FORALLs with their 
potential synchronisation overhead. 

\subparagraph{Elemental function references}

Pure functions with scalar dummy arguments and result can be invoked
{\em elementally\/} in array expressions with the 
same interpretation as Fortran~90 elemental intrinsic functions.
This interpretation (Fortran~90 standard, Section~13.2.1) is as follows:
\begin{quote}
If a generic name or a specific name is used to reference an elemental
intrinsic function, the shape of the result is the same as the shape of 
the argument with the greatest rank.
If the arguments are all scalar, the result is scalar.
For those elemental intrinsic functions that have more than one argument, 
all arguments must be conformable.
In the array-valued case, the values of the elements, if any of the 
result are the same as would have been obtained if the scalar-valued 
function had been applied separately, in any order, to corresponding 
elements of each argument. [An argument called KIND must be specified as 
a scalar integer initialization expression and must specify a 
representation method for the function result that exists on the processor.]
\end{quote}
(The last sentence of this section, enclosed in square brackets,
does not apply to elemental references of user-defined pure functions.)

Examples of elemental usage are:
                                                              \CODE
    INTERFACE 
!HPF$ PURE
      REAL FUNCTION foo (x, y, z)
        REAL, INTENT(IN) :: x, y, z
      END FUNCTION
    END INTERFACE

    REAL a(100), b(100), c(100)
    REAL p, q, r

    p      = foo (p, q, r)         ! OK - scalar call
    a(1:n) = foo (a(1:n), b(1:n), c(1:n))    ! OK - elemental call
    a(1:n) = foo (a(1:n), q, r)    ! OK - scalar args 'promoted' to arrays
    a(1:n) = foo (p, q, r)         ! OK - scalar result assigned to array
                                                              \EDOC
An example involving a WHERE-ELSEWHERE construct is:
                                                              \CODE
    INTERFACE
!HPF$ PURE
      REAL FUNCTION f_egde (x)
         REAL x
      END FUNCTION f_edge
!HPF$ PURE
      REAL FUNCTION f_interior (x)
        REAL x
      END FUNCTION f_interior
    END INTERFACE

    REAL a (10,10)
    LOGICAL edges (10,10)
! ...  initialise mask array 'edges' ...

    WHERE (edges)
      a = f_egde (a)
    ELSE WHERE
      a = f_interior (a)
    END WHERE
                                                              \EDOC
(Incidentally, this example also presents the possibility of obtaining
MIMD parallelism, if the compiler can establish that the two assignments 
are independent and so does not force a synchronisation at the ELSEWHERE
statement.)

\subparagraph{Elemental subroutine references}

Pure subroutines with scalar dummy arguments can be invoked 
{\em elementally\/} with the same interpretation as Fortran~90 
elemental intrinsic subroutines (of which there is only one).
This interpretation (Fortran~90 standard, Section~13.2.2) is as follows:
\begin{quote}
An elemental subroutine is one that is specified for scalar arguments, 
but may be applied to array arguments.  In a reference to an elemental 
intrinsic subroutine, either all actual arguments must be scalar or all 
INTENT(OUT) and INTENT(INOUT) arguments must be arrays of the same shape 
and the remaining arguments must be conformable with them. In the case 
that the INTENT(OUT) and INTENT(INOUT) arguments are arrays, the values 
of the elements, if any, of the results are the same as would be obtained 
if the subroutine with scalar arguments were applied separately, in any 
order, to corresponding elements of each argument.
\end{quote}

\subparagraph{Advantages of elemental usage}

User-defined elemental procedures have several potential advantages.
They would be a very convenient programming tool, as the same procedure 
can be applied to actual arguments of any rank.

In addition, the implementation of an elemental function returning an
array-valued result in an array expression is likely to be more 
efficient than that of an equivalent array function.  One reason is 
that it requires less temporary storage for the result (i.e.\ storage 
for a single result versus storage for the entire array of results).  
Another is that it saves on looping if an array expression is 
implemented by sequential iteration over the component elemental 
expressions (as may be done for the `segment' of the array expression 
local to each process).  This is because, in the sequential version, 
the elemental function can be invoked elementally in situ within the 
expression.  The array function, on the other hand, must be executed 
before the expression is evaluated, storing its result in a temporary 
array for use within the expression.  Looping is then required during 
the execution of the array function body as well as the expression 
evaluation.