Fred's Home Page
An Introduction to the occam Language[ about | csp | processes | types | expressions | functions | parallel | alting | time | identities | syntax ] About this tutorialThis document is intended to be an introduction to programming occam, for those who already know some other programming language (C, Java, etc.). The occam language, named after the 14th century Oxford philosopher William of Ockham, is a simple language for the construction of parallel (or sequential) programs. The semantics of occam are taken from the CSP process algebra (see below), which is essentially a mathematical representation of parallel programs. The syntax of occam tends to put some people off, as the compiler insists on "correct indentation". Below is a small occam fragment demonstrating the indentation:
INT x, y:
SEQ
x := 4
y := (x + 1)
CHAN INT c:
PAR
some.procedure (x, y, c!)
another.procedure (c?)
y := 5
Although this may appear a bit unpleasant, you soon get used to it, and it certainly helps with reading other peoples code since it has a consistent appearance. Having a decent editor helps lots, especially one which does auto-indenting and syntax colouring for example. Some people like to fold their occam with folding editors. This tutorial uses a newer version of the occam language (that we are loosely calling `occam-M' and/or `occam-Pi'). Currently, The only occam compiler that supports these new language features is KRoC/Linux (official page here). CSP - communicating sequential processesCSP is a process algebra which is used to describe parallel programs. occam is a language which supports (sometimes enforcing) the rules of CSP. In this world, a program is a network of processes, which are connected using channels. A channel is a point-to-point, uni-directional, synchronous unbuffered comms link. Processes only need to be aware of the channels connecting them to other processes, and how to communicate on those channels (generally using the same protocol as the process on the other end). The nature of channels means that the communication is (considered) instantaneous, and takes place when both the inputting and outputting processes have reached the communication statement. The first process to arrive at a channel will wait for the second one. When the second process arrives, it wakes the other one up, the data is copied and both processes carry on as before.
A simple implementation of `foo' and `bar' could be nothing (the SKIP process). Even though a channel connects them, it doesn't have to be used. A slightly more useful example is one where `foo' outputs something down the channel, and where `bar' reads something from the channel. For example:
More information on CSP can be found on the Formal Methods Wiki CSP archive pages. For the purists: CSP doesn't really have channels. CSP processes engage in events. A process only performs an event when all processes that have that event synchronise -- i.e. a barrier synchronisation. Channels in occam are events on which two processes only synchronise (the inputter and the outputter). When expressing occam programs in CSP, channel events tend to be tagged with the data that they carry. Thus, for a ``CHAN INT c', the events are c(mostneg int), ..., c-1, c0, c1, ..., c(mostpos int). Some CSP `hackery' is involved to get a concept of `variables', e.g. `c?x', where `x' is the data communicated. This doesn't affect the CSP, however. ProcessesAn occam program is ultimately a collection of process definitions, and instances of processes. Where C and Java programs have main(), occam takes the last process definition in a file which is compiled without the -c option. Primative processes The following table lists the primative processes, along with a breif example:
Assignment simply assigns an expression to a variable. As long as the types are compatible, anything can be assigned (not limited to word/double-word quantities). Multiple assignment is also allowed (and often necessary), eg, "x, y, z := 4, z, x". Input and output fall under the umbrella of communication, and are one of the key features of occam which make it suitable for parallel programming. Channels are uni-directional, unbuffered and synchronised "wires". When one process communicates on a channel, it will block until the other party engages in the communication. At that moment, the data is transferred and both processes continue. The SKIP process does nothing and terminates. This is used to specify "no-nothing". The STOP process does nothing but never terminates. In the run-time implementation, executing STOP causes the program to abort. Constructing processes The above primative processes aren't much use on their own, so several ways of putting processes together are provided. The basic process constructor is SEQ (sequential). This arranges for the processes inside it to execute in sequence, for example:
SEQ
x := 10
d ! x
c ? x
Being a parallel language, there is also the PAR process constructor. This arranges for the processes inside it to be executed in parallel, for example:
PAR
c ! x
d ? y
a := b
For conditionals/selections, occam provides IF, CASE and WHILE process constructors. These are synonymous with C's if, switch and while statements, although the syntax of the occam IF takes some getting used to, as it's radically different from the way we normally think about `if' statements in imperative languages. A WHILE process, for instance, might look like:
WHILE (x < 20)
SEQ
do.something (x)
x := (x + 1)
One notable feature about occam is that it lacks C's continue and break statements for jumping about inside loops. This is a good thing for program verification, since the loop can only finish when the condition evaluates FALSE. There is also an ALTernative (external/internal choice) for constructing processes. This is covered in this bit. Data types and declarationsThe occam language provides the usual collection of data types, along with the capability to compose your own types (like struct's in C). Here are the primative types:
Declarations in occam occur before a process, making the declared variable/type/whatever available to the following process. This differs from C and Java, where variables are declared inside a "process". The following example declares two integers and does some assignments:
INT x, y:
SEQ
x := 10
y := (x * 20)
As a side note, the single colon `:' marks the end of a declaration. Array types All occam arrays must be of a known size (dimensions). This is partly due to the non-dynamic nature of occam, but it also reduces the potential for errors. The only time when the size of an array need not be specified is when it appears as a formal parameter in a PROC or FUNCTION definition. The dimensions of occam array declations appear before the array type. Here are some examples:
[4]BYTE some.bytes: -- array of 4 bytes
[64][64][64]REAL64 matrix: -- 64x64x64 array of real64s
User-defined types Primative types, arrays and RECORD types can be used to form user-defined types. For example:
DATA TYPE TAG.T IS INT64:
This would declare the type TAG.T, which is an INT64 in reality. Declaring types in this way is similar to C's typedef operator. Occam, however, considers the types to be different (as it should), thus attempting to assign an INT64 to a TAG.T will not work without an explicit cast. The RECORD type constructor allows the user to define structured types, for example:
DATA TYPE MY.TYPE
RECORD
INT16 some.int16:
INT32 some.int32:
[255]BYTE message:
BYTE len:
:
Fields within the record are accessed in a similar way to arrays (with square brackets). For example:
MY.TYPE f:
SEQ
f[some.int16] := 25052
f[len] := 5
[f[message] FOR f[len]] := "hello"
The last line of this uses an array slice (see expressions). Protocol types Protocol types are what can be communicated over channels (see parallel). Protocols are probably best explained by their bnf-type notations:
simple-protocol ::= <type> // basic types
|| <type<::>type> // counted-array
sequential-protocol ::= simple-protocol [; simple-protocol [ ... ]]
tagged-protocol ::= CASE
<tag0> [; sequential-protocol]
<tag1> [; sequential-protocol]
...
protocol ::= sequential-protocol
|| tagged-protocol
Here are some examples of various simple and sequential protocol definitions:
PROTOCOL ADDR IS INT: -- simple protocol ADDR
PROTOCOL PACKET IS INT::[]BYTE: -- INT counted array of BYTEs
PROTOCOL COORD.3D IS REAL64; REAL64; REAL64: -- 3 REAL64 values
PROTOCOL TAGGED.PACKET IS BYTE; INT::[]BYTE: -- BYTE followed by INT counted array of BYTEs
Tagged-protocols (or variant protocols) have a different syntax for their definitions:
PROTOCOL DISPLAY
CASE
clear.screen
int.x.y; BYTE; BYTE; INT
string.x.y; BYTE; BYTE; BYTE::[]BYTE
:
Unlike `DATA TYPE's, you cannot declare items of a PROTOCOL type. The data items required are described by the PROTOCOL definition. For example, a simple input and output process for the above `DISPLAY' protocol might be:
PROC writer (CHAN DISPLAY out!)
SEQ
out ! clear.screen
SEQ i = 0 FOR 10
out ! int.x.y; 1; (BYTE i) + 1; i
VAL []BYTE str IS "hello, new world!":
out ! string.x.y; 1; 11; (SIZE str)::str
:
PROC reader (CHAN DISPLAY in?)
WHILE TRUE
in ? CASE
clear.screen
.. code to clear screen
BYTE x, y:
INT num:
int.x.y; x; y; num
.. code to put number `num' at position (x,y)
BYTE x, y:
[255]BYTE str:
BYTE str.len:
string.x.y; x; y; str.len::str
.. code to put string `[str FOR str.len]' at position (x,y)
:
The purpose of the variant (CASE) protocol is to allow a single channel to carry multiple types. The same effect can be achieved with multiple channels between the two communicating processes. However, the use of multiple channels would require more memory at run-time and (possibly) overheads in ALTing. Before the inputting process can perform input from a CASE protocol channel, it must know which particular CASE (identified by the tag in the protocol definition) is being sent by the outputting process. It does this by using CASE input, as shown above. For example, a channel of the variant protocol:
PROTOCOL BORING
CASE
nothing
something; INT
lots; INT; INT
:
can be read using a `CASE' to select between the various possibilities:
INT x, y:
in ? CASE
nothing -- tag
SKIP -- process
something; x -- tag and 1 INT
SKIP -- process
lots; x; y -- tag and 2 INTs
SKIP -- process
When a process executes this code, it will block at the `in ? CASE' until an outputting process synchronises. The first thing the outputting process does is send the tag, so that the inputting process can make the appropriate selection. The corresponding output for the above might be:
out ! something; 42 -- tag and 1 INT
If a tag is sent which is not handled by the inputting process (because it was omitted from the CASE input) then the inputting process will STOP (produces a run-time error in halt error-mode). ExpressionsExpressions in occam encompass "computation", distint from "communication". Occam requires that expressions are non-side-effecting, ie, they don't modify the state of anything outside themselves. Generally this means that no assignments or communication are allowed inside an expression. A value process is the exception to this, as it may use assignment, but only internally -- it can't modify anything outside itself. The occam compiler enforces these restrictions. Some expression example:
42 -- simple value
5 + 7 -- addition
array[i/32][i\32] -- array element
[array FROM j] -- array slice
foo (32) + ((bar (i) + thing (j)) * 42) -- function calls
[array FROM foo(i) FOR bar(i+32)] -- mixed
[1, 2, foo (3), 4, bar(5)] -- constant array with function calls
Most expressions are obvious and behave as expected. There are however some oddities, mainly array-slices. This allows part of an array to be selected and used in an expression. For example, if we have the byte-array constant:
VAL []BYTE str IS "hello, new world!":
Then the following are true:
[str FROM 7] = "new world!"
[str FOR 5] = "hello"
[str FROM 7 FOR 3] = "new"
[str FROM 7 FOR (SIZE str) - 7] = "new world!"
If not specified in the slice, ``FROM 0'' is assumed. If the ``FOR'' part is not specified, the rest of the array (starting at FROM) is used. Array-slices and constant arrays just don't exist in C and Java (slices are do-able in C, but involve some pointer-arithmetic). This enables some interesting things to be written, such as a subscripted array slices, etc:
[array FROM s FOR l][i]
[[[array FROM s FOR l] FOR i][j],42]
A recent addition to the occam-compiler now allows array-constructors to be used for generating arrays. These follow a syntax similar to that found in functional languages. For example:
[i = 0 FOR 10 | foo (i)]
[j = 0 FOR 10 | [k = 0 FOR 15 | (foo(j) * bar(k))]]
Internally, these are transformed into value-processes which yield an array. As such, the count part of the replicator must be constant. One thing that is worth noting is that occam expressions have no concept of operator precedence. This is actually a good thing: expressions must be fully bracketed, that makes very explicit the partial evaluations. The following, for example, are illegal:
INT a, b:
SEQ
a := x + y + z
b := x * -a
The second assignment is slightly more subtle -- unary-minus is an operator. Functions (and value processes)Functions in occam are deeply strange compared to C or Java. As they yield an expression, they may not cause side-effects. Functions can be defined in one of two ways:
A short function has the syntax:
<return type list> FUNCTION <name> (<value parameters>) IS <expression list>:
The ``return type list'' is a comma-seperated list of types, consistent with the ``expression list''. Occam allows a function to return any number of results (except zero), whereas C and Java only allow one. For example:
INT FUNCTION magic.number () IS 42:
INT FUNCTION square (VAL INT x) IS (x * x):
BYTE, BYTE FUNCTION split.int16 (VAL INT16 v) IS (BYTE (v >> 8)), (BYTE (v /\ #FF)):
REAL64 FUNCTION pythagoras (VAL REAL64 a, b) IS SQRT ((a * a) + (b * b)):
Calls to these result in expressions. For functions which return more than one result (two BYTEs in the case of split.int16 above) using them inside expressions is meaningless (and not allowed). The following example demonstrates something which is illegal (and meaningless):
INT, INT FUNCTION wibble (VAL INT r) IS (r * r), (r + r):
INT x:
SEQ
x := (wibble (42) * 10)
...
The other type of functions (long functions) involve value processes. A value process is synonymous with an anonymous function -- it has no name. Wrapping it inside a function "gives it a name". Some FUNCTION examples first:
INT FUNCTION foo (VAL INT i)
INT r:
VALOF
SEQ
r := 0
SEQ l = 0 FOR i
r := r + (l * l)
RESULT r
:
BYTE, BYTE FUNCTION split.int16 (VAL INT16 n)
BYTE high, low:
VALOF
SEQ
high := BYTE (n >> 8)
low := BYTE (n /\ #FF)
RESULT high, low
:
Value processes are like these, but with the ``FUNCTION'' and ``:'' lines missing. As they're expressions, their usage is likely to occur on the RHS of assignments, outputs and abbreviations, and in parameters to PROCs/FUNCTIONs. This makes the layout and indenting of these a bit tricky, possibly why they're not used much. For example:
INT x, j:
SEQ
..
in ? j
x := magic.number() + (INT r:
VALOF
SEQ
r := 0
SEQ i = 0 FOR j
r := r + ((i + 1) * i)
RESULT r
)
Dispite the nasty syntax they remain highly useful. This is why array-constructors were added, since you can only really get the same effect using a VALOF (functions can't return arrays of an unknown size). For example, the relatively simple occam:
[32]INT stuff:
SEQ
stuff := [i = 0 FOR SIZE stuff | (i - 2)]
...
that fills the array ``stuff'' with values from -2 to 29 inclusive, is equivalent to the following:
[32]INT stuff:
SEQ
stuff := ([SIZE stuff]INT tmp:
VALOF
SEQ i = 0 FOR SIZE tmp
tmp[i] := (i - 2)
RESULT tmp
)
...
Initial declarations can also take array-constructors, but they cannot use their own name. We cannot write, for example, the above as:
INITIAL [32]INT stuff IS [i = 0 FOR SIZE stuff | (i - 2)]:
...
The compiler rejects ``SIZE stuff'' on the grounds that ``stuff'' isn't declared. Quite rightly, since things in occam only come into scope at the end of their declaration (see types and declarations above). You have to write ``32'' instead of ``SIZE stuff'' in this case. The arrays generated in these examples only occur on the RHS of an assignment. Value parameters are also valid places where they can be used. For example:
PROC bar2 (VAL [][]INT n, CHAN BYTE out!)
SKIP
:
PROC ac1 (CHAN BYTE kyb?, scr!, err!)
SEQ
bar2 ([i = 0 FOR 10 | ([4]INT r:
INT vvv:
VALOF
SEQ j = 0 FOR SIZE r
r[j] := (i + j)
RESULT r
)], scr!)
:
Even though what's going on is well-defined and mostly clear, the syntax isn't entirely pleasant. This, of course, could be written:
PROC bar2 (VAL [][]INT n, CHAN BYTE out!)
SKIP
:
PROC ac1 (CHAN BYTE kyb?, scr!, err!)
SEQ
bar2 ([i = 0 FOR 10 | [j = 0 FOR 4 | i + j]], scr!)
:
It compiles and runs just fine! Going parallelThis bit is all about how parallel components are composed to build useful systems. This is more a description of what's provided rather than insight into designing parallel code. Parallelism is introduced through the PAR process constructor. There is a barrier synchronisation at the end of a PAR, on which all the sub-processes synchronise. As well as synchronising at the end of a PAR block, processes may also wish to synchronise with other processes at various points during their lifetime. This is normally achieved by using channels, which allows two processes to synchronise and communicate some data between them. In many programs, the data communicated is not used, instead the channel is used purely for synchronisation. A simple example, of two communicating processes might be:
PROC producer (CHAN INT out!)
INT x:
SEQ
x := 0
WHILE TRUE
SEQ
out ! x
x := x + 1
:
PROC consumer (CHAN INT in?)
WHILE TRUE
INT v:
SEQ
in ? v
.. do something with `v'
:
PROC network ()
CHAN INT c:
PAR
producer (c!)
consumer (c?)
:
The `network' process declares a channel of INTs called `c', then passes it as a parameter to the `producer' and `consumer' processes, which are run in parallel. The above example has fairly simple processes inside the PAR - just two procedure calls. The PAR can take any process as a sub-component. Here are some examples:
PROC mystery ()
CHAN INT c, d:
PAR
INT x:
SEQ
x := 42
c ! x
c ! 99
SEQ
INT any:
c ? any
d ! 42
INT any:
c ? any
INT y:
SEQ
d ? y
.. do something with `y'
:
PROC mystery2 ()
[4][4]CHAN INT c:
PAR i = 0 FOR 4
PAR j = 0 FOR 4
PAR
c[i][j] ! ((i * 4) + j)
INT n:
SEQ
c[j][i] ? n
.. do something with `n'
:
AltingAlting is perhaps one of the most useful features of the occam language (and CSP). It allows a process to wait for multiple events, but only engage in one of them. From a very abstract view, occam's ALT is similar to POSIX's `select()' function. Two flavours of alting are provided for in occam. Firstly, plain ALT, which waits for multiple events then makes an arbitrary [1] selection between those available. Secondly, PRI ALT, which wated for multiple events then selects the first availble, giving highest priority to the one at the top of the list. The generic syntax for an ALT is trivial:
ALT
guard.0
process.0
guard.1
process.1
...
guard.n
process.n
and:
PRI ALT
guard.0
process.0
guard.1
process.1
...
guard.n
process.n
The types of guard (event selector) supported are:
Here are some examples:
INT v:
ALT
in.a ? v
out ! v
in.b ? v
out ! v
PRI ALT
tim ? AFTER timeout
SEQ
out ! timed.out
timeout := timeout PLUS 1000000 -- 1 second
in ? v
SEQ
out ! data; v
tim ? timeout
timeout := timeout PLUS 1000000
PRI ALT
in ? v
out ! v
SKIP
out ! 0
The last example here is that of `polling'. This code will either find the `in' channel ready, then perform the output on `out', or, it will find the `in' channel not ready and output zero on the `out' channel. In general, polling is a bad thing. This is because most of the time it's not required, the desired result is usually achievable through the use of parallelism (PAR), plus some suitable ALT or PRI ALT. Sometimes however it is desirable, for instance on a loop body whose termination is signalled on an incomming channel. For an example of polling used in this way, consider the following loop:
WHILE TRUE
INT v:
SEQ
to.foo ! 42
from.foo ? v
IF
v = 0
from.foo ? v
TRUE
SKIP
to.bar ! v
If we wanted to terminate it on an input from the `term' channel (say of BOOLs), we could do the following:
INITIAL BOOL running IS TRUE:
WHILE running
INT v:
SEQ
to.foo ! 42
PRI ALT
BOOL any:
term ? any
SEQ
running := FALSE
from.foo ? v
from.foo ? v
SKIP
IF
v = 0
from.foo ? v
TRUE
SKIP
to.bar ! v
But this is not entirely nice.. Hence we can use polling (at any point in the loop) to check the `term' channel and if signalled, set `running' to false:
INITIAL BOOL running IS TRUE:
WHILE running
INT v:
SEQ
-- poll `term' channel
PRI ALT
BOOL any:
term ? any
running := FALSE
SKIP
SKIP
-- maybe put this code in an "IF running" type block
to.foo ! 42
from.foo ? v
IF
v = 0
from.foo ? v
TRUE
SKIP
to.bar ! v
This is much neater, seperating out the issues with loop-termination from the actual processing done in the loop. But... since those functionalities are seperated, interactions between the process connected on the `term' channel and processes connected on the `to.foo', etc. channels may result in deadlock. The code above simply demonstrate where polling might be useful, not how to use it safely :). For a discussion on that subject, in particular graceful termination and graceful resetting, see [2].
Time and timersTime in occam is an ever-increasing 32-bit value that wraps-round to ``MOSTNEG INT'' when it exceeds ``MOSTPOS INT''. The time is accessed through a `TIMER' variable, typically called `tim', by perfoming an input. A timeout (delay) is done using an input combined with `AFTER'. Timeouts are always absolute -- i.e. the program waits until a certain time, not for that time. Thus, to implement a delay, the current time must be read first. Time is measured in microseconds, giving a total clock period of approximatly 1h 11m. The maximum delay is half this, since half of time is considered to be in the past (and timeouts for such times will complete immediately) -- about 35 minutes.
PROC do.delay (VAL INT us)
TIMER tim:
INT t:
SEQ
tim ? t -- read current time
t := t PLUS us -- add delay
tim ? AFTER t -- wait until time "t"
:
Note the use of `PLUS' rather than `+'. Time wraps around, so calculations on time must wrap too. The normal arithmetic operators will generate overflow errors if they wrap around. `PLUS', `MINUS' and `TIMES' will not. `AFTER' may also be used as a relational operator to compare times. For example:
INT t0, t1:
SEQ
in ? t0; t1 -- input some times from somewhere
IF
t0 AFTER t1
out.string ("t0 happened after t1.*n", 0, scr!)
t0 = t1
out.string ("t0 and t1 happened at the same time.*n", 0, scr!)
TRUE
out.string ("t0 happened before t1.*n", 0, scr!)
Useful identitiesBeing formal, CSP has useful transformation rules (needed to prove things about parallel systems). In the occam world, this allows certain constructs in different ways. Here are some of the more useful and less obvious ones, with a very short intro to this CSP-ish notation:
The identities:
Selected Syntax SummaryI've attempted to put some comparative examples of code here, occam on one side, C on the other. Unfortunately, there isn't any real equivalent of the occam PAR and ALT in C.
|
|
[ls] [plain] |
|