Søk etter:

Published Sept2012, updated 9May2021
This page is in groups Technology and My Go (golang) notes.

Intro

After I had done most of this blog note I started a thread in golang-nuts, also called «Priority select in Go» pointing back to this page, see [7]. It grew quite long. Log-on is required. There also was an earlier thread called «Guarded selective waiting» there, see [10]. Also see my Already in Go? at the end.

Abstract: This page suggests a way to introduce priority to select [1] in the Go programming language. It also introduces an optional side effect free boolean expression that could be used in the guards. And, a «suggestion 2» for a syntax: if there is a boolean expression in one of the guards, the Go compiler will pick prioritised choice. If not it will pick the default pseudo-random choice, being backwards compatible. Also, the viability of this rather strange syntactic mix is discussed.

I will jump straight into it: Today, if «multiple cases can proceed, a uniform pseudo-random choice is made to decide which single communication will execute» [1].

There is no way that I am aware of to write a prioritised select. (However, the golang-nuts comments mentioned above seems to show that this is possible in Go. So, it may be worth while to read all those comments and then this note.)

Most of this blog note concerns a suggestion that a real language designer probably would reject on first look. But of course I wouldn’t know that. Because I am not certain if I am proposing an orthogonal suggestion to the problem. If I am, the product is zero. If I am not, the product is a little more.

Definition

A new specification would in addition also read «if multiple cases can proceed, a prioritised choice is made to decide which single communication will execute. Any case takes priority over the next case, making the first case having highest priority». But there is some syntax that defines when to use prioritised or pseudo-random choice.

Priority here does not define process (goroutine) priority, nor is there any priority attached to a channel. It is the way a simple communication is chosen if multiple cases can proceed.

Rationale

There are reasons to have prioritised select (or PRI ALT) in a channel based or CSP-based language. After all, occam had it, which to me is an important reason in itself. I have used it with occam and several libraries over the last 20++ years in embedded code.

But most importantly: pseudo-random choice and fair choice are not the same. So, both pseudo-random and prioritised choice should be present as tools. Because, what is fair to me may not be fair to you. Or was it the other way around?

But Bill Roscoe in a 2010 book [4] seems to have concluded that prioritised choice is not necessary. I have not read it myself, but I have drawn this from a mail in an occam discussion group [5] (thanks, Ian East!):

Roscoe rejects prioritised choice because it presents problems «when the priority orders of different parallel processes cannot be resolved». More of Ian’s words:

1. in the presence of many low-cost processors (‘cores’), we can usually forget prioritisation in practice
2. where a programming language does incorporate prioritisation, it is better to prioritise events (and their response), in which case there must be an opportunity to declare a partial order over the events concerned over the scope affected.

Still I will proceed as if I were to decide.

Suggestions

Suggestion 1: pri select

The most obvious suggestion is to prefix select with pri, so that the construct will be pri select. However, this does not have the extra effect to introduce another and missing matter into the language:

Suggestion 2: case abool && communicationclause

(Missing and missing. Idiomatic Go sends over a channel with the communication taken by the select, to be used for any future session. The boolean condition is not necessarily necessary. But Go took it away, in a way. Is it time to suggest it into the language?)

I will use the standard term guard for the case here. The other suggestion is to introduce occam-like syntax for PRI ALT [2],[3]. Here is a suggestion of a rewrite of the description of ALT in Wikipedia to suite the suggestion here:

select specifies a list of guarded commands. The guards are a combination of an optional boolean condition and an input or output communication. Each guard for which the condition is true and the input channel is ready is successful. One of the successful alternatives is selected for execution. If any of the guards have an expression, prioritised selection is used, if not pseudorandom choice is done.»

The syntax could look something like this:

var c, c1, c2, c3 chan int
var i1, i2 int
rec, send := true, true
select {
case rec && i1 = <-c1:
    print("received ", i1, " from c1\n")
case send && c2 <- i2:
     print("sent ", i2, " to c2\n")
case i3, ok := (<-c3): // same as: i3, ok := <-c3
    if ok {
        print("received ", i3, " from c3\n")
    } else {
        print("c3 is closed\n")
    }
}

That code is a modified code from [1]. In the situation above select is prioritised. The code is trivial and never changes rec and send. Of course, as the internal state of the program changes, so must rec and send. And, I have not even tried to study the soundness of having rec and send here. But I only wanted to show the syntax. Taken directly from occam.

The good thing is that Go would get conditions in the guards. So the programmer could start a session with a client over the same channel that took the select. and block the others out. Now it would have to pass those channels along with the first communication. The condition would represent a possibility for the programmer to choose any one method.

This syntax is context dependent. (Thanks to Jim Whitehead II for pointing this out to me in a private mail prior to this page.) Some would dislike that. But since expression evaluation in Go by design is not side effect free anyhow (occam had side effect free expressions), Goe has context dependent expressions by design by design, which is good for doubly linked lists etc. Of course, a select may go over several pages, so context dependent syntax may be difficult, if there is real no folding editor around [6].

There are some important traits here:

1. If a prioritised select of this case has all guards with conditions, and all conditions are evaluated to false, then we have a deadlock. The Go runtime system should treat this as any other deadlock
2. The compiler should attach the appropriate choice algorithm, pseudo-random or priority
3. The expression evaluation should be side effect free (or less stringent not contain a function call.) (I have heard stated that conditional expressions were not introduced in go select precisely because generally expression evaluation is not side effect free, and that conditional in this case that allows side effects would open a can of worms.)
4. There is no dynamic handling of which algorithm to use. It’s done at compile time

Discussion of suggestion 2

The selection algorithm and introduction of expressions in guards are two concepts that should not be connected? Maybe.

A falsification criterion (against suggestion 2) would be that:

• if there are situations where pseudo-random choice is wanted and at the same time expression evaluations is needed, then the pri select suggestion 1 should be used.

I fear that suggestion 2 may be easily ruled out by a proper language designer because of the falsification criterion above. But should a proper language designer conequently also rule out suggestion 1?

A contrary argument (for suggestion 2) would be that:

• if hand control of when to take a guard is wanted, then pseudo-random choice is not (or never) needed or explicitly not wanted.

If this is asserted, then suggestion 2 is a good idea, provided one agrees that priorisation is needed at all.

Anyway, I hope this note may spur some discussion around in the thousand homes. Go ahead!

Already in Go?

The threads in golang-nuts [7] and [8] indicate rather strongly that 1.) prioritised choice and 2.) boolean expressions in guards may be simulated by present constructs.

But do remember that my suggestion in this note goes further: to combine the two. See above.

Prioritised choice

I will try to write down some design and test criteria to judge whether a suggested piece of code really implements prioritised choice. This is my list based on occam PRI ALT that I have used for 10 years of my career:

1. A construct must not end in a default clause, because we don’t want to do busy-polling. Example [7.Rog1], which doesn’t!
2. n-pri-select must be of arbitrary number of priorities. Particularly, two components are not enough. Example:  [7.Rog2], which is n-pri.

Unnecessary to say:

1. The capacity of the processor should not redefine what prioritised means. Especially it should always be prioritised, not almost always
2. Changing GOMAXPROCS shall also not redefine .. (see above)
3. I think criterion 2 makes this unnecessary: If the pri-select is in a consumer, the producer must not always committ to a communication with the server, to avoid the system under test becoming livelocked between producer and consumer.

Since Go only has pseudo-random choice in select, priority select must be built on top of that. It is possible! And guess if the golang-nuts people did! As mentioned above there are two very nice examples that Roger Peppe has posted, see  [8] and [9].

boolean expressions in guards

I think this goes in here, and not at the above chapter:

There is a «maybe» function by Russ Cox in  [10] , see here. Rob Pike in [7] states that «A similar sort of thing can already be achieved with a channel-valued closure that returns nil if some condition is not satisfied.»

I am not certain if «maybe» will always be side effect free. And I would have to use one maybe-function per case.

As mentioned in this blog note, Go can already simulate the effect of not having these boolean expressions directly by sending reply channels over in an initial communication.

golang-nuts: Still “missing” priority or ordered select in go?

See 113:[golang-nuts: Still “missing” priority or ordered select in go?] (April-May 2021)

[7] and [8] below point to threads where the select-hi-default-select-hi-low pattern is suggested. This is probabaly shown in the above thread not to be correct.

References

1. Go select specification at http://golang.org/ref/spec#Select_statements
2. occam at Wikipedia: http://en.wikipedia.org/wiki/Occam_(programming_language)
3. and occam 2.1 reference manual at http://www.wotug.org/occam/documentation/oc21refman.pdf
4. Roscoe, A. W. : 2010, «Understanding Concurrent Systems», Springer ISBN 978-1-84882-257-3. This book is seen as successor to is «Theory and Practice of Concurrency».  Chapter 20.2 Priority, pp. 486-496
5. occam-com@kent.ac.uk administered by https://lists.kent.ac.uk/sympa/help/user. An outdated archive (to 2010) is at http://occam-pi.org/list-archives/occam-com/index.html
6. http://www.teigfam.net/oyvind/pub/notes/11_Wishes.html – «Wishes for a folding editor», Øyvind Teig
7. «Priority select in Go», a golang-nuts thread started by me, see
   https://groups.google.com/forum/#!topic/golang-nuts/M2xjN_yWBiQ (Update 9May2021: see «golang-nuts: Still “missing” priority or ordered select in go?» (above))
8. http://play.golang.org/p/1ZVdYlA52x – By Roger Peppe. This does priority select for four channels, so it’s 4-pri kind of. Do observe that there is no select in the bottom-most select in priselect. This took me a day to see while the others were trying to do their best to help! Thanks! (Update 9May2021: see «golang-nuts: Still “missing” priority or ordered select in go?» (above))
9. http://play.golang.org/p/lYKah_7CVw – By Roger Peppe. This is an n-priority select. Not efficient the author said, but quite nice!
10. «Guarded selective waiting», an older thread in golang-nuts, see https://groups.google.com/forum/?fromgroups=#!topic/golang-nuts/ChPxr_h8kUM