# Various Extensions to the occam Compiler

Fred Barnes, Department of Computer Science, University of Kent.

Last modified 20th March 2005

- 20/03/2005 Variables of any channel type
- 13/03/2005 Mobile BARRIER support
- 26/02/2005 Native BARRIER support
- 19/01/2005 Channels of any channel type
- 21/12/2004 Tag-value specification for tagged protocols
- 05/05/2004 MOBILE process types
- 04/01/2004 Protocol inheritance
- 30/12/2003 Forward declarations for channel-types
- 09/08/2003 Basic nested MOBILEs support
- 20/03/2003 DEFINED dynamic mobile operator support
- 16/03/2003 Pre-processing support
- 13/02/2003 Empty array specifications
- 03/09/2002 Recursive channel types
- 03/09/2002 Anonymous channel types
- 01/09/2002 FORKed parallel processes
- 30/06/2002 MOBILE structured channel types
- 04/02/2002 Process priority support
- 14/01/2002 PLACED channels and arrays
- 10/01/2002 Modified ALT disabling sequence
- 19/12/2001 Extended rendezvous
- 18/12/2001 RESULT parameters and abbreviations
- 12/12/2001 Nested PROTOCOL definitions
- 10/12/2001 Modified parsing of SKIP in ALTs
- 30/11/2001 Recursion in occam
- 14/11/2001 STEP in replicators
- 23/10/2001 Channel direction specifiers
- 23/10/2001 Optional OF
- 08/10/2001 Array constructors
- 01/10/2001 Variable replicated PARs
- 08/09/2001 MOBILE data types

As of 1.3.3 (final), the majority of these extensions are enabled by default. Future/ongoing extensions may require the use of the ```-X7`'' flag to kroc. This document is compatible with versions 1.3.4 (pre7) and above of KRoC/Linux.

A plain version of this document is available, as is a clean version (keeping syntax highlighting).

## Variables of any channel type

added 20/03/2005

The support for channels of any channel type has now been extended to support variables and parameters of the "`MOBILE.CHAN`" type. Variables of this type (that can be specialised in the usual way with "`SHARED`" and/or a direction-specifier) may be communicated on matching channels, or assigned to each other. Furthermore, a regular mobile-channel-end may be assigned to a "`MOBILE.CHAN`" and visa-versa (with an additional run-time check in the latter case to ensure the correct type is present). For example:

        CHAN TYPE FOO
          MOBILE RECORD
            CHAN INT c?:
        :

        MOBILE.CHAN x, y:
        FOO! f.c:
        SEQ
          ...  acquire f.c
          x := f.c
          y := x
          f.c := y

## Mobile BARRIER support

added 13/03/2005

Mobile barriers are mobile equivalent of static barriers. These barriers must be explicitly allocated through the use of a special mobile assignment (that follows the style of other dynamic mobile allocation):

        MOBILE BARRIER b:
        SEQ
          b := MOBILE BARRIER
          ...  use "b"

Unlike static barriers, mobile barriers may be freely communicated and assigned except when extended by a "`PAR BARRIER`". Extended barriers may not be over-written, but may still be used as the source in assignment or communication. For example:

        PROC recv (CHAN MOBILE BARRIER in?)
          MOBILE BARRIER x:
          SEQ
            in ? x
            SYNC x
        :

        PROC send (CHAN MOBILE BARRIER out!)
          MOBILE BARRIER v:
          SEQ
            v := MOBILE BARRIER
            out ! v
            SYNC v
        :

        CHAN MOBILE BARRIER c:
        PAR
          send (c!)
          recv (c?)

Following the semantics of communication, mobile barriers may be passed to "`FORK`"ed processes, that can overwrite their mobile barrier parameters even when extended. Mobile barriers may also be "`RESIGN`"ed in the normal way. For example:

        PROC foo (MOBILE BARRIER x)
          SEQ
            SYNC x
            x := MOBILE BARRIER
            SYNC x
        :

        MOBILE BARRIER b:
        SEQ
          b := MOBILE BARRIER
          PAR BARRIER b
            FORK foo (b)
    	SYNC b
    	RESIGN b
    	  ...  do stuff without "b"

## Native BARRIER support

added 26/02/2005

This extension provides a "`BARRIER`" type, used to synchronise multiple parallel processes (channels synchronise two processes only). Barriers may be declared and renamed (passed as parameters and abbreviated) like ordinary variables, but may not be communicated or assigned. Normal parallel-usage rules apply to barriers, except when a "`PAR`" construct extends a barrier (specified using "`PAR BARRIER`"). For example:

        PROC foo (BARRIER x)
          SEQ
            SYNC x
            SYNC x
        :

        BARRIER b:
        PAR BARRIER b
          foo (b)
          foo (b)

Processes may resign themselves from a barrier, but this introduces non-determinism. For example:

        BARRIER b:
        PAR BARRIER b
          SYNC b
          SEQ
            RESIGN b
    	  ...  do stuff without the barrier
            SYNC b

The default behaviour of the compiler is to resign parallel processes from the barrier as soon as they terminate -- without waiting for the whole "`PAR`" to terminate before resigning the processes.

## Channels of any channel type

added 19/01/2005

This addition allows a channel to carry a special "any channel-type" protocol. This is essentially the same as variant (tagged) communication, except that the tag is implied by the channel-type. For example:

        CHAN TYPE LINK
          MOBILE RECORD
            CHAN INT c?:
        :

        PROC recv (CHAN MOBILE.CHAN in?)
          LINK! l.cli:
          SHARED LINK! l.scli:
          in ? CASE
            l.cli
              ...  process using l.cli
            l.scli
              ...  process using l.scli
        :

        PROC send (CHAN MOBILE.CHAN out!)
          LINK! l.cli:
          LINK? l.svr:
          SEQ
            l.cli, l.svr := MOBILE LINK
            out ! l.cli
        :

These could be connected with just:

        CHAN MOBILE.CHAN c:
        PAR
          send (c!)
          recv (c?)

Or something more elaborate.. As far as parameters and abbreviations are concerned (renaming), channels of the any channel-type are only type-compatible with themselves. More specialised declarations can also be made, e.g. to only carry shared channel-ends or client/server channel-ends. For example:

        CHAN SHARED MOBILE.CHAN? c:
        CHAN MOBILE.CHAN! d:
        ...  process using c and d

The "`MOBILE.CHAN`" type may also be used to declare any-channel-type variables and parameters. These may be directly inputted or outputted to a correspondingly typed channel, including use in sequential/variant protocols. For example:

        PROTOCOL ILINK
          CASE
            get.status
            route; INT; MOBILE.CHAN
        :

        PROC linkify (CHAN MOBILE.CHAN in?, CHAN ILINK out!)
          WHILE TRUE
            MOBILE.CHAN x:
            SEQ
              in ? x
              out ! route; 0; x
        :

Ordinary channel-types may also be output as a "`MOBILE.CHAN`" protocol component, but not input (since there is no clear way to define this in the language syntax). "`MOBILE.CHAN`" variables are covered in detail above.

## Tag-value specification for tagged protocols

added 21/12/2004

This addition allows the programmer to specify specific values for the tags in tagged (variant) protocols. This allows external C code (using the CIF framework) to communicate on variant protocol channels with occam processes, without relying on (occam-pi) compiler-generated constants. Tag values are specified in a natural way, for example:

        PROTOCOL EXTERNAL.LINK
          CASE
            mouse.x.y = 0; INT; INT
            mouse.down = 2; INT
            mouse.up = 3; INT
        :

The compiler will check that specified tag-values do not conflict when dealing with nested protocols and/or inherited protocols. Additionally the compiler will disallow any tagged protocol with a mixture of value-specified and non-value-specified tags.

## MOBILE process types

added 05/05/2004

This extension adds support for `MOBILE` processes in `occam-pi' (the new name for the evolving occam-originating language). Mobile processes have an associated process-type that characterises the interface to the process. Mobile processes encapsulate code and data, like any other occam process, but may be moved around a process network. The main restriction is that a mobile process may not be moved whilst it is active. Activations of a mobile process are implemented using an `instance-style' syntax. A mobile process ceases to be active when it terminates or ``SUSPEND`'s. Once it has terminated, a mobile process may not be reactivated.

The following code defines a fairly simple mobile process (and associated process-type):

        PROC TYPE PT IS (CHAN INT in?, out!):

        MOBILE PROC integrate (CHAN INT in?, out!) IMPLEMENTS PT
          INT total:
          SEQ
            total := 0
            WHILE TRUE
              INT v:
              SEQ
                in ? v
                total := total + v
                out ! total
                SUSPEND
        :

This implements the familiar `integrate' component. When activated, the process will complete one cycle of input and output then suspend. Allocation of a mobile process is done in a similar way as it is for other dynamic mobile types -- with a slightly special form of assignment. For example:

        MOBILE PT x:
        INT v:
        SEQ
          x := MOBILE integrate

          CHAN INT to.int, from.int:
          PAR
            x (to.int?, from.int!)
            to.int ! 42
            from.int ? v

After the activation has finished (because ``integrate`' `SUSPEND`ed), the mobile process in ``x`' may be assigned or communicated. When it is next activated, the process may have a completely different environment.

Due to the somewhat special nature of a mobile process activation, there are several restrictions on what parameters may appear in a ``PROC TYPE`' definition -- only synchronisation `objects' may be used as parameters. This currently includes channels, fixed-size arrays of channels and mobile channel-bundle ends.

If a mobile process goes parallel internally, all parallel processes must `SUSPEND` in order to suspend the mobile process as a whole. This example program demonstrates this using a parallel version of the `integrate' process. Rather than suspending once per cycle, the process interprets ``MOSTNEG INT`' on its input channel as `suspend'. This is one way of handling the suspend -- it could just as easily be supported using dedicated channels (that may be more desirable for clarity).

## Protocol inheritance

added 04/01/2004

Support for protocol inheritance has now been added to the occam compiler. This allows tagged (variant) protocols to inherit tags from others, creating a type-compatibility between them.

For example:

        PROTOCOL MOUSE.EVENTS
          CASE
            mouse.x.y; INT; INT
            mouse.down; INT
            mouse.up; INT
        :

        PROTOCOL KEY.EVENTS
          CASE
            key.down; INT; INT
            key.up; INT; INT
        :

        PROTOCOL GFX.EVENTS EXTENDS MOUSE.EVENTS, KEY.EVENTS
          CASE
            gen.error; INT
        :

This can be used in the expected way. Given the set of `PROC`s:

        PROC graphics.server (CHAN GFX.EVENTS in?)
        PROC mouse.driver (CHAN MOUSE.EVENTS out!)
        PROC keyboard.driver (CHAN KEY.EVENTS out!)

We can wire them up this way:

        CHAN GFX.EVENTS c:
        PAR
          mouse.driver (c!)
          graphics.server (c?)

or this way:

        CHAN KEY.EVENTS c:
        PAR
          keyboard.driver (c!)
          graphics.server (c?)

These show the two allowed ways of using protocol inheritance. There are two others which are not legal, however, and are banned by the compiler.

In the first example, there would normally be a type incompatability in the instance of ``mouse.driver`', since a channel of a different type is passed as a parameter. However, since ``GFX.EVENTS`' (actual type) includes all the tags of ``MOUSE.EVENTS`' (formal type), anything that ``mouse.driver`' outputs is potentially handled (by a process that inputs ``GFX.EVENTS`').

In the second example, the incompatability is the instance of ``graphics.server`'. A similar logic as before applies, however. The ``graphics.server`' process accepts (potentially) any of the ``GFX.EVENTS`', of which ``KEY.EVENTS`' are a subset.

The two invalid cases are substantially less natural. Assuming there was:

        PROC mouse.handler (CHAN MOUSE.EVENTS in?)
        PROC graphics.plex ([]CHAN GFX.EVENTS in?, CHAN GFX.EVENTS out!)

Then:

        CHAN MOUSE.EVENTS c:
        PAR
          graphics.plex (..., c!)
          mouse.handler (c?)

and

        CHAN GFX.EVENTS c:
        PAR
          graphics.plex (..., c!)
          mouse.handler (c?)

are illegal. In the first, for example, an attempt is made to connect a channel of ``MOUSE.EVENTS`' to a process that outputs any ``GFX.EVENTS`', of which ``MOUSE.EVENTS`' are possibly only a subset -- i.e. ``graphics.plex`' could output something that couldn't be handled by ``mouse.handler`'. And that makes good sense. The second example is similar, but with the error being at the other end of the channel (an attempt to connect an input channel carrying potentially any ``GFX.EVENTS`' to a process that can only handle ``MOUSE.EVENTS`').

There are several restrictions associated with protocol inheritance, that are largely technical. The compiler will abort when it finds cases that it can't handle.

## Forward declarations for channel-types

added 30/12/2003

Support for forward declarations of channel-types has now been added to the occam compiler. This allows the use of a channel-type name before its actual definition. Unlike forward declarations for procedure (names), forward declarations of channel-types do not add any recursion-related problems (an equivalent would be outputting an output, and so on, which isn't legal occam).

The practical up-shot is that channel-types may carry ends of each other recursively; or that a channel-type may carry itself (essentially a recursive channel-type).

For example:

        CHAN TYPE BAR:                -- forward declaration

        PROTOCOL FOO.IN
          CASE
            a.bar.client; BAR!
        :

        CHAN TYPE FOO
          MOBILE RECORD
            CHAN FOO.IN in?:
        :

        PROTOCOL BAR.IN
          CASE
            a.foo.client; FOO!
        :

        CHAN TYPE BAR
          MOBILE RECORD
            CHAN BAR.IN in?:
        :

Or more simply:

        CHAN TYPE BLIP:               -- forward declaration

        CHAN TYPE BLIP
          MOBILE RECORD
            CHAN BLIP! blip.in?:
        :

which is equivalent to a ``RECURSIVE`' declaration:

        RECURSIVE CHAN TYPE BLIP
          MOBILE RECORD
            CHAN BLIP! blip.in?:
        :

## Basic nested MOBILEs support

added 09/08/2003

Support for some basic nested `MOBILE` types has now been added to the occam compiler. These represent only a fraction of the possible nested mobile type-system, but are a start. The two types currently supported are limited to single-level nesting and were implemented first because of a need for them.

They are:

- dynamic mobile arrays of dynamic mobile arrays
- dynamic mobile arrays of mobile channel-ends

Examples of these:

        MOBILE []MOBILE []BYTE messages:      -- array of arrays
        MOBILE []SHARED FOO! s.foo.clients:   -- array of channel ends

Note that the first example and the type ``MOBILE [][]BYTE`' are very different -- the latter is a single-level array of two dimensions (a 2D matrix of `BYTE`s), whilst the former is a two-level array, each of one dimension (an array of arrays of `BYTE`s).

Any channel-type `end-type' is valid for arrays of channel-ends, shared or unshared, client or server.

Initialisation of such data is as expected -- the outer array must be allocated first. For example:

        MOBILE []MOBILE []BYTE msgs:
        INT i:
        SEQ
          i := 10
          msgs := MOBILE [i]MOBILE []BYTE
          msgs[0] := "hello, world!*n"
          msgs[1] := msgs[0]
          out.string (msgs[1], 0, screen!)

## `DEFINED` dynamic mobile operator support

added 20/03/2003

For the majority of programming languages, once defined, a variable stays that way -- there is no clear way to undefine variables in most languages (with some exceptions, such as assigning from a function whose result is undefined). In occam, ordinary variables are considered undefined until assignment or input to. Once defined, they stay that way. Mobile variables, however, can transition between undefined and defined, based on the program logic (there is also other definedness states -- partially defined and possibly defined amongst them).

At some points in a program, it may be unknown (in the program logic) whether a particular variable is defined or undefined. For example, consider a mobile channel-end -- it may or may not be connected to a server. Or a dynamic mobile array -- it may either contain zero elements (undefined) or some elements (defined), separate from the definedness states of those elements.

The ``DEFINED`' operator provides a way of testing this at run-time, with subtle effects on the undefinedness checker. For example, the following code fragment is valid:

        CHAN TYPE FOO
          MOBILE RECORD
            CHAN INT c?:
        :

        FOO! f.c:
        SEQ
          IF
            DEFINED f.c
              f.c[c] ! 42
            TRUE
              FOO? f.s:
              SEQ
                f.c, f.s := MOBILE FOO
                FORK server (f.s)
                f.c[c] ! 42

Attempts to use the `DEFINED` operator with non-dynamic mobiles (i.e. static mobiles and ordinary variables) results in a compiler error. This may be modified in the future to work with other types.

## Pre-processing support

added 16/03/2003

A limited support for pre-processing has now been added to occam. Most usefully, it adds a mechanism for conditional compilation, using pre-processor constants. Given the issues relating to the combination of conditional compilation and occam's indentation, the pre-processor is implemented as part of the compiler, with a special directive for limited control of indentation.

For example:

        #DEFINE USE.INT.OUT

        PROC write.int (VAL INT x, CHAN BYTE out!)
          #IF DEFINED (USE.INT.OUT)
          out.int (x, 0, out!)
          #ELSE
          out.number (x, 0, out!)
          #ENDIF
        :

This would cause the use of ``out.int`' inside ``write.int`', instead of ``out.number`'. Removing the ``#DEFINE USE.OUT.INT`' (or commenting it out) would reverse this.

The above example demonstrates the obvious problem with indentation -- it would be nice if the contents of conditional compilation blocks were indented, but it would be somewhat extreme to always enforce this (temporary ``#IF FALSE`'ing of code, for example). Therefore, a special ``#RELAX`' directive is provided, that `relaxes' the indentation inside a conditional compilation block.

Re-writing the above, for example:

        #DEFINE USE.INT.OUT

        PROC write.int (VAL INT x, CHAN BYTE out!)
          #IF DEFINED (USE.INT.OUT)
            #RELAX
            out.int (x, 0, out!)
          #ELSE
            #RELAX
            out.number (x, 0, out!)
          #ENDIF
        :

In addition to simply defining pre-processor constants, they may be defined (and re-defined) with values. The values used may either be integers or strings. Anything else (besides nothing) is invalid. When referring to pre-processor constant values in code, the name must be prefixed with ``##`'. Such substitutions are always literal.

The compiler, before parsing of a file starts, defines various pre-processor constants. Some of these depend on compiler build-time or run-time options. These are:

Name | Type | Description
--- | --- | ---
`PROCESS.PRIORITY` | integer | if defined, the number of process priority levels supported
`OCCAM2.5` | none | if defined, indicates that support for user-defined types and other occam 2.1 features is available
`USER.DEFINED.OPERATORS` | none | defined if user-defined operators are supported
`INITIAL.DECL` | none | defined if `INITIAL` declarations are supported
`MOBILES` | none | defined if `MOBILE`s (all types) are supported
`BLOCKING.SYSCALLS` | none | defined if blocking system-calls are supported
`VERSION` | string | compiler version string
`NEED.QUAD.ALIGNMENT` | none | defined if the target architecture requires 64-bit alignment of data
`TARGET.CANONICAL` | string | canonical compiler target name, i.e. the host type that ``occ21`' was compiled for
`TARGET.CPU` | string | target CPU -- the CPU type that the compiler runs on
`TARGET.OS` | string | target OS -- the OS that the compiler runs on
`TARGET.VENDOR` | string | target vendor -- the hardware in use (e.g. `pc')

There is nothing to prevent a file re-defining or un-defining these. In general, it is not a good idea, however. Two additional built-ins are also maintained by the compiler, ``FILE`' and ``LINE`'. These refer to the current file-name and line-number respectively. For example:

        PROC message (VAL []BYTE file, VAL INT line, CHAN BYTE scr!)
          SEQ
            out.string ("Hello from ", 0, scr!)
            out.string (file, 0, scr!)
            out.string (", line ", 0, scr!)
            out.int (line, 0, scr!)
            scr ! '*n'
        :

        PROC main (CHAN BYTE kyb?, scr!, err!)
          SEQ
            ...  do stuff
            message (##FILE, ##LINE, scr!)
            ...  do more stuff
        :

The mechanism for conditional compilation is formed using ``#IF`', ``#ELIF`', ``#ELSE`' and ``#ENDIF`'. The expressions used in ``#IF`' and ``#ELIF`' are similar to occam expressions, but should not be mistaken for them. Such expressions must be boolean and fully bracketed. The values of pre-processor constants may be referred to simply by name (omitting the ``##`'), and compared with constants and each other using a limited range of boolean operators.

The three basic tests/expressions are ``TRUE`', ``FALSE`' and ``DEFINED (`name`)`', that tests whether or not a particular name is a pre-processor define. For comparing strings are the operators ``<>`' and ``=`'. For comparing integers, ``<>`', ``=`', ``<=`', ``<`', ``>`' and ``>=`'. For combining/modifying the results of sub-expressions are ``NOT`', ``AND`' and ``OR`'. Evaluation of boolean tests is done in strict lazy order, so that one can write, for example:

        #IF (NOT DEFINED (PROCESS.PRIORITY)) OR (PROCESS.PRIORITY < 32)
          #RELAX
          #ERROR not enough or no priority!
        #ENDIF

The two special pre-processor directives ``#ERROR`' and ``#WARNING`' are used to emit errors and warnings respectively. An error will abort compilation. Substitutions of pre-processor values in the message are done using the ``##`' prefix.

A more interesting example is where conditional compilation alters the logic of an occam program (alteration beyond clarity is not recommeded, however). For example:

        WHILE TRUE
          #IF DEFINED (USE.PRIALT)
          PRI ALT
          #ELSE
          ALT
          #ENDIF
            ...  alt guards

## Empty array specifications

added 13/02/2003

Traditionally in occam, producing an array of size zero has been difficult -- using a zero-length slice of another array. Attempts to write ``[]`' would be banned by the compiler. You could write ``""`' for an empty array of `BYTE`s, however.

This has now been remedied. The literal empty array ``[]`' may be used where appropriate (and legal). Additionally, ``[]`' is allowed as a parameter to non-`VAL` formals, and in abbreviations (both renaming). For example:

        SEQ
          out.string ([], 0, scr!)

          []BYTE x IS []:
          out.string (x, 0, scr!)

The abbreviation is not something that would be written normally, but can happen when `PROC` calls are inlined. Note that although ``[]`' is valid for non-val renamings, ``[[]]`' is not -- the outermost array contains a single element.

## Recursive channel types

added 03/09/2002

Recursive channel-types add a useful feature to the existing mobile channel-types -- the ability for a channel within a mobile channel-type to transport ends of its own type. This is particularly useful in client-server networks that involve one-to-one connections between clients and servers, established over shared channels -- it provides a means for the client to say ``i'm done'' to the server. For example:

        RECURSIVE CHAN TYPE BUF.MGR
          MOBILE RECORD
            CHAN INT req?:
            CHAN MOBILE []BYTE resp!, ret?:
            CHAN BUF.MGR! done?:
        :

        PROC server (SHARED CHAN BUF.MGR? clients?)
          BUF.MGR? link:
          WHILE TRUE
            SEQ
              CLAIM clients?
                clients ? link
              INITIAL BOOL ok IS TRUE:
              WHILE ok
                ALT
                  INT size:
                  link[req] ? size
                    ...  allocate buffer, give to client, take back again
                  BUF.MGR! cli:
                  link[done] ? cli
                    ok := FALSE
        :

        PROC client (SHARED CHAN BUF.MGR? to.servers!)
          SEQ
            ...  some initial local processing
            BUF.MGR? svr:
            BUF.MGR! cli:
            SEQ
              svr, cli := MOBILE BUF.MGR
              -- connect to a server
              CLAIM to.servers!
                to.servers ! svr
              ...  communicate with server using `cli'
              cli[done] ! cli
              -- `cli' and `svr' both undefined
        :

The interesting bit is the last action performed by the client, ``cli[done] ! cli`', that returns the channel-end to the server, to which it is connected. One way to think of this is to imagine the two processes connected by a hose-pipe, where the returning action turns the hose-pipe in on itself at the client end, until it `pops out' at the server end.

For completeness, a network using the above ``client`' and ``server`' processes is easily constructed (using anonymous channel-types and forked processes):

        PROC network (VAL INT n.cli, n.svr)
          SHARED CHAN BUF.MGR c:
          FORKING
          	SEQ
              SEQ i = 0 FOR n.cli
                FORK client (c!)
              SEQ i = 0 FOR n.svr
                FORK server (c?)
        :

## Anonymous channel types

added 03/09/2002

Anonymous channel-types provide a convenience. Quite often, we want a mobile channel-end of only one channel. The usual way would be to declare a mobile channel-type with a single channel, and use that. For example:

        CHAN TYPE THING
          MOBILE RECORD
            CHAN INT c?:
        :

        THING? svr:
        SHARED THING! cli:
        SEQ
          svr, cli := MOBILE THING
          PAR
            SEQ i = 0 FOR 2
              INT x:
              svr[c] ? x
            CLAIM cli
              cli[c] ! 42
            CLAIM cli
              cli[c] ! MOSTNEG INT

This is somewhat cumbersome, given the simple nature of what we're trying to do -- share a single channel. An equivalent version, using anonymous channel types, is:

        SHARED! CHAN INT c:
        PAR
          SEQ i = 0 FOR 2
            INT x:
            c ? x
          CLAIM c!
            c ! 42
          CLAIM c!
            c ! MOSTNEG INT

This is much easier to follow, and it is still largely clear what is going on.

Anonymous channel-types are created by use of the ``SHARED`' keyword in an ordinary channel declaration. By default, both ends of the anonymous channel type will be shared, unless restricted by an additional ``?`' or ``!`' (as in the above fragment). Two restrictions apply to anonymous channel-types. Firstly, whenever referred to by name, a channel-direction specifier must be used to indicate the client or server end (e.g. ``c!`' for the client-end). Secondly, anonymous channel types may not be assigned or communicated, but they may be renamed. The one exception is that the compiler allows an anonymous channel-type to be used as a parameter for a `FORK`ed process. Additionally, the KRoC run-time system supports anonymous channel-types for the standard top-level parameters (in addition to different combinations of top-level parameters). For example:

        PROC say.hello (SHARED CHAN BYTE out!)
          VAL []BYTE message IS "hello, forked and shared world!*n":
          CLAIM out!
            SEQ i = 0 FOR SIZE message
              out ! message[i]
        :

        PROC example (CHAN BYTE kyb?, SHARED CHAN BYTE scr!)
          FORKING
            SEQ
              FORK say.hello (scr!)
              FORK say.hello (scr!)
        :

As can be inferred from the above example, when an anonymous channel-type is used as a formal parameter, any restriction on the `SHARED` can be omitted.

Inside the body of a `CLAIM` an anonymous channel-type behaves like an ordinary occam channel. This includes renaming, which is not allowed for ordinary mobile channel-types. Typical usage, for example:

        #USE "course.lib"

        PROC simple (SHARED CHAN BYTE scr!)
          PAR
            CLAIM scr!
              out.string ("hello world 1!*n", 0, scr!)
            CLAIM scr!
              out.string ("hello world 2!*n", 0, scr!)
        :

## `FORK`ed parallel processes

added 01/09/2002

The ``FORK`' provides a means for dynamically creating a free-running parallel process. A type of `join' is available by use of a ``FORKING`' block, that acts as a barrier on which forked processes synchronise. If a `FORK` is not enclosed in any `FORKING` block, it runs freely.

The type of `FORK` supported is that of a new `PROC` instance. When instanced normally, `PROC` parameters use a renaming semantics. When `FORK`ed, the parameters use a communication semantics. This means that non-communicable parameter types are not allowed in a `FORK`. This restriction is typically channel and reference parameters. However, if the need really arises, such things can be declared ``#PRAGMA SHARED`' and passed anyway. Any mobile type is, of course, allowed.

The use of ``FORK`' is likely to be application-specific (particularly useful for building server-farms -- see Prioritised dynamic communicating processes: Part 2, downloadable from here). A simple example of the `FORK` is:

        PROC big.sum (VAL []INT data)
          ...  spend some time processing and write results to file
        :

        PROC application (CHAN BYTE kyb?, scr!, err!)
          FORKING
            MOBILE []INT data:
            SEQ
              ...  allocate and initialise `data'
              FORK big.sum (data)
              ...  continue with application
        :

After the `FORK`, ``data`' will remain defined. Since the formal parameter type is ``VAL []BYTE`', the data will be copied locally into the `FORK`ed process, leaving the source (a mobile in this case) alone.

Connecting a `FORK` process to the rest of the process network is best done using mobile channel types or anonymous channel types. For example:

        CHAN TYPE FOO
          MOBILE RECORD
            CHAN INT in?:
            CHAN INT out!:
        :

        PROC server (FOO? link)
          WHILE TRUE
            ...  do server stuff
        :

        PROC client (SHARED FOO! link)
          CLAIM link
            ...  do client stuff
        :

        PROC network ()
          FOO? f.s:
          SHARED FOO! f.c:
          SEQ
            f.s, f.c := MOBILE FOO
            FORK server (f.s)
            SEQ i = 0 FOR 10
              FORK client (f.c)
            ...  do some other stuff
        :

## MOBILE structured channel types

added 30/06/2002

Structured channel-types provide a mechanism for grouping related channels together inside a ``RECORD`' type. Ordinarily, these types are declared to be mobile. This provides a mechanism for moving bundles of channel ends around inside a process network. Starting with an example type declaration:

        CHAN TYPE FOO
          MOBILE RECORD
            CHAN INT request?:
            CHAN INT response!:
        :

A channel in occam has two ends -- one for reading and one for writing. Channel types (bundles) have two conceptual ends, termed `server' and `client'. Channel direction-specifiers must be used inside the channel-type declaration, so that the compiler can enforce correct usage on a particular end (client or server).

Declaration and initialisation of a channel-bundle (mobile channel-type) is relatively simple. For example, using the above declaration of ``FOO`':

        FOO! foo.c:         -- client end
        FOO? foo.s:         -- server end
        SEQ
          foo.c, foo.s := MOBILE FOO
          ...  processes using `foo.c' and `foo.s'

The allocating assignment is similar to that used with dynamic mobile arrays (see the mobiles section). A bundle of channels is dynamically created and the two ends assigned to ``foo.c`' and ``foo.s`'. The order in which the end-variables are given is unimportant; what matters is that one is a client-end and the other a server-end of the same mobile channel type.

The channel-ends within a channel-bundle are accessed using the familiar record subscription syntax. For (a slightly expanded) example:

        CHAN TYPE BUF.MGR
          MOBILE RECORD
            CHAN INT request?:
            CHAN MOBILE []BYTE response!:
            CHAN MOBILE []BYTE return?:
        :

        PROC server (BUF.MGR? link)
          WHILE TRUE
            INT n:
            MOBILE []BYTE b:
            SEQ
              link[request] ? n         -- input required size
              b := MOBILE [n]BYTE       -- allocate buffer
              SEQ i = 0 FOR SIZE b      -- zero buffer
                b[i] := 0 (BYTE)
              link[response] ! b        -- give to client
              link[return] ? b          -- take back from client
        :

        PROC client (BUF.MGR! link)
          MOBILE []BYTE buf:
          SEQ
            link[request] ! 1024        -- send request
            link[response] ? buf        -- get response
            ...  use `buf'
            link[return] ! buf          -- return buffer
        :

        PROC network ()
          BUF.MGR! cli:
          BUF.MGR? svr:
          SEQ
            cli, svr := MOBILE BUF.MGR
            PAR
              server (svr)
              client (cli)
        :

Unfortunately, an array constructor cannot be used (at present) in the ``server`' process to create the array, since the size of an array-constructor must be a compile-time constant.

The above ``network`' allocates a ``BUF.MGR`' channel bundle then runs client and server processes in parallel, connected by that bundle. Because the channel-ends are mobile, however, they can be communicated (and assigned). Thus, we might `wrap' the earlier ``client`' and ``server`' processes such that the ends (on which to communicate with each other) are inputted first. For example:

        PROC w.server (CHAN BUF.MGR? link.in?)
          BUF.MGR? link:
          SEQ
            link.in ? link
            server (link)
        :

        PROC w.client (CHAN BUF.MGR! link.in?)
          BUF.MGR! link:
          SEQ
            link.in ? link
            client (link)
        :

The modified ``network`' process would be:

        PROC w.network ()
          CHAN BUF.MGR! c.cli:
          CHAN BUF.MGR? c.svr:
          PAR
            w.server (c.svr?)
            w.client (c.cli?)

            BUF.MGR! cli:
            BUF.MGR? svr:
            SEQ
              cli, svr := MOBILE BUF.MGR
              c.cli ! cli
              c.svr ! svr
              -- `cli' and `svr' now undefined (moved)
        :

Although such channel-bundle ends are mobile, applying the `CLONE` operator (to produce a mobile copy) makes little sense -- how would access between copies be controlled ? or, would new server processes be automatically generated..?.

The paradigm of a shared server is one that has long existed in occam -- usually controlled by `ALT`ing over multiple channels. To capture this more effectively, channel-bundle ends may be declared ``SHARED`'. This allows for four different arrangements of client/server connections: single client, single server; multiple clients, single server; single client, multiple servers; and multiple clients with multiple servers.

To control access to shared channel-ends, `CLAIM` blocks must be used. Modifying the ``client`' process for example:

        PROC client (SHARED BUF.MGR! link)
          CLAIM link
            MOBILE []BYTE buf:
            SEQ
              link[request] ! 1024        -- send request
              link[response] ? buf        -- get response
              ...  use `buf'
              link[return] ! buf          -- return buffer
        :

Parallel processes compete for access to a `CLAIM` block by means of a semaphore, on which they queue in FIFO order. The rules pertaining to nested `CLAIM`s are that no nested claims are allowed inside a client-end claim, and that server claims may be nested (possibly with a client claim at the innermost point). This prevents partially-aquired resource deadlock on clients, but not on servers. Neither does it prevent cyclic deadlock. Avoiding deadlock through the use of `CLAIM` is a program design issue. Possible (or partial) compiler-based solutions to this are being thought about -- strict ordering and multi-claims (``CLAIM x, y`') may be one solution.

Inside a `CLAIM` block, the channel-end being `CLAIM`ed behaves largely as its non-shared version. However, it may not be input or assigned to, or renamed. This ensures that whatever is `CLAIM`ed doesn't move (and isn't given the opportunity to through renaming -- less obvious in separate compilation).

For shared ends, the `CLONE` operator is meaningful. In fact, when dealing with shared ends, the compiler will always `CLONE` for assignment or communication, regardless of whether the ``CLONE`' keyword is present. If the need ever arises to forcefully release a channel-end, it can be done by declaring it undefined to the compiler (that will insert code if it thinks otherwise). For example:

        SHARED FOO! f.c:
        SHARED FOO? f.s, f.other:
        SEQ
          f.c, f.s := MOBILE FOO
          f.other := f.s
          -- auto-clone, `f.s' still valid
          #PRAMGA UNDEFINED f.s
          -- `f.s' no longer defined

The above examples show only a small amount of what can be achieved using mobile channel-types. For a fuller analysis, see the papers ``Prioritised dynamic communicating processes: Part 1'' and ``Prioritised dynamic communicating processes: Part 2''. The texts of these papers are available on my publications page, and also from the WoTUG website.

## Process priority support

added 04/02/2002

Support for 32 levels of process priority has been added to the occam system. These range from 0 (highest priority) to 31 (lowest priority). Most of the hard work related to priority handling is done in the run-time kernel. In occam, priority is handled using the following compiler pre-defines:

        INT FUNCTION GETPRI ()
        PROC SETPRI (VAL INT p)

        PROC INCPRI ()
        PROC DECPRI ()

These simply end up as calls to two new transputer instructions, ``GETPRI`' and ``SETPRI`'. By default, the top-level occam process starts at the highest priority (0).

## `PLACED` channels and arrays

added 14/01/2002

Placed channels are what constitutes the compiler support for user-defined channels. Placed arrays allow occam programs to use externally allocated memory. While fairly separate in function, placed arrays and channels share a large amount of compiler code, thus their description together here.

Placed channels can be defined in one of two ways:

        INT addr:
        SEQ
          .. get "addr" from UDC stuff

          CHAN INT c!:
          PLACE c! AT addr:
          .. process using "c" for output

or:

        INT addr:
        SEQ
          .. get "addr" from UDC stuff

          PLACED CHAN INT c! addr:
          .. processing using "c" for output

The second example demonstrates the optional `OF` and optional `AT`. These channels are flagged as being placed by the compiler. When communication is performed on these channels, a second set of I/O instructions is used: `EXTIN`, `EXTOUT`, `EXTOUTWORD`, `EXTOUTBYTE`, `EXTENBC` and `EXTNDISC`. The operation of these is similar to the same non-`EXT` instructions. When the channel is `PLACE`d, the `EXTVRFY` instruction is generated to check the channel before using it for communication.

Currently not supported for placed channels are `MOBILE` communication and extended rendezvous. There is documentation on-the-way for using placed channels and some example code is provided in the KRoC/Linux distribution.

Placed arrays allow occam programs to access external memory, much like the transputer did. Rather than having a static address, the address used in the `PLACE`ment can be run-time computed. Both the two-line placement and the single-line `PLACED` syntaxes are supported, for example:

        INT addr:
        SEQ
          C.malloc (#8000, addr)      -- or however

          PLACED [#8000]BYTE data addr:
          .. process using "data"

The hash character is just the occam way of specifying hexadecimal numbers. For i386 systems, a special compiler-directive exists (``#PRAGMA IOSPACE`') which arranges for i/o space to be used, rather than memory space. This would typically be used, for example, to access the VGA registers, parallel port registers, etc., for example:

        INT io.base, io.size:
        SEQ
          io.base := #378          -- parport0
          io.size := 8

          .. get access to region with ioperm() / whatever ..

          PLACED [8]BYTE parport0 io.base:
          #PRAGMA IOSPACE parport0
          SEQ
            BYTE b:
            b := parport0[0]       -- will turn into "inb" at address 0x378

Note: because placed channels and arrays allow access to memory outside the normal workspace/vectorspace, there is a high degree of risk associated with using them. That is, if a bad address is supplied to the `PLACE`, undefined behavior may result.

## Modified `ALT` disabling sequence

added 10/01/2002

The ALT disabling sequence has been modified to perform a reverse disable in the case of ```PRI ALT`''s, and a reversed ```PRI ALT`'' in the case of plain ```ALT`''s.

Three new instructions have been added to the instruction set which are now used in place of the three existing alternative-disable instructions (```DISC`'', ```DIST`'' and ```DISS`''). These new instructions behave differently in that the guard will always be selected if it is ready, rather than being selected if it is ready and nothing had been ready previously, which was the default behavior with ```DISC`'', etc. These new instructions are called ```NDISC`'', ```NDIST`'' and ```NDISS`''. The input and output registers used are the same as the existing ones.

For example, the code:

        ALT
          a ? x
            P
          b ? y
            Q
          c ? z
            R

will enable ``a'', ``b'' and ``c'' in that order, do the alternative wait if none were ready, then disable in the same sequence using the ```NDISC`'' instruction. If ``c'' is ready, it will be be selected, since it is the last guard examined in the disable sequence, regardless of whether ``a'' and/or ``b'' were ready. The ```PRI ALT`'' is handled in a similar way, except that the guards are examined in reverse. For example:

        PRI ALT
          a ? x
            P
          b ? y
            Q
          c ? z
            R

will have the guards disabled in the order ``c'', ``b'' then ``a''. Thus, if ``a'' is ready, it will be selected regardless of whether ``b'' and/or ``c'' were ready.

For the most part, correct programs will run as they did. Programs which assume a ```PRI ALT`'' for a regular ```ALT`'' may behave incorrectly. There are some cases where this might not be immediately obvious though, for example:

        TIMER tim:
        INT t:
        BOOL got.first:
        SEQ
          got.first := FALSE
          tim ? t
          ALT
            tim ? AFTER (t PLUS 10000)
              got.first := TRUE
            tim ? AFTER (t PLUS 20000)
              IF
                got.first
                  SKIP

will often find itself going ```STOP`'', when ```got.first`'' is false in the `IF` (last 3 lines). This is because a fine-grained timer is not guaranteed with the current run-time system (KRoC/Linux), if you ask to sleep for 10ms, it might be after 20ms when you wake up. In the old `ALT` disabling sequence, the first guard would always be selected, since the ```DIST`'' on the second would not select that process. ```NDIST`'' will select the second process, if that time has expired.

## Extended rendezvous

added 19/12/2001

The extended rendezvous allows an inputting process to specify a process which will be executed after the communication has been performed, but before the outputting process resumes. The syntax for these uses the double question-mark ```??`'', for example, a simple echoing program might look like:

        PROC echoing (CHAN BYTE kyb?, scr!, err!)
          WHILE TRUE
            BYTE b:
            kyb ?? b
              scr ! b
              scr ! #FF   -- flush
        :

Indented under the extended input ```??`'' are two processes. The first (during process) is the one executed before the outputting process continues; the second (after process) is the one executed after the outputting process has resumed. This second process may be missing, in which case ``SKIP`' is assumed. The during process may not engage in the extended event (``kyb`' channel in the above example) since this would cause deadlock. The compiler checks for this.

Tagged protocol channels are handled using a slightly different syntax (since we want during and after processes for each variant). For example:

        PROTOCOL TAGGED
          CASE
            empty
            num; INT
        :

        PROC foo (CHAN TAGGED in?, CHAN BYTE out!)
          WHILE TRUE
            SEQ
              ..
              in ?? CASE
                empty
                  out ! '**'
                INT n:
                num; n
                  out ! BYTE (num /\ #FF)
                  out ! '**'
              ..
        :

## `RESULT` parameters and abbreviations

added 18/12/2001

As per the occam-3 specification, parameters and abbreviations may be declared with the `RESULT` `prefix'. The primary purpose of these is to provide more information to the compiler, so it can check that parameters are defined when `PROC`s return, and that `RESULT` abbreviations are left defined when they go out of scope.

Syntactically, the `RESULT` occurs where one might park a `VAL`, for example:

        PROC fac (VAL INT n, RESULT INT v)
          SEQ
            ...
            v := ...
        :

        PROC thing (...)
          INT v:
          SEQ
            ...
            RESULT INT i IS v:
            fac (6, i)
        :

Two different implementations of `RESULT` abbreviations are supported. The first, and default, treats the abbreviation as one without the `RESULT` keyword, but performs the additional check (for definedness) when the variable leaves scope, e.g.:

        RESULT TYPE a IS v:
        P

becomes:

        TYPE a IS v:
        SEQ
          P
          -- checks that `a' is defined

The second implementation, selected with the ``-zrv`' compiler flag generates a fresh variable then assigns into it. From the above:

        TYPE anon:
        SEQ
          TYPE a IS anon:
          P
          -- checks that `a' is defined
          v := anon

Although probably rare, there are cases where this second transformation will ultimately result in more efficient code, especially if ``v`' is large and non-local (accessed through the static-link).

## Nested `PROTOCOL` definitions

added 12/12/2001

Nested `PROTOCOL`s allow one `PROTOCOL` definition to be used within another. For example:

        PROTOCOL simple IS INT:
        PROTOCOL seq.proto IS INT; INT; simple:
        PROTOCOL seq.other IS BYTE; seq.proto; INT::[]BYTE
        PROTOCOL similar IS seq.other:

In the above, ``seq.other`' has the structure ```BYTE; INT; INT; INT; INT::[]BYTE`''. It should be noted that ``similar`' and ``seq.other`' are still distinct `PROTOCOL`s.

Tagged protocols can also be used, for example:

        PROTOCOL tagged
          CASE
            empty
            int; INT
            data; BYTE; similar; INT16
        :

        PROTOCOL more.tags
          CASE
            FROM tagged
            flibble; seq.proto
        :

## Modified behavior for `SKIP` in `ALT`s

added 10/12/2001

The checking of `SKIP` guards in `ALT`s and `PRI ALT`s has been modified. For ``ALT`' processes, the absence of a ```exp &`'' pre-condition on a ```SKIP`'' will result in a warning. If the ``-strict`' option is used, non-pre-conditioned ``SKIP`'s will generate errors (as was the default behavior). This code, for example:

        PROC wibble (CHAN INT in.0?, in.1?, out!)
          INT v:
          ALT
            in.0 ? v
              out ! v
            SKIP
              out ! 0
            in.1 ? v
              out ! v
        :

will generate a warning about the non-pre-conditioned `SKIP` (or error with ``-strict`'). For ``PRI ALT`'s, a non-pre-conditioned `SKIP` guard is allowed, but only as the last (or only) guard. The following is a valid example:

        PROC wibble2 (CHAN INT in.0?, out!)
          PRI ALT
            INT v:
            in.0 ? v
              out ! v
            SKIP
              out ! (-1)
        :

## Recursion in occam

added 30/11/2001

On the theme of dynamic occam, recursion has now been implemented. This is still fairly basic and there are several restrictions:

- Only PROCs can be recursive
- Only self-recursion is allowed

Recursive `PROC`s are declared by adding the ```RECURSIVE`'' or ```REC`'' keyword to the procedure header. Here is an example:

        REC PROC thing (VAL INT c, CHAN BYTE out!)
          SEQ
            out.string ("Hello world at ", 0, out!)
            out.int (c, 0, out!)
            out ! '*n'
            IF
              c = 0
                SKIP
              TRUE
                thing (c - 1, out!)
        :

This example is actually slightly silly, since we could do tail-call optimisation, thus removing the recursion. This optimisation has not been implemented yet however.

## `STEP` in replicators

added 14/11/2000

The ability to have STEP in replicators has been added to the compiler. This allows the addition of ```STEP` n'' to replicator expressions of (`SEQ`, `PAR`, `ALT` and `IF`). For example:

        SEQ i = 0 FOR 5 STEP 2
          foo (i)

is equivalent to:

        SEQ
          foo (0)
          foo (2)
          foo (4)
          foo (6)
          foo (8)

The `STEP` expression is evaluated before the replication, and may be any valid occam expression (including `VALOF` expressions) in `SEQ`, `ALT` and `IF` replications. For `PAR`allel replicators, the `STEP` expression must be constant.

For efficiency, three loop-end (`LEND`) instructions are provided. One is for a `STEP` of 1, another for a `STEP` of -1, and a final one for arbitrary `STEP`s. For instance, having:

        PRI ALT i = 4 FOR 5 STEP -1
          ...

is no more expensive than having:

         PRI ALT i = 0 FOR 5
           ...

or

         PRI ALT i = 0 FOR 5 STEP 1
           ...

## Channel direction specifiers

added 23/10/2001

The direction of communication on channel parameters to `PROC`s can now be specified in their formal and actual parameters. The compiler will bear this in mind when checking the channel usage inside a `PROC`. It also adds more information to a `PROC`s interface from the code perspective. For example:

        PROC foo (CHAN INT in?, out!, CHAN BOOL terminate?)
          ...
        :

and:

        CHAN INT c:
        PAR
          foo (c?, ...)
          other (c!)

The usage of this also applies to channel abbreviations, for example:

        PROC foo.2 ([8]CHAN INT64 in?, CHAN INT64 out!)
          ...
          CHAN INT r? IS in[i]?:
          ...
        :

the compiler will check that output channels are not abbreviated as input channels and visa-versa.

In strict mode (using the ```-s`'' flag to `kroc`), usage of channel-direction specifiers is enforced.

When referring to array slices, the direction specifier should go inside with the array, eg:

        PROC thing ([]CHAN INT in?)
          []CHAN INT i? IS [in? FROM 2]:
          ...
        :

## Optional `OF`

added 23/10/2001

The usage of the ```OF`'' keyword in channel specifiers is also optional now. For example:

        PROC bar (CHAN INT in?, out!)
          ...
          out ! 42
          ...
        :

        PROC switch ([2]CHAN INT in?, out!)
          ...
        :

## Array constructors

added 08/10/2001

Array constructors allow arrays to be created using a replicator and an expression. An example of this is:

        [10]INT array:
        SEQ
          ...
          array := [i = 0 FOR SIZE array | f(i)]
          ...

where `f()' is some expression, which might or might not involve `i'.

Internally, the array constructor is turned into a `VALOF` process, so array-constructors may be used as parameters, or anywhere an expression is valid. The (obvious) limitation here is that array-constructors may not cause side-effects. The non-obvious limitation is that the count must be a compiler-known constant. This will be fixed at some point in the near future. The `STEP` addition may also be used in array constructors. The general syntax for this type of expression is:

        "[" <repl> "=" <start> "FOR" <count> [ "STEP" <stride> ] "|" <expr> "]"

The line can be broken after the ```|`'' to avoid things getting to long. A more extreme example of array constructors might be:

        PROC show.3d (VAL [][][]INT n, ...)
          ...
        :

        ...
        SEQ
          show.3d ([x = 0 FOR 10 | [y = 0 FOR 10 | [z = 0 FOR 10 |
                   ((x - z) * (y + z)) ]]])
          ...

`INITIAL` declarations now permit these to be used with dynamic `MOBILE` arrays. For example:

        INITIAL MOBILE []INT x IS [i = 0 FOR 100 | foo(i)]:
        ...

## Variable replicated `PAR`s

added 01/10/2001

This new feature allows for `PAR` replicators to have a variable count field. This uses the dynamic memory support provided by the run-time system. A simple example of this is:

        PROC foo (CHAN INT in?)
          INT count:
          SEQ
            in ? count
            PAR i = 0 FOR count
              some.process (i)
        :

In order to help support this, dynamic `MOBILE []CHAN` arrays are allowed, but no checking is performed on them when used with a replicated `PAR`. Run-time checking will probably be added at some point.

An example of this type of usage (to build a pipeline of processes) is:

        PROC sort.pump (VAL INT size, CHAN INT in?, out!)
          IF
            size > 1
              INITIAL MOBILE []CHAN INT pipe IS MOBILE [size - 1]CHAN INT:
              PAR
                sort.cell (in, pipe[0])
                PAR i = 0 FOR (size - 2)
                  sort.cell (pipe[i], pipe[i+1])
                sort.cell (pipe[size-2], out)
            TRUE
              sort.cell (in, out)
        :

## `MOBILE` data types

added 08/09/2001

Mobiles are a new type class in occam -- i.e. for most ordinary types, a compatible mobile version now exists. Mobiles are different in one key way: assignment and communication of mobiles uses a movement semantics, instead of the usual copying semantics. This implies that when a process outputs a mobile variable, it loses it -- and any subsequent attempt to read from the variable is undefined (illegal).

To the programmer, mobiles offer a potential performance gain, with only minor intrusion to code. The run-time system (on a single-memory machine) implements mobiles by pointer-swapping references, that is a very low-cost operation (mobile commstime is around 20ns more than the ordinary commstime). More importantly, however, mobiles provide an efficient means to implement the familiar ``packet passing'' abstraction (in the past, occam programs have moved pointers around at run-time, for efficiency, but this was wholly un-checked and required the use of in-line assembler).

Essentially, two basic types of mobile variables are supported:

- Static mobiles, whose size is known at compile-time
- Dynamic mobile arrays, whose size is only known at run-time

Static mobiles are allocated (by the compiler) into a global memory `heap' known as mobilespace. Like workspace and vectorspace, the required size of this area is known at compile-time. Dynamic process creation (recursion, variable replicated `PAR`s, and forked processes) complicates this slightly. For mobilespace requiring dynamic processes, hooks are allocated inside the enclosing mobilespace. Once dynamic memory has been allocated for mobilespace, it cannot be returned to the general memory pool -- since references inside mobilespace may have migrated into other processes. More details on the technical aspects of mobilespace can be found in the `Mobile Data, Dynamic Allocation and Zero Aliasing: an occam Experiment' paper.

Dynamic mobile arrays are somewhat simpler, since they are largely run-time only -- but incur a greater overhead for allocation/release than static mobiles (tens of nano-seconds).

Mobile variables can be declared in two ways: using the ``MOBILE`' keyword directly in the declaration; or declaring variables of a named ``MOBILE`' type. The first, for example:

        MOBILE INT x, y:
        SEQ
          x := 42
          y := x
          -- `x' now undefined

        MOBILE []REAL64 data:
        SEQ
          data := MOBILE [128]REAL64
          data[42] := 99.0

The first fragment declares two simple mobile integers. The second is slightly more interesting, requiring a special allocation assignment to create the array. Until they are allocated, dynamic mobile arrays have zero-size and are considered to be undefined (as far as the undefinedness checker is concerned). Any attempt to access a non-existant element will result in the usual run-time (range) error.

Communication behaves in much the same way as assignment, for example:

        CHAN MOBILE []INT vals:
        PAR
          --{{{  producer
          MOBILE []INT x:
          SEQ
            x := MOBILE [10]INT
            SEQ i = 0 FOR SIZE x
              x[i] := i
            c ! x
            -- `x' is no longer defined
          --}}}
          --{{{  consumer
          MOBILE []INT v:
          INT x:
          SEQ
            c ? v
            x := v[5]
          --}}}

As far as type compatability goes: wherever a non-mobile variable is valid, its mobile equivalent is valid too. For example:

        MOBILE REAL64 m.v:
        REAL64 s.v:
        SEQ
          m.v := 24.5 (REAL64)
          s.v := m.v
          -- m.v still valid (copy)

Assignment is only considered mobile if both variables (LHS and RHS) are themselves mobile -- i.e. mixed mobile/non-mobile assignment results in the usual copy semantics. Communication is only mobile if the channel protocol is mobile. The following, for example, uses non-mobile communication:

        CHAN [5]INT c:
        PAR
          --{{{  producer
          MOBILE [5]INT x:
          SEQ
            SEQ i = 0 FOR SIZE x
              x[i] := i
            c ! x
            -- `x' is still defined
          --}}}
          --{{{  consumer
          MOBILE [5]INT v:
          INT x:
          SEQ
            c ? v
            x := v[5]
          --}}}

Changing the channel declaration to ``CHAN MOBILE [5]INT c:`' would, as expected, result in mobile communication. This is static mobile communication, however, since the size of ``[5]INT`' is known at compile-time.

When a non-mobile variable is used in mobile communication or assignment, the compiler automatically promotes the variable to its mobile equivalent. For dynamic mobile arrays, this includes automatic allocation of the array, making the programmer's life somewhat easier.

The second method of declaring mobiles involves declaring mobile types. For example:

        DATA TYPE STRING IS MOBILE []BYTE:

        DATA TYPE PACKET
          MOBILE RECORD
            [1024]BYTE data:
            INT offset:
        :

Then using that type as usual. For example, and demonstrating automatic mobile promotion:

        STRING s:
        PACKET p:
        SEQ
          s := "hello, occam world!*n"
          [p[data] FOR SIZE s] := s
          p[offset] := SIZE s

The array constructor may also be used with dynamic mobile arrays and automatic promotion. For example:

        CHAN MOBILE []REAL64 c:
        PAR
          --{{{  producer
          c ! [i = 0 FOR 128 | ((REAL64 i) * PI) / 128.0]
          --}}}
          --{{{  consumer
          MOBILE []REAL64 data:
          SEQ
            c ? data
            ...  use `data'
          --}}}

In some cases, it may be desirable to prevent mobile assignment or communication, where movement semantics are the default. This is done through use of the ``CLONE`' operator, that produces a duplicate of its mobile argument. The compiler will not automatically promote a non-mobile operand given to `CLONE`, thus ``CLONE 5`' is illegal. The `CLONE` operator also helps resolve potential ambiguities. The following fragment, for example, leaves ``x`' and ``y`' both defined:

        MOBILE INT x, y:
        SEQ
          x := 42
          y := (x + 5)

But if we later removed the ``+ 5`':

        MOBILE INT x, y:
        SEQ
          x := 42
          y := (x)

It is not immediately clear whether this results in movement or copying semantics -- i.e. whether ``x`' is defined after the second assignment. In fact, the compiler will use copying semantics for this -- two reasons: firstly, because of the brackets; and secondly, because any mobile type less than or equal to 8 bytes is automatically made non-mobile (because the equivalent non-mobile assignments and communications are quicker).

The `CLONE` operator can clear this ambiguity up, however:

        MOBILE INT x, y:
        SEQ
          x := 42
          y := CLONE x

A more practical example might be:

        DATA TYPE STRING IS MOBILE []BYTE:
        CHAN STRING c:
        PAR
          --{{{  producer
          STRING x:
          SEQ
            x := "hello, world!*n"
            c ! CLONE x
            [x FROM 7 FOR 5] := "occam"
            c ! x
          --}}}
          --{{{  consumer
          STRING v, w:
          SEQ
            c ? v
            c ? w
            ...  use `v' and `w'
          --}}}

Or in a mobile ``tap`' process (using the extended rendezvous), for example:

        PROC mi.tap (CHAN MOBILE []INT in?, out!, report!)
          WHILE TRUE
            MOBILE []INT x:
            in ?? x
              out ! CLONE x
              report ! x
        :

The compiler (and run-time system) also support multi-dimensional dynamic mobile arrays. These can be used with automatic-promotion and array constructors too. For example:

        DATA TYPE I.MATRIX IS MOBILE [][]INT:

        PAR
          --{{{  producer
          I.MATRIX x:
          SEQ
            x := [i = 0 FOR 64 | [j = 0 FOR 64 | (i * j)]]
            c ! x
          --}}}
          --{{{  consumer
          I.MATRIX m:
          INT sum:
          SEQ
            c ? m
            sum := 0
            SEQ i = 0 FOR SIZE m
              SEQ j = 0 FOR SIZE m[i]
                sum := sum + m[i][j]

            ...  do something useful
          --}}}

Last modified: Sun Mar 20 13:46:45 2005 by Fred Barnes.