
\section{\label{elements}The Elements of Adhoc}

     Most of this section deals with ``Vanilla Adhoc''.  This abstracts
away various details of distribution format which are important in
HPF.  A more pragmatic distributed version is described in section
\ref{distribAdhoc}.  That version incorporates the same semantic ideas
as the ``vanilla'' language, and adds information on distribution
formats.

\subsection{Process Arrays}

     The HPF declaration
\begin{verbatim}
!HPF$ PROCESSORS P (10, 10)
\end{verbatim}
introduces a 10 by 10 arrangment of virtual processors, over which
program data can be distributed.  In Adhoc the role of the HPF
processor arrangement is taken by the {\em process array}.

     An Adhoc process array has a set of process dimensions.  In
Vanilla Adhoc---unlike HPF---process dimensions are unsized.  A more
important difference from HPF is that process arrays are initially
declared {\em without} dimensions; dimensions are attached by
subsequent declarations.  In the fragment
\begin{verbatim}
  procs p ;
  dimension p_1 of p ;
  dimension p_2 of p ;
\end{verbatim}
a process array \verb$p$ is declared, then two dimensions of this array
are declared, and named \verb$p_1$ and \verb$p_2$.  This fragment can
be regarded as the translation of the single HPF statement above.

     In the example above \verb$p_1$ and \verb$p_2$ exist as long as
\verb$p$ does.  In general though a process dimension may have a more
restricted scope than the process array it belongs to; a dimension can
appear and subsequently disappear during the course of program
execution.  This flexibility is needed because in Adhoc {\em every}
dimension of a data array\footnote{Subsequently data array dimensions
will nearly always be referred to as {\em ranges}, rather than
``dimensions'', to distinguish them from process dimensions.} is
associated with some process dimension.  So if we want to declare a
rank 3 array within some scope, and distribute it over \verb$p$, we
first have to attach a new dimension to \verb$p$.

     Given the need such a mechanism, the purist approach is to
use it the initial creation of multi-dimensional process arrays, as
well as for creation of temporary dimensions (in the less pure
{\em distributed} version of Adhoc, process arrays {\em are} declared
with an initial set of dimensions; dimensions attached subsequently are
associated with collapsed, on-processor mappings).

\subsection{Ranges}

     A central idea of Adhoc is the {\em range}.  There is no
completely analogous object in HPF.  A range is a one-dimensional index
space.  A range of extent $n$ has the values $0 \ldots n - 1$
associated with it.  The range also associates a process mapping with
the elements of this index space; to this extent it resembles the HPF
template, which also defines a mapping from an index space into
distributed processor memories\footnote{The exact correspondence is
between a {\em primitive} range and an HPF template {\em dimension}.}.

     Suppose \verb$p_1$ is a (process) dimension.  Then
\begin{verbatim}
  20 # p_1
\end{verbatim}
is a {\em primitive range} of extent 20.  This range is ``distributed
over'' \verb$p_1$.  It can be named in a declaration:
\begin{verbatim}
  range x(20 # p_1) ;
\end{verbatim}
then referred to as \verb$x$.

     There is another kind of a range---the {\em derived range}.  First
we introduce the Adhoc version of a ``triplet''---this looks slightly
different to a Fortran triplet.  The Adhoc triplet is characterised by
an extent rather than an upper bound.  For example
\begin{verbatim}
  3 : base 2 step 5
\end{verbatim}
represent the index values $2, 7, 12$.  The \verb$base$ and \verb$step$
clauses are optional and default to 0 and 1 respectively, so
\begin{verbatim}
  3 : base 2
\end{verbatim}
represents $2, 3, 4$,
\begin{verbatim}
  3 : step 5
\end{verbatim}
represents $0, 5, 10$, and
\begin{verbatim}
  3 :
\end{verbatim}
represents $0, 1, 2$.  Using these triplets we can derive various
ranges from \verb$x$:
\begin{verbatim}
  3 : base 2 step 2 : x
  3 : base 2 : x
  3 : step 5 : x
  3 :: x
\end{verbatim}
These ranges all have extent 3, so they have the same index range $0,
1, 2$.  But they have different alignments to the primitive range.  For
the first of these ranges, for example, the 0 element is aligned with
the 2 element of \verb$x$, the 1 element with the 7, and the 2 element
with the 12.

     It is also allowed to derive a range from a derived range.  Any
range is characterised by the primitive range from which it is
ultimately derived, and its alignment is defined with respect to that
range.  Two derived ranges are equivalent if they have to same (extent
and) alignment, however they are derived.

     Of course a derived range can be named, as in
\begin{verbatim}
  range y(3 : base 2 step 2 : x) ;
\end{verbatim}


\subsection{Embeddings}

     An {\em embedding} is similar to a derived range, but is ``scalar''.
It is aligned with a single element of some range.  The
embedding
\begin{verbatim}
  3 : y
\end{verbatim}
is aligned to element 3 of the range \verb$x$.  An embedding can be
named in a declaration:
\begin{verbatim}
  embed e(3 : y) ;
\end{verbatim}
If \verb$y$ has primitive range \verb$x$, \verb$e$ is said to be an
embedding {\em in} \verb$x$.

     An {\em embedding set} is an unordered list of embeddings.
The following embedding sets are equivalent\footnote{The last form,
which is interpretted as a set union, is used in
conjunction with the embedding-set inquiry function to establish certain
alignments between arrays.  See section \ref{embedUnion} for an example.}
\begin{verbatim}
  {e, f, g}
  {f, g, e}
  {f, g} \/ {e}
\end{verbatim}

%Again, the primitive ranges of embeddings in an embedding set must all
%be distributed over distinct dimensions of the same process array
 
\subsection{\label{arrays}Arrays}

     A {\em range list} is an ordered list of ranges and has the syntax
\begin{verbatim}
  [x, y, z]
\end{verbatim}
(assuming \verb$x$, \verb$y$ and \verb$z$ are ranges)\footnote{It may
seem mysterious that ranges appear in ordered lists whereas embeddings
appear in unordered sets.  In the language of \cite{geometric} there
were no embeddings, but the analogues of ranges always appeared in {\em
unordered} sets, as embeddings do here.  It turns out that ordered
lists of ranges make for easier translation of Fortran; but ordered
embedding sets would be a nuisance.}.
%(An HPF template can be treated as a list of primitive
%ranges, one range for each dimension of the template.)

    An {\em array} of rank $r$ has a range list of length $r$ and,
optionally, an embedding set.  The primitive ranges of all embeddings
in the embedding set of an array, and of all ranges in its range list,
must be distributed over distinct dimensions of the same process
array.

    A rank-0 \verb$array$ with empty embedding set is formally
equivalent to a simple variable of the array-element type\footnote{Or,
perhaps more precisely, such an array can always be coerced to a simple
variable, and vice versa.}.
% THIS STATEMENT PROBABLY NEEDS MODIFYING.  REVERT TO ORIGINAL POSITION
% THAT SUCH ARRAYS ARE FORBIDDEN?

    Suppose \verb$t_1$, \verb$t_2$ and \verb$t_3$ are dimensions of some
process array.  Then we could have the following declarations
% BETTER TO HAVE SOME SIMPLER EXAMPLES FIRST
\begin{verbatim}
  range i_a(10 # t_1) ;
  range j_a(10 # t_2) ;
  array int a [i_a, j_a] ;

  range k_b(10 # t_3) ;
  embed e_b(0 : k_b) ;
  array float b {e_b} [i_a, j_a] ;

  array int c {e_b, 9 : j_a} [8 : base 1 : i_a] ;
\end{verbatim}
The arrays \verb$a$ and \verb$b$ have the same shape, but \verb$b$ is
embedded at location 0 of the range \verb$k_b$, which is distributed
over dimension \verb$t_3$.  In HPF terms, \verb$a$ would be replicated
in this process dimension.  \verb$c$ is a rank 1 array, distributed
over dimension \verb$t_1$, and embedded in dimensions \verb$t_2$ and
\verb$t_3$
\footnote{The \verb$array$ keyword distinguishes an Adhoc array from an
ordinary C array.}.

    {\em Every} dimension of an Adhoc array is associated with some
process dimension.  The effect of an HPF collapsed array dimension is
achieved by creating an extra ``temporary'' process dimension,
and aligning the array dimension to that.

     Adhoc arrays can be subscripted in a way similar, syntactically,
to Fortran.  Unlike Fortran, the result of subscription is never a
simple variable\footnote{In Vanilla Adhoc---this statement is qualified
in Distributed Adhoc.  See section \ref{distribAdhoc}}.
The signature of
\begin{verbatim}
  a [2, 3]
\end{verbatim}
is not simply \verb$int$, but
\begin{verbatim}
  array int {2 : i_a, 3 : j_a}
\end{verbatim}
A simple subscript turns an array range into an embedding.  A triplet
subscript turns a range into a derived range, in an obvious way.  It is
also legitimate to use an embedding or range as a subscript, provided
the latter is a subrange of the subscripted range of the array, and
the former is an embedding in such a range.  So the expressions
\begin{verbatim}
  b [8 : base 2 : i_a, 4 : j_a]
\end{verbatim}
and
\begin{verbatim}
  b [8 : base 2, 4]
\end{verbatim}
are equivalent; both have signature
\begin{verbatim}
  array float {4 : j_a, e_b} [8 : base 2 : i_a]
\end{verbatim}
It is convenient to allow the isolated symbol \verb$:$ as a subscript.
This works exactly as in Fortran---it stands for the whole of the
corresponding array range.

     To summarise: subscripting an array doesn't involve any remapping
(communication) of data.  It yields a new \verb$array$ object.  It {\em
does not} provide access to the data in an array.  Within Adhoc, the
data in an array can only be accessed by using the \verb$at$ or
\verb$where$ constructs described in the following sections.

     As a very convenient shorthand, a range can be used to
stand for a one-dimensional array containing its index values.
Regarded as an array, the index \verb$x$ has signature
\begin{verbatim}
  const array int [x]
\end{verbatim}
and contains the values \verb$0, ..., x.size() - 1$.
% THIS SHOULD BE REGARDED AS A PROMOTION?

\subsection{Embedding of control: \em at}

     In the preceding sections we have reinvented the HPF model of
distributed data, using a slightly different set of primitive concepts,
and a slightly different set of conventions.  In this section major
divergences from HPF start to emerge.  Adhoc permits and requires
explicit mapping of {\em control}, as well as mapping of data.

     In Adhoc, elements of an array are accessed by using \verb$at$ and
\verb$where$ constructs.  This section deals with the simpler \verb$at$
construct, used for sequential access to array elements.

     An \verb$at$ construction is built from an embedding set and a
statement (possibly compound).  The statement is executed on any
processor which would hold data with the specified embedding.  For
example, if \verb$x$ is a range
\begin{verbatim}
  array float a {3 : x} ;
  array float b [x] ;
  ...
  at({3 : x})
    a = 23 + b ;
\end{verbatim}
assigns the sum of the 23 and the fourth element of \verb$b$ to
\verb$a$.  We say that the construct {\em embeds control} in the
process dimension associated with \verb$x$.  From a type-checking point
of view, the way to think of this is that the \verb$at$ strips the
embedding from \verb$a$, and the range from \verb$b$ (focussing
attention on the element of \verb$b$ with embedding \verb$3 : x$).
Formally, an \verb$array$ without embedding or range is equivalent to a
simple variable.
% THAT STATEMENT MAY NEED RECONSIDERING.
So, within the \verb$at$, the variables \verb$a$ and
\verb$b$ behave like a simple \verb$float$ objects.  In particular
ordinary C operators like \verb$=$ and \verb$+$ can be applied to
them.

     This is the oddest feature of Adhoc.  Within \verb$at$ (and
\verb$where$) variables temporarily acquire types {\em different} from
the ones with which they were declared.  In the example above
the construct turned the arrays into simple variables.  In
general it converts them to arrays with smaller embedding sets
or range lists.  So in
\begin{verbatim}
  array float c [x, y, z] ;
  array float d [y, x, z] ;
  array float e {3 : x} [y, z] ;
  ...
  at({3 : x})
    ...
\end{verbatim}
\verb$c$, \verb$d$ and \verb$e$ all have the effective
signature
\begin{verbatim}
  array float [y, z]
\end{verbatim}
inside the \verb$at$ construct.

     The set of variables that can be referenced inside the body of a
particular \verb$at$ is restricted.  First, a definition: if an
\verb$array$ is distributed over some process array, and the process
array has a dimension which doesn't appear in any range or embedding of
the data array, the data array is {\em replicated} over that process
dimension.  By convention, a simple variable is replicated in
every dimension of every process array.  Now, consider a restricted
\verb$at$ construct with a singleton embedding set (containing only one
embedding):
\begin{verbatim}
  at({e})
    S
\end{verbatim}
An externally declared variable \verb$v$ may be references in \verb$S$
if {\em one} of the following conditions holds
\begin{enumerate}
\item
{\em outside} the \verb$at$, \verb$v$ is an array distributed over the
process array which \verb$e$ embeds in, and \verb$e$ appears in
the embedding set of \verb$v$, {\em or} \verb$v$ has a range
with an element aligned to \verb$e$.
\item
{\em outside} the \verb$at$, \verb$v$ is replicated over the process
dimension associated with \verb$e$ and, in \verb$S$, \verb$v$ {\em is
only accessed by value}.
%{\em outside} the \verb$at$, \verb$v$ is a simple variable or
%an array distributed over process array which \verb$e$ embeds in,
%and, in \verb$S$, \verb$v$ {\em is only accessed by value}, and
%\verb$e$ appears in the embedding set of \verb$v$, or \verb$v$ has a
%range with an element aligned to \verb$e$, {\em or} \verb$v$ is
%replicated over the process dimension associated with \verb$e$.
\end{enumerate}
Case 1 is illustrated by the references to \verb$a$ and \verb$b$ in the
example above: the embedding set of \verb$a$ contains the only
embedding specified by the \verb$at$; the range of \verb$b$ has an
element aligned to that embedding.  Case 2 is fairly self-explanatory.
The example above would remain legal if the 23 was replaced by the name
of a variable replicated in the dimension of \verb$x$---for example a
simple variable\footnote{From an implementation point of view, this
makes sense if replicated variables are literally stored in a
replicated fashion.  On the other hand it wouldn't make sense to {\em
assign} a simple variable inside an \verb$at$, because the replicated
copy of the variable needs to be updated everywhere, not just where the
\verb$at$ statement is executed.}.

     These rules extend to general \verb$at$ statements by
identifying
\begin{verbatim}
  at({e_1, ..., e_n})
    S
\end{verbatim}
with
\begin{verbatim}
  at({e_1})
    ...
      at({e_n})
        S
\end{verbatim}
So, for example
\begin{verbatim}
  array float a {3 : x} ;
  array float b {3 : x} [y] ;
  ...
  at({3 : x, 1 : y})
    b = a ;
\end{verbatim}
is equivalent to
\begin{verbatim}
  array float a {3 : x} ;
  array float b {3 : x} [y] ;
  ...
  at({3 : x})
    at({1 : y})
      b = a ;
\end{verbatim}

     We have described the peculiarities of array reference inside
\verb$at$.  Reference to {\em ranges} inside these constructs are
subject to analogous rules.  These rules can be inferred by regarding
an array as a one-dimensional array, as explained at the end of section
\ref{arrays}.  Suppose an \verb$at$ specifies an embedding in some
range with primitive range is \verb$x$.  Outside the construct \verb$y$
is a named range, derived from \verb$x$.  Inside the construct,
\verb$y$ can be referenced, {\em but} in that context it means a simple
integer value---the associated index value of the range.

     This regime automatically rules out nested \verb$at$s which
embed control in the same process dimension
\begin{verbatim}
  at({3 : x})
    at({1 : x})
      ...
\end{verbatim}
Inside the outer construct \verb$x$ ``becomes'' the simple integer
value 3.  It cannot be used as the target of an embedding.  This is
just as well, because it is contradictory for a statement to be
executed only at location 3 {\em and} only at location 1!

     Finally it is necessary to place restrictions on what functions
can be called inside an \verb$at$.  If the \verb$at$ embeds control in
a particular process dimension, it is illegal to call a function which
directly or indirectly references that dimension (for example, through
a global name).  Similarly, no data distributed over a process array
{\em other} than the one specified by the \verb$at$ can be accessed in
the procedure.

% [A process array declared outside an \verb$at$ or \verb$where$
% can't be accessed inside it?]


\subsection{Distribution of control: \em where}

     If \verb$at$ is like a conditional, \verb$where$ is like a loop
(the constructor names are supposed to be reminiscent of \verb$if$ and
\verb$while$).  Instead of an embedding set it takes a
range\footnote{Given that \verb$at$ specifies an embedding {\em set},
one might expect \verb$where$ to take a range {\em list}.  To translate HPF
\verb$at$ must take a set, because the size of the embedding set of
arrays (specifically dummy arguments) isn't always known statically.
To process such arrays we need a construct which takes embedding sets
of arbitrary size.  It {\em is} always known at compile time how
many ranges any array has (this number is simply the rank of the array)
so there's no practical reason why a \verb$where$ must take an
arbitrary-length list.  Translation of Adhoc is simplified if
\verb$where$ it specifies a single range.}.  The statement in the body
of a \verb$where$ construct is executed for every element of the range,
notionally in parallel (in practise the loop is split into sequential
subranges processing data local to each processor).

     The fragment
\begin{verbatim}
  where(x)
    S
\end{verbatim}
is {\em logically} equivalent to the fragment
\begin{verbatim}
  for (int i = 0 ; i < x.size() ; i++)
    at({i : x})
      S
\end{verbatim}
provided the statement \verb$S$ satisfies a set of restrictions,
required for a correct program.  The restrictions on the body of a
\verb$where$ are very similar to the ones given in the previous section
(in fact a little simpler, because the \verb$where$ specifies a single
range) and can be deduced from them through the equivalence above.
They won't be enumerated here.


\subsection{\em remap}

     None of the operations discussed so far have required
communication of data.  Adhoc has a small handful of primitives for
communication.  The simplest is \verb$remap$.  Syntactically
\verb$remap$ looks like a procedure call with two arguments.  These are
two arrays which must have the same shape, but will normally have
different mappings.  They could be distributed over different process
arrays, or they could have the same process array with differently
aligned ranges, or different embeddings.  \verb$remap$ simply copies
the values in its second argument into its first argument.

    Here is an example where the arguments of \verb$remap$ share
a process array
\begin{verbatim}
  range x(12 # t_1) ;
  array float u [x] ;
  range x_internal(10 : base 1 : x) ;
  array float n [x_internal] ;
  array float p [x_internal] ;

  ...

  for( ; ; ) {
    remap(n, u [10 : base 0]) ;
    remap(p, u [10 : base 2]) ;
    where(x_internal)
      u = 0.5 * (n + p) ;
  }
\end{verbatim}
The values in the two sections of \verb$u$ are copied into the
arrays \verb$n$ and \verb$p$.

     \verb$remap$ has a poorer cousin---\verb$broadcast$.  The first
argument of \verb$broadcast$ is a pointer to a simple C variable.  The
second argument is an \verb$array$.  If the \verb$array$ has rank 0,
it's single data item is copied to the simple variable addressed by the
first argument.  It is also reasonable to permit higher rank
\verb$array$s, in which case all data in the \verb$array$ is copied to
the simple vector pointed at by the first argument, sequenced in
some specified way.  [BUT WHAT IF THE ARRAY IS NON-CARTESIAN?.]


\subsection{{\em gather} and {\em scatter}}

     The most general communication patterns provided by Adhoc are
achieved with the primitives \verb$gather$ and \verb$scatter$.  Again
these look syntactically like procedure calls.  The first argument is
the ``gathered data''; the second argument is the ``scattered
data''---an array of rank {\em r}.  This argument is followed by {\em
r} further arguments---the subscripts.  The subscripts are arrays with
elements of type \verb$int$.

     The gathered data and the subscripts must {\em conform}, in the
following sense: if any subscript has a particular range, the gathered
data must also have that range.  Likewise, if any subscript has a
particular embedding, the scattered data must also have that
embedding.

     Note well: the {\em number} of subscript expressions is determined
by the rank of the {\em scattered data}; their {\em mapping} is
constrained by agreement with the {\em gathered data}.

     The {\em gather} operation copies data from the second argument to
the first.  The {\em scatter} operation copies data from the first
argument to the second.

     In the following example the data from square $n \times n$ array
is copied to an $n^2$ array.
\begin{verbatim}
  range x_a(n # t_1) ;
  range y_a(n # t_2) ;
  array float a [x_a, y_a] ;

  range x_b(n * n # s_1) ;
  array float b [x_b] ;

  ...

  array int subscript [x_a, y_a] ;
  where(x_a) 
    where(y_a) 
      subscript = n * x_a + y_a ;
  scatter(a, b, subscript) ;
\end{verbatim}
The scattered data is \verb$b$---a rank-1 array---so there is just
one subscript expression.  The code here is equivalent to the HPF
\begin{verbatim}
  REAL A (0 : N - 1, 0 : N - 1) DISTRIBUTE T (BLOCK, BLOCK)

  REAL B (0 : N * N - 1) DISTRIBUTE S (BLOCK)

  ...

  FORALL (X = 0 : N - 1, Y = 0 : N - 1)
    B (N * X + Y) = A (X, Y)
  END
\end{verbatim}
Replacing the \verb$scatter$ operation by a \verb$gather$ would be
equivalent to reversing the direction of the assignment in the HPF.

     Another example, with two subscripts this time.  Suppose
\verb$a$ is declared as above, then\dots
\begin{verbatim}
  array float c [x_a] ;

  ...

  gather(c, a, x_a, x_a) ;
\end{verbatim}
is equivalent to the HPF
\begin{verbatim}
  REAL C (0 : N - 1) ALIGN A ( : , *)

  ...

  FORALL (X = 0 : N - 1)
    C (X) = A (X, X)
  END
\end{verbatim}
We exploited the shorthand which allows a range to stand for a
vector---the range \verb$x_a$ is used for the two equal subscript
expressions.

     Finally, if \verb$a$ is declared as above, and $m \leq n / 2$\dots
\begin{verbatim}
  range x_d(m :: x_a) ;
  range y_d(m :: y_a) ;
  array float d [x_d, y_d] ;

  ...

  array int subscript2 [x_d, y_d] ;
  where(x_d) 
    where(y_d) 
      subscript2 = x_d + y_d ;
  gather(d, a, x_d, subscript2) ;
\end{verbatim}
is equivalent to the HPF
\begin{verbatim}
      REAL D (0 : M - 1, 0 : M - 1)
!HPF$ ALIGN D WITH A (0 : M - 1, 0 : M - 1)

      ...

      FORALL (X = 0 : M - 1, Y = 0 : M - 1)
        D (X, Y) = A (X, X + Y)
      END
\end{verbatim}
This illustrates how subscripts can have different rank to the gathered
data, so long as they conform, in the sense explained above.

     Why not introduce some neat syntax for \verb$gather$ and
\verb$scatter$, to make them look more like conventional subscripting
operations---and less intimidating?  Mainly to emphasise that these are
big, expensive operations, implemented in a run-time library.  We don't
particularly {\em want} to make them easy to use!  In this connection
it's worth pointing out that in the last example one could achieve the
same effect---almost certainly more efficiently---with the simpler
\verb$remap$ operation.  \verb$a$ and \verb$c$ are declared as above,
then\dots
\begin{verbatim}
  where(x_d)
    remap(d, a [m : base x_d : y_a]) ;
\end{verbatim}
Inside the \verb$where$, \verb$d$ behaves like a vector with range
\verb$y_d$ and \verb$a$ behaves like a vector with range \verb$y_a$
(the \verb$where$ range \verb$x_d$ is a subrange of \verb$x_a$,
so \verb$a$ can properly appear here).  \verb$x_d$ behaves like a simple
integer value, so it can appear as the base of the section subscript on
\verb$a$.  Of course, we can do a similar thing in HPF:
\begin{verbatim}
  FORALL (X = 0 : M - 1)
    D (X, : ) = A (X, X : X + M - 1)
  END
\end{verbatim}

     \verb$gather$ and \verb$scatter$ have an optional final
argument---an array of type \verb$int$, conforming with the gathered
data.  This is a mask, controlling assignment.   The assignment is
disabled where the mask is zero.

     Notice that if \verb$a$ and \verb$b$ are rank-\verb$r$ arrays
with the same shape, the following operations all have the same effect
\begin{verbatim}
  remap(a, b) ;

  gather(a, b, a.rng(1), ..., a.rng(r)) ;

  scatter(b, a, b.rng(1), ..., b.rng(r)) ;
\end{verbatim}


\subsection{Procedures}

     The procedure interface should provide static information about
the arguments, which assists in efficient compilation of both the
procedure and the calling program.

     The external interface of an HPF procedure can contain an
extraordinary amount of detailed information.  The shape and alignment
parameters of some arguments can depend on run-time values of other
arguments, or of global variables, through arbitrary ``specification
expressions''---more restrictive than ordinary Fortran expressions, but
not by a great deal.  This is different from most languages---for
example C++---where the external interface only depends type
information, always available at compile time.

     Adhoc attempts to capture as much static information as practical
from the original Fortran program, so it has a comparably complex
procedure interface.  It also allows attributes of arguments to depend
on other arguments through arithmetic expressions and various inquiry
functions.  Like Fortran, Adhoc will require a restricted class of
expression which can be used in this context.  We don't intend to
define this class here (probably it would be simpler than the Fortran
specification expression, just allowing scalar integer arithmetic and
some inquiry functions).  The main novel feature of Adhoc relative to
HPF is the systematic use of a ``wild-card'' mechanism to put
incomplete information in the interface.

     The identifier \verb$_$ is reserved for a wild-card, which
can stand for
\begin{itemize}
\item
an integer expression,
\item
a process dimension,
\item
a triplet,
\item
a range, or
\item
an embedding set.
\end{itemize}
Array signatures appearing in the formal parameter list can involve
\verb$_$ in various places.
For example the interface
\begin{verbatim}
  void foo(array int a _ [_, _]) {
    ...
  }
\end{verbatim}
specifies that \verb$foo$ has a rank-2 array argument, but leaves
its embedding and ranges unspecified.  We could have specified
just the size of these ranges, as in
\begin{verbatim}
  void goo(array int a _ [10 :: _, 10 :: _]) {
    ...
  }
\end{verbatim}
or we could have specified empty embedding, and primitive ranges
distributed over specific globally defined process dimensions\dots
\begin{verbatim}
  void hoo(array int a [_ # t_1, _ # t_2]) {
    ...
  }
\end{verbatim}
\dots or ranges derived in an unspecified way from primitive ranges
over the same process dimensions\dots
\begin{verbatim}
  void koo(array int a [_ : _ # t_1, _ : _ # t_2]) {
    ...
  }
\end{verbatim}
\dots and so on\footnote{In these examples the syntax rules of Adhoc
provide an unambiguous classification of each underscore into one of the
five categories enumerated above.  This is always possible.}.
Many further examples are given in section \ref{dummies}.

    There is no analogue of HPF ``prescriptive'' mappings.  Actual
parameters must match the patterns specified in the formal parameter.
Section \ref{dummies} shows the various effects of the HPF dummy argument
mappings are reproduced.


\subsection{Allocatable and non-Cartesian arrays}

     Sometimes it is necessary to defer allocation of an array.  For
example, one may want to achieve the effect of a function returning an
array whose shape is defined within the function call.  Adhoc doesn't
directly support \verb$array$-valued functions\footnote{Adhoc is meant
to be a relatively low-level target language.  Array-valued
functions are high-level features; the compiler has to allocate array
temporaries for them.}.  But one can pass an allocatable array to a procedure,
and have the procedure allocate it.

     The declaration of an allocatable array uses the keyword
\verb$alloc$ rather than \verb$array$, and the embeddings and ranges
can use wildcards in the same way as the signatures of formal
parameters.  Analysis of an Adhoc program is simplified if the {\em process
dimensions} at least, are specified by the patterns
used in the \verb$alloc$ declaration\footnote{Otherwise it may be
difficult to statically determine properties as fundamental
as the effective rank of the array within \verb$at$ or \verb$where$
contructs.}.  For example
\begin{verbatim}
  alloc float a [_ # t_1, _ # t_2] ;
\end{verbatim}

     To allocate \verb$a$ we use the special syntax \verb$<- new$\dots
\begin{verbatim}
  a <- new array float [10 # t_1, 10 # t_2] ;
\end{verbatim}
Subsequently \verb$a$ can be used exactly like an ordinary array, until
it is deallocated with the \verb$delete$ operator:
\begin{verbatim}
  delete a ;
\end{verbatim}

     A ``non-Cartesian array'' is a non-rectangular array.  It is
essentially an array of arrays.  The declaration syntax is illustrated
by
\begin{verbatim}
  range x_b(10 # t_1) ;
  range y_b(10 # t_2) ;

  array float b [x_b, y_b] [_ # t_3] ;
\end{verbatim}
which is a two-dimensional array of one-dimensional arrays (embedding
lists are optionally permitted before each range list).  More
precisely, it is an \verb$array$ of \verb$alloc$ objects, so incomplete
specifications of ranges can appear in ``inner'' embedding sets and range lists.
The elements of a non-Cartesian array must to be allocated with
the \verb$new$ operator.  For example
\begin{verbatim}
  where(x_b)
    where(y_b)
      b <- new array float [x_b + y_b # t_3] ;
\end{verbatim}
which sets the extent of the third dimension of \verb$b$ to be some
function of the indices in the first two dimensions.  The elements
must be deleted in a matching construct:
\begin{verbatim}
  where(x_b)
    where(y_b)
      delete b ;
\end{verbatim}

     An extra restriction is needed concerning access to non-Cartesian
arrays: a non-Cartesian array cannot be accessed inside an \verb$where$
or \verb$at$ construct specifying a process dimension associated with
an {\em inner} range or embedding of the array.  Does that render the
data in non-Cartesian arrays forever inaccessible?  Happily not,
because within the context of the loops
\begin{verbatim}
  where(x_b)
    where(y_b)
      ...
\end{verbatim}
(for example) the variable \verb$b$ behaves like a one-dimensional
Cartesian array, and is accessible by a loop specifying \verb$t_3$.
The new restriction only forbids access to \verb$b$ in a \verb$where$
or \verb$at$ specifying \verb$t_3$ {\em if} the \verb$t_1$ and
\verb$t_2$ context has not been specified by enclosing \verb$at$ or
\verb$where$ constructs, to ``convert'' the array to a Cartesian one.

      The \verb$remap$ call can be applied to non-Cartesian arrays.
Both arguments of \verb$remap$ must be fully allocated before the
call.  They must have the same detailed shape---the functions defining
higher level extents in terms of lower level indices must be identical
for the two arrays.

      In \verb$gather$ and \verb$scatter$ the gathered data and the
subscripts may be conforming non-Cartesian arrays.  The {\em scattered
data} should always be a simple Cartesian array [THAT MEANS THAT
`REMAP' FOR A NON-CARTESIAN ARRAY CANNOT BE EXPRESSED IN TERMS OF
`GATHER' OR `SCATTER'].  In this context {\em conforming} means that
embedding sets and range lists are identical, except at the innermost
level, where the weaker constraints for conforming Cartesian arrays
apply\footnote{This wording is not unambiguous.  It is arguable that
the signature \verb$array float [x, y] [z]$ conforms with \verb$array
int [x]$ because the innermost range list of the latter conforms with
the {\em corresponding} range list of the former, according to the
earlier rules}.


\subsection{IO}

     The procedures \verb$input$ and \verb$output$ take a single array
argument.


\subsection{Miscellany}

     The communication primitives introduced so far are sufficient to
translate any HPF program which doesn't use array intrinsics (and many
that do).  Efficient translation of some the array intrinsics need
further operations; for example, reduction operations.  Most of these
can be specified by Adhoc procedure interfaces, and implemented as
library functions.

     Inquiry functions are provided for:
\begin{itemize}
\item
extracting an embedding set from an array,
\item
extracting a range, identified positionally, from an array,
\item
extracting the extent of a range,
\item
extracting the process dimension from a range, and
\item
extracting a process dimension, identified positionally, from a process array.
\end{itemize}


\subsection{\label{distribAdhoc}Distributed Adhoc}

     {\em Distributed Adhoc} allows declarations like
\begin{verbatim}
  procs p(4, 4) ;
  dimension p_1(p.dim(1)) ;
  dimension p_2(p.dim(2)) ;
\end{verbatim}
This combination of declarations is supposed to be ``semantically
equivalent'' to
\begin{verbatim}
  procs p
  dimension p_1 of p ;
  dimension p_2 of p ;
\end{verbatim}
in Vanilla Adhoc.  With the new syntax \verb$p_1$ and \verb$p_2$ are
``distributed dimensions''.

     The syntax for primitive ranges is changed along the following
lines\dots
\begin{verbatim}
  range x(10 #blk    p_1) ;
  range y(10 #cyc    p_2) ;
  range i(10 #blk(2) p_1) ;
  range j(10 #cyc(2) p_2) ;

  range z(10 #* p_3) ;
\end{verbatim}
The first four declarations reflect the four distribution formats in
HPF.  The last declaration introduces a ``collapsed range''.  We insist
that collapsed ranges cannot be created over distributed
dimensions---in the example, \verb$p_3$ may not be a distributed
dimension.  By definition, a range derived from a collapsed range is
also collapsed (but not {\em primitive} collapsed---there is still a
vestigial alignment relation between collapsed ranges, so that the
control-mapping constructs can be meaningfully applied over collapsed
ranges).

     Semantically the new operators \verb$#blk$, \verb$#cyc$, etc, and
\verb$#*$ are identical to the \verb$#$ of Vanilla Adhoc {\em with the
following exception}:  in Distributed Adhoc an embedding in a {\em
collapsed} range is regarded as a {\em null embedding}.  Two arrays
whose mappings differ only by null embeddings are considered to have
equivalent mappings; a null embedding in the embedding set of an
\verb$at$ constructor can be omitted without changing the meaning of a
program; finally, an array section which in Vanilla Adhoc would yield
an \verb$array$ with only null embeddings (and an empty range list)
{\em can be used like a simple variable} in Distributed Adhoc.  For example
\begin{verbatim}
  array float a [10 #* p_3] ;
  ...
  a [3] = 3 + a [2] ;
\end{verbatim}
is legal in Distributed Adhoc---an array whose ranges are collapsed can
be used in much the same way an ordinary C or Fortran
array\footnote{The introduction of null embeddings means that the
semantics of Distributed Adhoc is strictly larger than Vanilla Adhoc.
It would be nice to say that any Distributed Adhoc program can be
trivially mapped to a Vanilla Adhoc program.  This nice feature was
sacrificed by introducing null embeddings.  One could fix that by
adding the idea of a collapsed range to Vanilla Adhoc---we preferred
not to complicate its semantics---or by forgoing null embeddings in
Distributed Adhoc---but they are rather convenient.}.

