GUARDED selective waiting

[mau...@murus.org]

Dear developers,

One of the most simple examples for synchronous message passing
is the construction of a general semaphore by means of two channels
with the following "nucleus":

if val == 0 {
<-v
val++ // or: val = 1
} else { // val > 0
select {
case <-p:
val--
case <-v:
val++
}
}

Much more elegant would be a solution with the boolean expression "val
> 0"
as "guard" (the keyword "when" as e.g. in Ada might well be omitted):

select {
val > 0 case <-p:
val--
case <-v:
val++
}

(Of course, there are immediately many more classical examples.)

So what really is missing, is >>> guarded <<< selective waiting
by extending the CommCase in the CommClause of the SelectStmt:

CommCase = [ Expr ] "case" ( SendStmt | RecvStmt | default" .
where "Expr" is any boolean valued expression.

DO YOU THINK THERE IS ANY CHANCE OF ENRICHING GO
BY THIS VERY USEFUL CONSTRUCTION ?

Thanks in advance for any favourable reply,

Christian
--
References:

Ada:
"when"-construct in tasks
Andrews, G. R.:
Foundations of Multithreaded, Parallel and Distributed Programming.
Addison-Wesley (2000), p. 323
Burns, A., Davies, G.:
Concurrent Programming.
Addison-Wesley (1993), p. 118

[Kyle Lemons]

I actually think that would obscure the intent of the select statement in question.  Seeing the cases and the selects inside them is much more explicit.

Also, a counted semaphore can somewhat more simply be represented by sem := make(chan bool, size), then your p and v (I can never remember which one is which) are <-sem and sem <- true.

[Rob 'Commander' Pike]

There are languages whose equivalent to the select statement does this, but I believe they're all single-threaded. It's hard to combine general evaluation and communication in a thread-safe manner.

There are no plans to add this feature to Go.

-rob

[mau...@murus.org]

Dear Kyle,

I of course see your point with implementing a general semaphore with
asynchronous message passing
instead of synchronous - this surely is a classical example. But this
objection misses the point:
My cited case was the most easy example as sort of representative for
more complicated situations,
just to explain the matter. So - sorry - but I do absolutely NOT agree
with your first sentence.

On the contrary, there are lots of examples, where things are
extremely more elegant with
guarded selective waiting than just with selective waiting.
Here another one, which, I think, cannot be replaced as simply as the
semaphore example
by using asynchronous message passing: The first readers writers
problem
(Original reference: Courtois, P. J., Heymans, F., Parnas, D. L.:
Concurrent Control with `"Readers'' and `"Writers''. Commun. ACM 14
(1971) p.667-668;
and furthermore: any book on concurrent programming)

Here the simple "naive" solution with four channels
rE, rL for readers entry/leave and wE, wL for writers entry/leave:

var nR, nW int // number of active readers, writers
for {
if nW == 0 {
if nR == 0 {
select {
case <-rE:
nR++
case <-wE:
nW++
}
} else { // nR > 0
select {
case <-rE:
nR++
case <-rL:
nR--
}
}
} else { // nW == 1
<-wL
nW--
}
}

Definitely much better structured (less cases and a
clear 1:1-mapping between entry-conditions and things to "do")
with selective waiting:

select {
nW == 0 case <-rE:
nR++
nL > 0 case <-rL
nR--
nR == 0 && nW == 0 case <-wE:
nW = 1
nW == 1 case <-wL:
nW = 0
}

You certainly can imagine more complicated examples, where things fall
much more apart;
there are even cases, where an understandable solution with guarded
selective waiting is quite easy,
but without guards more or less at least difficult, if not to say
horrible!
(Start off with the second readers writers problem, generalize to
singe lane bridge problem,
make it more complicated by adding bounds, etc., etc.)

[Paul Borman]

On Tue, Jan 31, 2012 at 12:51 PM, mau...@murus.org <mau...@murus.org> wrote:

Definitely much better structured (less cases and a
clear 1:1-mapping between entry-conditions and things to "do")
with selective waiting:

select {
nW == 0 case <-rE:
 nR++
nL > 0 case <-rL
 nR--
nR == 0 && nW == 0 case <-wE:
 nW = 1
nW == 1 case <-wL:
 nW = 0
}

To expand on Rob's comment, what does this actually mean?  nW, nR, and nL can al change  while processing the select as well as from the time they are checked until the end of the case (which I would guess assumes that the expression remain true for the duration of the case).   By the time you have addressed these concurrency issues I am afraid your desire to make the code more beautiful will have been lost.  I think it is an unreasonable expectation that the language could resolve these issues for you.

    -Paul

[mau...@murus.org]

May I quote from Burns/Davies, p. 119:
"The guards have to be evaluated >once< at the start of the execution
of the select statement.
If the guard evaluates to true, then the alternative is said to be
open;
false guards are termed closed. Any alternative for which the guard is
closed,
is ignored for the remainder ot that execution of the select
statement.
Note that an alternative without a guard is always open."
Would this approach defuse the matter ?

[Paul Borman]

What if you evaluate nW then evaluate nR but nW has now changed?  This is not addressing concurrency issues.

[Sonia Keys]

From the spec, "A channel may be nil, which is equivalent to that case not being present..."  This provides a guard-like capability.  You could write,

gp := p
for {
  select {
  case <-gp:
    val--
    if val == 0 {
      gp = nil
    }
  case <-v:
    val++
    gp = p
  }
}

Kyle's technique is much cleaner though.  Similarly, the clean solution to readers-writers is to use sync.RWMutex.

[mau...@murus.org]

Dear Rob,

certainly you are right by saying "It's hard ...".
I can well imagine that; I know of at least one language, where the
constructor wrote, that
"... this belongs to the most complex mechanisms of communication
between processes".

However, I think, you and your colleages until now have managed really
very difficult problems
in an admirable manner - so why throw away that great concept after
thinking about it maybe
just a few minutes ? I really think, you should "carry it in your
heart", eventually you will be able
to prove, that you even can cope with Ada in one more interesting and
extremely useful aspect.
(Ada tasks "single-threaded" ?)

[mau...@murus.org]

This cannot happen:

On 31 Jan., 22:28, Paul Borman <bor...@google.com> wrote:
> What if you evaluate nW then evaluate nR but nW has now changed?  This is
> not addressing concurrency issues.

nW is (only!) changed by the server, that executes the code in my
example.
So the evaluation of nW and nR is run under mutual exclusion by the
concept of message passing.

[mau...@murus.org]

Indeed a very interesting idea, thankyou for your advice.
Might well be, that that can be generalized ...

No doubt, this is a sober solution. But if we restrict ourselves to
follow that
direction, we need XYZMutex for Jupiter knows how many classes of
XYZ-...-problems (three examples of which I mentioned).

[Russ Cox]

On Tue, Jan 31, 2012 at 14:53, mau...@murus.org <mau...@murus.org> wrote:
> select {
>  val > 0 case <-p:
>    val--
>  case <-v:
>    val++
>  }

func maybe(b bool, c chan int) chan int {
if !b {
return nil
}
return c
}

select {
case <-maybe(val>0, p):
val--
case <-v:
val++
}

Russ

[mau...@murus.org]

Equivalent hint as from Sonia Keys - quite convincing.
Christian <-RussCox thankyouVeryMuch !

[Steven Blenkinsop]

Nifty function, if you only use int channels...

[Paul Borman]

I:%s/int/MyType/g

[Paul Borman]

This may be true for one usage, but the language must deal with the problem in general, not just one case.  I also think Russ has now provided a nice solution.

    -Paul

[mau...@murus.org]

A big THANKYOU to Ross Cox.
His idea is really good (sort of Columbus' egg).
It looks to me, as if it's consequence is:
Go HAS guarded selective waiting !

So here the (in my opinion very elegant) nucleus of the server's code
for the first readers writers problem based on his hint
(I beg his pardon for calling maybe "when"; so with the syntax we are
near to Ada, Pascal-FC, SR etc.):

func when (b bool, c chan int) chan int {
if b {
return c
}
return nil
}

var nR, nW uint // active readers, writers
for {
select {
case <-when (nW == 0, rE):
nR++
case <-when (nR > 0, rL):
nR--
case <-when (nR == 0 && nW == 0, wE):
nW = 1
case <-when (nW == 1, wL):
nW = 0
}
}

I am going to eat my hat, if that principle is not fully
generalizable.
So you developers PLEASE should take into consideration,
to give a hint to Cox's idea in some proper place in your
documentation !

[Rémy Oudompheng]

Hello,
There is a small wiki at code.google.com/p/go-wiki/ where you might record it.
Rémy.

[mau...@murus.org]

In one of my comments I thanked you for your very favourable idea.
Please do not laugh, as of course a bounded buffer with asynchronous
message passing is trivial,
but with your idea we now also have a nifty (I just learned this word
from a comment from
Steven Blenkinsop) solution to that with synchronous message passing.
(It might not be the "professional" solution, but as an academic
teacher I am interested
in a wide range of possible solutions, also of pure academic
interest):

using channels cI, cG of type chan interface{} (for Insert / Get)
and the (chan int --> chan interface{})-modification "when" of your
function "maybe",
here is the nucleus of the synchronous bounded buffer server:

buffer:= make ([]Any, n) // n = capacity of the buffer
var in, out, count uint
for {
select {
case buffer[in] = <-when (count < n, cI):
in = (in + 1) % n; count++
case when (count > 0, cG) <- buffer[out]:
out = (out + 1) % n; count--
}
}

Is tested, works perfectly. So we now know:
Go has guarded selective waiting. Great.

Kind regards,
Christian

On 31 Jan., 23:25, Russ Cox <r...@golang.org> wrote:

[mau...@murus.org]

Thanks a lot for that hint!
Christian

[mau...@murus.org]

We now know, due to a hint of Sonia Keys and an
(FP based? monad maybe?) idea of Ross Cox,
that this feature need not be added, because Go has it already.
I posted some examples, based on those very helpful answers.

Christian

On 31 Jan., 21:48, Rob 'Commander' Pike <r...@google.com> wrote: