Subject: New proposal

From: [email-masked]
Date: Sun, 18 Oct 1992 23:47:00 -0600

I just received a new proposal from Syracuse for changing/expanding the
FORALL and INDEPENDENT parts of HPF.  For a number of reasons (starting
with wanting to get some sleep tonight), I can't incorporate them into the
HPF draft by the deadline tomorrow morning.  Instead, I am circulating them
to these lists.  Copies will be available at the HPFF meeting Wednesday,
but the "official" FORALL/INDEPENDENT chapter will be the one I send out
later tonight (or early tomorrow morning, depending on how fast I tpe).

                                                Chuck
%chapter-head.tex

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

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

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

%syntax-macs.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\alternative#1 #2#3{\def\@tempa{#1}\def\@tempb{A}\ifx\@tempa\@tempb\else
    \expandafter\@altbumpdown\string#2\@foo\fi
    #2{Version #1: #3}}
\def\@altbumpdown#1#2\@foo{\global\expandafter\advance\csname c@#2\endcsname-1}

\def\@ifpa#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\re
lax}}
\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\endgr
oup}}
\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\@temp
c\@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\@spto
ken \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 folowing 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-macs.tex

\title{{\em D R A F T} \\High Performance Fortran \\ FORALL Proposal}
\author{G. Fox, T. Haupt, A. Choudhary, S. Ranka \\
Northeast Parallel Architectures Center\\
at Syracuse University, Syracuse, New York}
\date{October 15, 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 Final Report 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

%Revision history:
%August 2, 1992 - Original version of David Loveman, Digital Equipment
%       Corporation and Charles Koelbel, Rice University
%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
%September 3, 1992 - chk - reorganized sections
%September 21, 1992 - chk - began incorporating updates from Sept
%       10-11 meeting
%October 14, 1992 - chk - Incorporated ON and revised PURE 

\newenvironment{constraints}{
        \begin{list}{Constraint:}{
                \settowidth{\labelwidth}{Constraint:}
                \settowidth{\labelsep}{w}
                \settowidth{\leftmargin}{Constraint:w}
                \setlength{\rightmargin}{0cm}
        }
}{
        \end{list}
}

\chapter{Statements}
\label{statements}

\section{Overview}

\footnote{Version of October 15, 1992 
- G. Fox, T. Haupt, A. Choudhary, S. Ranka, Syracuse University.}
Programs written according to the current standard of Fortran, Fortran 90,
do not provide enough information to exploit fully capability of modern
architectures. In particular, detection of parallelism in fortran codes is 
usually very difficult. As a consequence, compilers are not able to 
generate efficient codes for machines, architecture of which support
concurrent execution. And although Fortran 90 includes some features which
make it possible to prepare codes to be run concurrently on some type of
architectures, notably array assignments on SIMD machines, in general, 
these features are not sufficient.

\subsection{Parallel Statements in Fortran 90}

Natural candidates for parallel execution are do loops, in cases where 
the are no loop carried data dependencies. The simplest example is an array 
assignment, introduced in Fortran 90. The array assignment, like that shown
below

                                                                     \CODE
    REAL, ARRAY(N) :: N
    ...
    A(I)=A(I-1)
    ...
                                                                     \EDOC
can be interpreted in terms of Fortran 77 syntax as a sequence of two
do loops: 

                                                                     \CODE
    DO I=1,N
    TEMP(I)=A(I-1)
    ENDDO

    DO I=1,N
    A(I)=TEMP(I)
    ENDDO
                                                                     \EDOC
Introduction of a temporary array TEMP is an implementation detail, actually
not necessary for many existing or future processor and/or system 
architectures. Nevertheless, it helps to understand the semantics of the
assignment. In particular, it is clearly seen that the resulting value of 
elements of the array A does not depend on the order in which they are 
assigned. This property of the array assignment makes it possible to
perform the assignments in parallel.

Masked array assignments, to assign only certain elements of one array
to another array, are introduced in Fortran 90 by WHERE statements and
WHERE construct. For example,

                                                                      \CODE
  EAL, ARRAY(N) :: A
    ...
    WHERE (A/=0) 
     RECIP_A=1.0/A
    ELSEWHERE
     RECIP_A=1.0
    ENDWHERE
                                                                     \EDOC
As an regular array assignment, the masked array assignment can be executed
in parallel.

The idea of array assignment is further extended by Fortran 90 elemental 
intrinsic functions. The simplest example of their use is

                                                                    \CODE
   REAL, ARRAY(N) :: A,X
   ...
   A=F(X)
   ...
                                                                    \EDOC
where F is one of 67 predefined intrinsics functions such as ABS, COS, 
LOG, etc. Semantics of this assignment is that each array element A(I) is
assigned a value of function F evaluated for the actual argument X(I). Each
invocation of F is independent of each other, regardless how complicated is
evaluation of the function value,  and therefore the function can be
called concurrently for different values of actual arguments.  

It has been demonstrated that a class of algorithms can be efficiently
implemented on parallel machines, in particular SIMD, using exclusively
Fortran 90 parallel statements described above. Nevertheless, the Fortran-90
does not provide sufficient syntactical means to define parallelism. 
As a consequence, we propose to extend Fortran 90 standard by introducing 
a generalization of array assignment statement, FORALL statement and FORALL 
construct with possibility of invoking user defined procedures in elemental 
fashion, in a close analogy to Fortran 90 elemental intrinsics functions.

\subsection{Overview of Proposed Extensions}

\subsubsection{FORALL statement}
\footnote{Proposed earlier by D. Loveman (DEC) and Ch. Koelbel (Rice), and
approved at second reading on September 10, 1992}
Fortran 90 introduces several restrictions on array assignments, 
in particular, it require that operands of the right side expressions be 
conformable with the left hand side array. These restrictions can be
relaxed by introducing an explicit parallel loop construct FORALL. FORALL,
which essentially preserves semantics of Fortran 90 array assignments and it
allows for convenient assignments like

                                                                  \CODE
   REAL, ARRAY(N,M) :: A
   ...
   FORALL(I=1:N,J=1:N) A(I,J)=I+J

                                                                  \EDOC
as opposed to standard Fortran 90 
                                                                  \CODE
   REAL, ARRAY(N,M)    :: A,A1,A2
   INTEGER, ARRAY(N)   :: IMN
   INTEGER, ARRAY(M)   :: IMM

   IMN=[1..N]
   A1=SPREAD(IMN,DIM=2,NCOPIES=M)
   IMM=[1..N]
   A2=SPREAD(IMM,DIM=1,NCOPIES=N)
   A=A1+A2              
                                                                \EDOC
or, to give more examples of convenience of FORALL statements
                                                                  \CODE
   REAL, ARRAY(N,M) :: B
   LOGICAL, ARRAY(N):: MASK
   REAL, ARRAY(N)   :: X
   REAL, ARRAY(M)   :: Y
   ...
   FORALL(I=1:N,J=1:N,MASK.EQ.-1) A(I,J)=A(I,J)-X(I)*Y(J)
   ...
   
   REAL, ARRAY(N,N) :: C
   REAL, ARRAY(N)   :: D
   ...
   C=0
   FORALL(I=1:N,J=1:N, I.EQ.J) C(I,J)=D(I)
   ...  
                                                                  \EDOC
which are difficult or tedious to express in Fortran 90.
   
Determinism of results requires that all array elements on the left hand side
be assigned at most once, and each subscript must appear within the
subscript expression(s) on the left hand side of the assignment.

\subsubsection{FORALL-ELSEFORALL construct}

\footnote{This is an extension to previously proposed FORALL construct, as
defined in the draft 0.2 of the HPF proposal}
FORALL-ELSEFORALL construct is a natural generalization of Fortran 90 
WHERE-ELSEWHERE construct. Accepting it, the last example can be rewritten as

                                                                  \CODE
   REAL, ARRAY(N,N) :: C
   REAL, ARRAY(N)   :: D
   ...
   FORALL(I=1:N,J=1:N, I.EQ.J) 
         C(I,J)=D(I)
   ELSEFORALL
         C(I,J)=0
   ENDFORALL
   ...
                                                                  \EDOC
The intended semantics can be inferred by comparison of these exaple codes,
and a detailed description in given later. A construct proposed in previous
drafts of the HPF: 
                                                                  \CODE
   FORALL(I=1:N,J=1:N)
    WHERE(MASK)
      assignment
    ELSEWHERE
      assignment
    ENDWHERE
   ENDFORALL
                                                                  \EDOC
seems to introduce unnecessary limitations coming from limitations
of WHERE construct: the mask array must conform with the variables on the 
right side in all of the array assignment statements in the construct.

\subsubsection{Parallel Loops}
Next, a limitation that only single array assignment statements can appear
in FORALL may be relaxed. This, however, implies some assertions made by
programmer about data dependencies in a body of parallel statements, nicely
depictured by G. Steele (TMC) in figure 1.1 and 1.2. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Here come the pictures!
%

{

%length for use in pictures
\setlength{\unitlength}{0.03in}

%nodes used in all pictures
\newsavebox{\nodes}
\savebox{\nodes}{
    \small\sf
    \begin{picture}(80,105)(10,-2.5)
    \put(50.0,100){\makebox(0,0){BEGIN}}
    \put(20.0,80.0){\makebox(0,0){rhsa(1)}}
    \put(50.0,80.0){\makebox(0,0){rhsa(2)}}
    \put(80.0,80.0){\makebox(0,0){rhsa(3)}}
    \put(20.0,60.0){\makebox(0,0){lhsa(1)}}
    \put(50.0,60.0){\makebox(0,0){lhsa(2)}}
    \put(80.0,60.0){\makebox(0,0){lhsa(3)}}
    \put(20.0,40.0){\makebox(0,0){rhsb(1)}}
    \put(50.0,40.0){\makebox(0,0){rhsb(2)}}
    \put(80.0,40.0){\makebox(0,0){rhsb(3)}}
    \put(20.0,20.0){\makebox(0,0){lhsb(1)}}
    \put(50.0,20.0){\makebox(0,0){lhsb(2)}}
    \put(80.0,20.0){\makebox(0,0){lhsb(3)}}
    \put(50.0,0){\makebox(0,0){END}}
    \put(50.0,100){\oval(25,5)}
    \put(20.0,80.0){\oval(20,5)}
    \put(50.0,80.0){\oval(20,5)}
    \put(80.0,80.0){\oval(20,5)}
    \put(20.0,60.0){\oval(20,5)}
    \put(50.0,60.0){\oval(20,5)}
    \put(80.0,60.0){\oval(20,5)}
    \put(20.0,40.0){\oval(20,5)}
    \put(50.0,40.0){\oval(20,5)}
    \put(80.0,40.0){\oval(20,5)}
    \put(20.0,20.0){\oval(20,5)}
    \put(50.0,20.0){\oval(20,5)}
    \put(80.0,20.0){\oval(20,5)}
    \put(50.0,0){\oval(25,5)}
    \put(50,97.5){\vector(-2,-1){30}}
    \put(50,97.5){\vector(0,-1){15}}
    \put(50,97.5){\vector(2,-1){30}}
    \put(20,17.5){\vector(2,-1){30}}
    \put(50,17.5){\vector(0,-1){15}}
    \put(80,17.5){\vector(-2,-1){30}}
    \end{picture}
}

\begin{figure}

\begin{minipage}{2.70in}
\CODE
FORALL ( i = 1:3 )
  lhsa(i) = rhsa(i)
  lhsb(i) = rhsb(i)
END FORALL
\EDOC

\centering
\begin{picture}(80,105)(10,-2.5)
\small\sf
%save the messy part of the picture & reuse it
\newsavebox{\web}
\savebox{\web}{
    \begin{picture}(60,15)(0,0)
    \put(0,15){\vector(0,-1){15}}
    \put(0,15){\vector(2,-1){30}}
    \put(0,15){\vector(4,-1){60}}
    \put(30,15){\vector(-2,-1){30}}
    \put(30,15){\vector(0,-1){15}}
    \put(30,15){\vector(2,-1){30}}
    \put(60,15){\vector(0,-1){15}}
    \put(60,15){\vector(-2,-1){30}}
    \put(60,15){\vector(-4,-1){60}}
    \end{picture}
}
\put(10,-2.5){\usebox\nodes}
\put(20,62.5){\usebox\web}
\put(20,42.5){\usebox\web}
\put(20,22.5){\usebox\web}
\end{picture}
\end{minipage}
%
\hfill
%
\begin{minipage}{2.70in}
\CODE
DO i = 1, 3
  lhsa(i) = rhsa(i)
  lhsb(i) = rhsb(i)
END DO
\EDOC

\centering
\begin{picture}(80,105)(10,-2.5)
\small\sf
%save the messy part of the picture & reuse it
\newsavebox{\chain}
\savebox{\chain}{
    \begin{picture}(20,70)(0,0)
    \put(2.5,2.5){\oval(5,5)[bl]}
    \put(2.5,0){\vector(1,0){5}}
    \put(7.5,2.5){\oval(5,5)[br]}
    \put(10,2.5){\vector(0,1){32.5}}
    \put(10,35){\line(0,1){32.5}}
    \put(12.5,67.5){\oval(5,5)[tl]}
    \put(12.5,70){\vector(1,0){5}}
    \put(17.5,67.5){\oval(5,5)[tr]}
    \end{picture}
}
\put(10,-2.5){\usebox\nodes}
\put(20,77.5){\vector(0,-1){15}}
\put(20,57.5){\vector(0,-1){15}}
\put(20,37.5){\vector(0,-1){15}}
\put(25,15){\usebox\chain}
\put(50,77.5){\vector(0,-1){15}}
\put(50,57.5){\vector(0,-1){15}}
\put(50,37.5){\vector(0,-1){15}}
\put(55,15){\usebox\chain}
\put(80,77.5){\vector(0,-1){15}}
\put(80,57.5){\vector(0,-1){15}}
\put(80,37.5){\vector(0,-1){15}}
\end{picture}
\end{minipage}

\caption{Dependences in DO and FORALL without
INDEPENDENT assertions}
\label{fig-dep}
\end{figure}

\begin{figure}

%Draw the picture once, use it twice
\newsavebox{\easy}
\savebox{\easy}{
    \small\sf
    \begin{picture}(80,105)(10,-2.5)
    \put(10,-2.5){\usebox\nodes}
    \put(20,77.5){\vector(0,-1){15}}
    \put(20,57.5){\vector(0,-1){15}}
    \put(20,37.5){\vector(0,-1){15}}
    \put(50,77.5){\vector(0,-1){15}}
    \put(50,57.5){\vector(0,-1){15}}
    \put(50,37.5){\vector(0,-1){15}}
    \put(80,77.5){\vector(0,-1){15}}
    \put(80,57.5){\vector(0,-1){15}}
    \put(80,37.5){\vector(0,-1){15}}
    \end{picture}
}

\begin{minipage}{2.70in}
\CODE
!HPF$ INDEPENDENT
FORALL ( i = 1:3 )
  lhsa(i) = rhsa(i)
  lhsb(i) = rhsb(i)
END FORALL
\EDOC

\centering
\usebox\easy
\end{minipage}
%
\hfill
%
\begin{minipage}{2.70in}
\CODE
!HPF$ INDEPENDENT
DO i = 1, 3
  lhsa(i) = rhsa(i)
  lhsb(i) = rhsb(i)
END DO
\EDOC

\centering
\usebox\easy
\end{minipage}

\caption{Dependences in DO and FORALL with
INDEPENDENT assertions}
\label{fig-indep}
\end{figure}

}

%
%
% End of pictures
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In essence, 3 types of data dependencies are relevant in the context of this
proposal.

\begin{enumerate}
\item  `SEQUENTIAL DO LOOP' : the right hand sides values of depend on 
       computations made in other iterations of the loop: it is often 
       referred to as loop carried dependencies, and it is shown on right 
       hand side 
       of figure 1.1. In this case parallel execution is not possible, at
       least within the computational model adopted by HPF.
\item `FORALL LOOP': there are no loop carried dependencies, and assignments
        can be made simultaneously for each iterations. That is, processors 
        may be  synchronized after each assignment in the block. 
        This situation is shown on left hand side of fig.  1.1.
\item `INDEPENDENT LOOP':  there are no loop carried dependencies, but 
       operands of right hand side expressions may depend on results obtained
       earlier in the same iteration, as shown in fig. 1.2. In other words, 
       iterations of the loop can be performed independently from each other,
        however, the sequence of assignment in an iteration must not be 
       changed to preserve semantics of the loop. As a consequence, a 
       parallel execution is possible by assigning processors distinct 
       subsets of loop instantiations  and synchronization is forced after 
       all iterations are completed.   

\end{enumerate}
The semantics of these constructs cannot be adequately expressed in terms
of Fortran 90 syntax. It can be done using HPF extensions, however, a further
generalization of FORALL is necessary.

\subsubsection{General FORALL Construct}

\footnote{This is an extension of previously proposed FORALL construct, as
defined in the draft 0.2 of the HPF proposal}
The `FORALL LOOP' (case 2 above) can be expressed by the FORALL construct
                                                                    \CODE
    FORALL (I=1:M)
      lhs1=rhs1   
      ...
      lhsN=rhsN
    ENDFORALL
                                                                    \EDOC
which is just a shorthand for a tedious
                                                                    \CODE
    FORALL (I=1:M) lhs1=rhs1
    ...
    FORALL (I=1:M) lhsN=rhsN
                                                                    \EDOC
with an important semantical modifications of FORALL that evaluation of all 
valid combinations of loop indices is made
once before actual execution of the FORALL construct body, and it implies
an assertion of the programmer that data dependencies allow
for parallel execution with synchronization of processors after each 
assignment.
   
The full form of the FORALL construct
                                                                    \CODE
    FORALL (I=1:M, MASK)
      statement1
      ...
      statementN
    ELSEFORALL
      statementN+1
      ...
      statementsN+K
    ENDFORALL
                                                                    \EDOC
can be interpreted as a following sequence of opreations
\begin{enumerate}
\item determine a set of valid combinations of indices
\item evaluate mask expressions for all valid combination of indices
\item execute the block of statements (from statement1 through statementN)
      masked by MASK
\item execute the block of statetments (from statementN+1 through 
      statementN+K) masked by .NOT.MASK  
\end{enumerate}

\subsubsection{Procedures in FORALL statement/construct}

`INDEPENDENT LOOP' has been addressed in previous drafts of the HPF proposal
by G. Steele (TMC), Ch. Koelbel (Rice), and others. They proposed to
annotate a loop with that kind of data dependencies with the
                             \CODE
     !HPF$  INDEPENDENT
                             \EDOC
directive. Indeed, such a solution reflects the intended semantics. On the 
other hand, it introduces some syntactic challenges, and it tempts
to violate the HPF computational model by requesting private instances of 
variables. 

All that can be avoided by noticing that the body of the loop may be defined
as a procedure, with the loop index, say i, or an array  as (one of) dummy 
argument(s). By construction, each invocation of the function is independent 
from others (for other values of i or other element of the array). Now, since
each instantiation of the function creates its own, distinct set of local 
variables the problem of scope of the variables and determinism is 
solved. Thus the proposed solution for the independent loop is to use 
elementally invocated procedures as operands of the left hand side 
expression of the FORALL assignments. This can be 
illustrated by an example given by D. Loveman (DEC) and C. Koelbel (Rice) 
\footnote{draft 0.2 of the HPF proposal, page 34}:
                                              \CODE                     
                                        
       REAL A(1000)    
!HPF$  TEMPLATE(1000)
!HPF$  PROCESSORS P(10)
!HPF$  DISTRIBUTE T(BLOCK) ONTO P
!HPF$  ALIGN A(:) WITH T(:)

       ...
       FORALL(I=1:1000) A(I)=FOO(I)
       ...
       END

       FUNCTION F00(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
          ENDIF
       ENDDO
       FOO=K
       END
                                                                 \EDOC
as opposed to
                                                                 \CODE

       REAL A(1000)
       INTEGER I,J,K

       ...
!HPF$ INDEPENDENT
       DO I=1,1000
         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
            ENDIF
         ENDDO
         A(I)=K
       ENDDO
                                                                     \EDOC

By using FORALL with a function, whole chunk of Fortran 90 code is 
preserved (in practice, when dealing with various 'dusty decks' many parts of 
Fortran 77 codes can be saved this way), and local variables are used
in a way consistent with the HPF computational model.

In this way, it is possible to express conveniently majority of embarrassingly
parallel algorithms without introducing new syntactic features. However,
as in case of the FORALL construct, semantically, it implies assertions on
data dependencies. It is dsirable to annotate classes of functions and
subroutines which can be used in FORALL statements/constructs by a dedicated
HPF directives.

Procedures which can be invoked elementally in array assignments, beside
being explicitly annotated, must satisfy some restrictions. The basic idea
is that any instantiation of the procedure must not influence other
instantiations, that is, all invocation may be made in arbitrary order
without violating determinism of results. As a consequence, local variable
must not have SAVE attribute, must not (re)distribute nor (re)align global
data. The access to the global data must be restricted, too. There are two
possibilities of imposing restrictions of that kind, described in the 
following two sections.

\subsubsection{INDEPENDENT procedure}

\footnote{This is an extension to previously proposed PURE procedures by
 J. Merlin (Southampton) and Ch. Koelbel (Rice)}
The procedure does not assign to global data. In that case, there is no
restrictions on 'read only' access to global data, passed to it as
arguments with explicitly specified intent IN. Basically, it is equivalent
to the PURE procedure, defined in draft v0.2 of the HPF proposal. Here,
an extenstion of that idea is proposed.

An INDEPENDENT procedure may have scalar arguments declared with intent OUT, 
and an INDEPENDENT procedure may not produce side effects in the sense that
its execution is equivalent to execution of a single iteration of an
INDEPENDENT LOOP (c.f. fig. 1.2).

                                                                  \CODE     
        REAL, ARRAY(N) :: A,X       
        ...
        FORALL (I=1:N) A(I)=FOO(I,A,X(I))
        ...
                                                                  \EDOC
In this example, a global array A is passed to the function FOO, and the
function returns two scalar variables to be assigned to global arrays
A and X. According to the owner compute rule, evaluation of the function
is carried by the logical processor owning the element of the template,
which the array element A(I) is aligned to.  Sequentialization of
this FORALL assignment is

                                                                  \CODE
       DO I=1,N
        TEM1(I)=FOO(I,A,TEM2(I)) 
       ENDDO

       DO I=1,N
        A(I)=TEM1(I)
        X(I)=TEM2(I)
       ENDDO
                                                                 \EDOC

A directive !HPF$INDEPENDENT is used to annotate  INDEPENDENT procedures.

An example of usage of an INDEPENDENT function is given below:
                                                                 \CODE
        ...
      REAL, ARRAY(N,M) :: A,B
!HPF$ TEMPLATE FRED(N,M)
!HPF$ DISTRIBUTE FRED(BLOCK,BLOCK)
!HPF$ ALIGN A with FRED
!HPF$ ALIGN B with FRED
      ...
      INTERFACE
       REAL FUNCTION FOO(I,J,N,M,A,Y)
!HPF$   INDEPENDENT FOO
       INTENT (IN) :: I,J,N,M,A
       INTENT (OUT) :: Y
       REAL, ARRAY(N,M) :: A
!HPF$   TEMPLATE FELIX(N,M)
!HPF$   DISTRIBUTE FELIX *
!HPF$   ALIGN A * 
      END INTERFACE 
      ...
      DO I=1,NEVENTS
      FORALL (I=1:N,J=1:M) A(I,J)=FOO(I,J,N,M,A,B(I,J))
      IF(MAXVAL(B).LT.XLIMIT) EXIT
      ENDDO
     ...

      REAL FUNCTION FOO(I,J,N,M,A,Y)
!HPF$ INDEPENDENT FOO
      INTENT (IN) :: I,J,N,M,A
      INTENT (OUT) :: Y
      REAL, ARRAY(N,M) :: A
!HPF$ TEMPLATE FELIX(N,M)
!HPF$ DISTRIBUTE FELIX *
!HPF$ ALIGN A * 
      ...
      COUNT=1.0
      X=A(I,J)
      IF(I.GT.1) THEN
         X=X+A(I-1,J)
         COUNT=COUNT+1.0
      ENDIF
      IF(I.LT.N) THEN
         X=X+A(I+1,J)
         COUNT=COUNT+1.0
      ENDIF
      IF(J.GT.1) THEN
         X=X+A(I,J-1)
         COUNT=COUNT+1.0
      ENDIF
      IF(J.LT.M) THEN
         X=X+A(I,J+1)
         COUNT=COUNT+1.0
      ENDIF
      FOO=X/COUNT  
      Y=ABS(A(I,J),FOO)
      END
                                                                 \EDOC

\subsubsection{LOCAL procedures}

The procedure has access only to that part global data which are aligned to
the template element owned by a logical processor executing the procedure. 
For example

                                                                  \CODE
       REAL, ARRAY(N) :: A,B,C
!HPF$  TEMPLATE FRED(N)
!HPF$  ALIGN A with FRED
!HPF$  ALIGN B(I) with FRED(I+1)
!HPF$  ALIGN C with FRED
!HPF$  DISTRIBUTE FRED(CYCLIC)
       INTERFACE
         SUBROUTINE FOO(I,N,A,B,C)
!HPF$    LOCAL FOO
         REAL, ARRAY(N) :: A,B,C
!HPF$    TEMPLATE FRED(N)
!HPF$    ALIGN A *
!HPF$    ALIGN B(I) *
!HPF$    ALIGN C *
!HPF$    DISTRIBUTE FRED *
       END INTERFACE           

       FORALL (I=1:N) CALL FOO(I,N,A,B,C)
                                                                  \EDOC
Here the subroutine FOO inherits the distribution and alignment
of arrays A, B, and C (as it is described in Chapter 3 of the HPF 
proposal), and it is free to assign new values to array elements 
aligned to the element of the template FRED(I), in this case A(I), B(I-1) 
and C(I). On the other hand, the function cannot access the other 
elements of arrays A, B and C. To make this arrangement unambiguous, there 
must be exaclty one template defined in the LOCAL procedure. The template
index (indices for 2 or more dimensionial templates) must be passed as
arguments to the LOCAL procedure.

This construct can be used for 
embarrassingly parallel evaluation of arrays of coefficient, Monte Carlo 
simulations, etc., followed by a 'regular' matrix algebra, HPF reduction 
functions or other computations conveniently expressable in HPF syntax.

The sequentialization of the FORALL statement with subroutine is simply:
                                                                   \CODE
      DO I=1,N
       CALL FOO(I,A,B,C)
      ENDDO
                                                                   \EDOC 
where subroutine FOO has access only to single elements of arrays A,B,C,
namely A(I),B(I-1), and C(I). All arrays are aligned to the same template,
and an instantiation of the subroutine is executed by the processors
owning the corresponding element of the template, here FRED(I).
     
A directive !HPF$LOCAL is used to annotate LOCAL procedures.

An example of usage of the LOCAL function is given below:
                                                           \CODE
     ...
     
C    NP=NUMBER_OF_PROCESSORS     

      REAL,  ARRAY(NP) :: PX,PX2,SEED
CHPF$ TEMPLATE T(NP)
CHPF$ DISTRIBUTE T(CYCLIC)
CHPF$ ALIGN PX with T
CHPF$ ALIGN PX2 with T
CHPF$ ALIGN SEED with T
      INTERFACE
       SUBROUTINE FOO(I,SEED,X,X2)
!HPF$  LOCAL FOO
       REAL,  ARRAY(:) :: X,X2,SEED
CHPF$  ALIGN PX with *
CHPF$  ALIGN PX2 with *
CHPF$  ALIGN SEED with *
      END INTERFACE

      FORALL (I=1:NP) SEED(I)=something(I)
      DO I=1,NEVENTS
       N=I*NP
       FORALL (I=1:NP) CALL FOO(I,SEED,PX,PX2)
       X=X+SUM(PX)
       X2=X2+SUM(PX2)
       IF(SQRT(X2/N-(X/N)**2).LT.0.01) EXIT
      ENDDO
      AVERAGE=X/N
      ...
      END

      SUBROUTINE FOO(I,SEED,X,X2)
!HPF$ LOCAL FOO
      REAL,  ARRAY(:) :: X,X2,SEED
CHPF$ ALIGN PX with *
CHPF$ ALIGN PX2 with *
CHPF$ ALIGN SEED with *
      Z=RANDOM(SEED(I))
      Y=RANDOM(SEED(I))
      X(I)=(Z**2+Y**2)/2.0
      X2(I)=X(I)**2
      END
                                         \EDOC

The difference between a LOCAL and PURE procedure is that they access
global data different way. 

The difference between LOCAL function and FOREIGN procedure are that:

\begin{itemize}
\item LOCAL function supports the HPF computational model, while FOREIGN
procedure
  does not
\item a reference to a non-local data in FOREIGN procedure is possible by
  explicit message passing while in LOCAL procedure it is prohibited.
\item a LOCAL function is invoked elementally.
\end{itemize}

\subsubsection{User Defined Elemantal Functions}

\footnote{Introduced by J. Merlin (Southampton) and Ch. Koelbel (Rice).}
Fortran 90 introduces the concept of `elemental procedures', which are 
defined for scalar arguments but may also be applied to conforming 
array-valued arguments.  The latter type of reference to an elemental 
procedure is called an `elemental' reference.    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 as 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 elemental reference to a subset of 
the intrinsic procedures --- programmers cannot define their own 
elemental procedures.  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
introduced by requesting the function to be a pure function.

\section{PURE Procedures}

\footnote{This section is copied from the FORALL draft (Oct. 14, 1992). The
only modification is that PURE function are allowed to be within body of
INDEPENDENT procedures and to be actual argument in an INDEPENDENT procedure
reference.}
A {\it pure function} is one that produces no side effects. This means that 
the only effect of a pure function reference on the state of a program
is to return a result - it does not modify the values, pointer associations
or data mapping of any of its arguments or global data, and performs no
I/O. A {\it pure subroutine} is one that produces no side effects except for
modifying the values and/or pointer associations of certain arguments.

A PURE procedure (i.e. function or subroutine) may be used in any way that
a normal procedure can. In addition, a procedure is required to be PURE in
any of the following context:
\begin{itemize}
\item an elemental reference
\item within the body of a PURE procedure
\item as an actual argument in a PURE procedure reference
\end{itemize}
A PURE procedure may be used
\begin{itemize}
\item in a FORALL statement or construct
\item within the body of an INDEPENDENT procedure
\item as an actual argument in an INDEPENDENT procedure reference 
\end{itemize}

A PURE procedure must have explicit interface, and it must be defined to be
PURE in both its definition and interface. The form of this declaration is
a directive 
                                                                     \BNF
pure-directive  \IS   PURE function-name
                                                                     \FNB
\subsubsection{Pure function definition}

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

        \item If a {\it procedure-name\/} is present in the 
{\it pure-directive\/}, it must match the {\it function-name\/} in the 
{\it function-stmt\/}.

        \item In a pure function, a local variable must not have the 
SAVE attribute. (Note that this means that a local variable cannot be 
initialised in a {\it type-declaration-stmt\/} or a
{\it data-stmt\/}, which imply the SAVE attribute.)

        \item A pure function must not use a dummy argument, a global 
variable, or an object that is storage associated with a global variable,
or a subobject thereof, in the following contexts:
        \begin{itemize}
                \item as the assignment variable of an {\it assignment-stmt\/}
or {\it forall-assignment\/};
                \item as a DO variable or implied DO variable, or as a 
{\it subscript-name\/} in a {\it forall-triplet-spec\/};
                \item in an {\it assign-stmt\/};
                \item as the {\it pointer-object\/} or {\it target\/}
of a {\it pointer-assignment-stmt\/};
                \item as the {\it expr\/} of an {\it assignment-stmt\/}
or {\it forall-assignment\/} whose assignment variable is of a derived 
type, or is a pointer to a derived type, that has a pointer component 
at any level of component selection;
                \item as an {\it allocate-object\/} or {\it stat-variable\/}
in an {\it allocate-stmt\/} or {\it deallocate-stmt\/}, or as a
{\it pointer-object\/} in a {\it nullify-stmt\/};
                \item as an actual argument associated with a dummy 
argument with INTENT (OUT) or (INOUT) or with the POINTER attribute.
        \end{itemize}

        \item Any procedure referenced in a pure function, including
one referenced via a defined operation or assignment, must be pure.

        \item In a pure function, a dummy argument or local variable 
must not appear in an {\it align-directive\/}, {\it realign-directive\/},
{\it distribute-directive\/}, {\it redistribute-directive\/},
{\it realignable-directive\/}, {\it redistributable-directive\/} or
{\it combined-directive}.

        \item In a pure function, a global variable must not appear in
{\it realign-directive\/} or {\it redistribute-directive\/}.

        \item A pure function must not contain a {\it pause-stmt\/},
{\it stop-stmt\/} or I/O statement (including a file operation).

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

The above constraints are designed to guarantee that a pure function
is free from side effects (i.e.\ modifications of data visible outside
the function), which means that it is safe to reference concurrently, 
as explained earlier.

The second constraint ensures that a pure function does not retain
an internal state between calls, which would allow side-effects between 
calls to the same procedure.

The third constraint ensures that dummy arguments and global variables
are not modified by the function.
In the case of a dummy or global pointer, this applies to both its 
pointer association and its target value, so it cannot be subject to 
a pointer assignment or to an ALLOCATE, DEALLOCATE or NULLIFY
statement.
Incidentally, these constraints imply that only local variables and the
dummy result variable can be subject to assignment or pointer assignment.

In addition, a dummy or global data object cannot be the {\it target\/}
of a pointer assignment (i.e.\ it cannot be used as the right hand side
of a pointer assignment to a local pointer or to the result variable), 
for then its value could be modified via the pointer.

In connection with the last point, it should be noted that an ordinary 
(as opposed to pointer) assignment to a variable of derived type that has 
a pointer component at any level of component selection may result in a 
{\em pointer\/} assignment to the pointer component of the variable.
That is certainly the case for an intrinsic assignment.  In that case
the expression on the right hand side of the assignment has the same type 
as the assignment variable, and the assignment results in a pointer 
assignment of the pointer components of the expression result to the
corresponding components of the variable (see section 7.5.1.5 of the 
Fortran~90 standard).  However, it may also be the case for a 
{\em defined\/} assignment to such a variable, even if the data type of 
the expression has no pointer components;  the defined assignment may still 
involve pointer assignment of part or all of the expression result to the 
pointer components of the assignment variable.  Therefore, a dummy or 
global object cannot be used as the right hand side of any assignment to 
a variable of derived type with pointer components, for then it, or part 
of it, might be the target of a pointer assignment, in violation of the 
restriction mentioned above.

(Incidentally, the last two paragraphs only prevent the reference of 
a dummy or global object as the {\em only\/} object on the right hand
side of a pointer assignment or an assignment to a variable with pointer
components.  There are no constraints on its reference as an operand, 
actual argument, subscript expression, etc.\ in these circumstances).

Finally, a dummy or global data object cannot be used in a procedure 
reference as an actual argument associated with a dummy argument of
INTENT (OUT) or (INOUT) or with a dummy pointer, for then it may be
modified by the procedure reference.  
This constraint, like the others, can be statically checked, since any
procedure referenced within a pure function must be either a pure 
function, which does not modify its arguments, or a pure subroutine, 
whose interface must specify the INTENT or POINTER attributes of its 
arguments (see below).
Incidentally, notice that in this context it is assumed that an actual 
argument associated with a dummy pointer is modified, since Fortran~90 
does not allow its intent to be specified.

Constraint 4 ensures that all procedures called from a pure function 
are themselves pure and hence side effect free, except, in the case of
subroutines, for modifying actual arguments associated with dummy pointers 
or dummy arguments with INTENT(OUT) or (INOUT).  As we have just 
explained, it can be checked that global or dummy objects are not used
in such arguments, which would violate the required side-effect freedom.

Constraints 5 and 6 protect dummy and global data objects from realignment 
and redistribution (another type of side effect).  
In addition, constraint 5 prevents explicit declaration of the mapping 
(i.e.\ alignment and distribution) of dummy arguments and local variables.  
This is because the function may be invoked concurrently, with each 
invocation operating on a segment of data whose distribution is specific 
to that invocation.  Thus, the distribution of a dummy object must be 
`assumed' from the corresponding actual argument.  
Also, it is left to the implementation to determine a suitable mapping 
of the local variables, which would typically depend on the mapping of 
the dummy arguments.

Constraint 7 prevents I/O, whose order would be non-deterministic in 
the context of concurrent execution.  A PAUSE statement requires input
and so is disallowed for the same reason.

\subsubsection{Pure subroutine definition}

To define pure subroutines, Rule~R1219 is changed to:
                                                                 \BNF
subroutine-subprogram \IS       subroutine-stmt
                                [pure-directive]
                                [specification-part]
                                [execution-part]
                                [internal-subprogram-part]
                                end-subroutine-stmt
                                                                \FNB
with the following additional constraints in Section~12.5.2.3 of the 
Fortran~90 standard:
\begin{constraints}

        \item If a {\it procedure-name\/} is present in the 
{\it pure-directive\/}, it must match the {\it sub\-rou\-tine-name\/} in the 
{\it subroutine-stmt\/}.

        \item The {\it specification-part\/} of a pure subroutine must 
specify the intents of all non-pointer and non-procedure dummy arguments.

        \item In a pure subroutine, a local variable must not have the 
SAVE attribute. (Note that this means they cannot be initialised in a 
{\it type-declaration-stmt\/} or a {\it data-stmt\/}.)

        \item A pure subroutine must not use a dummy parameter with 
        INTENT(IN), a global variable, or an 
object that is storage associated with a global variable, or a subobject 
thereof, in the following contexts:
        \begin{itemize}
                \item as the assignment variable of an {\it assignment-stmt\/}
or {\it forall-assignment\/};
                \item as a DO variable or implied DO variable, or as a 
{\it subscript-name\/} in a {\it forall-triplet-spec\/;
                \item in an {\it assign-stmt\/};
                \item as the {\it pointer-object\/} or {\it target\/}
of a {\it pointer-assignment-stmt\/};
                \item as the {\it expr\/} of an {\it assignment-stmt\/}
or {\it forall-assignment\/} whose assignment variable is of a derived 
type, or is a pointer to a derived type, that has a pointer component 
at any level of component selection;
                \item as an {\it allocate-object\/} or {\it stat-variable\/}
in an {\it allocate-stmt\/} or {\it deallocate-stmt\/}, or as a
{\it pointer-object\/} in a {\it nullify-stmt\/};
                \item as an actual argument associated with a dummy 
argument with INTENT (OUT) or (INOUT) or with the POINTER attribute.
        \end{itemize}

        \item Any procedure referenced in a pure subroutine, including
one referenced via a defined operation or assignment, must be pure.

        \item In a pure subroutine, a dummy argument or local variable 
must not appear in an {\it align-directive\/}, {\it realign-directive\/},
{\it distribute-directive\/}, {\it redistribute-directive\/},
{\it realignable-directive\/}, {\it redistributable-directive\/} or
{\it combined-directive}.

        \item In a pure subroutine, a global variable must not appear in
{\it realign-directive\/} or {\it redistribute-directive\/}.

        \item A pure subroutine must not contain a {\it pause-stmt\/},
{\it stop-stmt\/} or I/O statement (including a file operation).

\end{constraints}
To declare that a subroutine is pure, a {\it pure-directive\/} must be
given.

The constraints for pure subroutines are based on the same principles 
as for pure functions, except that now side effects to dummy arguments 
are permitted.  

\subsubsection{Pure procedure interfaces}
\label{pure-proc-interface}

To define interface specifications for pure procedures, Rule~R1204 is 
changed to:
                                                                \BNF
interface-body \IS      function-stmt
                        [pure-directive]
                        [specification-part]
                        end-function-stmt
                \OR     subroutine-stmt
                        [pure-directive]
                        [specification-part]
                        end-subroutine-stmt
                                                                \FNB
with the following constraint in addition to those in
Section~12.3.2.1 of the Fortran~90 standard:
\begin{constraints}

        \item An {\it interface-body\/} of a pure subroutine must specify
the intents of all non-pointer and non-procedure dummy arguments.

\end{constraints}

The procedure characteristics defined by an interface body must be
consistent with the procedure's definition.
Regarding pure procedures, this is interpreted as follows:
\begin{enumerate}
        \item A procedure that is declared pure at its definition may be
declared pure in an interface block, but this is not required.
        \item A procedure that is not declared pure at its definition must 
not be declared pure in an interface block.
\end{enumerate}
That is, 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.

\subsection{Pure procedure reference}
To define pure procedure references, the following extra constraint is 
added to Section~12.4.1 of the Fortran~90 standard:
\begin{constraints}

        \item In a reference to a pure procedure, a {\it procedure-name\/} 
{\it actual-arg\/} must be the name of a pure procedure.

\end{constraints}

\section{INDEPENDENT Procedures}

An {\it independent procedure} is one that all its instantiations can be
executed independently on each other and the results are deterministic. 
This means that an INDEPENDENT function 
may have an access to global data passed to it as arguments with explicit
intent IN and it returns scalar variables to be assigned to global arrays
in a FORALL statement or construct.

An INDEPENDENT procedure (i.e. function or subroutine) may be used only in
FORALL statement or construct.

An INDEPENDENT procedure must have explicit interface, and it must be defined
to be INDEPENDENT in both its definition and interface. The form of this 
declaration is a directive 
                                                                     \BNF
independent-directive  \IS   INDEPENDENT function-name
                                                                     \FNB

\subsubsection{Independent function definition}

To define independent functions, Rule~R1215 of the Fortran~90 standard is 
changed to:
                                                                 \BNF
function-subprogram \IS         function-stmt
                                [independent-directive]
                                [specification-part]
                                [execution-part]
                                [internal-subprogram-part]
                                end-function-stmt
                                                                \FNB
with the following additional constraints in Section~12.5.2.2 of the 
Fortran~90 standard:
\begin{constraints}
        \item If a {\it procedure-name\/} is present in the 
{\it independent-directive\/}, it must match the {\it function-name\/} 
in the {\it function-stmt\/}.

        \item In an independent function, a local variable must not have 
the SAVE attribute. (Note that this means they cannot be initialised in a 
{\it type-declaration-stmt\/} or a {\it data-stmt\/}.)

        \item The {\it specification-part\/} of a independent function must 
specify the intents of all non-pointer and non-procedure dummy arguments.

        \item In an independent function, only {\it scalar variables} are
allowed with intent OUT.  

        \item An independent function must not contain assignments to
global data objects.

        \item Any procedure referenced in an independent function, including
one referenced via a defined operation or assignment, must be independent
or pure.

        \item In an independent function, a dummy argument or local 
variable must not appear in an {\it align-directive\/}, 
{\it realign-directive\/},
{\it distribute-directive\/}, {\it redistribute-directive\/},
{\it realignable-directive\/}, {\it redistributable-directive\/} or
{\it combined-directive}.

        \item In a independent function, a global variable must not appear in
{\it realign-directive\/} or {\it redistribute-directive\/}.

        \item A independent function must not contain a {\it pause-stmt\/},
{\it stop-stmt\/} or I/O statement (including a file operation).

\end{constraints}

To declare that a function is independent, a {\it indepenendent-directive\/} 
must be given.

\subsubsection{independent subroutine definition}

To define independent subroutines, Rule~R1219 is changed to:
                                                                 \BNF
subroutine-subprogram \IS       subroutine-stmt
                                [independent-directive]
                                [specification-part]
                                [execution-part]
                                [inrnal-subprogram-part]
                                end-subroutine-stmt
                                                                \FNB
with the following additional constraints in Section~12.5.2.3 of the 
Fortran~90 standard:
\begin{constraints}

        \item If a {\it procedure-name\/} is present in the 
{\it independent-directive\/}, it must match the {\it sub\-rou\-tine-name\/} 
in the {\it subroutine-stmt\/}.

        \item In an independent subroutine, a local variable must not have 
the SAVE attribute. (Note that this means they cannot be initialised in a 
{\it type-declaration-stmt\/} or a {\it data-stmt\/}.)

        \item The {\it specification-part\/} of a pure subroutine must 
specify the intents of all non-pointer and non-procedure dummy arguments.

        \item In an independent subroutine, all subscripts defined in
{\it forall-triplet-list} must be passed to that as arguments with explicit
intent IN.

        \item In an independent subroutine, only {\it scalar variables} are
allowed with intent OUT.  

        \item An independent subroutine must not cointain assignments to
global data objects.

        \item Any procedure referenced in an independent subroutine, including
one referenced via a defined operation or assignment, must be independent
or pure.

        \item In an independent subroutine, a dummy argument or local 
variable must not appear in an {\it align-directive\/}, 
{\it realign-directive\/},
{\it distribute-directive\/}, {\it redistribute-directive\/},
{\it realignable-directive\/}, {\it redistributable-directive\/} or
{\it combined-directive}.

        \item In an independent subroutine, a global variable must not appear
in {\it realign-directive\/} or {\it redistribute-directive\/}.

        \item An independent subroutine must not contain a {\it pause-stmt\/},
{\it stop-stmt\/} or I/O statement (including a file operation).

\end{constraints}
To declare that a subroutine is independent, a {\it independent-directive\/} 
must be given.

\subsubsection{independent procedure interfaces}
\label{independent-proc-interface}

To define interface specifications for independent procedures, Rule~R1204 is 
changed to:
                                                                \BNF
interface-body \IS      function-stmt
                        [independent-directive]
                        [specification-part]
                        end-function-stmt
                \OR     subroutine-stmt
                        [independent-directive]
                        [specification-part]
                        end-subroutine-stmt
                                                                \FNB
with the following constraint in addition to those in
Section~12.3.2.1 of the Fortran~90 standard:
\begin{constraints}

        \item An {\it interface-body\/} of an independent subroutine must 
specify the intents of all non-pointer and non-procedure dummy arguments.

\end{constraints}

The procedure characteristics defined by an interface body must be
consistent with the procedure's definition.
Regarding independent procedures, this is interpreted as follows:
\begin{enumerate}
        \item A procedure that is declared independent at its definition 
may be declared independent in an interface block, but this is not required.
        \item A procedure that is not declared independent at its definition 
must not be declared independent in an interface block.
\end{enumerate}
That is, if an interface body contains a {\it independent-directive\/}, then 
the corresponding procedure definition must also contain it, though the 
reverse is not true. When a procedure definition with an 
{\it independent-directive\/}
is compiled, the compiler may check that it satisfies the necessary 
constraints.

\subsection{Independent procedure reference}
To define independent procedure references, the following extra constraint is 
added to Section~12.4.1 of the Fortran~90 standard:
\begin{constraints}

        \item In a reference to an independent procedure, a 
{\it procedure-name\/}  {\it actual-arg\/} must be the name of an
independent  procedure.

\end{constraints}

\section{LOCAL Procedures}
A {\it local procedure} is one that operate on global variables aligned to a 
single template element or local variables. 

A LOCAL procedure (i.e. function or subroutine) may be used only in FORALL
statement or construct.

A LOCAL procedure must have explicit interface, and it must be defined to be
LOCAL in both its definition and interface. The form of this declaration is
a directive 
                                                                     \BNF
local-directive  \IS   LOCAL function-name
                                                                     \FNB

\subsubsection{Local function definition}

To define local functions, Rule~R1215 of the Fortran~90 standard is 
changed to:
                                                                 \BNF
function-subprogram \IS         function-stmt
                                [local-directive]
                                [specification-part]
                                [execution-part]
                                [internal-subprogram-part]
                                end-function-stmt
                                                                \FNB
with the following additional constraints in Section~12.5.2.2 of the 
Fortran~90 standard:
\begin{constraints}
        \item If a {\it procedure-name\/} is present in the 
{\it local-directive\/}, it must match the {\it function-name\/} 
in the {\it function-stmt\/}.

        \item In an local function, a local variable must not have 
the SAVE attribute. (Note that this means they cannot be initialised in a 
{\it type-declaration-stmt\/} or a {\it data-stmt\/}.)

        \item The {\it specification-part\/} of a local function must 
specify the intents of all non-pointer and non-procedure dummy arguments.

        \item Replicated global data are not allowed as arguments.

        \item All global variables passed as arguments to a local function
must be alligned to the same template both in the calling procedure and
the called function, and the distribution of the global variables must
be the same as in calling procedure. 

        \item Indices of the template pointing which element of the template 
is to be used by an invocation of the local function must be passed as an 
argument with explicit intent IN.

        \item A local function must not access global data objects which
are not aligned to the template element owned by the invovation of the
function.

        \item Any procedure referenced in a local function, including
one referenced via a defined operation or assignment, must be local.

        \item In a local function, a dummy argument or local 
variable must not appear in an {\it align-directive\/}, 
{\it realign-directive\/},
{\it distribute-directive\/}, {\it redistribute-directive\/},
{\it realignable-directive\/}, {\it redistributable-directive\/} or
{\it combined-directive}.

        \item In a local function, a global variable must not appear in
{\it realign-directive\/} or {\it redistribute-directive\/}.

        \item A local function must not contain a {\it pause-stmt\/},
{\it stop-stmt\/} or I/O statement (including a file operation).

\end{constraints}

To declare that a function is local, a {\it indepenendent-directive\/} 
must be given.

\subsubsection{local subroutine definition}

To define local subroutines, Rule~R1219 is changed to:
                                                                 \BNF
subroutine-subprogram \IS       subroutine-stmt
                                [local-directive]
                                [specification-part]
                                [execution-part]
                                [internal-subprogram-part]
                                end-subroutine-stmt
                                                                \FNB
with the following additional constraints in Section~12.5.2.3 of the 
Fortran~90 standard:
\begin{constraints}

        \item If a {\it procedure-name\/} is present in the 
{\it local-directive\/}, it must match the {\it sub\-rou\-tine-name\/} 
in the {\it subroutine-stmt\/}.

        \item In an local subroutine, a local variable must not have 
the SAVE attribute. (Note that this means they cannot be initialised in a 
{\it type-declaration-stmt\/} or a {\it data-stmt\/}.)

        \item The {\it specification-part\/} of a local subroutine must 
specify the intents of all non-pointer and non-procedure dummy arguments.

        \item In an local subroutine, all subscripts defined in
{\it forall-triplet-list} must be passed to that as arguments with explicit
intent IN.

        \item Replicated global data are not allowed as arguments.

        \item all global variables passed as arguments to a local function
must be alligned to the same template both in the calling procedure and
and called function, and the distribution of the global variables must
be the same as in calling procedure. 

        \item indices of the template pointing which element of the template is
owned by an invocation of the function must be passed as an argument with
explicit intent IN.

        \item A local function must not access global data objects which
are not aligned to the template element owned by the invovation of the
function.

        \item In a local subroutine, a dummy argument or local 
variable must not appear in an {\it align-directive\/}, 
{\it realign-directive\/},
{\it distribute-directive\/}, {\it redistribute-directive\/},
{\it realignable-directive\/}, {\it redistributable-directive\/} or
{\it combined-directive}.

        \item In a local subroutine, a global variable must not appear
in {\it realign-directive\/} or {\it redistribute-directive\/}.

        \item A local subroutine must not contain a {\it pause-stmt\/},
{\it stop-stmt\/} or I/O statement (including a file operation).

\end{constraints}
To declare that a subroutine is local, a {\it local-directive\/} 
must be given.

\subsubsection{local procedure interfaces}
\label{local-proc-interface}

To define interface specifications for local procedures, Rule~R1204 is 
changed to:
                                                                \BNF
interface-body \IS      function-stmt
                        [local-directive]
                        [specification-part]
                        end-function-stmt
                \OR     subroutine-stmt
                        [local-directive]
                        [specification-part]
                        end-subroutine-stmt
                                                                \FNB
with the following constraint in addition to those in
Section~12.3.2.1 of the Fortran~90 standard:
\begin{constraints}

        \item An {\it interface-body\/} of an local subroutine must 
specify the intents of all non-pointer and non-procedure dummy arguments.

\end{constraints}

The procedure characteristics defined by an interface body must be
consistent with the procedure's definition.
Regarding local procedures, this is interpreted as follows:
\begin{enumerate}
        \item A procedure that is declared local at its definition 
may be declared local in an interface block, but this is not required.
        \item A procedure that is not declared local at its definition 
must not be declared local in an interface block.
\end{enumerate}
That is, if an interface body contains a {\it local-directive\/}, then 
the corresponding procedure definition must also contain it, though the 
reverse is not true. When a procedure definition with an 
{\it local-directive\/}
is compiled, the compiler may check that it satisfies the necessary 
constraints.

\subsection{Local procedure reference}
To define local procedure references, the following extra constraint is 
added to Section~12.4.1 of the Fortran~90 standard:
\begin{constraints}

        \item In a reference to an local procedure, a 
{\it procedure-name\/}  {\it actual-arg\/} must be the name of an
local  procedure.

\end{constraints}

\section{Element Array Assignment - FORALL}
\label{forall-stmt}

\footnote{Version of September 21, 1992 - David
Loveman, Digital Equipment Corporation and Charles Koelbel, Rice
University.
Approved at second reading on September 10, 1992. It is extended by allowing
independent or local subroutine calls in a FORALL body}
The element array
assignment statement (FORALL statement) is used to specify an array
assignment in terms of array elements or groups of 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
                     \OR CALL independent-subroutine-subprogram
                     \OR CALL local-subroutine-subprogram
                                                                       \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}.

\noindent Constraint\footnote{this constraint superseed that present in the
original FORALL proposal}: procedure reference (~Rule1209) allowed in 
{\it expr} (~Rule723 and ~Rule701) must be {\it pure-function-reference},
{\it independent-procedure-reference} or {\it local-procedure-reference}.
\noindent
Constraint\footnote{this constraint is an extension to the original FORALL
proposal}: When an independent or local subroutine is called in a FORALL
statement, all subsripts defined in {\it forall-triplet-spec-list} must be
passed to that subroutine as arguments with explicit intend IN.

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, ..., \lfloor \frac{m2 - m1 +
1}{m3} \rfloor  \]
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 
\(\lfloor (m2 -m1 + 1) / m3 \rfloor \leq 0\), the {\it
forall-assignment} is not executed.

\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}.
The assignments may be made in any order.
In the case of a pointer assignment where the {\it target} is not a 
pointer, this assignment consists of associatin 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.

\footnote{this is a modification of the original FORALL proposal}
PURE, INDEPENDENT and LOCAL procedures allowed in a FORALL statement does not
affect other expressions' evaluations, either for the same combination of
{\it subscript-name} values or for a different combination. In addition, it
is possible that the compiler can perform more extensive optimizations when
all function are declared PURE, INDEPENDENT or LOCAL.

\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 ) &
      forall-assignment
                                                                   \EDOC
and if the {\it forall-assignment} has a form
                                                                   \CODE     
      a(e1,...,em) = rhs
                                                                   \EDOC

\noindent
then it is equivalent to the following standard Fortran 90 code:

\raggedbottom
                                                                   \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
\flushbottom
and if the {\it forall-assignment} has a form
                                                                   \CODE     
      CALL independent-subroutine(e1,...,em,A1,...,Ap, &
         B1(e1,...,em),...,Bq(e1,...,em))
  where 
      A1,...,Ap are arguments with intent IN
      B1(e1,...,em),...,Bq(e1,...,em) are scalar arguments with intent OUT

                                                                   \EDOC

\noindent
then it is equivalent to the following standard Fortran 90 code:

\raggedbottom
                                                                   \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 call the subroutine in the forall-assignment for all valid 
!combinations of subscript names for which the scalar mask  

DO v1=templ1,tempu1,temps1
  DO v2=tel2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        IF (tempmask(v1,v2,...,vn)) THEN
          call subroutine(v1,v2,...,vn,A1,...,Ap,  &
              1(v1,v2,...,vn),...,tempq(v1,v2,...,vn))
        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
          B1(e1,...,em) = temp1(v1,v2,...,vn)
          ...
          Bq(e1,...,em) = tempq(v1,v2,...,vn)
        END IF
      END DO
          ...
  END DO
END DO
                                                                      \EDOC
\flushbottom
Finally, if the {\it forall-assignment} has a form
                                                                   \CODE     
      CALL local-subroutine(e1,...,em,A1,...,Ap,B1,...,Bq)
  where 
      A1,...,Ap are arguments with intent IN
      B1(e1,...,em),...,Bq(e1,...,em) are arguments with intent OUT
                                                                   \EDOC

\noindent
then it is equivalent to the following standard Fortran 90 code:

\raggedbottom
                                                                   \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 call the subroutine in the forall-assignment for all valid 
!combinations of subscript names for which the scalar mask  

DO v1=templ1,tempu1,temps1
  DO v2=tel2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        IF (tempmask(v1,v2,...,vn)) THEN
          call subroutine(v1,v2,...,vn,A1,...,Ap,B1,...,Bq)
        END IF
      END DO
          ...
  END DO
END DO

                                                                      \EDOC
\flushbottom

\section{FORALL Construct}

\label{forall-construct}

\footnote{Version of August 20, 1992 -
David Loveman, Digital Equipment Corporation and 
Charles Koelbel, Rice University.  Approved at second reading on
September 10, 1992. It is modified by introducing ELSEFORALL in place of
WHERE and/or WHERE-ELSEWHERE constructs within FORALL body}
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}.

\subsection{General Form of the FORALL Construct}

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

forall-body-stmt     \IS forall-assignment
                     \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, ..., \lfloor \frac{m2 - m1 +
1)}{m3} \rfloor  \]
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 
\(\lfloor (m2 -m1 + 1) / m3 \rfloor \leq 0\), the {\it
forall-assignment}s are not  executed.

\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.
One set of active combinations of {\it subscript-name} values is the 
subset of the valid combinations for which the mask evaluates to true and
a second one is the subset of the valid combinations for which the mask
evaluates to false.

\item Execute the first {\it forall-body-stmts} in the order they appear for
the first set of the valid combination of {\it subscript-name}.
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, pointer 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 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}

\item Execute the second {\it forall-body-stmts} for the second set of active
{\it subscript-name} the same way as in 3.

\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.
Different statements may, however, assign to the 
same array element, and assignments made in one
statement may affect the execution of a later statement.

\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 {\it forall-construct} of the form:

                                                                \CODE
FORALL ( v=l:u:s, mask )
    a(l:u:s) = rhs1 
ELSEFORALL
    a(l:u:s) = rhs2
END FORALL
                                                                \EDOC

is equivalent to the following standard Fortran 90 code:

                                                                \CODE
!evaluate subscript and stride expressions in any order

templ = l
tempu = u
temps = s

!then evaluate the FORALL mask expression

DO v=templ,tempu,temps
 tempmask(v) = mask
END DO

!then evaluate the masks 

DO v1=templ,tempu,temps
    tempmask(v) = mask(v)
  END IF
END DO

!then evaluate the first block of statements

DO v=templ,tempu,temps
  IF (tempmask(v)) THEN
      temprhs1(v) = rhs1
  END IF
END DO
DO v1=templ,tempu,temps
  IF (tempmask(v)) THEN
   a(v)=temprhs1(v)  
  END IF
END DO

!then evaluate the second block of statements

DO v=templ,tempu,temps
  IF (not.tempmask(v)) THEN
      temprhs2(v) = rhs2
  END IF
END DO
DO v1=templ,tempu,temps
  IF (.not.tempmask(v)) THEN
   a(v)=temprhs2(v)
  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

\section{Pure Procedures and Elemental Reference}
\footnote{Version of October 14, 
1992 - John Merlin, University of Southampton, 
and Charles Koelbel, Rice University. Approved at first reading on
September 10, 1992, subject to technical revisions for correctness.
The suggestions made there have been incorporated in this draft.}
\subsubsection{Elemental reference of pure functions}

A non-intrinsic pure function may be referenced {\em elementally\/} 
in array expressions, with a similar interpretation to the elemental
reference of Fortran~90 elemental intrinsic functions, provided it
satisfies the additional constraints that:
\begin{enumerate}
        \item Its non-procedure dummy arguments and dummy result are 
scalar and do not have the POINTER attribute.
        \item The length of any character dummy argument or result is 
independent of argument values (though it may be assumed, or depend on the 
lengths of other character arguments and/or a character result).
\end{enumerate}
We call non-intrinsic pure functions that satisfy these constraints 
`elemental non-intrinsic functions'.

The interpretation of an elemental reference of such a function is as 
follows (adapted from Section 12.4.3 of the Fortran~90 standard):
\begin{quotation}

A reference to an elemental non-intrinsic function is an elemental
reference if one or more non-procedure actual arguments are arrays
and all array arguments have the same shape.  If any actual argument 
is a function, its result must have the same shape as that of the 
corresponding function dummy procedure.  A reference to an elemental 
intrinsic function is an elemental reference if one or more actual 
arguments are arrays and all arrays have the same shape.

The result of such a reference has the same shape as the array arguments,
and the value of each element of the result, if any, is obtained by 
evaluating the function using the scalar and procedure arguments and
the corresponding elements of the array arguments.  The elements of
the result may be evaluated in any order.

For example, if \verb@foo@ is a pure function with the following interface:
                                                \CODE
    INTERFACE
      REAL FUNCTION foo (x, y, z, dummy_func)
        !HPF$ PURE foo
        REAL, INTENT(IN) :: x, y, z
        INTERFACE        ! interface for 'dummy_func'
          REAL FUNCTION dummy_func (x)
            !HPF$ PURE dummy_func
            REAL, INTENT(IN) :: x
          END FUNCTION my_func
        END INTERFACE
      END FUNCTION foo
    END INTERFACE
                                                \EDOC
and \verb@a@ and \verb@b@ are arrays of shape \verb@(m,n)@ and \verb@sin@
is the Fortran~90 elemental intrinsic function, then:
                                                \CODE
    foo (a, 0.0, b, sin)
                                                \EDOC
is an array expression of shape \verb@(m,n)@ whose \verb@(i,j)@ element
has the value:
                                                \CODE
    foo (a(i,j), 0.0, b(i,j), sin)
                                                \EDOC
\end{quotation}

To define elemental references of elemental non-intrinsic functions, 
the following extra constraints are added after Rule~R1209 
({\it function-reference\/}):
\begin{constraints}

        \item A non-intrinsic function that is referenced elementally 
must be a pure function with an explicit interface, and must satisfy 
the following additional constraints:
        \begin{itemize}
                \item Its non-procedure dummy arguments and dummy result
must be scalar and must not have the POINTER attribute.
                \item The length of any character dummy argument or a 
character dummy result must not depend on argument values (though it may 
be assumed, or depend on the lengths of other character arguments and/or a 
character result).
        \end{itemize}

        \item In an elemental reference of a non-intrinsic function,
a {\it function-name\/} {\it actual-arg\/} must have a result whose shape 
agrees with that of the corresponding function dummy procedure.

\end{constraints}

The reasons for these constraints are explained in the next section.

\subsubsection{Elemental reference of pure subroutines}

A non-intrinsic pure subroutine may be referenced {\em elementally\/}, 
with a similar interpretation to the elemental reference of Fortran~90 
elemental intrinsic subroutines, provided it satisfies the additional 
constraints that:
\begin{enumerate}
        \item Its non-procedure dummy arguments are scalar and do not 
have the POINTER attribute.
        \item The length of any character dummy argument is independent 
of argument values (though it may be assumed, or depend on the lengths of 
other character arguments).
\end{enumerate}
We call non-intrinsic pure subroutines that satisfy these constraints 
`elemental non-intrinsic subroutines'.

The interpretation of an elemental reference of such a subroutine 
is as follows (adapted from Section 12.4.5 of the Fortran~90 standard):
\begin{quotation}

A reference to an elemental non-intrinsic subroutine is an elemental
reference if all actual arguments corresponding to INTENT(OUT) and
INTENT(INOUT) dummy arguments are arrays that have the same shape 
and the remaining non-procedure actual arguments are conformable with 
them.  If any actual argument is a function, its result must have the 
same shape as that of the corresponding function dummy procedure.
A reference to an elemental intrinsic subroutine is an elemental 
reference if all actual arguments corresponding to INTENT(OUT) and 
(INTENT(INOUT) dummy arguments are arrays that have the same shape and 
the remaining actual arguments are conformable with them.

The values of the elements of the arrays that correspond to INTENT(OUT)
and INTENT(INOUT) dummy arguments are the same as if the subroutine were 
invoked separately, in any order, using the scalar and procedure arguments 
and corresponding elements of the array arguments.

\end{quotation}

To define elemental references of elemental non-intrinsic subroutines, 
the following constraints are added after Rule~R1210 ({\it call-stmt\/}):
\begin{constraints}

        \item A non-intrinsic subroutine that is referenced elementally 
must be a pure subroutine with an explicit interface, and must satisfy 
the following additional constraints:
        \begin{itemize}
                \item Its non-procedure dummy arguments must be scalar 
and must not have the POINTER attribute.
                \item The length of any character dummy argument must 
not depend on argument values (though it may be assumed, or depend on 
the lengths of other character arguments).
        \end{itemize}

        \item In an elemental reference of a non-intrinsic subroutine,
a {\it function-name\/} {\it actual-arg\/} must have a result whose shape 
agrees with that of the corresponding function dummy procedure.

\end{constraints}

It is perhaps worth outlining the reasons for the extra constraints 
imposed on pure procedures in order for them to be referenced elementally.  

The dummy result of a function or `output' arguments of a subroutine
are not allowed to have the POINTER attribute because of a Fortran~90
technicality, namely, that under elemental reference the corresponding 
actual arguments must be array variables, and Fortran~90 does not permit 
an array of pointers to be referenced.\footnote{
        See the final constraint after Rule~R613 of the Fortran~90 standard.
Note the difference between an {\em array of pointers\/}, which cannot 
be declared or referenced in Fortran~90, and a {\em pointer array\/},
which can.
}
The `input' arguments of an elemental reference are prohibited from 
having the POINTER attribute for consistency with the output arguments 
or result.  However, this last constraint does not impose 
any real restrictions on an elemental reference, as the corresponding 
actual arguments {\em can\/} be pointers, in which case they are 
`de-referenced' and their tats are associated with the dummy arguments.  
In fact, the only reason for a dummy argument to be a pointer is so that
its pointer association can be changed, which is not allowed for `input'
arguments.  (Incidentally, since a pure function has only `input' 
arguments, there would be no loss of generality in disallowing dummy 
pointers in pure functions generally.)  Note that the prohibition of 
dummy pointers in pure subroutines that are elementally referenced means 
that all their non-procedure dummy arguments can have their intent 
explicitly specified (and indeed this is required by the constraints for 
pure subroutine interfaces---see Section \ref{pure-proc-interface}) which 
assists the checking of argument usage.

In an elemental reference, any actual argument that is a function
must have a result whose shape agrees with that of the corresponding 
function dummy procedure.  That is, elemental usage does not extend to 
function arguments, as Fortran~90 does not support the concept of an `array' 
of functions.
Naively it might appear that a function actual argument that is associated 
with a scalar dummy function could return an array result provided it 
conforms with the other array arguments of the elemental reference.  
However, this is not meaningful under elemental reference, as an 
array-valued function cannot be decomposed into an `array' of scalar 
function references, as would be required in this context.

Finally, the length of any character dummy argument or a character
dummy result cannot depend on argument {\em values\/} (though it can
be assumed, or depend on the lengths of other character arguments and/or
a character result).  This ensures that under elemental reference, all 
elements of an array argument or result of character type will have the 
same length, as required by Fortran~90.

\end{document}