Subject: New proposal draft

From: [email-masked]
Date: Mon, 31 Aug 92 14:26:47 -0500

This is the latest draft I have.  It makes several cosmetic
changes, and has the PURE function proposal that John Merlin made
earlier today.  (Actually, it has three changes to John's text, made
with his permission - removing the constraints against explicitly
distributed data in PURE functions, and changing a footnote into a
list item.)

Any discussion, new proposals, etc. should reach me by Friday in order
to make it on the agenda for the next HPFF meeting.

						Chuck

%Version of August 5, 1992 - David Loveman, Digital Equipment Corporation

\documentstyle[11pt]{report}
\pagestyle{plain}
\pagenumbering{arabic}
\marginparwidth 0pt
\oddsidemargin=.25in
\evensidemargin  .25in
\marginparsep 0pt
\topmargin=-.5in
\textwidth=6.0in
\textheight=9.0in
\parindent=2em

%the file syntax-macros.tex is physically included below

%syntax-macros.tex

%Version of July 29, 1992 - Guy Steele, Thinking Machines

\newdimen\bnfalign         \bnfalign=2in
\newdimen\bnfopwidth       \bnfopwidth=.3in
\newdimen\bnfindent        \bnfindent=.2in
\newdimen\bnfsep           \bnfsep=6pt
\newdimen\bnfmargin        \bnfmargin=0.5in
\newdimen\codemargin       \codemargin=0.5in
\newdimen\intrinsicmargin  \intrinsicmargin=3em
\newdimen\casemargin       \casemargin=0.75in
\newdimen\argumentmargin   \argumentmargin=1.8in

\def\IT{\it}
\def\RM{\rm}
\let\CHAR=\char
\let\CATCODE=\catcode
\let\DEF=\def
\let\GLOBAL=\global
\let\RELAX=\relax
\let\BEGIN=\begin
\let\END=\end

\def\FUNNYCHARACTIVE{\CATCODE`\a=13 \CATCODE`\b=13 \CATCODE`\c=13 \CATCODE`\d=13
		     \CATCODE`\e=13 \CATCODE`\f=13 \CATCODE`\g=13 \CATCODE`\h=13
		     \CATCODE`\i=13 \CATCODE`\j=13 \CATCODE`\k=13 \CATCODE`\l=13
		     \CATCODE`\m=13 \CATCODE`\n=13 \CATCODE`\o=13 \CATCODE`\p=13
		     \CATCODE`\q=13 \CATCODE`\r=13 \CATCODE`\s=13 \CATCODE`\t=13
		     \CATCODE`\u=13 \CATCODE`\v=13 \CATCODE`\w=13 \CATCODE`\x=13
		     \CATCODE`\y=13 \CATCODE`\z=13 \CATCODE`\[=13 \CATCODE`\]=13
                     \CATCODE`\-=13}

\def\RETURNACTIVE{\CATCODE`\
=13}

\makeatletter
\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus 
 -.2ex}{2.3ex plus .2ex}{\large\sf}}
\def\subsection{\@startsection{subsection}{2}{\z@}{-3.25ex plus -1ex minus 
 -.2ex}{1.5ex plus .2ex}{\large\sf}}

\def\@ifpar#1#2{\let\@tempe\par \def\@tempa{#1}\def\@tempb{#2}\futurelet
    \@tempc\@ifnch}

\def\?#1.{\begingroup\def\@tempq{#1}\list{}{\leftmargin\intrinsicmargin}\relax
  \item[]{\bf\@tempq.} \@intrinsictest}
\def\@intrinsictest{\@ifpar{\@intrinsicpar\@intrinsicdesc}{\@intrinsicpar\relax}}
\long\def\@intrinsicdesc#1{\list{}{\relax
  \def\@tempb{ Arguments}\ifx\@tempq\@tempb
			  \leftmargin\argumentmargin
			  \else \leftmargin\casemargin \fi
  \labelwidth\leftmargin  \advance\labelwidth -\labelsep
  \parsep 4pt plus 2pt minus 1pt
  \let\makelabel\@intrinsiclabel}#1\endlist}
\long\def\@intrinsicpar#1#2\\{#1{#2}\@ifstar{\@intrinsictest}{\endlist\endgroup}}
\def\@intrinsiclabel#1{\setbox0=\hbox{\rm #1}\ifnum\wd0>\labelwidth
  \box0 \else \hbox to \labelwidth{\box0\hfill}\fi}
\def\Case(#1):{\item[{\it Case (#1):}]}
\def\&#1 {\@ifnextchar({\def\@tempq{#1}\@intrinsicopt}{\item[#1]}}
\def\@intrinsicopt(#1){\item[{\@tempq} (#1)]}

\def\MATRIX#1{\relax
    \@ifnextchar,{\@MATRIXTABS{}#1,\@FOO, \hskip0pt plus 1filll\penalty-1\@gobble
  }{\@ifnextchar;{\@MATRIXTABS{}#1,\@FOO; \hskip0pt plus 1filll\penalty-1\@gobble
  }{\@ifnextchar:{\@MATRIXTABS{}#1,\@FOO: \hskip0pt plus 1filll\penalty-1\@gobble
  }{\@ifnextchar.{\hfill\penalty1\null\penalty10000\hskip0pt plus 1filll
		  \@MATRIXTABS{}#1,\@FOO.\penalty-50\@gobble
  }{\@MATRIXTABS{}#1,\@FOO{ }\hskip0pt plus 1filll\penalty-1}}}}}

\def\@MATRIXTABS#1#2,{\@ifnextchar\@FOO{\@MATRIX{#1#2}}{\@MATRIXTABS{#1#2&}}}
\def\@MATRIX#1\@FOO{\(\left[\begin{array}{rrrrrrrrrr}#1\end{array}\right]\)}

\def\@IFSPACEORRETURNNEXT#1#2{\def\@tempa{#1}\def\@tempb{#2}\futurelet\@tempc\@ifspnx}

{
\FUNNYCHARACTIVE
\GLOBAL\DEF\FUNNYCHARDEF{\RELAX
    \DEFa{{\IT\CHAR"61}}\DEFb{{\IT\CHAR"62}}\DEFc{{\IT\CHAR"63}}\RELAX
    \DEFd{{\IT\CHAR"64}}\DEFe{{\IT\CHAR"65}}\DEFf{{\IT\CHAR"66}}\RELAX
    \DEFg{{\IT\CHAR"67}}\DEFh{{\IT\CHAR"68}}\DEFi{{\IT\CHAR"69}}\RELAX
    \DEFj{{\IT\CHAR"6A}}\DEFk{{\IT\CHAR"6B}}\DEFl{{\IT\CHAR"6C}}\RELAX
    \DEFm{{\IT\CHAR"6D}}\DEFn{{\IT\CHAR"6E}}\DEFo{{\IT\CHAR"6F}}\RELAX
    \DEFp{{\IT\CHAR"70}}\DEFq{{\IT\CHAR"71}}\DEFr{{\IT\CHAR"72}}\RELAX
    \DEFs{{\IT\CHAR"73}}\DEFt{{\IT\CHAR"74}}\DEFu{{\IT\CHAR"75}}\RELAX
    \DEFv{{\IT\CHAR"76}}\DEFw{{\IT\CHAR"77}}\DEFx{{\IT\CHAR"78}}\RELAX
    \DEFy{{\IT\CHAR"79}}\DEFz{{\IT\CHAR"7A}}\DEF[{{\RM\CHAR"5B}}\RELAX
    \DEF]{{\RM\CHAR"5D}}\DEF-{\@IFSPACEORRETURNNEXT{{\CHAR"2D}}{{\IT\CHAR"2D}}}}
}

%%% Warning!  Devious return-character machinations in the next several lines!
%%%           Don't even *breathe* on these macros!
{\RETURNACTIVE\global\def\RETURNDEF{\def
{\@ifnextchar\FNB{}{\@stopline\@ifnextchar
{\@NEWBNFRULE}{\penalty\@M\@startline\ignorespaces}}}}\global\def\@NEWBNFRULE
{\vskip\bnfsep\@startline\ignorespaces}\global\def\@ifspnx{\ifx\@tempc\@sptoken \let\@tempd\@tempa \else \ifx\@tempc
\let\@tempd\@tempa \else \let\@tempd\@tempb \fi\fi \@tempd}}
%%% End of bizarro return-character machinations.

\def\IS{\@stopfield\global\setbox\@curfield\hbox\bgroup
  \hskip-\bnfindent \hskip-\bnfopwidth  \hskip-\bnfalign
  \hbox to \bnfalign{\unhbox\@curfield\hfill}\hbox to \bnfopwidth{\bf is \hfill}}
\def\OR{\@stopfield\global\setbox\@curfield\hbox\bgroup
  \hskip-\bnfindent \hskip-\bnfopwidth \hbox to \bnfopwidth{\bf or \hfill}}
\def\R#1 {\hbox to 0pt{\hskip-\bnfmargin R#1\hfill}}
\def\XBNF{\FUNNYCHARDEF\FUNNYCHARACTIVE\RETURNDEF\RETURNACTIVE
  \def\@underbarchar{{\char"5F}}\tt\frenchspacing
  \advance\@totalleftmargin\bnfmargin \tabbing
  \hskip\bnfalign\hskip\bnfopwidth\hskip\bnfindent\=\kill\>\+\@gobblecr}
\def\endXBNF{\-\endtabbing}

\def\BNF{\BEGIN{XBNF}}
\def\FNB{\END{XBNF}}

\begingroup \catcode `|=0 \catcode`\\=12
|gdef|@XCODE#1\EDOC{#1|endtrivlist|end{tt}}
|endgroup

\def\CODE{\begin{tt}\advance\@totalleftmargin\codemargin \@verbatim
   \def\@underbarchar{{\char"5F}}\frenchspacing \@vobeyspaces \@XCODE}
\def\ICODE{\begin{tt}\advance\@totalleftmargin\codemargin \@verbatim
   \def\@underbarchar{{\char"5F}}\frenchspacing \@vobeyspaces
   \FUNNYCHARDEF\FUNNYCHARACTIVE \UNDERBARACTIVE\UNDERBARDEF \@XCODE}

\def\@underbarsub#1{{\ifmmode _{#1}\else {$_{#1}$}\fi}}
\let\@underbarchar\_
\def\@underbar{\let\@tempq\@underbarsub\if\@tempz A\let\@tempq\@underbarchar\fi
  \if\@tempz B\let\@tempq\@underbarchar\fi\if\@tempz C\let\@tempq\@underbarchar\fi
  \if\@tempz D\let\@tempq\@underbarchar\fi\if\@tempz E\let\@tempq\@underbarchar\fi
  \if\@tempz F\let\@tempq\@underbarchar\fi\if\@tempz G\let\@tempq\@underbarchar\fi
  \if\@tempz H\let\@tempq\@underbarchar\fi\if\@tempz I\let\@tempq\@underbarchar\fi
  \if\@tempz J\let\@tempq\@underbarchar\fi\if\@tempz K\let\@tempq\@underbarchar\fi
  \if\@tempz L\let\@tempq\@underbarchar\fi\if\@tempz M\let\@tempq\@underbarchar\fi
  \if\@tempz N\let\@tempq\@underbarchar\fi\if\@tempz O\let\@tempq\@underbarchar\fi
  \if\@tempz P\let\@tempq\@underbarchar\fi\if\@tempz Q\let\@tempq\@underbarchar\fi
  \if\@tempz R\let\@tempq\@underbarchar\fi\if\@tempz S\let\@tempq\@underbarchar\fi
  \if\@tempz T\let\@tempq\@underbarchar\fi\if\@tempz U\let\@tempq\@underbarchar\fi
  \if\@tempz V\let\@tempq\@underbarchar\fi\if\@tempz W\let\@tempq\@underbarchar\fi
  \if\@tempz X\let\@tempq\@underbarchar\fi\if\@tempz Y\let\@tempq\@underbarchar\fi
  \if\@tempz Z\let\@tempq\@underbarchar\fi\@tempq}
\def\@under{\futurelet\@tempz\@underbar}

\def\UNDERBARACTIVE{\CATCODE`\_=13}
\UNDERBARACTIVE
\def\UNDERBARDEF{\def_{\protect\@under}}
\UNDERBARDEF

\catcode`\$=11  

%the following line would allow derived-type component references 
%FOO%BAR in running text, but not allow LaTeX comments
%without this line, write FOO\%BAR
%\catcode`\%=11 

\makeatother

%end of file syntax-macros.tex

\title{{\em Tentative Proposal} \\ High Performance Fortran \\ 
FORALL and INDEPENDENT Proposal}
\author{FORALL Subgroup, High Performance Fortran Forum}
\date{August 31, 1992}

\hyphenation{RE-DIS-TRIB-UT-ABLE sub-script Wil-liam-son}

\begin{document}

\maketitle

\newpage

\pagenumbering{roman}

\vspace*{4.5in}

This is the result of a LaTeX run of a draft of a single chapter of 
the HPFF Language Specification document.

\vspace*{3.0in}

\copyright 1992 Rice University, Houston Texas.  Permission to copy 
without fee all or part of this material is granted, provided the 
Rice University copyright notice and the title of this document 
appear, and notice is given that copying is by permission of Rice 
University.

\tableofcontents

\newpage

\pagenumbering{arabic}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%put text of chapter here

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%put \end{document} here

%statements.tex

%Version of August 2, 1992 - David Loveman, Digital Equipment Corporation 
%	and Chuck Koelbel, Rice University

%Revision history:
%August 19, 1992 - chk - cleaned up discrepancies with Fortran 90 array 
%	expressions
%August 20, 1992 - chk - added DO INDEPENDENT section, Guy Steele's 
%	pointer proposals
%August 24, 1992 - chk - ELEMENTAL functions proposal
%August 31, 1992 - chk - PURE functions proposal

\chapter{Statements\protect\footnote{Version of August 2, 1992 - David
Loveman, Digital Equipment Corporation and Chuck Koelbel, Rice University}}
\label{statements}

\section{Overview}

The purpose of the FORALL construct is to provide a convenient syntax for 
simultaneous assignments to large groups of array elements.
In this respect it is very similar to the functionality provided by array 
assignments and WHERE constructs.
FORALL differs from these constructs primarily in its syntax, which is 
intended to be more suggestive of local operations on each element of an 
array.
It is also possible to specify slightly more general array regions than 
are allowed by the basic array triplet notation.
Both single-statement and block FORALLs are defined in this proposal.

Recent discussions within the FORALL subgroup have made it clear that 
some are opposed to the construct on the grounds that it is unnecessary 
and perhaps confusing.
It is, however, clear that others in the group strongly support the added 
expressiveness provided by FORALL.
Because of this disagreement, the committee recommends that if FORALL is 
accepted into HPF, that it not be included in the official subset.
We feel, however, that it is important to define the construct so that 
implementations with this functionality have consistent semantics.

The following proposal is designed as a modification of the Fortran 90 
standard; all references to rule numbers and section numbers pertain to 
that document unless otherwise noted.

\section{Element Array Assignment - FORALL\protect\footnote{Version of 
August 20, 1992 - David
Loveman, Digital Equipment Corporation and Chuck Koelbel, Rice University}}  

\label{forall-stmt}

The element array
assignment statement is used to specify an array assignment in terms of
array elements or array sections.  The element array assignment may be
masked with a scalar logical expression.  Rule R215 for {\it
executable-construct} is extended to include the {\it forall-stmt}.

\subsection{General Form of Element Array Assignment}

                                                                       \BNF
forall-stmt          \IS FORALL (forall-triplet-spec-list 
                           [,scalar-mask-expr ]) forall-assignment

forall-triplet-spec  \IS subscript-name = subscript : subscript 
                           [ : stride]
                                                                       \FNB

\noindent
Constraint:  {\it subscript-name} must be a {\it scalar-name} of type integer.

\noindent
Constraint:  A {\it subscript} or a {\it stride} in a {\it
forall-triplet-spec} must not contain a reference to any {\it
subscript-name} in the {\it forall-triplet-spec-list}.

                                                                       \BNF
forall-assignment    \IS array-element = expr
					 \OR array-element => target
                     \OR array-section = expr
                                                                       \FNB

\noindent
Constraint:  The {\it array-section} or {\it array-element} in a {\it
forall-assignment} must reference all of the {\it forall-triplet-spec
subscript-names}.

\noindent
Constraint: In the cases of simple assignment, the {\it array-element} and 
{\it expr} have the same constraints as the {\it variable} and {\it expr} 
in an {\it assignment-stmt}.

\noindent
Constraint: In the case of pointer assignment, the {\it array-element} 
and {\it target} have the same constraints as the {\it pointer-object} 
and {\it target}, respectively, in a {\it pointer-assignment-stmt}.

\noindent
Constraint: In the cases of array section assignment, the {\it 
array-section} and 
{\it expr} have the same constraints as the {\it variable} and {\it expr} 
in an {\it assignment-stmt}.

For each subscript name in the {\it forall-assignment}, the set of
permitted values is determined on entry to the statement and is
\[  m1 + (k-1) * m3, where~k = 1, 2, ..., INT((m2 - m1 + m3) / m3)  \]
and where {\it m1}, {\it m2}, and {\it m3} are the values of the first
subscript, the second subscript, and the stride respectively in the
{\it forall-triplet-spec}.  If {\it stride} is missing, it is as if it
were present with a value of the integer 1.  The expression {\it
stride} must not have the value 0.  If for some subscript name 
\(INT((m2 -m1 + m3) / m3) \leq 0\), the {\it forall-assignment} is not
executed.

Examples of element array assignments are:

                                                                  \CODE
FORALL (I=1:N, J=1:N) H(I,J) = 1.0 / REAL(I + J - 1)

FORALL (I=1:N, J=1:N, A(I,J) .NE. 0.0) B(I,J) = 1.0 / A(I,J)

TYPE MONARCH
    INTEGER, POINTER :: P
END TYPE MONARCH
TYPE(MONARCH) :: A(N)
INTEGER B(N)
      ...
! Set up a butterfly pattern
FORALL (J=1:N)  A(J)%P => B(1+IEOR(J-1,2**K))

                                                                  \EDOC 

\subsection{Interpretation of Element Array Assignments}  

Execution of an element array assignment consists of the following steps:

\begin{enumerate}

\item Evaluation in any order of the subscript and stride expressions in 
the {\it forall-triplet-spec-list}.
The set of valid combinations of {\it subscript-name} values is then the 
cartesian product of the sets defined by these triplets.

\item Evaluation of the {\it scalar-mask-expr} for all valid combinations 
of {\em subscript-name} values.
The mask elements may be evaluated in any order.
The set of active combinations of {\it subscript-name} values is the 
subset of the valid combinations for which the mask evaluates to true.

\item Evaluation in any order of the {\it expr} or {\it target} and all 
subscripts contained in the 
{\it array-element} or {\it array-section} in the {\it forall-assignment} 
for all active combinations of {\em subscript-name} values.
In the case of pointer assignment where the {\it target} is not a 
pointer, the evaluation consists of identifying the object referenced 
rather than computing its value.

\item Assignment of the computed {\it expr} values to the corresponding 
elements specified by {\it array-element} or {\it array-section}.
In the case of a pointer assignment where the {\it target} is not a 
pointer, this assignment consists of associating the {\it array-element} 
with the object referenced.

\end{enumerate}

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.
Similarly, the evaluations of {\em expr}, {\it array-element} or {\it 
array-section} may not cause any scalar data object to be assigned a 
value more than once, nor may they cause an array element to be assigned 
which is also assigned directly by the {\it forall-assignment}.
Local variables within two instantiations of the same function do not 
refer to the same data object unless they have the SAVE attribute or are 
sequence or storage associated with the same object.
 
The evaluation of the {\it expr} for a particular active combination of
{\it subscript-name} values may neither affect nor be affected by 
the evaluation of {\it expr} for any other combination of {\it 
subscript-name} values.
In particular, functions cannot produce side effects that are visible in 
the FORALL; 
nor may global variables be updated by functions unless the results of 
those updates are independent of the order of execution of {\it 
subscript-name} values.
The evaluation of the {\it expr} or any subscript on the left-hand side 
of the {\it forall-assignment} for any active combination of {\it 
subscript-name} values may not affect 
nor be affected by 
the evaluation of any subscript in the {\it forall-assignment}, either 
for the same 
combination of {\it subscript-name} values or a different active
combination.
In particular, a function reference
appearing in any expression in the {\it forall-assignment} must not
redefine any subscript name.

\subsection{Scalarization of the FORALL Statement}

A {\it forall-stmt} of the general form:

                                                                   \CODE
FORALL (v1=l1:u1:s1, v2=l1:u2:s2, ..., vn=ln:un:sn , mask ) &
      a(e1,...,em) = rhs
                                                                   \EDOC

is equivalent to the following standard Fortran 90 code:

                                                                   \CODE
!evaluate subscript and stride expressions in any order

templ1 = l1
tempu1 = u1
temps1 = s1
templ2 = l2
tempu2 = u2
temps2 = s2
  ...
templn = ln
tempun = un
tempsn = sn

!then evaluate the scalar mask expression

DO v1=templ1,tempu1,temps1
  DO v2=templ2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        tempmask(v1,v2,...,vn) = mask
      END DO
	  ...
  END DO
END DO

!then evaluate the expr in the forall-assignment for all valid 
!combinations of subscript names for which the scalar mask 
!expression is true (it is safe to avoid saving the subscript 
!expressions because of the conditions on FORALL expressions)

DO v1=templ1,tempu1,temps1
  DO v2=tel2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        IF (tempmask(v1,v2,...,vn)) THEN
          temprhs(v1,v2,...,vn) = rhs
        END IF
      END DO
	  ...
  END DO
END DO

!then perform the assignment of these values to the corresponding 
!elements of the array being assigned to

DO v1=templ1,tempu1,temps1
  DO v2=templ2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        IF (tempmask(v1,v2,...,vn)) THEN
          a(e1,...,em) = temprhs(v1,v2,...,vn)
        END IF
      END DO
	  ...
  END DO
END DO
                                                                      \EDOC

\subsubsection{Consequences of the Definition of the FORALL Statement}

\begin{itemize}

\item The {\it scalar-mask-expr} may depend on the {\it subscript-name}s.

\item Each of the {\it subscript-name}s must appear within the
subscript expression(s) on the left-hand-side.  
(This is a syntactic
consequence of the semantic rule that no two execution instances of the
body may assign to the same array element.)

\item Right-hand sides and subscripts on the left hand side of a {\it 
forall-assignment} are
evaluated only for valid combinations of subscript names for which the
scalar mask expression is true.

\item Side-effects of function calls are allowed 
under the usual condition of Fortran statements that order of evaluation 
of subexpressions is undefined.
This principle has been extended so that side effects in computing one 
array element cannot affect other array elements.

\item Side-effects cannot assign to the same global array element or 
element of a function's actual argument twice.
This effectively disallows accumulations in function calls (including 
recording how many times a function is called).
It is still legal, however, to create side effects on {\it different} 
global array elements.

\item I am unable to find a clear answer to the following in the 
Fortran~90 standard: Can the evaluation of a function affect the values 
of global objects not referenced in the calling statement?
For example, is the following legal?
                                                                 \CODE
X = F(1) + F(2)
...
REAL FUNCTION F(K)
COMMON /HUH/ ICOUNT
ICOUNT = ICOUNT+1
F = K
END
																 \EDOC
The assignments to ICOUNT do not affect the values computed by F, and the 
final value of ICOUNT is mathematically independent of the order of 
evaulation here.
The constraints on FORALL evaluation above would not allow F to be called 
from a FORALL; if this is inconsistent with array expressions, the 
proposal should be amended or a note of the inconsistency made in the text.

\item Distinct function instantiations explicitly have distinct sets of 
local variables, to remove ambiguity about whether the following is legal:
                                                                  \CODE
FORALL ( I = 1:N ) A(I) = FOO( I )
...
INTEGER FUNCTION FOO( I )
INTEGER I, J, K
J = 1
K = I
DO WHILE ( K .GT. 1 )
  J = J+1
  IF (MOD(K,2) .EQ. 0) THEN
    K = K / 2
  ELSE
    K = K * 3 + 1
  END IF
END DO
FOO = K
END
                                                                 \EDOC 
Assuming distinct function calls have their own variables, there are no 
side effects to any global variable.
This is consistent (some might argue implied by) Section~12.5.2.4 of the 
Fortran~90 standard.
I don't claim this is particularly easy to implement on all machines.

\item This proposal is mute on whether I/O is allowed in functions called 
from FORALL statements.
This could, and probably should, be added as a constraint in the 
interpretation section.

\end{itemize}

\section{FORALL Construct\protect\footnote{Version of August 20, 1992 - David
Loveman, Digital Equipment Corporation and Chuck Koelbel, Rice University}}

\label{forall-construct}

The FORALL construct is a generalization of the element array
assignment statement allowing multiple assignments, masked array 
assignments, and nested FORALL statements to be
controlled by a single {\it forall-triplet-spec-list}.  Rule R215 for
{\it executable-construct} is extended to include the {\it
forall-construct}.

\subsubsection{General Form of the FORALL Construct}

                                                                    \BNF
forall-construct        \IS FORALL (forall-triplet-spec-list 
                                  [,scalar-mask-expr ])
                               forall-body-stmt-list
                            END FORALL

forall-body-stmt     \IS forall-assignment
                     \OR where-stmt
                     \OR forall-stmt
                     \OR forall-construct
                                                                    \FNB

\noindent
Constraint:  {\it subscript-name} must be a {\it scalar-name} of type
integer.

\noindent
Constraint:  A {\it subscript} or a {\it stride} in a {\it
forall-triplet-spec} must not contain a reference to any {\it
subscript-name} in the {\it forall-triplet-spec-list}.

\noindent
Constraint:  Any left-hand side {\it array-section} or {\it 
array-element} in any {\it forall-body-stmt}
must reference all of the {\it forall-triplet-spec
subscript-names}.

\noindent
Constraint: If a {\it forall-stmt} or {\it forall-construct} is nested 
within a {\it forall-construct}, then the inner FORALL may not redefine 
any {\it subscript-name} used in the outer {\it forall-construct}.
This rule applies recursively in the event of multiple nesting levels.

For each subscript name in the {\it forall-assignment}s, the set of
permitted values is determined on entry to the construct and is
\[  m1 + (k-1) * m3, where~k = 1, 2, ..., INT((m2 - m1 + m3) / m3)  \]
and where {\it m1}, {\it m2}, and {\it m3} are the values of the first
subscript, the second subscript, and the stride respectively in the
{\it forall-triplet-spec}.  If {\it stride} is missing, it is as if it
were present with a value of the integer 1.  The expression {\it
stride} must not have the value 0.  If for some subscript name 
\(INT((m2 -m1 + m3) / m3) \leq 0\), the {\it forall-assignment}s are not 
executed.

Examples of the FORALL construct are:

                                                                 \CODE
FORALL ( i = 2:n-1, j = 2:i-1 )
  a(i,j) = a(i,j-1) + a(i,j+1) + a(i-1,j) + a(i+1,j)
  b(i,j) = a(i,j)
END FORALL

FORALL ( i = 1:n-1 )
  FORALL ( j = i+1:n )
    a(i,j) = a(j,i)
  END FORALL
END FORALL

FORALL ( i = 1:n, j = 1:n )
  a(i,j) = MERGE( a(i,j), a(i,j)**2, i.eq.j )
  WHERE ( .not. done(i,j,1:m) )
    b(i,j,1:m) = b(i,j,1:m)*x
  END WHERE
END FORALL

         \EDOC

\subsection{Interpretation of the FORALL Construct}  

Execution of a FORALL construct consists of the following steps:

\begin{enumerate}

\item Evaluation in any order of the subscript and stride expressions in 
the {\it forall-triplet-spec-list}.
The set of valid combinations of {\it subscript-name} values is then the 
cartesian product of the sets defined by these triplets.

\item Evaluation of the {\it scalar-mask-expr} for all valid combinations 
of {\em subscript-name} values.
The mask elements may be evaluated in any order.
The set of active combinations of {\it subscript-name} values is the 
subset of the valid combinations for which the mask evaluates to true.

\item Execute the {\it forall-body-stmts} in the order they appear.
Each statement is executed completely (that is, for all active 
combinations of {\it subscript-name} values) according to the following 
interpretation:

\begin{enumerate}

\item Assignment statements and array assignment statements (i.e. 
statements in the {\it forall-assignment} category) evaluate the 
right-hand side {\it expr} and any left-and side subscripts for all 
active {\it subscript-name} values,
then assign those results to the corresponding left-hand side references.

\item WHERE statements evaluate their {\it mask-expr} for all active 
combinations of values of {\it subscript-name}s.
All elements of all masks may be evaluated in any order. 
The assignments within the WHERE branch of the statement are then 
executed in order using the above interpretation of array assignments 
within the FORALL, but the only array elements assigned are those 
selected by both the active {\it subscript-names} and the WHERE mask.
Finally, the assignments in the ELSEWHERE branch are executed if that 
branch is present.
The assignments here are also treated as array assignments, but elements 
are only assigned if they are selected by both the active combinations 
and by the negation of the WHERE mask.

\item FORALL statements and FORALL constructs first evaluate the 
subscript and stride expressions in 
the {\it forall-triplet-spec-list} for all active combinations of the 
outer FORALL constructs.
The set of valid combinations of {\it subscript-names} for the inner 
FORALL is then the union of the sets defined by these bounds and strides 
for each active combination of the outer {\it subscript-names}.
For example, the valid set of the inner FORALL in the second example in 
the last section is the upper triangle (not including the main diagonal) 
of the \(n \times n\) matrix a.
The scalar mask expression is then evaluated for all valid combinations 
of the inner FORALL's {\it subscript-names} to produce the set of active 
combinations.
If there is no scalar mask expression, it is assumed to be always true.
Each statement in the inner FORALL is then executed for each valid 
combination (of the inner FORALL), recursively following the 
interpretations given in this section.

\end{enumerate}

\end{enumerate}

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

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

A single assignment or array assignment statement in a {\it 
forall-construct} must obey the same restrictions as a {\it 
forall-assignment} in a simple {\it forall-stmt}.
(Note that the lowest level of nested statements must always be an 
assignment statement.)
For example, an assignment may not cause the same array element to be 
assigned more than once.
It is, however, permitted that different statements may assign to the 
same array element, or that the evaluation of subexpressions in one 
statement affect the execution of a later statement.
Evaluation of the mask or subscript bounds and stride 
expressions in an inner WHERE or FORALL for one active combination of 
{\it subscript-name} values may not affect nor be affected by the 
evaluations of those subexpressions for any other active combination.

\subsection{Scalarization of the FORALL Construct}

A {\it forall-construct} othe form:

                                                                \CODE
FORALL (... e1 ... e2 ... en ...)
    s1
    s2
     ...
    sn
END FORALL
                                                                \EDOC

where each si is an assignment is equivalent to the following scalar code:

                                                                \CODE
temp1 = e1
temp2 = e2
 ...
tempn = en
FORALL (... temp1 ... temp2 ... tempn ...) s1
FORALL (... temp1 ... temp2 ... tempn ...) s2
   ...
FORALL (... temp1 ... temp2 ... tempn ...) sn
                                                                \EDOC

A similar statement can be made using FORALL constructs when the 
si may be WHERE or FORALL constructs.

A {\it forall-construct} of the form:

                                                                \CODE
FORALL ( v1=l1:u1:s1, mask )
  WHERE ( mask2(l2:u2) )
    a(vi,l2:u2) = rhs1
  ELSEWHERE
    a(vi,l2:u2) = rhs2
  END WHERE
END FORALL
                                                                \EDOC

is equivalent to the following standard Fortran 90 code:

                                                                \CODE
!evaluate subscript and stride expressions in any order

templ1 = l1
tempu1 = u1
temps1 = s1

!then evaluate the FORALL mask expression

DO v1=templ1,tempu1,temps1
 tempmask(v1) = mask
END DO

!then evaluate the masks for the WHERE

DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    tmpl2(v1) = l2
    tmpu2(v1) = u2
    tempmask2(v1,tmpl2(v1):tmpu2(v1)) = mask2(tmpl2(v1):tmpu2(v1))
  END IF
END DO

!then evaluate the WHERE branch

DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    WHERE ( tempmask2(v1,tmpl2(v1):tmpu2(v1)) )
      temprhs1(v1,tmpl2(v1):tmpu2(v1)) = rhs1
    END WHERE
  END IF
END DO
DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    WHERE ( tempmask2(v1,tmpl2(v1):tmpu2(v1)) )
      a(v1,tmpl2(v1):tmpu2(v1)) = temprhs1(v1,tmpl2(v1):tmpu2(v1))
    END WHERE
  END IF
END DO

!then evaluate the ELSEWHERE branch

DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    WHERE ( .not. tempmask2(v1,tmpl2(v1):tmpu2(v1)) )
      temprhs2(v1,tmpl2(v1):tmpu2(v1)) = rhs2
    END WHERE
  END IF
END DO
DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    WHERE ( .not. tempmask2(v1,tmpl2(v1):tmpu2(v1)) )
      a(v1,tmpl2(v1):tmpu2(v1)) = temprhs2(v1,tmpl2(v1):tmpu2(v1))
    END WHERE
  END IF
END DO
                                                                   \EDOC

A {\it forall-construct} of the form:

                                                                   \CODE
FORALL ( v1=l1:u1:s1, mask )
  FORALL ( v2=l2:u2:s2, mask2 )
    a(e1,e2) = rhs1
	b(e3,e4) = rhs2
  END FORALL
END FORALL
                                                                   \EDOC

is equivalent to the following standard Fortran 90 code:

                                                                   \CODE
!evaluate subscript and stride expressions in any order

templ1 = l1
tempu1 = u1
temps1 = s1

!then evaluate the FORALL mask expression

DO v1=templ1,tempu1,temps1
 tempmask(v1) = mask
END DO

!then evaluate the inner FORALL bounds, etc

DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    templ2(v1) = l2
    tempu2(v1) = u2
    temps2(v1) = s2
	DO v2 = templ2(v1),tempu2(v1),temps2(v1)
      tempmask2(v1,v2) = mask2
	END DO
  END IF
END DO

!first statement

DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
	DO v2 = templ2(v1),tempu2(v1),temps2(v1)
	  IF ( tempmask2(v1,v2) ) THEN
        temprhs1(v1,v2) = rhs1
	  END IF
	END DO
  END IF
END DO
DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
	DO v2 = templ2(v1),tempu2(v1),temps2(v1)
	  IF ( tempmask2(v1,v2) ) THEN
        a(e1,e2) = temprhs1(v1,v2)
	  END IF
	END DO
  END IF
END DO

!second statement

DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
	DO v2 = templ2(v1),tempu2(v1),temps2(v1)
	  IF ( tempmask2(v1,v2) ) THEN
        temprhs2(v1,v2) = rhs2
	  END IF
	END DO
  END IF
END DO
DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
	DO v2 = templ2(v1),tempu2(v1),temps2(v1)
	  IF ( tempmask2(v1,v2) ) THEN
        b(e3,e4) = temprhs2(v1,v2)
	  END IF
	END DO
  END IF
END DO
                                                                   \EDOC

\subsubsection{Consequences of the Definition of the FORALL Construct}

\begin{itemize}

\item A block FORALL means the same as replicating the FORALL
header in front of each array assignment statement in the block, except
that any expressions in the FORALL header are evaluated only once,
rather than being re-evaluated before each of the statements in the body.
(This statement needs some modification in the case of nesting.)

\item One may think of a block FORALL as synchronizing twice per
contained assignment statement: once after handling the rhs and other 
expressions
but before performing assignments, and once after all assignments have
been performed but before commencing the next statement.  (In practice,
appropriate dependence analysis will often permit the compiler to
eliminate unnecessary synchronizations.)

\item The {\it scalar-mask-expr} may depend on the {\it subscript-name}s.

\item In general, any expression in a FORALL is evaluated only for valid 
combinations of all surrounding subscript names for which all the
scalar mask eressions are true.

\item Nested FORALL bounds and strides can depend on outer FORALL {\it 
subscript-names}.  They cannot redefine those names, even temporarily (if 
they did there  would be no way to avoid multiple assignments to the same 
array element).

\item Dependences are allowed from one statement to later statements, but 
never from an assignment statement to itself.
Masks and subscript bounds could conceivably have side effects visible in 
the rest of the nested statement.

\end{itemize}

\section{The INDEPENDENT Directive\protect\footnote{Version of August 20, 1992
 - Guy Steele, Thinking Machines Corporation, and Chuck Koelbel, Rice University}}

\label{do-independent}

Let there be a directive
                                                  \CODE
!HPF$INDEPENDENT
                                                  \EDOC
that can precede a DO loop.
It asserts to the compiler that the iterations of the loop
may be executed independently--that is, in any order, or
interleaved, or concurrently--without changing the semantics
of the program.  (The compiler is justified in producing
a warning if it can prove otherwise.)
                                                  \CODE
!HPF$INDEPENDENT
      DO I=1,100
        A(P(I))=B(I)   !I happen to know that P is a permutation
      END DO
                                                  \EDOC

One may apply this directive to a nest of multiple loops
by listing all the loop variables of the loops in question;
the loops must be contiguous with the directive and in the
same order that the variables are listed:
                                                  \CODE
!HPF$INDEPENDENT (I1,I2,I3)
      DO I1 = ...
        DO I2 = ...
          DO I3 = ...
            DO I4 = ...    !The inner two loops are *not* independent!
              DO I5 = ...
                ...
              END DO
            END DO
          END DO
        END DO
      END DO
                                                  \EDOC

These directives are purely advisory and a compiler is free
to ignore them if it cannot make use of the information.

This directive is of course similar to the DOSHARED directive
of Cray MPP Fortran.  A different name is offered here to avoid
even the hint of commitment to execution by a shared memory machine.
Also, the "mechanism" syntax is omitted here, though we might want
to adopt it as further advice to the compiler about appropriate
implementation strategies, if we can agree on a desirable set
of options.

\section{Other Proposals}

The proposals in this section have not been approved, even as a first 
reading.
Sections~\ref{begin-independent}, \ref{forall-pointer}, 
\ref{forall-allocate}, and \ref{data-ref} 
extend parts of the previous sections and/or the Fortran~90 standard.
Section~\ref{forall-elemental} is an alternative to the treatment of 
function calls in Sections~\ref{forall-stmt} and~\ref{forall-construct}.

\subsection{FORALL with INDEPENDENT Directives\protect\footnote{Version 
of July 21, 1992) - Min-You Wu}}
\label{begin-independent}

This proposal is an extension of Guy Steele's INDEPENDENT proposal.
We propose a block FORALL with the directives for independent 
execution of statements.  The INDEPENDENT directives are used
in a block style.  

The block FORALL is in the form of
                                                         \CODE
      FORALL (...) [ON (...)]
        a block of statements
      END FORALL
                                                         \EDOC
where the block can consists of a restricted class of statements 
and the following INDEPENDENT directives:
                                                         \CODE
!HPF$BEGIN INDEPENDENT
!HPF$END INDEPENDENT
                                                         \EDOC
The two directives must be used in pair.  
A sub-block of statements 
parenthesized in the two directives is called an {\em asynchronous} 
sub-block or {\em independent} sub-block.  
The statements that are 
not in an asynchronous sub-block are in {\em synchronized} sub-blocks
or {\em non-independent} sub-block.  
The synchronized sub-block is 
the same as Guy Steele's synchronized FORALL statement, and the 
asynchronous sub-block is the same as the FORALL with the INDEPENDENT 
directive.  
Thus, the block FORALL
                                                          \CODE
      FORALL (e)
        b1
!HPF$BEGIN INDEPENDENT
        b2
!HPF$END INDEPENDENT
        b3
      END FORALL
                                                           \EDOC
means roughly the same as
                                                           \CODE
      FORALL (e)
        b1
      END FORALL
!HPF$INDEPENDENT
      FORALL (e)
        b2
      END FORALL
      FORALL (e)
        b3
      END FORALL
                                                          \EDOC
														  
Statements in a synchronized sub-block are tightly synchronized.
Statements in an asynchronous sub-block are completely independent.
The INDEPENDENT directives indicates to the compiler there is no 
dependence and consequently, synchronizations are not necessary.
It is users' responsibility to ensure there is no dependence
between instances in an asynchronous sub-block.
A compiler can do dependence analysis for the asynchronous sub-blocks
and issue an error message when there exists a dependence or a warning
when it finds a possible dependence.

\subsubsection{What does ``no dependence between instances" mean?}

It means that no true dependence, anti-dependence,
or output dependence between instances.
Examples of these dependences are shown below:
\begin{enumerate}
\item True dependence:
                                                            \CODE
      FORALL (i = 1:N)
        x(i) = ... 
        ...  = x(i+1)
      END FORALL
                                                            \EDOC
Notice that dependences in FORALL are different from that in a DO loop.
If the above example was a DO loop, that would be an anti-dependence.

\item Anti-dependence:
                                                            \CODE
      FORALL (i = 1:N)
        ...  = x(i+1)
        x(i) = ...
      END FORALL
                                                            \EDOC

\item Output dependence:
                                                            \CODE
      FORALL (i = 1:N)
        x(i+1) = ... 
        x(i) = ...
      END FORALL
                                                            \EDOC
\end{enumerate}

Independent does not imply no communication.  One instance may access 
data in the other instances, as long as it does not cause a dependence.  
The following example is an independent block:
                                                            \CODE
      FORALL (i = 1:N)
!HPF$BEGIN INDEPENDENT
        x(i) = a(i-1)
        y(i-1) = a(i+1)
!HPF$END INDEPENDENT
      END FORALL
                                                            \EDOC

\subsubsection{Statements that can appear in FORALL}

FORALL statements, WHERE-ELSEWHERE statements, some intrinsic functions 
(and possibly elemental functions and subroutines) can appear in the FORALL:
\begin{enumerate}
\item FORALL statement
                                                            \CODE
      FORALL (I = 1 : N)
        A(I,0) = A(I-1,0)
        FORALL (J = 1 : N)
!HPF$BEGIN INDEPENDENT
          A(I,J) = A(I,0) + B(I-1,J-1)
          C(I,J) = A(I,J)
!HPF$END INDEPENDENT
        END FORALL
      END FORALL
                                                            \EDOC

\item WHERE
                                                            \CODE
      FORALL(I = 1 : N)
!HPF$BEGIN INDEPENDENT
        WHERE(A(I,:)=B(I,:))
          A(I,:) = 0
        ELSEWHERE
          A(I,:) = B(I,:)
        END WHERE
!HPF$END INDEPENDENT
      END FORALL
                                                            \EDOC
\end{enumerate}

\subsubsection{Rationale}

\begin{enumerate}
\item A FORALL with a single asynchronous sub-block as shown below is 
the same as a do independent (or doall, or doeach, or parallel do, etc.).
                                                            \CODE
      FORALL (e)
!HPF$BEGIN INDEPENDENT
        b1
!HPF$END INDEPENDENT
      END FORALL
                                                            \EDOC
A FORALL without any INDEPENDENT directive is the same as a tightly 
synchronized FORALL.  We only need to define one type of parallel 
constructs including both synchronized and asynchronous blocks.  
Furthermore, combining asynchronous and synchronized FORALLs, we 
have a loosely synchronized FORALL which is more flexible for many 
loosely synchronous applications.

\item With INDEPENDENT directives, the user can indicate which block
needs not to be synchronized.  The INDEPENDENT directives can act 
as barrier synchronizations.  One may suggest a smart compiler 
that can recognize dependences and eliminate unnecessary 
synchronizations automatically.  However, it might be extremely 
difficult or impossible in some cases to identify all dependences.  
When the compiler cannot determine whether there is a dependence, 
it must assume so and use a synchronization for safety, which 
results in unnecessary synchronizations and consequently, high 
communication overhead.
\end{enumerate}

\subsection{ALLOCATE in FORALL\protect\footnote{Version of July 28, 1992 
- Guy Steele, Thinking Machines Corporation}}

\label{forall-allocate}

Proposal:  ALLOCATE, DEALLOCATE, and NULLIFY statements may appear
	in the body of a FORALL.

Rationale: these are just another kind of assignment.  They may have
	a kind of side effect (storage management), but it is a
	benign side effect (even milder than random number generation).

Example:
                                                            \CODE
      TYPE SCREEN
        INTEGER, POINTER :: P(:,:)
      END TYPE SCREEN
      TYPE(SCREEN) :: S(N)
      INTEGER IERR(N)
      ...
!  Lots of arrays with different aspect ratios
      FORALL (J=1:N)  ALLOCATE(S(J)%P(J,N/J),STAT=IERR(J))
      IF(ANY(IERR)) GO TO 99999
                                                            \EDOC
\subsection{Generalized Data References\protect\footnote{Version of July 28, 1992 
- Guy Steele, Thinking Machines Corporation}}

\label{data-ref}

Proposal:  Delete the constraint in section 6.1.2 of the Fortran 90
	standard (page 63, lines 7 and 8):
\begin{quote}
	Constraint: In a data-ref, there must not be more than one
		part-ref with nonzero rank.  A part-name to the right
		of a part-ref with nonzero rank must not have the
		POINTER attribute.
\end{quote}

Rationale: further opportunities for parallelism.

Example:
                                                                     \CODE
      TYPE(MONARCH) :: C(N), W(N)
      ...
C  Munch that butterfly
      C = C + W * A%P		!Currently illegal in Fortran 90
                                                                      \EDOC
																	  
\subsection{ELEMENTAL Functions\protect\footnote{Version of August 31, 
1992 - John Merlin, University of Southhampton, and Chuck Koelbel, Rice 
University}}

\label{forall-elemental}

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 fctions 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.

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.

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 invok 
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.

\item One of us (JHM) is still in favour of disallowing access to global 
variables for a number of reasons: 
\begin{enumerate}
\item 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; 
\item 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; 
\item 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!
\end{enumerate}

\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 auments 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.

\subsection{A Proposal for MIMD Support in HPF\protect\footnote{Version 
of July 18, 1992 - Clemens-August Thole, GMD I1.T}}

\label{mimd-support}

\subsubsection{Abstract}

This proposal tries to supply sufficient language support in order 
to deal with loosely sysnchronous programs, some of which have been 
identified in my "A vote for explicit MIMD support".
This is a proposal for the support of MIMD parallelism, which extends
Section~\ref{do-independent}. 
It is more oriented
towards the CRAY - MPP Fortran Programming Model and the PCF proposal. 
The fine-grain synchronization of PCF is not proposed for implementation.
Instead of the CRAY-mechanims for assigning work to processors an 
extension of the ON-clause is used.
Due to the lack of fine-grain synchronization the constructs can be executed
on SIMD or sequential architectures just by ignoring the additional information.

\subsubsection{Summary of the current situation of MIMD support as part of HPF}

According to the Chuck Koelbel's (Rice) mail dated March 20th "Working Group 4 -
Issues for discussion" MIMD-support is a topic for discussion within working
group 4. 

Dave Loveman (DEC) has produced a document on FORALL statements 
(inorporated in Sections~\ref{forall-stmt} and \ref{forall-construct}) which
summarizes the discussion. Marc Snir proposed some extensions. These
constructs allow to describe SIMD extensions in an extended way compared
to array assignments. 

A topic for working papers is the interface of HPF Fortran to program units
which execute in SPMD mode. Proposals for "Local Subroutines" have been made
by Marc Snir and Guy Steele
(Chapter~\ref{foreign}). Both proposals
define local subroutines as program units, which are executed by all
processors independent of each other. Each processor has only access
to the data contained in its local memory. Parts of distributed data objects
can be accessed and updated by calls to a special library. Any message-passing
library might be used for synchronization and communication.
This approach does not really integrate MIMD-support into HPF programming.

The MPP Fortran proposal by Douglas M. Pase, Tom MacDonald, Andrew Meltzer (CRAY)
contained the following features in order to support integrated MIMD features:
\begin{itemize}
   \item  parallel directive
   \item  shared loops 
   \item  private variables
   \item  barrier synchronization
   \item  no-barrier directive for removing synchronization
   \item  locks, events, critical sections and atomic update
   \item  functions, to examine the mapping of data objects.
\end{itemize}

Steele's "Proposal for loops in HPF" (02.04.92) included a proposal for a 
directive "!HPF$ INDEPENDENT( integer_variable_list)", which specifies
for the next set of nested loops, that the loops with the specified
loop variables can be executed independent from each other.
(Sectin~\ref{do-independent} is a short version of this proposal.) 

Chuck Koelbel gave an overview on different styles for parallel loops
in "Parallel Loops Position Paper". No specific proposal was made.

Min-You Wu "Proposal for FORALL, May 1992" extended Guy Steele's 
"!HPF$INDEPENDENT" proposal to use the directive in a block style.

Clemens-August Thole "A vote for explicit MIMD support" contains 3 examples
from different application areas, which seem to require MIMD support for
efficient execution. 

\paragraph{Summary}

In contrast to FORALL extensions MIMD support is currently not well-established
as part of HPF Fortran. The examples in "A vote for explicit MIMD support"
show clearly the need for such features. Local subroutines do not fulfill
the requirements because they force to use a distributed memory programming model,
which should not be necessary in most cases.

With the exception of parallel sections all interesting features
are contained in the MPP-proposal. I would like to split the discussion
on specifying parallelism, synchronization and mapping into three different
topics. Furthermore I would like to see corresponding features to be expessed
in the style of of the current X3H5 proposal, if possible, in order to
be in line with upcoming standards.

\subsubsection{Proposal for MIMD support}

In order to support the spezification of MIMD-type of parallelism the following
features are taken from the "Fortran 77 Binding of X3H5 Model for 
Parallel Programming Constructs": 
\begin{itemize}
    \item   PARALLEL DO construct/directive
    \item   PARALLEL SECTIONS worksharing construct/directive
    \item   NEW statement/directive
\end{itemize}

These constructs are not used with PCF like options for mapping or 
sysnchronisation but are combined with the ON clause for mapping operations
onto the parallel architecture. 

\paragraph{PARALLEL DO}

\subparagraph{Explicit Syntax}

The PARALLEL DO construct is used to specify parallelism amoung the 
iterations of a block of code. The PARALLEL DO construct has the same
syntax as a DO statement. For an directive approach the directive
!HPF$ PARALLEL can be used in front of a do statement.
After the PARALLEL DO statement a new-declaration may be inserted.

A PARALLEL DO construct might be nested with other parallel constructs. 

\subparagraph{Interpretation}

The PARALLEL DO is used to specify parallel execution of the iterations of
a block of code. Each iteration of a PARALLEL DO is an independent unit
of work. The iterations of PARALLEL DO must be data independent. Iterations
are data independent if the storage sequence accociated with each variable
are array element that is assigned a value by each iteration is not referenced
by any other iteration. 

A program is not HPF conforming, if for any iteration a statement is executed,
which causes a transfer of control out of the block defined by the PARALLEL
DO construct. 

The value of the loop index of a PARALLEL DO is undefined outside the scope
of the PARALLEL DO construct. 

\paragraph{PARALLEL SECTIONS}

The parallel sections construct is used to specify parallelism among sections
of code.

\subparagraph{Explicit Syntax}

                                                              \CODE
        !HPF$ PARALLEL SECTIONS
        !HPF$ SECTION
        !HPF$ END PARALLEL SECTIONS
                                                              \EDOC
structured as
                                                              \CODE
        !HPF$ PARALLEL SECTIONS
        [new-declaration-stmt-list]
        [section-block]
        [section-block-list]
        !HPF$ END PARALLEL SECTIONS
                                                              \EDOC
where [section-block] is
                                                              \CODE
        !HPF$ SECTION
        [execution-part]
                                                              \EDOC

\subparagraph{Interpretation}

The parallel sections construct is used to specify parallelism among sections
of code. Each section of the code is an independent unit of work. A program
is not standard conforming if during the execution of any parallel sections
construct a transfer of control out of the blocks defined by the Parallel
Sections construct is performed. 
In a standard conforming program the sections of code shall be data 
independent. Sections are data independent if the storage sequence accociated 
with each variable are array element that is assigned a value by each section
is not referenced by any other section. 

\paragraph{Data scoping}

Data objects, which are local to a subroutine, are different between 
distinct units of work, even if the execute the same subroutine.

\paragraph{NEW statement/directive}

The NEW statement/directive allows the user to generate new instances of 
objects with the same name as an object, which can currently be referenced.

\subparagraph{Explicit Syntax}

A [new-declaration-stmt] is
                                                                \CODE
       !HPF$ NEW variable-name-list
                                                                \EDOC

\subparagraph{Coding rules}

A [varable-name] shall not be
\begin{itemize} 
\item    the name of an assumed size array, dummy argument, common block, 
function or entry point
\item    of type character with an assumed length
\item    specified in a SAVE of DATA statement
\item    associated with any object that is shared for this parallel construct.
\end{itemize}

\subparagraph{Interpretation}
 
Listing a variable on a NEW statement causes the object to be explicitly
private for the parallel construct. For each unit of work of the parallel 
construct a new instance of the object is created and referenced with the
specific name. 

\end{document}