From: "Marc Snir" <[email-masked]>
Date: Tue, 16 Jun 92 22:23:48 EDT

%forall.tex
%Snir
\documentstyle[11pt]{article}
\pagestyle{plain}
\pagenumbering{arabic}
\marginparwidth 0pt
\oddsidemargin  .25in
\evensidemargin  .25in
\marginparsep 0pt
\topmargin   -.5in
\textwidth 6in
\textheight  9.0in

\title{Proposal for FORALL}
\author{Marc Snir}
%\date{   }

\begin{document}

\maketitle

\section{Overview}

This document expands on the proposals of Dave Loveman and Guy Steele for a
FORALL statement.  The definition of a single statement FORALL is taken,
almost verbatim, from Dave's proposal.  A new definition is given for block
FORALL.

\section{Single Statement FORALL}

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

\subsubsection{General Form of single statement FORALL}

\begin{verbatim}
forall-stmt          is FORALL (forall-triplet-spec-list [ ,scalar-mask-expr ])
                          forall-assignment

forall-triplet-spec  is subscript-name = subscript : subscript [ : stride]
\end{verbatim}

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

Examples of element array assignments are:

\begin{verbatim}
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)
\end{verbatim}

\subsubsection{Interpretation of Single Statement FORALL}
\label{forall-single-interpret}
\begin{enumerate}
\item
The subscript and stride expressions in the {\it
forall-triplet-spec-list} are evaluated in any order.
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)  \]

\noindent
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 set of permitted values is empty.
The {\it Iteration Set} for the FORALL construct is
the Cartesian product of the set of permitted values for each subscript.

\item
The scalar mask is evaluated for each combination of subscript values in
the Iteration Set, in any order.   The Iteration Set is restricted to those
combinations of values for which the mask evaluates to true.
If the scalar mask expresion is omitted, it is as if it were
present with the value true.

\item
The rhs expr
in the {\it forall-assignment} is evaluated for each combination of subscript
values in the Iteration Set, in any order.

\item
The computed values are assigned
to the corresponding elements of the array being assigned
to.
\end{enumerate}

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 the
subscript name is the FORALL statement itself.

\noindent
Constraint:  The evaluation of a {\it subscript} or a {\it stride} in a {\it
forall-triplet-spec} must not affect of be affected by the evaluation of any
other {\it subscript} or {\it stride}.

\noindent
Constraint:  The evaluation of the {\it scalar-mask-expression} for one
combination of subscript names
may not affect or be affected by the evaluation
of the {\it scalar-mask-expression} for another combination, nor can it
redefine any subscript name.

\noindent
Constraint:  The evaluation of the right-hand-side expression for
one combination of subscript names
may not affect or be affected by the evaluation
of the expression for another combination,
nor can it redefine any subscript name.

\subsubsection{Scalarization of the FORALL Statement}

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

\begin{verbatim}
FORALL (v1=l1:u1:s1, v2=l1:u2:s2, ..., vn=ln:un:sn [, mask] ) &
      a(e1,...,em) = rhs
\end{verbatim}

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

\begin{verbatim}
!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
!(and lhs subscripts)
!for all valid combinations of subscript names
!for which the scalar mask expression is true
DO v1=templ1,tempu1,temps1
  DO v2=templ2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        IF (tempmask(v1,v2,...,vn)) THEN
          !in any order
          tempe1(v1,v2,...,vn) = e1
            ...
          tempem(v1,v2,...,vn) = em
          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(tempe1(v1,v2,...,vn),...,tempem(v1,v2,...,vn)) = temprhs(v1,v2,...,vn)
        END IF
      END DO
          ...
  END DO
END DO
\end{verbatim}

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

\end{itemize}

\section{General FORALL Construct}

The FORALL construct is a generalization of the element array
assignment statement allowing multiple {\it forall-assignment}s to be
controlled by a single {\it forall-triplet-spec-list}.  The body of a
FORALL construct is an arbitrary sequence of executable constructs, possibly
including FORALL assignments.

The execution of a FORALL construct starts with the evaluation of the {\it
forall-triplet-spec-list} and {\it scalar-mask-expr}.
This yields the set of subscript values that binds each {\it
forall-assignment}
in the {\it forall-body}.  The constructs in the {\it forall-body} are then
executed sequentially.
When a {\it forall-assignment} is encountered then the assignment is
executed for all
combinations of combinations of subscript values defined by the {\it
forall-triplet-spec-list} and {\it scalar-mask-expr}.

Rule R215 for {\it executable-constructs} is extended to include the
{\it forall-construct}.

\subsection{Block FORALL}

\begin{verbatim}
forall-stmt          is FORALL (forall-triplet-spec-list [ ,scalar-mask-expr ])
                          forall-block
                        END FORALL

forall-triplet-spec  is subscript-name = subscript : subscript [ : stride]
\end{verbatim}

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

A {\it forall-block} can be an arbitrary sequence of executable constructs,
treated as a unit (R801).  It can also contain {forall-assignment}'s.

\begin{verbatim}
forall-assignment    is array-element = expr
                     or array-section = expr
\end{verbatim}

\noindent
Constraint: No statement in a {\it forall-block}, other than the
{\it forall-assignment}'s, may reference any of the {\it
forall-triplet-spec subscript-names}.

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

Examples of the Block FORALL construct are:

\begin{verbatim}

FORALL(I=1:N)
   B(I,I) = 1
   DO J = 1, N
      A(I,J) = A(I,J-1) + A(I,J)
   END DO
END FORALL

FORALL(I=1:N, J=1:N, I.NE.J)
   IF(COND)
      THEN A(I,J) = I+J
      ELSE A(I,J) = I-J
   END IF
END FORALL
\end{verbatim}

\subsubsection{Interpretation of the Block FORALL Construct}

\begin{enumerate}
\item
An Iteration Set is computed, as described in
section~\ref{forall-single-interpret}.

\item
The {\it block-forall} is evaluated sequentially.  Whenever a
{\it forall-assignment} is encountered, then the assignment is executed
for the FORALL Iteration Set, as defined in
section~\ref{forall-single-interpret}.
\end{enumerate}

The evaluation of the {\it forall-triplet-spec-list} and {\it
scalar-mask-exp} and the separate evaluation of each {\it forall-assignment}
fulfils the constraints listed in section~\ref{forall-single-interpret}.

\subsubsection{Scalarization of the Block FORALL Statement}

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

\begin{verbatim}
FORALL (v1=l1:u1:s1, v2=l1:u2:s2, ..., vn=ln:un:sn [, mask] ) &
      s1
      s2
      ...
      sn
END FORALL
\end{verbatim}

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

\begin{verbatim}
!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 body
S1
S2
...
Sn

\end{verbatim}

If {\tt si} is a {\it forall-assignment} of the form {\tt a(e1,...,em)=rhs}
then {\tt Si} is the code

\begin{verbatim}
DO v1=templ1,tempu1,temps1
  DO v2=templ2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        IF (tempmask(v1,v2,...,vn)) THEN
          !in any order
          tempe1(v1,v2,...,vn) = e1
            ...
          tempem(v1,v2,...,vn) = em
          temprhs(v1,v2,...,vn) = rhs
        END IF
      END DO
          ...
  END DO
END DO
DO v1=templ1,tempu1,temps1
  DO v2=templ2,tempu2,temps2
    ...
      DO vn=templn,tempun,tempsn
        IF (tempmask(v1,v2,...,vn)) THEN
          a(tempe1(v1,v2,...,vn),...,tempem(v1,v2,...,vn)) = temprhs(v1,v2,...,vn)
        END IF
      END DO
          ...
  END DO
END DO
\end{verbatim}

If {\tt si} is not a {\it forall-assignment} then {\tt Si=si}

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

Each construct in a block FORALL, including
{\it forall-asignment}s, may depend on preceeding constructs, including
{\it forall-assignment}s, and on the evaluation of the
{\it forall-triplet-spec-list} and the {\it mask-scalar-expr}.

\subsection{WHERE-ELSEWHERE statement}

\begin{verbatim}
forall-where-construct   is WHERE ( scalar-mask-expr )
                                [ forall-block ]
                             [ ELSEWHERE
                                 [ forall-block ] ]
                             END WHERE
\end{verbatim}

The {\it scalar-mask-expr} may use (but not modify) the forall subscripts.

\subsubsection{Interpretation of the WHERE Construct}

\begin{enumerate}
\item
The {\it scalar-mask-expr} is
evaluated for each combination of values in the Iteration Set, in arbitrary
order.
\item
The
WHERE {\it forall-block} is executed, with the Iteration Set restricted to those
combinations of
values for which the {\it scalar-mask-expr} is true.
\item
The ELSEWHERE {\it forall-block} is executed, with the Iteration Set restricted
to those combinations of values for which the {\it scalar-mask-expr} is false.
\end{enumerate}

Each construct within the scope of a WHERE (or ELSEWHERE) may depend on the
evaluation of the {\it scalar-mask-expr} in the WHERE statement.

A construct within the ELSEWHERE {\it forall-block} may depend on constructs on
the WHERE {\it forall-block}.   (This is somewhat strange, but consistent with
Fortran 90 semantics for WHERE.)

Example \\
The following program will zero array {\tt A(1:N)} ({\tt N} even).

\begin{verbatim}

FORALL(I=1:N)
   WHERE(MOD(I,2)=0)
       A(I) = 0
   ELSEWHERE
       A(I) = A(I-1)
    END WHERE
END FORALL

\end{verbatim}
\subsection{Nested FORALL}

FORALL constructs may be nested.  The Iteration Set for {\it forall-assignment}s
inside nested FORALLs is the direct product of the Iteration Set defined by each
FORALL.

\subsection{General Form of the FORALL Statement}

\begin{verbatim}
forall-stmt           is FORALL (forall-triplet-spec-list [ ,scalar-mask-expr ])
                              forall-block
                         END FORALL

forall-triplet-spec     is subscript-name = subscript : subscript [ : stride]

forall-block            is forall-construct
                            [forall-block]

forall-construct        is executable-construct
                        or forall-stmt
                        or forall-where-construct

forall-where-construct  is WHERE ( scalar-mask-expr )
                                [ forall-block ]
                             [ ELSEWHERE
                                 [ forall-block ] ]
                            END WHERE
\end{verbatim}

\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: A {\it subscript-name} that occurs in a {\it
forall-triplet-spec-list} may be referenced inside the scope of the FORALL
statement only by the {\it scalar-mask-expr} of a FORALL or WHERE statement or
in an assignment of the form  {\tt array-element = expr} or
{\tt array-section = expr}.  A {\it subscript-name} may not be redefined
inside the scope of the FORALL. \\

Example \\

\begin{verbatim}

FORALL(I=1:N)
   WHERE(A(I).NE.0)
       A(I) =A(I)/ABS(A(I))
   END WHERE
   FORALL(J=1:N, J.NE.I)
       B(I,J) = A(I) + A(J)
   A(I) = SUM(B(I,1:N))
END FORALL

\end{verbatim}

\end{document}

---

From: [email-masked]
Date: Fri, 19 Jun 92 17:10:21 -0500

> Date: Tue, 16 Jun 92 22:23:48 EDT
> From: "Marc Snir" <[email-masked]>
> To: [email-masked]
> Status: RO

First off, congratulations on getting a technical document out of the
IBM mail domain :-)

> the Cartesian product of the set of permitted values for each subscript.

Issue: This description makes it impossible to create a triangular
FORALL.  For example, I can easily imagine someone wanting to say

	FORALL ( I = 1:N, J = 1:I ) A(I,J) = 0.0

(zero out the lower triangle of an array).  You can get the desired
effect by using a mask expression, but that's inelegant (and I suspect
inefficient on most implementations).  Or you can use the INDEPENDENT
directive in a DO loop.

Questions: Are triangular loops important enough to include them as
FORALLs?  Will triangular FORALLs put an undue burden on the compiler
writers?

As this restriction appears on the CMFortran FORALL, perhaps the TMC
people can comment on whether users miss triangular loops.

The other interpretation steps look OK to me.

> forall-triplet-spec} must not affect of be affected by the evaluation of any
                                       ^^ "or" not "of" (nitpick!)
> combination of subscript names
                           ^^^^^
> redefine any subscript name.

Shouldn't this be "values"?  The expression will always reference the
same names, i.e. variables.

The "name" at the end is used corectly.

> one combination of subscript names
                               ^^^^^ "values" again, I argue
> nor can it redefine any subscript name.

Don't we need two more constraints?

Constraint: The evaluation of an array subscript on the left-hand side for
one combination of subscript values may not affect nor be affected by
the evaluation of any right-hand-side expression, nor may it redefine
any subscript name.

Constraint: The evaluation of an array subscript on the left-hand side for
one combination of subscript values may not affect nor be affected by
the evaluation of any left-hand side subscript for any other
combination of subscript values.

(Marc's / Dave's constraint rules out RHS-RHS interference, but not
RHS-LHS or LHS-LHS interference.)

> scalar mask expression is true.

Another consequence worth noting:
Expressions on the right-hand side are evaluated only for combinations
of subscript values for which the mask is true.

Side issue:
Is anyone else confused by "subscript" meaning both "FORALL index" and
"subscript expression"?  Can anyone suggest a beter name?

> forall-assignment} must reference all of the {\it forall-triplet-spec

I think this is opening a very nasty can of worms.

Worm 1:
The BNF and text need to be fixed to state that only forall-assignment
is allowed in a forall-body.  (I assume this is what Marc means - if
not, then
	A(I) = B(i+1)
can be interpreted as either a regular assignment or a
forall-assignment, which apparently have different meanings (in the
scalarization, only forall-assignments are transformed).  Or, going
the other way,
	X = X + A(I)
is allowed in a forall-body, since it is syntactically not a
forall-assignment but otherwise a legal Fortran statement.)  

Worm 2:
Sort of a generalization on the last point - the grammar and
scalarization you give later don't seem to treat nested constructs
correctly.  Note that 
	IF ( SOME_CONDITION(N) ) THEN
	    A(I) = 1
	ELSE
	    A(I) = 1
	ENDIF
is, according to the Fortran 90 standard, one statement (which happens
to contain two other statements).  The statement 

> If {\tt si} is not a {\it forall-assignment} then {\tt Si=si}

(in the scalarization part) needs to explicitly rewrite any nested
statements.  Similar changes are required throughout the remaining
sections.

Worm 3:
The principle of least astonishment may need invocation here.  One
interesting consequence of Marc's proposal is that this is legal:
	FORALL ( I = 1:N )
	  IF ( N > 1 ) THEN
	    A(I) = 1.0
	  END IF
	END FORALL
but this is not legal:
	FORALL ( I = 1:N )
	  IF ( N > I ) THEN
	    A(I) = 1.0
	  END IF
	END FORALL
(Look carefully at the IF condition...  Marc does not allow the FORALL
index to be referenced in any statement except forall-assignments.)
The intent (I assume) is to force all iterations, and thus all
processors, down the same path at all branch points, and that sure
makes FORALL easier to define.  But it will make some useful
computations difficult to code:
	Iterating to convergence on each point of a grid
	Conditional assignment to points on a grid
	Having different formulas for different grid points
	Guy Steele's ragged array example (ALLOCATE different-sized blocks)
	Nested triangular loops or triangular FORALLs
	Boundary conditions
(Some of these limitations are solved by the WHERE construct.)
Question for users: Are you willing to live with these restrictions?

Worm 4:
If the statements in the forall-block can be arbitrary, we have to
define semantics for
	FORALL ( I = 1:N )
	    CALL FOO( A )	! How many times is FOO called?
				! Scalarization says 1, users will say N
	    OPEN(5,FILE='BAR')	! Parallel I/O, here we come
	    READ (5) B(1:100)
	    			! READ (5) B(I) is illegal, though
	    WRITE (5) C(1:5)
	    			! WRITE (5) C(I) is illegal
	    CLOSE (5)
	END FORALL
(Interestingly, I don't see any trouble from GOTO or STOP, since all
iterations must follow the same control flow.)  There may be other
problematic Fortran statements.

Worm 5:
Inlining a function or procedure may do quite unexpected things to its
meaning.  Of course, every other proposal has had this feature, and as
Guy pointed out "It's not fair to expect that inlining will be easy in
a language not designed for it."

Worm 6:
No other nested construct puts any restrictions on the statements
within its body, except for DO loops not allowing their index
variables to be redefined.  I argue that FORALLs (or other new
constructs) should not restrict their bodies either without good
reason.

Overall, I think the proposal went too far in generalizing the FORALL.
I'll make the following modest (and informal) counterproposal:
	Only "generalized assignment statements" (GASes) are allowed
	in a FORALL body.
	The following statements are GASes - assignment, WHERE,
	FORALL.
	Use Marc's semantics for interpreting GASes (no object
	assigned twice by one statement, assignments executed once for
	each element of the index space, GASes executed in sequence).
	I think that Marc's proposal still disallows triangular
	FORALLs; I propose lifting this restriction.
If there's interest, I'll write this up more formally.

	Chuck