Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!vax1.esprit.southampton.ac.uk!IAN
From: IAN@vax1.esprit.southampton.ac.uk
Newsgroups: comp.sys.transputer
Subject: What makes occam so good?
Message-ID: <8903291813.AA10019@uk.ac.ox.prg>
Date: 29 Mar 89 18:08:56 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The Internet
Lines: 164

For some time now, I have been somewhat dismayed by the lack of positive
things being said about occam on the occam and transputer mailing lists. 
Recent discussion on the mailing lists about 'what makes the transputer so
good?', reproduced in OUG newsletter No. 10, seems to have been generally
along the lines that transputers are really neat, but that occam is lousy. 
While it is true that occam has limitations, I personally consider them to be
far outweighed by the advantages it has to offer.

I can't really argue that occam has not been an obstacle to the general
acceptance of transputer systems, but I would argue that this is really a
problem of education of the consumers.  In this respect, although INMOS appear
to regard themselves primarily as chip manufacturers, I tend to think it would
benefit them in to invest a little effort in making occam available on
machines other than transputers. If people got hooked, they would surely want
to buy transputer chips, since they make such good occam engines, and make
distributing occam programs so easy.

For me, the most exciting and interesting thing about occam is not just that
it is a language designed specifically with parallelism in mind.  Even more
important is that it based on a well defined mathematical model of
concurrency, which gives the language exceptionally clean semantics. Few other
languages can lay claim to such a combination of qualities.  The mathematical
model in question is that of Communicating Sequential Processes (CSP), due to
Professor Tony Hoare [1].  Because of this formal basis, there exist a large
number of algebraic laws relating different programs which have the same
meaning.  For instance, a rather simple and intuitive law is that the process

   PAR 
     P
     Q

has the same meaning as the process

   PAR
     Q
     P

where P and Q are arbitrary processes.  This equivalence can be written with
an equals sign, as

   PAR             PAR
     P      =        Q
     Q               P

Another simple, but interesting, equivalence is that

   PAR
     c ! e      =      v := e
     c ? v  

where c is a channel, e is an expression, and v is a variable.  A slightly
less obvious example is that

   ALT
     c ? x               PAR
       d ? y      =        c ? x
     d ? y                 d ? y
       c ? x

It should be emphasised that the above laws express identities between the
processes on either side of the equals sign.  They are not just rough
equivalences, which break down in certain circumstances.  They always hold.
Thus, laws which involve arbitrary processes (like P and Q in the first
example) are extremely general.  This is to be contrasted with the semantics
of most commonly available languages, which typically contain many exceptions
and irregularities.

This is all very elegant, but so what?  How does this help us?  Well, it has
been shown that a set of laws exist, which completely characterise the
semantics of the language [2].  (Actually, the reference cited shows this for
occam 1, since that untyped version of the language is easier to deal with,
but it is expected that the same ideas can be extended to include occam 2). In
particular, for WHILE-free programs, it is shown that it is possible to use
the laws to transform any program into a 'normal form', containing only
assignments, IF's and ALT's (also obeying some other constraints).  The
special thing about the normal form is that any two programs which are
semantically equivalent (have the same meaning) will have the same normal
form.  Thus it is possible to check whether two different programs really do
the same thing!  What is more, the steps to transform a program into its
normal form can be (almost) automated.  If a tool existed which could check
the equivalence, or otherwise, of two programs, it would be immensely
valuable.  For instance, it would enable you to check with one hundred percent
confidence that that 'small edit' really didn't change the meaning of a
program.  From a slightly different standpoint, the laws could be used to make
transformations to a program, which would be guaranteed to be meaning
preserving.  This could be helpful, for instance, when trying to improve its
execution efficiency.

On a more down to earth level, the formal properties of the language enable
the occam compiler to perform extremely strong checking of code, which is a
great help in making sure a program really does what you think it does.  For
instance, it is the only compiler I know which actually enforces the complete
absence of variable name aliasing.  This particular kind of checking is
required by the simple substitution semantics of abbreviations and procedure
parameters.  On the other hand, the programmer is not prevented from doing
low level things such as accessing memory mapped peripherals, or accessing the
same machine word as more than one different type.  Those things are allowed,
but treated more hygienically than in most languages, with the PORT and
RETYPES declarations, respectively.  The strictness of the compiler can be
irritating at times, but, for me at least, this is outweighed by the extra
confidence I have in a piece of code which has passed its stringent
requirements.

One criticism of occam which is often raised, is that it is not recursive.  It
is interesting to note that the underlying CSP model is indeed recursive, and
there is no reason in principle why a recursive version of occam could not be
implemented.  No syntactic changes to the language would be necessary.  The
reason the definition in the occam 2 reference manual [3] is not recursive is
simply to allow an efficient and secure implementation of the language on the
transputer. For the same reason, there is no real reason why the process count
on a replicated PAR construct could not be allowed to be variable.  However,
the current definition does have the advantage that the amount of memory
needed to execute a process is known at compile time, and so there is no
possibility of a program crashing at run time, with stack or heap overflow. If
this were not the case, the program transformations mentioned above would no
longer, in general, be meaning preserving, and it would not be possible to
make use of the formal properties of the language (at least, not so easily).

Occam is not everything, of course, and I hope that we will be seeing, in due
course, an 'occam 3', containing some of the abstract data types which were
left out of occam 2 (give the guy's at INMOS a chance!).  Records, more
general arrays, and an enumeration type might be expected, for instance. 
Looking further ahead, what might be the line of development?  It has been
said that occam is an 'assembly language' for parallel processing.  This is
not meant to imply that the conventional aspects of occam are at the level of
an assembly language, as it is clearly a 'high level' language (whatever that
means) in that sense. Rather, the communication facilities provided by
channels are sufficiently primitive to allow higher level communication
constructs to be efficiently built on top of them.  At the moment, it is not
entirely clear what such constructs ought to be, but when it is, a new
language will presumably be designed around them.  Channels might be regarded
as the GOTO's of parallel programming, which will eventually be replaced by
more structured ideas.

In conclusion then, it is really the formal properties of occam which make it
such an interesting language, and it is the things which the occam compiler
does not allow you to do, almost as much as those which it does, that make it
such a useful tool.  I look forward to further occam inspired developments,
and, in the mean time, sincerely hope that the elegance and security of the
language will come to be appreciated by a wider circle within the computing
community. By the way, I'm also a fan of TDS [4], but that, as they say, is
another story!

[1] C.A.R. Hoare, "Communicating Sequential Processes",
    Prentice Hall International series in Computer Science, 1985,
    ISBN 0-13-153271-5, ISBN 0-13-153289-8 PBK

[2] A.W. Roscoe and C.A.R. Hoare, "The Laws of occam Programming",
    Oxford University Computing Laboratory Programming Research Group,
    Technical Monograph PRG-53, February 1986, ISBN 0-902928-34-1

[3] INMOS Limited, "occam 2 Reference Manual", Prentice Hall International
    Series in Computer Science, 1988, ISBN 0-13-629312-3

[4] INMOS Limited, "Transputer Development System", Prentice Hall
    International, 1988, ISBN 0-13-928995-X

+-----------------------------------------------------------------------------+
| Ian Glendinning                JANET:  ian@UK.AC.soton.esp.v1               |
| Fidelio Software GmbH          BITNET: ian%UK.AC.soton.esp.v1@AC.UK         |
| Widenmayerstrasse 6            UUCP:   ...!mcvax!sot-cm!igl                 |
| D-8000 Muenchen 22             other:  ian@v1.esp.soton.AC.UK               |
| West Germany                   Phone:  +49 89 2123080                       |
+-----------------------------------------------------------------------------+