1 An Extended occam-like Notation

Pure occam isn’t a suitable notation for expressing very dynamic algorithms. We need pointers, at least. To simplify presentation of algorithms in this article, we define a couple of extensions to current occam notation, with their informal semantics (this is a “meta-language”—no implementation exists. On the other hand it isn’t much more than a sugaring of capabilities available 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 are not 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 have been mooted, for example, in [?], although usage here will be slightly different.

To prevent simply copying the reference in one pointer variable to another (leading to an alias) pointers can’t appear in assignment statements (unless they have been dereferenced). Instead the primitive procedure

    PROC POINTER.COPY (POINTER T a, b)

copies the value of the pointer b to a, and makes the pointer b null. A precondition is that the a should be null before invoking the procedure. (The symbol T is used here as a type variable; 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

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

If both ends of chan live on the same processor the implementation of these operations is by straightforward pointer copying. If they live on different processors, POINTER.IN allocates space locally for the incoming data, the data is transfered, and POINTER.OUT deallocates the memory pointed to by b (and makes the pointer null). This implementation is applicable if T is a simple data type. If 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 discussed below. In any implementation one should presumably strive to maintain the law

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

For pointers to simple data the story is completed by adding a Pascal-like mechanism to the language for allocating memory (and a mechanism for dereferencing a pointer). So, for example,

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

allocates a as a pointer to an array of n integers. (Assume that a pointer is set to null when it’s declaration is elaborated. 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”. The language probably ought to have a NULL operator applicable to a pointer to test whether it is null, but no explicit null value need 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 traversing them with the primitives given (if the language doesn’t support recursive procedures). Simple stacks work quite well, but any recursive structure more complicated than that gets difficult. Nevertheless, non-recursive, bounded depth, trees still represent a significantly richer spectrum of data structures than those available in implemented, pointerless, versions of occam.

Pointers to data were mentioned first, but pointers to channel ends are more important in this article. Any dynamic channel has two ends (inputting and outputting). A pointer to a channel end will be called a PORT. A port deferenced by the FOLLOW operator can be used wherever a 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—POINTER.COPY, POINTER.IN and POINTER.OUT. A dynamic channel is allocated and freed by

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

The first of the pair of ports appearing in the NEW and 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.

    PROC SELF.OUT  (PORT OF T port)

is a primitive procedure which outputs a channel end on itself, making port null. The channel end emerges out of its own input port, (through a normal 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 NEW, FREE, POINTER.IN, POINTER.OUT and SELF.OUT is easily implemented 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.