Doing it better 1999-02-08 e
###

Forwarded it to Philippa and got a bollocking for my troubles. She forgave
me when I explained how little time I'm spending on it, and how much on
Java for my supervisees. Still haven't done any proper work, though.

So the following is for your eyes only!

___

One or two of my ideas were a bit untidy:

 1) You can only recurse via a channel, and you can only recurse by naming
a protocol, so lets say that you can only apply a channel to a named
protocol and can't use names anywhere else. That makes things simpler.

 2) Parameterised types stop you working out the memory requirements of a
message. It works in ML because the constructors are always applied to
pointers, but messages include the data by value. Therefore, let's consign
parameterised types to a higher-level language, and call them generics.

 3) Many of the base types are linear types. You can't copy a channel, nor
a memory resource. Let's formalise and generalise: there are linear types
and non-linear types. Linear types are constructed out of linear types and
non-linear types using the channel, memory-for, sum and product
constructors, and non-linear types are constructed only out of non-linear
types using sum and product. The base types are non-linear.

 4) The best implementation of the parallel constructor is the one which
can be expressed using channels. Let's therefore abandon the parallel
constructor.

 5) Pointer types would be useful. A pointer to a non-linear type is
non-linear, but a pointer to a linear type is linear. We should also try
to capture immutable types: pointers to things whose shallow and deep
copies are observationally indistinguishable. Example: the String object
in Java. It is read-only, so you don't care whether you share it or
whether you have a private copy. Example which is not read-only: a cache.


 6) You must send the memory which holds a message as part of that
message. (Otherwise 1 you'd be able to send another message using the same
memory, and 2 the recipient wouldn't be able to free the memory or reuse
it.) However, the type of the memory (the type which it is guaranteed to
be big enough to hold) is not necessarily the same as the type of the
message, so we can't eliminate the programmer completely. No ideas yet.

___

Here is an implementation of the above typing scheme, with efficient
pattern matching and inheritance and all that.

First, I need a language for the objects. Let's go for dumb-ish objects.
Not completely dumb (I want them to be able to make decisions and keep
running counters and things) but not capable of loops, and certainly not
capable of crashing. A finite state machine, with straight-line code on
the transitions. Enough for 60% of OS code. More complex things, like
Mandelbrot generators, go in special processing nodes with only one
channel, so they can be killed easily and so that they don't mess up
anybody elses synchronisation. For the sake of argument, and for no other
very plausible sake, I'm going to allow an unlimited number of channels to
converge on each object, as though it were a subroutine.

To define an object, you first define all the relevant protocols in terms
of base types. Use header files for brevity. Then you define a finite
number of channel-groups, each with a type. These will be used to say
things like 'if a message arrives down any of these, then...'. Then you
define the states of the machine, giving for each a finite list of named,
typed storage cells (oh all right: variables). Then for each state, list
those channel-groups from which you could accept a message. For each of
these, provide an ML-like case statement, giving some straight-line code
and the next state.

For example, suppose your object replies to messages of type frog straight
away, but needs two separate messages of types pig and goose before it can
send one of type sheep. Both reactions can be repeated, and they are to
take place asynchronously.

Your object has three states, six transitions, and four channel-groups.
The types of the channel groups are frog, pig, goose and sheep. Let's call
the states blue, green and red. Here are the transitions:

 - In state blue, the object will accept a message from the frog group,
after which it sends a reply and re-enters state blue.

 - In state blue, the object will accept a pig, send an empty reply, and
turn green.

 - In state green, the object will accept a frog, reply, and stay green.

 - In state green, the object will accept a goose, send an empty reply,
send a sheep, and turn red.

 - In state red, the object will accept a frog, reply, and stay red.

 - In state red, the object will accept an empty reply from sheep, and
turn blue.

In state blue, we have one live variable to hold the sheep channel. In
state green, we also have variables to hold anything we got from the pig.
In state red, we have no live variables at all. Remember that all messages
contain any channels needed for replies.

This example is a bit contrived, because the object is in fact separable
into two separate objects, but I hope you get the idea. The important
point is that you don't have to accept messages from every group all the
time (although you do have to eventually), that the case statements read
the data out of messages into the variables, and that these variables hold
a finite amount of information.

That's more detail than I'm going to need. Let's move on to pattern
matching.

We need to be able to represent a channel as a string of bits in a
message, so as to be able quickly to branch to the relevant straight-line
code when a message is sent down the channel. We know the type of the
channel at compile time. I suggest that the best representation of a
channel is a pointer to a pointer to a branch table, and a pointer to a
workspace (using the standard trick: one pointer for the class and one for
the instance). In case you were wondering, the branch table is doubly
indirected in order that we can change the state of the receiver quickly.

Indices into a branch table can be calculated from the type of the
channel. Here is an example: (A+B)C(D+E)+FG(H+I). Here are all the
possible types of message, and the corresponding indices into the branch
table:
        ACD     1
        ACE     2
        BCD     3
        BCE     4
        FGH     5
        FGI     6

You'd never even have to tag the elements of a sum-type. The only change
to the typing scheme is that A+B is no longer the same as B+A, though they
are easily inter-castable.

Which brings me onto casting. A cast is a table of branches into a table.
It takes a fixed small number of clock cycles at run-time.

The bit I've not planned well yet is what you do when an object is not
willing to receive a message in its current state. This is clearly going
to involve putting a value at the relevant place in the pointer to pointer
to branch table business, but I'm not sure who checks it because sending a
message starts a new thread of execution, and I'm not sure how the fork
works yet.

What do you think?

Alistair