igl@ecs.soton.ac.uk (Ian Glendinning) (02/07/91)
In <1991Feb6.122949.8210@rodan.acs.syr.edu> greeny@wotan.top.cis.syr.edu (Jonathan Greenfield) writes: >CSP is a fine theoretical entity, but it surely is not a programming language, >since CSP (as defined in Hoare's book) "programs" are not capable of actually >doing anything. (Hoare's definition of parallel composition is inadequate.) Please explain. Why is it inadequate? >Occam is the rather ugly result of one attempt at including the elegant >concepts of CSP in a practical and efficient programming language. Ugly? That's a matter of opinion... >(Note that, ignoring the procedural/functional differences, the main >conceptual difference between CSP and occam involves the action of parallel >composition.) Again, please explain. I always thought they were the same. >At a purely practical level, the 'copy-penalty' is probably not a real issue >since any program that aspires to efficieny (when compared to sequential >programs) must be coarse-grained enough so as to make the communication >time negligible when compared to the computation time. When this is the case >the 'copy-penalty' will obviously be negligible also. Agreed. >Jonathan Ian -- I.Glendinning@ecs.soton.ac.uk Ian Glendinning Tel: +44 703 593081 Electronics and Computer Science Fax: +44 703 593045 University of Southampton SO9 5NH England
greeny@wotan.top.cis.syr.edu (Jonathan Greenfield) (02/09/91)
In article <6591@ecs.soton.ac.uk> igl@ecs.soton.ac.uk (Ian Glendinning) writes: >> (Hoare's definition of parallel composition is inadequate.) > >Please explain. Why is it inadequate? A sequential process as defined by Hoare is essentially an automaton that defines a language of events (which correspond to messages) in which the process is capable of interacting. The parallel composition operator (||) transforms a pair of sequential processes into an equivalent single sequential process, defining a language of events in which both processes are capable of interacting. Consider the following example from Hoare's book: VMCT = coin -> (choc -> VMCT | toffee -> VMCT) (a vending machine with chocolate and toffe) GRCUST = (toffee -> GRCUST | choc -> GRCUST | coin -> choc -> GRCUST) (a greedy customer who tries to get something without paying) (GRCUST||VMCT) = coin -> choc -> (GRCUST||VMCT) Note that the parallel composition of the two is, itself, a sequential process. Furthermore, together, the greedy customer and the vending machine can only 'agree' to interact with a sequence of coin, chocolate, coin, chocolate, ... However, the parallel composition of these two processes does not cause an interaction to take place. (It does not cause the events to happen.) It simply defines a new language of interactions. Hoare's definition of parallel composition is based upon a 'broadcast' synchronization. That is if we perform another parallel composition with the example, ((GRCUST||VMCT)||VMCT) then we get the same sequential process defined above. (The name is changed, the process definition is identical. Hoare uses a notation that I cannot duplicate here, using mu, in order to avoid concern about the names.) The sequential processes that result are still ready to interact, but Hoare never introduces an additional notion of parallel composition that allows these events to ever take place. As a result, Hoare's parallel composition of processes defines processes that exist in a vacuum, and can't actually do anything (except to describe a possible set of events). >>(Note that, ignoring the procedural/functional differences, the main >>conceptual difference between CSP and occam involves the action of parallel >>composition.) > >Again, please explain. I always thought they were the same. If you are familiar with occam, it should be clear that the definition of the parallel composition operator (PAR) is quite different. Consider two occam processes, SEQ <interact in event> x := 1 and SEQ <interact in event> y := 2 (Let us use an <event>, without worrying about channels, communication, and other concepts that are not relevant to this discussion of parallel composition.) Now consider the parallel composition of these: PAR SEQ <interact in event> x := 1 SEQ <interact in event> y := 2 which is equivalent to the occam process: x, y := 1, 2 because the <event> actually takes place. It is an internal event that is invisible outside of the scope of the PAR operator. One may prefer to view this as: SEQ <event takes place> x, y := 1, 2 Notably, the parallel composition is NOT equivalent to: SEQ <interact in event> x, y := 1, 2 which is what one would expect based upon Hoare's notion of parallel composition. Fundamentally, when two processes share an event in occam, the event takes place. In CSP, it does not. Jonathan
dbc@ecs.soton.ac.uk (Bryan Carpenter) (02/12/91)
In <1991Feb8.121349.17501@rodan.acs.syr.edu> greeny@wotan.top.cis.syr.edu (Jonathan Greenfield) writes: >In article <6591@ecs.soton.ac.uk> igl@ecs.soton.ac.uk (Ian Glendinning) writes: >>> (Hoare's definition of parallel composition is inadequate.) >> >>Please explain. Why is it inadequate? >... >>>(Note that, ignoring the procedural/functional differences, the main >>>conceptual difference between CSP and occam involves the action of parallel >>>composition.) >> >>Again, please explain. I always thought they were the same. >If you are familiar with occam, it should be clear that the definition of >the parallel composition operator (PAR) is quite different. Consider two >occam processes, > SEQ > <interact in event> > x := 1 >and > SEQ > <interact in event> > y := 2 >(Let us use an <event>, without worrying about channels, communication, and >other concepts that are not relevant to this discussion >of parallel composition.) >Now consider the parallel composition of these: > PAR > SEQ > <interact in event> > x := 1 > SEQ > <interact in event> > y := 2 >which is equivalent to the occam process: > x, y := 1, 2 >because the <event> actually takes place. It is an internal event that >is invisible outside of the scope of the PAR operator. One may prefer >to view this as: > SEQ > <event takes place> > x, y := 1, 2 >Notably, the parallel composition is NOT equivalent to: > SEQ > <interact in event> > x, y := 1, 2 >which is what one would expect based upon Hoare's notion of parallel >composition. >Fundamentally, when two processes share an event in occam, the event takes >place. In CSP, it does not. I don't see what you're getting at really. The (communication) event in occam surely does take place. In occam though particular events (the only ones supported---communications) can only be in the alphabets of *two* processes, so their occurence will only directly effect these two processes. CSP, of course, has the same ability to limit particular events to the alphabets of a subset of all processes---I don't see that events are necessarily all "broadcast" in the way you seem to suggest. The difference seems to have more to do with how many processes can share an event (in their alphabets), rather than the nature of the concurrency. >Jonathan Bryan
greeny@wotan.top.cis.syr.edu (Jonathan Greenfield) (02/13/91)
In article <6679@ecs.soton.ac.uk> dbc@ecs.soton.ac.uk (Bryan Carpenter) writes: >I don't see what you're getting at really. The (communication) >event in occam surely does take place. In occam though >particular events (the only ones supported---communications) >can only be in the alphabets of *two* processes, so their occurence >will only directly effect these two processes. > >CSP, of course, has the same ability to limit particular events to >the alphabets of a subset of all processes---I don't see that events are >necessarily all "broadcast" in the way you seem to suggest. > >The difference seems to have more to do with how many processes can >share an event (in their alphabets), rather than the nature >of the concurrency. You are correct in noting that CSP has the ability to exclude certain processes from interaction in some events (on the basis of their alphabet). However, the events are all "broadcast" in nature (even when only two processes share the event). The problem seems to be the following. Consider a process A = event1 -> SKIP Hoare tells us that this is a process that engages in event1 and then terminates (successfully). The question at hand is does "execution" of A cause event1 to "occur." It seems to me that it does not. If event1 is an input event, say event1 = c.v = c?v and A = c?v -> SKIP then what does "execution" of A mean? Hoare says that process A is initially prepared to engage in event c.v. Since it seems to me that an input event can not be considered to have "occurred" when taken in isolation (as in process A, which is not composed with any other processes), I cannot interpret the statement that a process is "prepared to engage in" an event to mean that the event "occurs." As a result, it would appear that A||B = event1 -> SKIP (where event1 is just some event) is a process that is "prepared to engage in event1," and not a process in which event1 has "occured." Therefore, CSP processes all strike me as descriptions of possible sequences of events (and actions). They do not strike me as descriptions of actual sequences of events (and actions). Disclaimer: I cannot understand why Hoare would choose to define CSP with such a conceptual problem. Given Hoare's status relative to my own, it is probably far, far more likely that I am mistaken in my understanding of the definition, rather than that Hoare is mistaken in his definition. Any insights into an error that I may have made will be appreciated.
HALLAM@physics.oxford.ac.uk ("Phillip M. Hallam-Baker") (02/13/91)
Jonathan Greenfield writes :-
>>>>>>
If event1 is an input event, say
event1 = c.v = c?v
and
A = c?v -> SKIP
then what does "execution" of A mean? Hoare says that process A is initially
prepared to engage in event c.v. Since it seems to me that an input event can
not be considered to have "occurred" when taken in isolation (as in process
A, which is not composed with any other processes), I cannot interpret the
statement that a process is "prepared to engage in" an event to mean that the
event "occurs."
<<<<<<<<<
Although I am by no means a CSP person I suspect that the problem here is
lack of clarity and a confusion between different CSP models.
The original CSP notation does not have a concept of an `input event' or
output event. There are simply events. The input and output notation is part
of a collection of notational clutter that various persons have added to
CSP over the years.
There are very good reasons why the process
A = event -> B
is interpreted as `A is prepared to engage in event' and not `A performs
event'. If the latter interpretation were allowed then the hierarchy of
processes would not work. The parallel operator || is a binary operator
which takes as it's arguments two processes and returns a single process.
(Think of this as algebra not as executing a computer program). The symetry of
the whole is lost if you take the `performs' interpretation since if you have
the process `A||C' where C=STOP{with alphabet {event}} then the composite
process will behave as STOP -- making a complete nonsense of the idea of
the interpretation of A as `A performs...'
To interpret a CSP process and how it will behave it is necessary to look
at it's *traces*. The function tr (in dark squigly type) takes a process
as it's argument and returns the set of all possible behavious of the process
Unfortunately the CSP book does not seem to give as much attention to traces
as they deserve. I suspect because at the time the book was written the
traces model was considered of theoretical interest rather than of practical
interest.
The input and output notation is a bolt on accessory which may be retrofitted t
to almost any brand of CSP. It is simply another method of expressing the
alphabet of a process. Basicaly the idea is that if your network is
triple-disjoint (all communication is between pairs of processes) then you
can dispense with the tedium of defining an alphabet for each process.
The business of input and output is another layer of fancy stuff again
- basicaly it allows you to consider the notion of processes having state
apart form that directly concerning communication.
The input and output bit is not the only solution to the `problem' of the
alphabets the alternative, as used in Bill Roscoes timmed CSP and in most
of the probabalistic model I have seen is to bind the alphabets to the
parallel operator. - ie :
A || B
a b
where a and b are alphabets (no greek characters in email sob !)
This was used in the untimed CSP model at one time. I don't like it as it
makes hierachies of processes a pain. Also real systems with lots of processes
start to look horrible. However those who are prepared to brave the horrors
of contraction mappings on ultra metric spaces (or something like that) are
allowed a few notational idiosyncrasies.... (That should do -- hopefully
someone at the PRG will now explain why it makes everything lovely and simple!)
Anyway my point is that CSP does not contain a conceptual problem
as Mr Green suggests. The whole point of CSP is that parallel processes
*are* conceptual problems. CSP is merely a tool to help understand some of
them.
Phillip M. Hallam-Baker
Discaimer : The usual. Plus the fact that I don't research in this area and
so anything I say is no more likely to be correct as the next person.
Still since most of the point of science is trying to express yourself
if I have misrepresented anyone elses views its their own fault for
not explaining them better in the first place.greeny@wotan.top.cis.syr.edu (Jonathan Greenfield) (02/14/91)
In article <17289.9102131102@prg.oxford.ac.uk> HALLAM@physics.oxford.ac.uk ("Phillip M. Hallam-Baker") writes: >Although I am by no means a CSP person I suspect that the problem here is >lack of clarity and a confusion between different CSP models. > >The original CSP notation does not have a concept of an `input event' or >output event. There are simply events. The input and output notation is part >of a collection of notational clutter that various persons have added to >CSP over the years. Just an incidental--I based my comments on Hoare's definition of CSP in his book of the same name. >There are very good reasons why the process > >A = event -> B > >is interpreted as `A is prepared to engage in event' and not `A performs >event'. If the latter interpretation were allowed then the hierarchy of >processes would not work. The parallel operator || is a binary operator >which takes as it's arguments two processes and returns a single process. >(Think of this as algebra not as executing a computer program). The symetry of >the whole is lost if you take the `performs' interpretation since if you have >the process `A||C' where C=STOP{with alphabet {event}} then the composite >process will behave as STOP -- making a complete nonsense of the idea of >the interpretation of A as `A performs...' Well, this was merely my point in the first place--that CSP is a fine theoretical entity, but that it should not be considered a programming language. My whole point was that if we consider CSP processes to be programs, then we run into a problem. Since some have suggested that CSP processes are programs, I figured that either I or Hoare had a conceptual problem with CSP... >To interpret a CSP process and how it will behave it is necessary to look >at it's *traces*. The function tr (in dark squigly type) takes a process >as it's argument and returns the set of all possible behavious of the process Again, the *traces* of a process is merely an alternate description of (what I referred to in a previous posting as) the language of events for a process. If you are correct that CSP was not intended by Hoare as a programming language, then no problem exists (to my knowledge). We merely recognize CSP processes to be mathematical descriptions of automata, but not programs. As I do not research this area, either (and as I do not work as a theoretician), I am glad to see that my insights into CSP have been somewhat validated by your posting. Jonathan