Subject: Comments on last-but-one FORALL proposal!

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

I originally posted this (comments on the previous FORALL proposal
by David Loveman and Chuck Koelbel) on jJuly 21, which by dint
of bad timing was too late for people to read before the last HPF
meeting.  

While some of the comments have become obsolete with the new proposal, 
many still apply, so I've taken the liberty of posting it again in 
advance of the next meeting.  If you've recently read it and can 
remember its contents, or don't want to remember its contents, 
please ignore it.

-- John Merlin.
---------------------------------------------------------------------
Let me start with an obvious and uncontroversial observation: 
that a FORALL statement without a mask is like a generalised array 
assignment, and a FORALL with a mask is like a generalised masked
array assignment (i.e. WHERE statement).  Every array assignment, 
masked or not, can be written as a FORALL, and (I would maintain) 
sufficiently restricted FORALL statements should be expressible as 
array assignments or WHERE statements.  I think it's a good idea to 
keep this duality in mind and try to maintain it wherever possible.  
I mention this as it underlies some of my comments.

(1)   With Chuck's limitations on the contents of a FORALL construct,
this correspondence extends to FORALL constructs, which are equivalent
to a sequence of generalised array assignments or a WHERE construct.
I think that's a good reason for the limitations!

Incidentally, this correspondence leads to my first observation:
since Fortran 90 has a WHERE - ELSEWHERE construct, perhaps the 
FORALL construct should be extended to a FORALL - ELSEFORALL construct.  
(Of course, the ELSE FORALL part is only relevant if the FORALL has a mask; 
if not, the ELSE FORALL isn't executed).

(2)  The only restrictions I can see on the use of 'subscript-name's
in the LHS of a forall assignment are that every subscript name must 
be referenced, and that no array element must be assigned a value more 
than once.  Do you really want to keep it this general?

For example, can more than one subscript name appear in a single 
subscript expression?  E.g.:

	FORALL (i=1:n:2, j=0:1)  a(i+j) = ...

Can a subscript name appear in a subscript triplet?  E.g.:

	FORALL (i=1:n:2)  a(i:i+1) = ...

(Perhaps the correspondence with array assignments suggests that 
no more than one subscript name should appear in each subscript expression 
of the assignment variable, and that subscript names should not appear in a 
subscript triplet).

I assume that a subscript name can be used in more than one dimension
of the assignment variable (e.g. FORALL (i=1:n) b(i,i) ...), as you give 
an example of this, but perhaps it should be explicitly stated.

(3)  The use of the WHERE statement and construct within a FORALL
seems redundant, as the FORALL construct is already a generalised 
WHERE construct!  Everything you can express with an embedded WHERE 
can be expressed without it by scalarising the sectional dimensions 
and absorbing the mask in the forall-stmt.  My objection is that it
opens up multiple ways of expressing the same thing (which is already 
a big flaw with Fortran).  E.g. if A is 2 dimensional,

	WHERE (a > 0)  a = ...

can be written as:

	FORALL (i=1:n)
	  WHERE (a(i,:) > 0)  a(i,:) = ...
or:

	FORALL (i=1:n, j=1:n, a(i,j)>0)  a(i,j) = ...

or even as:

	FORALL (i=1:n, j=1:n)
	  WHERE (a(i:i, j:j) > 0)  a(i:i, j:j) = ...

etc.

In contrast to Arthur Veen, I'd advocate dropping the nested WHERE 
stmt and construct in FORALL in favour of the scalar mask expression in the 
forall-stmt, as the latter can express more general masks (as you've already
said in your reply).

I suppose an advantage with having a WHERE construct within a FORALL 
construct is that you can then have an ELSEWHERE part.  However, this
would be unnecessary if the FORALL construct had an optional ELSE FORALL, 
as I've already suggested.

A minor aesthetic argument against WHERE in FORALL is that Fortran 90 
doesn't allow nested WHERE constructs (for whatever reason), 
so it seems inconsistent to allow them to be nested within FORALL, 
which effectively amounts to the same thing.

Also, WHERE introduces a small inconsistency in FORALLs, namely, that
a normal 'forall-assignment' can be array valued and can have any shape,
but within the WHERE the shape is no longer free--it must conform 
with that of the WHERE mask expression.

(4) In a similar vein, nested FORALL's seem redundant.  It appears
that the main reason for using them is to obtain non-rectangular
index domains.  If so, why not just allow this to be achieved in a 
single 'forall-triplet-spec-list' and have done with it (i.e. allow
each forall-triplet to refer to previous subscript names, as
permitted in some other proposals).  Are there any advantages
in using nested FORALLs to achieve this effect?

Note that I'm not strongly against nested WHERE and FORALL---it's
just my gut reaction that they're superfluous, and I suspect it may 
be the reaction of users too.

<<< N.B. The following stuff in particular may not be so relevant
to the new proposal. >>>

Far more important is the consideration of how functions are handled 
within FORALL.  Basically, your proposal imposes no more constraints 
than already exist in Fortran 90, namely that there should be no side 
effects that affect the evaluation of the rest of the assignment 
(here extended to cover forall-assignment).
I can see the obvious attraction of this approach, but I believe it's 
inadequate for a number of reasons:

(i) You allow arbitrary access (read and write) to distributed 
global (i.e. common block) data, which in the FORALL context requires 
demand-driven communication for it's implementation.  This probably
poses no problems on shared memory architectures, but would require 
considerable software support on many distributed-memory message-passing 
platforms, with a big performance overhead.  I don't think this
requirement appears anywhere else in HPF, and I'm not convinced
that all vendors/implementors would want to support it (as it wouldn't
be High Performance).  If not, HPF programs would be *non-portable*.

>>> Extra comment: This isn't the whole extent of the problem.
>>> What if a FORALL function is just invoked once on a single process,
>>> but internally it declares distributed local variables.  Using any
>>> type of distributed data within functions callable in FORALL seems
>>> to be a minefield.

(ii) Your constraints permit non-determinism (e.g. multiple writes 
to the same global memory location, provided it's not read within 
the same assignment; non-deterministic I/O).
However, it seems that Fortran 90 tries assiduously to avoid 
non-determinism in its array syntax (right now, I can't think of any 
way it can arise via array syntax in standard-conforming programs---but 
I may have overlooked something!).  Also, apart from function calls, you 
extend this principle to FORALLs by not allowing multiple writes to the 
same element of a forall-assignment variable.

(i) & (ii) raise the spectres of non-portability, deadlock and non-determinism,
which appear nowhere else in HPF (as far as I can see).
For these reasons I think functions in FORALL shouldn't be allowed
to perform I/O, and access to global data should be restricted to read-only
access of non-distributed data.  (In fact, perhaps they shouldn't access
global data at all---it can always be passed-in as an argument).

(iii) I'd like to stick to my guns on the proposal that such functions
should be denoted by a directive like:

>>> N.B. Refs to 'elemental' in the original message have been replaced
>>> by 'pure' here, in line with the new proposal.

	!HPF$ PURE function-name

appearing in the function's interface and definition.
This would greatly simplify the job of checking these functions, as well
as making their characteristics and purpose obvious to programmers.

The simplification of checking resulting from this directive is fairly
obvious.  With the directive, checking can be done locally when the
function is compiled; if it calls other functions, they too must be 
'pure', which is established by the presence or absence of the directive 
in the function's interface body.  Without the directive, it appears 
that a preliminary pass thought the whole input program must be performed 
to establish whether each function is or is not 'pure', with backpatching 
required to fill in information when a function calls other functions, 
before the usage of any function in a FORALL can be checked.  Also, what 
about separate compilation?

I believe that checking is particularly desirable in the case of 'pure'
functions, for incorrect usage could result in deadlock, which can be 
very difficult for the user to track down.

                    Regards,
                         John Merlin.