
\section{\label{implementation}Translation of Adhoc to C++}

    By design {\em Adhoc} has a very straightforward transcription to
C++.  This transcription depends on a library containing:
\begin{itemize}
\item
Classes for process arrays and process dimensions
\item
Classes for ranges
\item
Template classes for arrays
\item
Functions to implement \verb$remap$, \verb$broadcast$,
\verb$gather$ and \verb$scatter$, \verb$input$ and \verb$output$
(and some reduction operations).
\end{itemize}

%\subsection{Elements of {\em Mini-Adlib}}

     {\em Mini-Adlib}\footnote{The name ``ADLIB'' predates ``Adhoc''.
It is the name of the (never-fully-implemented) communication library
supporting the Southampton ADAPT system \cite{}.} is a minimal run-time
library for Adhoc.  It is minimal in the sense of providing the
smallest reasonable set of operations for translation of the language.
The operations provided are deliberately ``high-level''---{\em
efficient} translation would depend on an extended RTL, providing a
large set of simpler, lower-level operations which the translator can
place ``in line'' in the generated code.

\subsection{Process arrays and dimensions}

      The public part of the Mini-Adlib library for handling
process arrays and process dimensions is displayed below.
\begin{verbatim}
  class Dimension ;

  class Procs {
    // ...
  public :
    Procs() ;
    Procs(int, ...) ;  // Procs(int r, int n_1, ..., int n_r)
    Dimension* dim(int) ;
  } ;

  class Dimension {
    // ...
  public :
    Dimension(Procs&) ;
    ~Dimension() ;
  } ;
\end{verbatim}
A process array is represented by an object of class \verb$Procs$.
There are two constructors.  The first constructor creates an ``empty''
process array, in the style of Vanilla Adhoc \verb$procs$ declaration.
The second, more useful, constructor sets up a process array of rank
\verb$r$, and the shape specified by the remaining
arguments\footnote{Note that this constructor will require access to
information about the physical process group on which the SPMD program
is executing.  It has to decide how to map virtual processes of the
array to this group.  For the moment we assume that this information is
available in some global variable.}.

     The Adhoc process dimension is represented by the \verb$Dimension$
class.  The \verb$Procs(r, ...)$ constructor internally creates \verb$r$
objects from this class.  The \verb$d$th dimension can be accessed
using the \verb$dim(d)$ inquiry function.  The constructor
\verb$Dimension(p)$ attaches a new dimension to the pre-existing
process array \verb$p$.  In practise a process dimension created
dynamically in this way will be ``collapsed'' or ``on-processor''---the
only truly distributed dimensions are those created by the
\verb$Procs(r, ...)$ constructor.

\subsection{Ranges and embeddings}

     \verb$Subscript$ is a base class representing any object which can be
used as an array subscript---namely an embedding or a range (in Adhoc
simple variables and triplets can also be subscripts; Mini-Adlib
assumes that these are promoted by applying them to the associated
range of the array being subscripted).
\begin{verbatim}
  class Subscript {
    // ...
  } ;
\end{verbatim}
\verb$Subscript$ has no public members.

     An Adhoc range is represented by a \verb$Range$ object
\begin{verbatim}
  class Format ;

  class Range : public Subscript {
    // ...
  public :
    Range(int, Dimension&) ;
    Range(int, Dimension&, Format) ;
    Range(int, Dimension&, Format, int) ;
    Range(int, int, int, Range&) ;

    int size() ;

    operator void*() ;
    void first() ;
    void operator++() ;
    void last() ;
    void operator--() ;

    int operator()(Subscript&) ;
    int operator()() ;
  } ;
\end{verbatim}
For all \verb$Range$ constructors the first argument is the extent of
the range.  The first three constructors build primitive ranges with
assorted distribution formats.  \verb$Format$ is some type which can
take the value ``block'' or ``cyclic''.  The fourth constructor builds
a derived range---the second and third arguments are base and stride
in the parent range.

     \verb$size$ is an inquiry function, which returns the extent
of a range.

     The next five members are iterator functions.  One of the
r\"{o}les of the \verb$Range$ class is as an iterator class for
implementing \verb$where$ loops.  The \verb$first$ function activates a
range as an iterator, the \verb$void*$ operator is a test function, and
the \verb$++$ operator is a ``next'' function.  These operations are
only ever used in a \verb$for$ loop.  If \verb$x$ is a range then
\begin{verbatim}
  for(x.first() ; x ; x++)
\end{verbatim}
is a translation of
\begin{verbatim}
  where(x)
\end{verbatim}
Clearly the state of a \verb$Range$ structure changes while it is being
used as an iterator.  In particular, between a call to \verb$first$ and
termination of the associated loop, an internal flag is set which
alters the behaviour \verb$Array$ member functions when the range is
passed as a \verb$Subscript$ argument.  We return to this point later.

     An alternative translation of \verb$where(x)$ is
\begin{verbatim}
  for(x.last() ; x ; x--)
\end{verbatim}
The only difference is that the single process sequential parts of the
loop are performed in reverse order.  This shouldn't alter the
behaviour of a program, but by performing memory deallocation in
inverted loops one can sometimes eliminate heap allocation of array
elements in favour of stack allocation.

    The two \verb$()$ operations are used to translate situations where
an index is standing for a one-dimensional array; their effect will be
explained later.

     The interface of the \verb$Embed$ class, used to implement
Adhoc embeddings, is simpler
\begin{verbatim}
  class Embed : public Subscript {
    // ...
  public :
    Embed(int, Range&) ;
    Embed(int, Range&, Embed*) ;

    Embed* next() ;

    operator void*() ;
  } ;
\end{verbatim}
The first constructor obviously creates an embedding at the specified
location in the specified range.  The second constructor does the same,
but also initialises a link field to another embedding; these link
fields are used to construct the (intrusive) linked lists which
implement embedding sets in Mini-Adlib.  The value of the link is
accessed by \verb$next()$.

     The \verb$void*$ operator is a vestige of the \verb$void*$
iterator function in the \verb$Range$ class.  It returns a non-zero
value only on a processor which contains the embedding.  It can be
used to translate \verb$at$.  So
\begin{verbatim} 
  embed e(...) ;
  ...
  at({e})
    ...
\end{verbatim} 
is translated by
\begin{verbatim} 
  Embed e(...) ;
  ...
  if(e)
    ...
\end{verbatim} 
The general construct
\begin{verbatim} 
  at(es)
    S
\end{verbatim} 
can be translated by
\begin{verbatim}
  Embed* tail = es ;
  while(*tail)
    if(! (tail = tail.next())) {
      S' ;
      break ;
    }
\end{verbatim}
assuming \verb$es$ is a pointer to an \verb$Embed$ structure at the
head of a linked list representing the embedding set, and \verb$S'$ is
the translation of \verb$S$.


\subsection{Arrays}

     The basic Adhoc array is represented by the \verb$Array$ class
\begin{verbatim}
  class Frame {
    // ...
  public :
  } ;

  template<int R, class T>
  class Array : public Frame {
    // ...
  public :
    Array(Embed*, ...) ;  // Array(es, x_1, ..., x_R)
    Array(Range&, ...) ;  // Array(x_1, ..., x_R)
    ~Array() ;

    Range* rng(int) ;
    Embed* emb() ;

    T& operator()(Subscript&, ...) ;  // this(i_1, ..., i_R)
    T& operator()() ;                 // ...used if R=0
  } ;
\end{verbatim}
The base class \verb$Frame$ is used to type certain function parameters
in the library, where functions must accept arrays of any rank and
type.  Generally ``users'' will only need the derived template class
\verb$Array$ (and sub-classes below) which statically specify rank and
element type through the template arguments.

     The first constructor takes an embedding set and a list of
ranges.  The second creates an array with an empty embedding set (the
most common case).

     The inquiry function \verb$rng(d)$ returns the \verb$d$th range
of the array; \verb$emb()$ returns its embedding set.

     Finally the \verb$()$ operator implements subscripting of the
array.  It's arguments are of class \verb$Subscript$---ie \verb$Range$
or \verb$Embed$, and the result is a reference to a single array
element.  This operation {\em cannot} be used to construct array
sections---they are constructed with the \verb$Section$ constructor,
introduced below.

     The effect of a subscript of class \verb$Embed$ should be fairly
obvious
\begin{verbatim}
  Array<1, int> a(x)
  ...
  Embed e(2, x) ;
  if(e)                // ie, if `e' is on this processor
    a(e) = 23 ;
\end{verbatim}
is the translation of
\begin{verbatim}
  array int a [x]
  ...
  embed e(2 : x) ;
  at(e)
    a = 23 ;
\end{verbatim}
It should {\em not} be obvious why a \verb$Range$ can be used as a
subscript in this operation, given that the operation cannot return a
section!  In fact a \verb$Range$ can only be used {\em while it is
activated as an iterator}.  During this time a flag is set in a
\verb$Range$ object which causes subscripting operations to treat the
range {\em as if} it were an embedding at the point associated with the
current iteration of the loop.  So
\begin{verbatim}
  Array<1, int> a(x)
  ...
  for(x.first() ; x ; x++)
    a(x) = 23 ;
\end{verbatim}
is the translation of
\begin{verbatim}
  array int a [x]
  ...
  where(x)
    a = 23 ;
\end{verbatim}

     As emphasised, the subscripting operation in the \verb$Array$
class cannot be used to construct array sections; in fact this
operation is normally used to implement Adhoc \verb$at$ and
\verb$where$ constructs rather than Adhoc subscripting operations.  The
latter are translated using the \verb$Section$ subclass.
\begin{verbatim}
  template<int R, class T>
  class Section : public Array<R, T> {
    // ...
  public :
    Section(Embed*, Frame, ...) ;  // Section(es, a, i_1, ..., i_s)
    Section(Frame, ...) ;          // Section(a, i_1, ..., i_s)
    ~Section() ;
  } ;
\end{verbatim}
The \verb$Frame$ argument of the constructors is the array to be
subscripted; it has rank \verb$s$, say.  Again the subscripts are of
type \verb$Subscript$---either \verb$Embed$ or \verb$Range$.  Again, if
the a \verb$Range$ subscript is activated as an iterator it will behave
like an embedding; but if a \verb$Range$ object which is not currently
activated as an iterator is used as a subscript, it will act like a
triplet, and add a range to the \verb$Section$ constructed.  So there
are \verb$R$ such range subscripts.

     The first constructor adds a non-trivial embedding set to the
\verb$Section$ array created, the second constructor leaves the
embedding set empty.  It is left up to the ``user'' to get this
embedding set right.  In principle the constructor itself could work
out an embedding set from the embedding of the original array and the
subscripting pattern, but in practise the caller can generally do it
more efficiently (recall also the rather subtle rules about array
embedding sets in Adhoc, which depend on the \verb$at$ context).

     Non-Cartesian arrays are translated by the \verb$Aggregate$
class.
\begin{verbatim}
  template<int R>
  class Aggregate : public Array<R, void*> {
    // ...
  public :
  } ;
\end{verbatim}
So far as its public interface is concerned an \verb$Aggregate$ is just
an array of untyped pointers; the private part of the implementation
will include extra members, specific to non-Cartesian arrays.  These
are used internally by other functions in the library.

     Finally, to support the treatment of ranges as one dimensional
arrays of index values we introduce the \verb$Index$ subclass.
\begin{verbatim}
  class Index : public Array<1, int> {
    // ...
  public :
    Index(Range&) ;
  } ;
\end{verbatim}
Now
\begin{verbatim}
  Index(x)
\end{verbatim}
can be used as a constant array containing the index values in
\verb$x$.

     We can now explain the two members
\begin{verbatim}
  int operator()(Subscript&) ;
  int operator()() ;
\end{verbatim}
in the range class.  These are subscripting operations which optimise
common usage The single-argument \verb$()$ operation
\begin{verbatim}
  x(i)
\end{verbatim}
is defined to return the same value as
\begin{verbatim}
  Index(x)(i)
\end{verbatim}
The no-argument \verb$()$ operation
\begin{verbatim}
  x()
\end{verbatim}
is defined in turn to return the same value as
\begin{verbatim}
  x(x)
\end{verbatim}

\subsection{Communication primitives}

     The semantics of the functions
\begin{verbatim}
  void remap(Frame&, Frame&) ;
  void gather(Frame&, Frame&, ...) ;
  void scatter(Frame&, Frame&, ...) ;
  void input(Frame&) ;
  void output(Frame&) ;
\end{verbatim}
are defined by the semantics of \verb$Adhoc$---they should not require
further explanation.

\subsection{Examples of translation}

    The appendix gives translations of many of the Adhoc examples
in earlier sections to C++ and Adlib.

