Re: Priority revisited: a new primitive

[A E Lawrence <adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>]

M_Boosten wrote:
> 
> Hi Adrian, Ian, Gerald, ...
> 
> General remark: I love mails that introduce new/different concepts,
> like Adrian's PAR PRI.
> 
> The fact that one talks about (1) PRI PAR, (2) PAR, (3) PRI ALT, (4) ALT,
> and (5) PAR PRI tells me: all this is TOO COMPLEX!  Something is
> FUNDAMENTALLY WRONG!

I think that PAR PRI may make PRI PAR redundant: I said as an aside in a
previous post that

PRI PAR    =   PAR PRI [\alphabet(P)]
  P              P
  Q              Q

where \alphabet(P) is the set of events in which P can potentially
engage. (Some early forms of CSP allowed \alphabet(P) to include extra
events that P can never perform: I exclude such redundant events here
for obvious reasons.) 

Standard CSP only has PAR and ALT. These are clearly needed and simple
primitives. occam introduced the PRI versions: they have proved their
worth in practice. But as we know, some things are awkward. AFAIK no
other language has anything better.

CSPP is an extension of CSP. It is really a new approach to denotational
semantics which gives a way to capture and define precisely what the PRI
versions mean and thus also prove laws about the extended language.

PAR PRI is just a suggestion at present. The CSPP acceptance semantics
is rather expressive, and allows some freedom is deciding how PAR PRI
may behave in "odd" situations like priority conflict. I don't intend to
try and define that precisely until I am convinced that PAR PRI is
useful, elegant and powerful. 

So I am not sure that things are that complex, but any suggestion for
simplification will obviously be welcomed by everyone here!

But  {PAR, ALT} as the unprioritized versions, and PRI {PAR,ALT},
possibly replaced by {PAR PRI, PRI ALT} or even {PAR PRI, ALT PRI},
doesn't seem that bad to me. Especially as there isn't much else in the
language beyond SEQ...
And as Geraint Jones once pointed out a long time ago, even SEQ is a
sort of PAR in which you insist on a particular order... :-)


> Note: I do not know a good solution for the moment, but this e-mail is
>       an attempt to start finding it...
> 
> Ian wrote:
> > I believe priority should be associated with events, and events only.

This was exactly what I was trying to capture in
 PAR PRI [a_bunch_of_events ]. 
As far as I can see, it does that in the simplest and purest form
possible.

> I know/believe/think/guess/hope the following:
> 
> 1. CSP Processes specify the order in which events occur.
> 2. This is a partial ordering: the system may make an arbitrary choice
>    at some point.

This is true of conventional CSP and any CSP defined by a semantics
involving traces. Since a trace cannot represent two events occuring
really simultaneously (unless you \merge events as in HCSP) CSP
specifies at least one possible order for the execution of a stream of
events. 
"Lack of true concurrency", as before... 

> 3. The choice MUST be arbitrary for processes that are considered part
>    of physically parallel systems.  Note: multi processor machines, and
>    different processes on parallel hardware (FPGAs/ICs).
>    [I find it difficult to express point 3 properly...]
>    [I find it difficult to abstract from hardware here, but, I would like
>    to in my reasoning...]

Again, this is the standard fudge for interpreting trace-based
semantics, but \merging and a different approach to semantics can give a
meaning to the syntax which may match intuition and physics better. And
may or may not give exactly the same algebraic laws for the language.

> 4. The ordering is important for those situations in which a single
>    physical execution unit is used.
> 
> I restrict myself to single-execution unit based systems:
> 1. The ordering must be hierarchically composable.
> 2. The hierarchy is the process hierarchy.
> 3. The ordering has to do with the events, not with the processes.

And PRI PAR fails that test if you really mean "arbitrary sets of
events". Otherwise, since processes are just things which perform
events, I doubt that there is any distinction.... 
 
> 4. The processes just specify the order.

In the sense that they define the possible traces? Ignoring failures and
divergences, conventional CSP might fit that.

> 5. Since processes consist of other processes, they can specify their
>    order by mixing the order of their childeren together with their
>    own influence.

I am beginning to get lost here. I guess that if you replace the word
"order" by "traces" this is sort of ok. But we have several sorts of
semantics. In muddies the water by inventing something else...

> Ok. Towards math:
> 
> Assume: Process Px has events Ex and ordering Zx
> 
> The ordering is a SEQUENCE of subSETs of Ex.
> 
> Example: Zx = [ {e1,e2}, {e3,e4,e5}]

I think that here you are trying to write a variant of traces based on
bags, something that I looked at for HCSP.

> Events e1 and e2 have the same priority, but their priority is
> higher than the priority of {e3,e4,e5}.

Ah, no. You are expressing a partial order relation by a sequence? 

> 
> Assume: Process Pxy consists of Px and Py.
> 
> Then: Pxy can specify how the ordering of Px and Py is interleaved.
> 
> Zx may be inconflict with Zy, if Px and Py share events.
> In that case, Px and Py cannot be composed (I think).
> 
> Assume Px and Py do not conflict.
> - If Px and Py share events, they communicate.  In that case, I would
>   expect Pxy not to be involved with those events.
> - The non-shared events can be ordered.
> - Zxy "kind of" zips Zx and Zy.  So: Zxy = Zx zip Zy.
> - Any zip operator can be useful... I guess...
> 
> Conclusion: many prioritisation functions exist.

I don't really know how to react to the above. I think that some of what
you are trying to say might be expressed in terms of traces. But you
must realize that there is *much* more involved than just traces.

CSP (and our extensions) have

1) Hiding     - absolutely fundamental to abstraction.
2) Divergence - as a result of hiding
3) refusals   - essentially deadlock modelling
4) recursion  - fixed points.

Perhaps the feature that makes CSP rather different and much more
powerful than almost any other language is its explicit support for
hiding and non-determination. All that must have a precise definition or
we are lost. It is hard work to get it right.

Although current occam does not support full recursion, nontrivial
recursion is fundamental to CSP. We must be able to prove what any
recursion means, perhaps identifying some as meaningless. That is
typically done via a fixed point theorem of some sort. It is even harder
work to establish those results.

Standard CSP denotational semantics is a very elegant sparse and thus
tight system that imposes constraints. There is not a lot of freedom.
This actually turns out to be very useful in guiding what is sensible.

My acceptance semantics breaks out of some of those constraints in order
to express things like priority. However, it may not be impossible to
express priority within the conventional semantics, and some attempts
have been made.
Acceptance semantics allows more freedom, but may suffer in that it does
not offer so much "guidance" in choosing sensible constructs.

>   Shouldn't CSP allow all zip operators/functions...

Hmm. Again. :-) If zip is just the usual zip from funstional
programming, then acceptance semantics can express all of them, I think.
Come to that, surely
   PAR PRI list
can do it? Each "zip function??" matches a particular choice of list?

But you seem to be advocating a vast increase in complexity? :-)

Adrian
-- 
Dr A E Lawrence (from home)