At 06:45 PM 10/28/2001 -0800, Ken Kahn wrote:
>You seem to be arguing that this is another example of parallelism or
>concurrency in the large and sequentiality in the small. But the behavior of
>a cell in the game of life or a cellular automata is not like a sequential
>thread. There is no need for a stack of procedure calls. Right?

But there is state -- state is state (actually, there's either
zero/one, or zero/many -- see far below).  In the case of (say)
reservoir simulation, a cell's state will include things like:

  temperature
  partial pressure of numerous substances
  geologic information (what sort of rock)
  and I imagine a good deal more.

The game-of-life is just a much simpler instance of
the same thing (state) and a stack of procedure calls
is a more complex instance of the same thing.

>And maybe there are better ways to deal with
>hardware interrupts.

At a recent C-- workshop, I think the consensus (among us,
various academics, and someone who had worked on Plan 9) was
that you wanted to make the hardware interrupts Go Away.  There
are two approaches -- polling (compiler/verifier inserted) and
service threads, which can also be combined.  It also helps to
use wait-free (Herlihy-style) data structures based on
compare-and-swap so that you can actually accomplish
something in your interrupt handler.  (So, at the very bottom
there is asynchrony, and it is tricky to reason about, but
that is the end of it).

>Some would argue that it is better to be able to reason about your program
>than try to test it exhaustively. And having a simpler cleaner underlying
>model of computation facilitates reasoning. It is harder to reason about
>programs that are both concurrent and sequential.

This is all absolutely true -- however, it is also absolutely
true that I am a fallible typist, and a fallible proofreader
(as the the repeated word example demonstrates all too too well).
Testing is absolutely necessary simply to test for transcription
errors, and there is also the possibility of a "thinko" (meaning,
I start with the wrong assumptions) in my design and proof.
There is, in any multi-person task, the existence of
communication errors between different people; I may not state
an "obvious" assumption that turns out not to be so obvious,
etc, etc.  Testing is good for smoking out all of these things,
and once there is smoke, you then go looking for fire.

>Performance can be high for highly concurrent programs in languages
>implemented well to support such a thing. See for example
>
>www.sics.se/~andreas/papers/JavaVsOz.ps

The central trick here (and a good one) is the use of single-assignment
synchronized variables.  That is, the waiting (as I see it, skimming
the text) is empty/full, with the restriction that once full, a
cell never goes empty again.  I have to say, this very well might
be the way to do it -- if you look at what happens when people
start building Really Big Systems in Cedar, or in Modula-3, or
in Java, there is less and less gratuitous state exposed, because
you can never be sure how an object might be shared.  State appears
only when it is part of the behavioral definition.  (The Java
libraries, inheriting all manner of cruft from old Taligent C++
code, contains a particular illuminating example of how
state is bad -- don't recall which, it was Date or Calendar).

So, what happens if you combine that sort of programming with
something like OO Squeak?  I imagine producers-consumers being
done with an endless linked list, where the consumer waits on
the next list element, which will contain one chunk of data, and
an initially empty next-list-element field.  At the low level,
what's going on is each "unknown" variable has a full-empty
indicator, and (because all blocked computations are wakened
at the same time) a thread can register its interest in data
by pushing itself onto a stack, where the head of the stack
is perhaps the full-empty indicator, using a compare-and-swap,
which is as fast as a simple synchronization-acquire in Java
(then the thread has to put itself to sleep, which requires
a bit more work and synchronization, urk).

David Chase

chase at naturalbridge.com
drchase at alumni.rice.edu
chase at world.std.com