Re: You must read this

["P.H.Welch" <P.H.Welch@xxxxxxxxx>]

Dear All,

Brinch Hansen seems to have done a bulk mailing!  I also received a brown
envelope containg just the article ... I wonder how we were all selected?!

  Re. `Java's Insecure Parallelism', ACM SIGPLAN Noticese 34, 4 (1999)
  ====================================================================

Several thoughts: first, the language used and emphasis on security is
precisely aligned with so many things we have all said so many times over
the past 15 years.  However, with Brinch Hansen saying this so loudly
and in public, this is wonderful ;-) ... I can't wait to rub several of
my colleagues' noses in this ;-) ;-) ;-) ...

Second - gloom!  Yet again, the whole technical, commercial and academic
development of occam has been as though it never happened.  He quotes
Hoare many times - but never mentions a word on CSP.  For example, from
Hoare [1974b]:

  ``For a parallel programming language, the most important security measure
  is to check that processes access disjoint sets of variable only and do
  not interfere with each other in time-dependent ways.''

Later in the page, he writes:

  From the begining, Hoare and I recommended extensive compile-time checking
  of modular parallel programs as an effective way of preventing most
  time-dependent errors.  However, by 1991 Hoare sadly concluded that
  ``a subsequent generation has lost that understanding''.

Those principles are the foundation of the engineering that went into
occam and, by 1991, although the owners of occam may have lost that
understanding, there was a vigorous community of users - including
industrial users - that hadn't!  And we're still here.  Somehow, we've
become invisible ... we speak and show and teach ... but nobody, not
even Brinch Hansen, can see us?  Was it something we ate???

Let's get technical.  I agree 100% with his wonderment that Java didn't
burn a bit more security into the language.  Putting in the monitor
methods but providing no compulsion (and checks) in their operation
was asking for trouble.  But putting in the monitor methods was better
than doing nothing at all ... I guess.

But he shows that his 1972 ideas for explicit `queues' for shared
variables are the same as the standard Java design pattern of waiting
for a condition in a while-loop and notifyAlling - the difference being
that his mechanism is enforced.  See his figures 2 and 3.

BUT it's the logic associated with reasoning over shared conditions in
this manner that I don't like - whether it's in Java or with Brinch Hansen
monitors.  In his shared buffer example (figure 2), there is in the send:

      while (full == max) await (e);

To see how we mysteriously exit this loop if (full == max) first time,
we need to look at a *different* algorithm ... the one inside the receive
method:

      full = full - 1;
      cause (e);

It's this strong coupling between the two methods that's bad in Java and
bad here.  That kind of logic doesn't scale well.  Try writing the
concurrent-read-exclusive-write monitor with these primitives and I'll
bet it's as hard as the one Tony Hoare came up with!  Also, I suspect
that the `Wot-no-chickens' example will also fail here ...

So, that brings us back to CSP ... whose semantics do compose decently.
Looking back to his first version of the buffer (figure 1), which is
``based on a restricted form of the class concept of Simula 67'',
there is something surprising:

  shared class B {

    int max = 10, p, c, full;
    int[] buffer = new int[max];

    public void send (int m) {
      await (full < max);
      buffer[p] = m;
      p = (p + 1) % max;
      full = full + 1;
    }

    public int receive () {
      await (full > 0);
      int m = buffer[c];
      c = (c + 1) % max;
      full = full - 1;
      return m;
    }

    public B () {
      p = 0; c = 0; full = 0;
    }

Here, there is no inter-dependence between the send and receive messages!
They can be understood independently.

In fact, the whole thing is in 1-1 correspondence with an occam server
module with pre-conditions.  Here it is in occam3:

  MODULE B ()
    INTERFACE
      SHARED CALL send (VAL INT m): 
      SHARED CALL receive (INT m): 
    TO
      VAL INT max IS 10:
      [max]INT buffer:
      INITIAL INT p IS 0, c IS 0, full IS 0:
      SERVER
	(full < max) & ACCEPT send (VAL INT m)
	  SEQ
	    buffer[p] := m
	    p := (p + 1)\max
	    full := full + 1
	  SKIP
	(full > 0) & ACCEPT receive (INT m)
	  SEQ
	    m := buffer[c]
	    c := (c + 1)\max
	    full := full - 1
	  SKIP
      :
  :

This has, of course, a 1-1 correspondence with occam2 code.  I've used
occam3 syntax because it's slightly closer in resemblance to the monitor
code just above.  We even declare and use them in the same way.  For
Brinch Hansen modules:

  B b;

and, then, from any parallel processes that can see it:

  b.send (5);

or:

  x = b.receive ();

In occam3, this becomes:

  MODULE b IS INSTANCE B ():

and, then, from any parallel processes that can see it:

  b.send (5)

or:

  b.receive (x)

where occam disallows the use of a functional notation for the recieve
channel communication (which is appropriate since the operation causes
side-effects - i.e. it is not functional!) ... minor quibble ;-)

Brinch Hansen explains that he moved away from the figure-1 style of
monitor (which seems to me to have a compositional scalable semantics)
to his figure-2 style (which doesn't) because he was ``concerned about
the inefficiency of conditional critical regions which retest Boolean
conditions repeatedly until they are true''.

I think his `await' conditions can occur anywhere (and any number of
times) in the body of his monitor methods - that *may* complicate things.
In the occam3 version, the pre-conditions can occur only at the start of
(actuallly before) the method code.  Even so, the only points at which
the `await' conditions need to be retested are when you exit one of
the methods - which is exactly what happens in the occam server loop.

This does give you the ALTing overhead (i.e. servicing a method forces
the reevaluation of all method preconditions), but I wouldn't have thought
that unacceptable - especially in 1972.  Maybe these conditions were
retested more than that, but I don't see why that would be needed?

So, a overwhelming vote of thanks is due for the sentiments so well
expressed in this article.

But oh ... occam deserved just a bit of a mention!  It ... and what happened
to it ... reinforce the story he is telling so well.

Cheers,

Peter.

PS 1. the occam open source release under (probably the GPL) *will* be
      happening ... but I have to do some work to gather it all together
      on to a CD-ROM ... and I'm looking at an alarming pile of marking :-(

PS 2. anyone trying to use KRoC occam on the latest Linux from Redhat
      (version 6.0) will find it doesn't work!  We have a fix for this
      that'll go on the web shortly - we just had to re-compile some
      of the kernel support routines.  Future open source releases will
      fix this - you get the sources and a Makefile and build it yourself!