Subject: FORALL proposal

From: [email-masked]
Date: Fri, 17 Jul 1992 18:08:27 -0600

\documentstyle{article}

\oddsidemargin=0.25in
\textwidth=6.0in
\topmargin=-1in
\textheight=9in
\parindent=1em

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\catcode`\$=11  \catcode`\%=11

\makeatother

\begin{document}

\title{Proposal for FORALL in High Performance Fortran}
\author{David Loveman and Charles Koelbel}

\maketitle

\section{Overview}

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

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

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

\section{Element Array Assignment - FORALL}  

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

\subsection{General Form of Element Array Assignment}

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

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

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

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

\begin{verbatim}
forall-assignment    \IS array-element = expr
                     \OR array-section = expr
\end{verbatim}

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

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

Examples of element array assignments are:
                                                                  \CODE
FORALL (I=1:N, J=1:N) H(I,J) = 1.0 / REAL(I + J - 1)
FORALL (I=1:N, J=1:N, A(I,J) .NE. 0.0) B(I,J) = 1.0 / A(I,J)
                                                                  \EDOC 

\subsection{Interpretation of Element Array Assignments}  

Execution of an element array assignment consists of the following steps:
\begin{enumerate}
\item Evaluation in any order of the subscript and stride expressions in 
the {\it forall-triplet-spec-list}.
The set of valid combinations of {\it subscript-name} values is then the 
cartesian product of the sets defined by these triplets.
\item Evaluation of the {\it scalar-mask-expr} for all valid combinations 
of {\em subscript-name} values.
The 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} 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.
\item Assignment of the computed {\it expr} values to the corresponding 
elements specified by {\it array-element} or {\it array-section}.
\end{enumerate}
If the scalar mask expresion is omitted, it is as if it were
present with the value true.

The {\it forall-assignment} must not cause any element of the array
being assigned to be assigned a value more than once.  The scope of a
{\it subscript-name} is the FORALL statement itself. 
The evaluation of the {\it expr} for a particular active combination of {\it 
subscript-name} values may neither affect nor be affected by 
the evaluation of {\it expr} for any other combination of {\it 
subscript-name} values.
In particular, functions cannot produce side effects that are visible in 
the FORALL.
The evaluation of the {\it expr} or any subscript on the left-hand side 
of the {\it forall-assignment} for any active combination of {\it 
subscript-name} values may not affect 
nor be affected by 
the evaluation of any subscript in the {\it forall-assignment}, either 
for the same 
combination of {\it subscript-name} values or a different active combination.
In particular, a function reference
appearing in any expression in the {\it forall-assignment} must not
redefine any subscript name.

\subsection{Scalarization of the FORALL Statement}

A {\it forall-stmt} of the general form:
                                                                   \CODE
FORALL (v1=l1:u1:s1, v2=l1:u2:s2, ..., vn=ln:un:sn , mask ) &
      a(e1,...,em) = rhs
                                                                   \EDOC
is equivalent to the following standard Fortran 90 code:
                                                                    \CODE
!evaluate subscript and stride expressions in any order
templ1 = l1
tempu1 = u1
temps1 = s1
templ2 = l2
tempu2 = u2
temps2 = s2
  ...
templn = ln
tempun = un
tempsn = sn

!then evaluate the scalar mask expression
DO v1=templ1,tempu1,temps1
  DO v2=templ2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        tempmask(v1,v2,...,vn) = mask
      END DO
	  ...
  END DO
END DO

!then evaluate the expr in the forall-assignment 
!for all valid combinations of subscript names 
!for which the scalar mask expression is true
!(it is safe to avoid saving the subscript expressions
!because of the conditions on FORALL expressions)
DO v1=templ1,tempu1,temps1
  DO v2=templ2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        IF (tempmask(v1,v2,...,vn)) THEN
          temprhs(v1,v2,...,vn) = rhs
        END IF
      END DO
	  ...
  END DO
END DO

!then perform the assignment of these values to 
!the corresponding elements of the array being assigned to
DO v1=templ1,tempu1,temps1
  DO v2=templ2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        IF (tempmask(v1,v2,...,vn)) THEN
          a(e1,...,em) = temprhs(v1,v2,...,vn)
        END IF
      END DO
	  ...
  END DO
END DO
                                                                      \EDOC

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

\begin{itemize}

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

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

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

\item The evaluation of expressions within {\it array-element} or {\it
array-section} must neither affect nor be affected by the evaluation of 
{\it expr}.

\item The evaluations of right-hand-side expressions in different FORALL 
instances (iterations) must not affect each other through side-effects.

\end{itemize}

\section{FORALL Construct}

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

\subsubsection{General Form of the FORALL Construct}

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

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

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

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

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

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

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

Examples of the FORALL construct are:
                                                                 \CODE
FORALL ( i = 2:n-1, j = 2:i-1 )
  a(i,j) = a(i,j-1) + a(i,j+1) + a(i-1,j) + a(i+1,j)
  b(i,j) = a(i,j)
END FORALL

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

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

\subsection{Interpretation of the FORALL Construct}  

Execution of 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 set of active combinations of {\it subscript-name} values is the 
subset of the valid combinations for which the mask evaluates to true.
\item Execute the {\it forall-body-stmts} in the order they appear.
Each statement is executed completely (that is, for all active 
combinations of {\it subscript-name} values) according to the following 
interpretation:
\begin{enumerate}
\item Assignment statements and array assignment statements (i.e. 
statements in the {\it forall-assignment} category) evaluate the 
right-hand side {\it expr} and any left-and side subscripts for all 
active {\it subscript-name} values,
then assign those results to the corresponding left-hand side references.
\item WHERE statements evaluate their {\it mask-expr} for all active 
combinations of {\it subscript-name} values.
The assignments within the WHERE branch of the statement are then 
executed in order using the above interpretation of array assignments 
within the FORALL, but the only array elements assigned are those 
selected by both the active {\it subscript-names} and the WHERE mask.
Finally, the assignments in the ELSEWHERE branch are executed if that 
branch is present.
The assignments here are also treated as array assignments, but elements 
are only assigned if they are selected by both the active combinations 
and by the negation of the WHERE mask.
\item FORALL statements and FORALL constructs first evaluate the 
subscript and stride expressions in 
the {\it forall-triplet-spec-list} for all active combinations of the 
outer FORALL constructs.
The set of valid combinations of {\it subscript-names} for the inner 
FORALL is then the union of the sets defined by these bounds and strides 
for each active combination of the outer {\it subscript-names}.
For example, the valid set of the inner FORALL in the second example in 
the last section is the upper triangle (not including the main diagonal) 
of the \(n \times n\) matrix a.
The scalar mask expression is then evaluated for all valid combinations 
of the inner FORALL's {\it subscript-names} to produce the set of active 
combinations.
If there is no scalar mask expression, it is assumed to be always true.
Each statement in the inner FORALL is then executed for each valid 
combination (of the inner FORALL), recursively following the 
interpretations given in this section.
\end{enumerate}
\end{enumerate}
If the scalar mask expresion is omitted, it is as if it were
present with the value true.

A single statement in a {\it forall-construct} must not cause any element 
of the array
being assigned to be assigned a value more than once.
It is, however, permitted that different statements may assign to the 
same array element.
The scope of a
{\it subscript-name} is the FORALL construct itself. 
The evaluation of any subexpression of an assignment or array 
assignment for a particular 
active combination of {\it subscript-name} values may neither affect nor be
affected by 
the evaluation any subexpression in the same statement for any other 
combination of {\it subscript-name} values.
Similarly, evaluation of the mask or subscript bounds and stride 
expressions in an inner WHERE or FORALL for one active combination of 
{\it subscript-name} values may not affect nor be affected by the 
evaluations of those subexpressions for any other active combination.
The evaluation of any subexpression in an assignment or array assignment 
for any active combination of {\it subscript-name} values may not affect 
nor be affected by 
the evaluation of any subscript in the same statement, either 
for the same 
combination of {\it subscript-name} values or a different active combination.
In particular, a function reference
appearing in any expression in the {\it forall-assignment} must not
redefine any subscript name.

\subsection{Scalarization of the FORALL Construct}

A {\it forall-construct} of the form:
                                                                \CODE
FORALL (... e1 ... e2 ... en ...)
    s1
    s2
     ...
    sn
END FORALL
                                                                \CODE
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
                                                                \CODE
A similar statement can be made using FORALL constructs when some of the 
si are WHERE or FORALL constructs.

A {\it forall-construct} of the form:
                                                                   \CODE
FORALL ( v1=l1:u1:s1, mask )
  WHERE ( mask2(l2:u2) )
    a(vi,l2:u2) = rhs1
  ELSEWHERE
    a(vi,l2:u2) = rhs2
  END WHERE
END FORALL
                                                                   \EDOC
is equivalent to the following standard Fortran 90 code:
                                                                    \CODE
!evaluate subscript and stride expressions in any order
templ1 = l1
tempu1 = u1
temps1 = s1

!then evaluate the FORALL mask expression
DO v1=templ1,tempu1,temps1
 tempmask(v1) = mask
END DO

!then evaluate the masks for the WHERE
DO v1=templ1,tempu1,temps1
  tmpl2(v1) = l2
  tmpu2(v1) = u2
  IF (tempmask(v1)) THEN
    tempmask2(v1,tmpl2(v1):tmpu2(v1)) = mask2(tmpl2(v1):tmpu2(v1))
  END IF
END DO

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

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

A {\it forall-construct} of the form:
                                                                   \CODE
FORALL ( v1=l1:u1:s1, mask )
  FORALL ( v2=l2:u2:s2, mask2 )
    a(e1,e2) = rhs1
	b(e3,e4) = rhs2
  END FORALL
END FORALL
                                                                   \EDOC
is equivalent to the following standard Fortran 90 code:
                                                                    \CODE
!evaluate subscript and stride expressions in any order
templ1 = l1
tempu1 = u1
temps1 = s1
!then evaluate the FORALL mask expression
DO v1=templ1,tempu1,temps1
 tempmask(v1) = mask
END DO

!then evaluate the inner FORALL bounds, etc
DO v1=templ1,tempu1,temps1
  IF (tempmask(v1)) THEN
    templ2(v1) = l2
    tempu2(v1) = u2
    temps2(v1) = s2
	DO v2 = templ2(v1),tempu2(v1),temps2(v1)
      tempmask2(v1,v2) = mask2
	END DO
  END IF
END DO

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

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

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

\begin{itemize}

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

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

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

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

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

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

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

\end{itemize}

\end{document}

---

From: [email-masked] (Arthur Veen)
Date: Sun, 19 Jul 92 12:23:12 +0200

A few remarks concerning Chuck's latest FORALL proposal
posted 17 Jul 1992 18:08:27

A - If HPF is going to extend the base language (I prefer that
    it doesn't), I would like to have one extension rather
    than two, i.e. EITHER the forall-stmt OR the forall-construct
	but not both.
	As far as I can tell, the only convenience the forall-stmt
	gives above the forall-construct is that you can leave out 
	"END FORALL".

B - If A is adopted and the choice is made to include
    forall-construct and to leave out forall-stmt, the proposal
	can be further simplified by leaving out the scalar-mask-expr.
	As far as I can tell masks do not give any expressiveness above
	the where-stmt.

C - There appears to be a contradiction in section 3.1

	> It is, however, permitted that different statements may assign to the

	However, "A single statement in a {\it forall-construct}" may be
	a inner forall-construct, which may assign to the same array
	element more than once.
	I think the intention is that for any level of a (possibly
	nested) forall-construct, *different* valid combinations of
	subscript-name values may not assign to the *same* array
	element.

	A separate question about these "must not"s and "may not"s that
	appear in the proposal. I hope these are meant as admonishments
	to the application programmer rather than to the compiler
	writers. In other words that they mean that programs that do
	not meet these requirements may produce arbitrary results.

	> FORALL ( i = 2:n-1, j = 2:i-1 )
                                ^
	should be

	  FORALL ( i = 2:n-1, j = 2:n-1 )

	I hope

--arthur

                 Arthur H. Veen
       Parallel Computing   ACE
       Postbus 16775        van Eeghenstraat 100
       1001 RG  Amsterdam   1071 GL  Amsterdam
       The Netherlands      The Netherlands
phone: +31-20-623 3274      +31-20-664 6416
Fax:                        +31-20-675 0389
E-mail:[email-masked]    [email-masked]

---

From: [email-masked]
Date: Mon, 20 Jul 1992 09:44:07 -0600

>	gives above the forall-construct is that you can leave out 

A reasonable view.  I suspect that TMC people will disagree with
you, since they already have the forall-stmt syntax implemented.
I'll go with the majority opinion that I hear on this list and at the
HPFF meeting in DC.

>	As far as I can tell masks do not give any expressiveness above

FORALL ( i = 1:n, j =1:n,  i<j )
  a(i,j) = b(i,j)
END FORALL

This can be done using WHERE, but it requires allocating a 2D integer
array.  My feeling is that programmers still care about large data
structures.

FORALL ( i=1:n, a(i,i) .ne. 0.0 )
  a(i,i) = 1/a(i,i)
END FORALL

I don't think this can be done in place using WHERE at all.  (You can do
anything using WHERE if you copy into temporary arrays.)

>	subscript-name values may not assign to the *same* array

I intended it to mean that no assignment (i.e. the bottom level of the
nesting structure) could assign more than once.  I think this is
equivalent to Arthur's interpretation, and will try to improve the wording.

>	not meet these requirements may produce arbitrary results.

I've tried to follow the usage in the Fortran 90 standard, where "must"
and "may" refer to standard-conforming programs (at least, that's my
understanding).  Thus, they are admonitions to the programmer, or to
the compiler writer who is forbidden to implement any extensions.

>	  FORALL ( i = 2:n-1, j = 2:n-1 )

You're right, thanks for spotting that.

>E-mail:[email-masked]    [email-masked]

                                                Chuck

---

From: [email-masked] (Min-You Wu)
Date: Mon, 20 Jul 92 15:39:44 EDT

> I'll go with the majority opinion that I hear on this list and at the

I agree with Arthur.

> anything using WHERE if you copy into temporary arrays.)

However, that can be done with IF:

   IF (i<j) THEN 
     a(i,j) = b(i,j)
   END IF
 END FORALL

 FORALL ( i = 1:n )
   IF (a(i,i) .ne. 0.0) THEN 
     a(i,i) = 1/a(i,i)
   END IF
 END FORALL

Min-You

---

From: [email-masked]
Date: Tue, 21 Jul 1992 07:45:52 -0600

>   IF (a(i,i) .ne. 0.0) THEN 

But IF is not permitted in FORALL in the current draft.  Are you
proposing adding it?

                                                Chuck

---

From: [email-masked] (Min-You Wu)
Date: Tue, 21 Jul 92 10:22:00 EDT

> But IF is not permitted in FORALL in the current draft.  Are you

Yes, I do.  In my INDEPENDENT proposal, I proposed allowing IF-THEN-ELSE
in the independent block, and IF-THEN in the non-independent block.
The reason of allowing only IF-THEN in the non-independent block is that
I do not want dependence carrying out from the THEN part to the ELSE part.

Min-You

---

From: [email-masked]
Date: Tue, 21 Jul 1992 09:44:26 -0600

>I do not want dependence carrying out from the THEN part to the ELSE part.

My impression was that consensus was to only allow assignment, array
assignment, WHERE, and FORALL nested within FORALL.  Certainly that was the
way the straw poll went a few weeks back (in fact, the poll might have
thrown out WHERE as well).  Does anybody want to support Min-You's
proposal?

I am firmly opposed to allowing different constructs inside independent
blocks as opposed to outside them.  This implies that a directive is
changing the syntax of the language (a rather more visible problem than
changing the semantics, which we're trying to avoid).

                                                Chuck

---

From: [email-masked] (Min-You Wu)
Date: Tue, 21 Jul 92 11:52:56 EDT

> changing the semantics, which we're trying to avoid).

The INDEPENDENT directive could have two features:

1). Let the compiler know that there is no dependence in the independent
block and no synchronization needed.

2). Allowing almost any Fortran construct in independent blocks.  That
will give users flexibility to write whatever they want for their application
problems.

I'd like to know if we want both 1) and 2) , or to limit INDEPENDENT 
directives to 1) ?  And if we want both features, should we use directives 
or change it to something else?

Min-You