CSP (or Pi?)
BarryNorton
CSP when, in the absence of any algebraic concurrency control features
- even a non-deterministic operator (called alt in occam and, I
believe, select in Newsqueak) - all that seems to be process-algebraic
is channel-passing, which is characteristic of the pi-calculus, not
CSP.
Am I missing some features?
Nigel Tao
There is a select statement.
http://golang.org/doc/go_spec.html#Select_statements
BarryNorton
'communication operators' was it.
Still, the question stands, does channel-passing not make this a more
pi-calculus like setting?
On Nov 11, 8:17 am, Nigel Tao <nigel.tao.gn...@gmail.com> wrote:
> 2009/11/12 BarryNorton <barrynor...@gmail.com>:
Jim Whitehead II
The presence of mobile channels certainly shows the influence of pi-calculus, yes.
On Nov 11, 2009 1:23 PM, "BarryNorton" <barry...@gmail.com> wrote:
Nigel, thanks. I missed it under statements and thought that
'communication operators' was it.
Still, the question stands, does channel-passing not make this a more
pi-calculus like setting?
On Nov 11, 8:17 am, Nigel Tao <nigel.tao.gn...@gmail.com> wrote:
> 2009/11/12 BarryNorton <barrynor...@gmail.com>:
> > > > > I'm struggling to understand why Go is described as inheriting from > > CSP when, in the a...
BarryNorton
Looking more at select, it seems to allow choice between both inputs
and outputs ("CommCase = "case" ( SendExpr | RecvExpr)").
I seem to remember that Alt in occam deliberately only allowed choice
on inputs, claiming that for this to be symmetric would mean no
scalable implementations. What's changed?
Roger Shepherd
On Nov 11, 1:41 pm, BarryNorton <barrynor...@gmail.com> wrote:
> Looking more atselect, it seems to allow choice between both inputs
BarryNorton
Adam Langley
> Interesting, yes. Occam had guards too.
To keep things simple. nil channels are never selected, so setting the
channel to nil is similar to a guard.
AGL
BarryNorton
> channel to nil is similar to a guard.
Adam Langley
> I don't see how that's like a guard at all (?)
It tends to work out.
Say you have a goroutine which loops around a select and you want to
do flow control. After the select, if you have too much information
processed, you set the channel that you're reading from to be nil.
select will stop reading from it. Later, when the backlog clears, you
can set it back to it's previous value and start reading again.
AGL
BarryNorton
It's going to take a while to get used to this mix of features...
Russ Cox
> on inputs, claiming that for this to be symmetric would mean no
> scalable implementations. What's changed?
Nothing changed, because Go didn't start with Occam.
The concurrency primitives are closer to Newsqueak
http://www.google.com/search?q=newsqueak
Russ
BarryNorton
patronising?
I don't mean what changed in a direct design lineage, rather is there
some change that's made this generally acknowledged difficulty in
implementing process algebraic external choices, in the presence of
data, feasible at scale?
Russ Cox
> Russ, maybe re-read my OP rather than jumping in and being
> patronising?
It was certainly not my intent to be patronising and I'm sorry that
it sounded that way. My point was that CSP doesn't necessarily
equal Occam, and that starting with a different lineage is the
actual explanation of why Go makes different choices than Occam.
I know you mentioned Newsqueak in your original post but
I left the URL for others who were reading along. And I used
the Google search URL because the two papers I actually
wanted to link to are the first two hits.
> I don't mean what changed in a direct design lineage, rather is there
> some change that's made this generally acknowledged difficulty in
> implementing process algebraic external choices, in the presence of
> data, feasible at scale?
I think the answer to that question depends a lot on your model of
parallelism and how shared you think the operations will be.
I think the general plan for Go is to provide the full functionality but
allow the easy cases to be implemented more efficiently than the hard ones.
For example, a sufficiently buffered channel might perform better than
an unbuffered one when it can decouple the communication from
strict synchronization, but sometimes strict synchronization is exactly
what you want, so an unbuffered channel might be just right.
And once you're selecting on unbuffered receives, you might
as well be able to select on unbuffered sends: those two are
approximately the same cost.
Russ
Ian Lance Taylor
> Also on the subject of "select"
...
> The select statement does not allow guards. Why?
I'm not sure that we've seen a need for them. Sorry to be dense, but
can you give an example of there they would be useful? Thanks.
Ian
roger peppe
> I seem to remember that Alt in occam deliberately only allowed choice
> on inputs, claiming that for this to be symmetric would mean no
> scalable implementations. What's changed?
occam did this because channels could map directly
to hardware communication channels and it's hard
to do bi-directional alt across processors.
i don't think go has that goal. although perhaps
unidirectional channels could make it possible
in some way - you could maybe privilege select statements which
select on all read-only channels (he says, hand waving horribly)\
Roger Shepherd
On 11 Nov, 19:18, Ian Lance Taylor <i...@google.com> wrote:
> > The select statement does not allow guards. Why?
>
> I'm not sure that we've seen a need for them. Sorry to be dense, but
> can you give an example of there they would be useful? Thanks.
>
> Ian
Although I'm no longer a practising concurrent programmer, I used them
extensively when I used to program in occam. I guess the essence of
the guarded select (ALT in occam) is that it enables an event driven
state machine to be captured easily. In particularly when certain
events (inputs) are only acceptable in certain states. In a language
with a select capable of choosing between inputs and outputs,
something like a bounded buffer is very natural to code: (forgive my
syntax)
while operational {
not_full & data <- input_channel // if buffer is
not full allow input
put_data_input_buffer()
not_empty & next_data -> output_channel // if buffer is
not empty allow output
take_data_from_buffer()
}
This is more elegant than the version which switches between three
behaviours depending on whether the buffer is full, empty or
otherwise. [I suspect it may always be possible to rewrite without
guards but there can be an explosive growth of cases if this natural
form cannot be used].
There are other - theoretical - reasons why the guard form is
attractive - see for example http://web.sau.edu/LillisKevinM/csci400/2009Fall/p453-dijkstra.pdf
which is part of the rationale behind CSP and occam's choices of
construct.
Roger
BarryNorton
> I guess the essence of
> the guarded select (ALT in occam) is that it enables an event driven
> state machine to be captured easily.
based design, back in the days that I was familiar with occam, but
there's a resurgence of this style in complex event processing for
business processes in recent years.
(On a side note, I really dislike this ability for every poster to
change the thread subject here)
BarryNorton
> to hardware communication channels and it's hard
> to do bi-directional alt across processors.
(As well it should - it used to say 'Transputer Support Centre' over
my desk when I started in research!)
Am I getting confused with Pict's choice of asynchronous Pi, or was
there not some related discussion on occam?
Time for some (re-)reading this weekend, I think...
Russ Cox
in Go's predecessors (Limbo, Alef, Newsqueak), and
it never really bothered me not to have guards.
I understand that there are examples, like the one you gave,
where they can be useful, but they bring with them a fair
amount of complexity in the implementation, especially
in a language with side-effects.
Your specific example could be written in Go by taking
advantage of the fact that if a channel involved in a select
is nil, that case cannot execute.
Russ
Roger Shepherd
On Nov 12, 8:20 am, Russ Cox <r...@golang.org> wrote:
> I've done a fair amount of channel-based programming
> in Go's predecessors (Limbo, Alef, Newsqueak), and
> it never really bothered me not to have guards.
> I understand that there are examples, like the one you gave,
> where they can be useful, but they bring with them a fair
>
But you have side-effects anyway - for example in the channel
expression. And you specify how you deal with them (all expressions
evaluated precisely once).
So how do guards complicate the implementation?
[Certainly side-effects do complicate things. occam did not have side-
effecting expressions; functions were pure functions, and xc, a recent
language which looks like it is the result of an illicit affair
between C and occam, forbids side-effects in its guards].
> Your specific example could be written in Go by taking
> advantage of the fact that if a channel involved in a select
> is nil, that case cannot execute.
take a channel and a boolean and returns either the channel or nil
depending on the boolean. (Although I don't understand enough about
the type structure to know whether this is simple or not).
>
> Russ
Roger