%\documentstyle{csart}

%\begin{document}

%\newenvironment{linear}{\\ \begin{minipage}[t]{\textwidth}}{\end{minipage}}

\section{\label{dynamic}An Extended occam-like Notation}

     Pure {\em occam} isn't a suitable notation for expressing very
dynamic algorithms.  Some sort of pointers seem necessary, at least.
To simplify presentation of algorithms in this article we use an ``algorithmic
language'' which is essentially {\em occam} with a couple of extensions
for handling dynamic objects.
(No implementation exists for this language.  On
the other hand it isn't much more than a sugaring of capabilities
inherent in the VCR run-time library).  For our purposes a restricted
form of pointer which doesn't lead to undesirable aliasing is
sufficient.  (One reason why aliasing is bad in occam is that
concurrently executing processes aren't supposed to share access to
variables or channel ends.  If there are several different names for
the same object, such a regime becomes difficult to enforce.)
Non-aliasing pointers for {\em occam} have been discussed, for example, in
\cite{welch}.  Usage here differs in detail.

     To prevent simply copying the reference in one pointer variable
to another (leading to an alias) pointers can't appear in assignment
statements (except in dereferenced form).
Instead the primitive procedure
\begin{linear}
\begin{verbatim}

    PROC POINTER.COPY (POINTER T a, b)

\end{verbatim}
\end{linear}
copies the value of the pointer $b$ to $a$, {\em and makes the pointer $b$
null}.  A precondition is that $a$ should be null before invoking
the procedure.  (The symbol \verb$T$ is used here as a type variable;
\verb$POINTER.COPY$ is overloaded for application to pointers to arbitrary
compatible types).

     So long as pointers are copied by this operation alone, one never
ends up with two pointers referencing the same object.  Pointer
communication can be defined along similar lines
\begin{linear}
\begin{verbatim}

    PROC POINTER.OUT (CHAN OF POINTER T chan, POINTER T b)
    PROC POINTER.IN  (CHAN OF POINTER T chan, POINTER T a)

\end{verbatim}
\end{linear}
If both ends of {\em chan} live on the same processor the implementation
of these (synchronising) operations is by straightforward pointer copying.
If they
live on different processors, \verb$POINTER.IN$ allocates space locally
for the incoming data, returning the address in $a$,
the data is transfered, and \verb$POINTER.OUT$
deallocates the memory pointed to by $b$ (and makes the pointer
null).  This implementation is applicable if \verb$T$ is a simple data
type.  If \verb$T$ is actually a record that contains other pointers,
complications ensue which won't be discussed here.  If it's a
channel, other complications ensue which will be mentioned below.
In an implementation one should presumably strive to maintain the law
\begin{linear}
\begin{verbatim}

    CHAN c :
    PAR
      POINTER.OUT (c, b)      =      POINTER.COPY (a, b)
      POINTER.IN  (c, a)

\end{verbatim}
\end{linear}

     For pointers to simple data the story is completed by adding
a Pascal-like mechanism to the language for allocating and freeing memory
(and a notation for dereferencing a pointer).  So,
for example,
\begin{linear}
\begin{verbatim}

    POINTER [] INT a :
    SEQ
      a NEW ([n] INT)
      ...
      (FOLLOW a) [i] := ...
      ...
      FREE a

\end{verbatim}
\end{linear}
allocates $a$ as a pointer to  an array of $n$ integers.  (Assume that
a pointer is set to null when it is declared.  Then
one can also demand, and in principle check, that the value of any
pointer should be null when its scope terminates, enforcing that
the user always explicitly deallocates allocated objects.  This is only
possible because pointers are ``non-aliasing''.  It represents
an interesting antithesis to automatic garbage collection!
The language probably ought to have
a \verb$NULL$ operator applicable to a pointer to test whether
it is null, but no explicit null value needs to be expressible).

     Of course these non-aliasing pointers are fairly restrictive.  Assuming
pointers are allowed to appear in records, one can still only build up
simple tree and list structures, and even with those structures there
are awkward complications about traversal with the
primitives given (especially if the language doesn't support recursive
procedures).  Simple stacks work quite well, but any recursive
structure more complicated than that gets painful.
Nevertheless, non-recursive, bounded depth, trees still represent a
significantly richer spectrum of data
structures than those available in implemented, pointerless, versions of {\em
occam}.

     Pointers to data were introduced first, but pointers to channel
ends are more important in this article.  Any channel has two ends
(inputting and outputting).  A pointer to a channel end will
be called a \verb$PORT$.  A port deferenced by the \verb$FOLLOW$ operator
can be used wherever a \verb$CHAN$ expression can appear in normal occam
(for example, on the left hand side of an input or output operation).
Also a port can be passed as a parameter to the generic operations on
pointers---\verb$POINTER.COPY$, \verb$POINTER.IN$ and \verb$POINTER.OUT$.
A dynamic channel is allocated and freed by
\begin{linear}
\begin{verbatim}

    PORT OF ANY c, d :
    SEQ
      c, d NEW (CHAN OF ANY)
      ...
      FREE c, d

\end{verbatim}
\end{linear}
The first of the pair of ports appearing in the \verb$NEW$ and \verb$FREE$
statements will be a pointer to the input end of the channel, and
the second a pointer to the output end (say).
Through the pointer IO operations a port can be passed from one process
to another.  We've specified that a connected pair of ports should
be deallocated together (because this seems more symmetric; it may
also simplify implementation slightly).  This means there has to be
some mechanism for getting connected ports back together again for
disposal.
\begin{linear}
\begin{verbatim}

    PROC SELF.OUT  (PORT OF T port)

\end{verbatim}
\end{linear}
is a primitive procedure which outputs a channel end on itself, making
{\em port} null.  The channel end emerges out of its own input port,
(through a normal \verb$POINTER.IN$ operation at that end)
and the two can then be deallocated (together, but
not necessarily in the same process they started in).

     The run-time system needed to implement \verb$NEW$, \verb$FREE$,
\verb$POINTER.IN$, \verb$POINTER.OUT$ and \verb$SELF.OUT$ is
easily built on top of the VCR run-time library.  The first
four calls formally apply to, but have very different implementations for,
both data and channels
(for data, only memory management and simple IO is needed; for channels
the full paraphernalia of channel-moving is needed).
Facilities for implementing both are available in VCR.

%\end{document}

