015 - In search of Go! programming language rendezvous

Intro

Update: I have (in 2021) bundled this up in my My Go (golang) notes even if this note is not about Go/golang at all.

I would not have known about the Go! programming language [1] if I had not been made aware of the Go programming language [2]. Since I liked so much of what I read about Go's concurrency solutions, what was more close than to have a look at Go!!

(Why Go! with an exclamation mark, a punctuation mark in the name? It's a smart language, but the whole idea of including ! in it, is this the reason why even Google didn't detect? See the mismatch above, the paragraph ended with two !!, not at same semantic level!) 

Name aside. I ordered the "Let's Go!" book [3] to have right here, beside me, since originally, I concluded there's no Go book to hold on to yet (Jan.10). The stuff I write here will be with reference to Let's Go! - but there's a "Go! reference manual" that's included in Go!'s download package. You'll find much of it there.

I will do no programming here.

Go! & concurrency

Go! is an object oriented, functional, procedural and logic programming language. I should study it, I see that I have a lot to learn. However, it is also multithreaded. My home field, even if I only know this little corner.

A user "spawns off computations as separate threads or tasks". It handles synchronized sharing of resources and coordination of activities. But a process (I prefer that here for thread or task) is not a primary citizen of the language. If you don't use a shared resource correctly, or don't comunicate between processes correctly, well - it's your problem.

However, there's sync that's built into the language (like synchronized in Java, I guess). It'd better be, it's harder not to, if you need them. Message communication is through a library: go.mbox is the standard message communication library.

Go! & sync

There is a sync mechanism. Any stateful object may be protected with sync. A stateful object uses @> where a statefree uses @= as class constructor. A stateful object seems to be a blacker box, since instance variables are only accessable through access methods. However,  there must be more to it than this, i.e. some stateful objects may not be protectable by sync, or some protectable with sync are not stateful (I don't know), since the book points out that deciding whether sync may be used around an object may have to be delayed until run time.

sync may have timeout.

sync may be guarded. According to the value a guard or guards, the sync will pick a choice. I don't know if the language requires the guard to be thread safe, local and not exportable from the process where the guard is used. I'm afraid not. The choice is prioritized, it runs the first (in time) first if several are ready. I don't see any non-determinstic choice. Also, I assume that fairness must be explicitly programmed, if it's a matter of concern. And since the guards only must be evaluated to true, then non-determinism may be programmed through random numbers. (But on a formal level non-deterministic and random choice are not the same [4].)

sync may also be used for notification. So, Java's synchronized and notify is not needed, since it's all in one mechanism here? An object sync'ed on a list may be notified when the list becomes non-empty. Nice! But only one object, so Java's notifyAll is not supported. (But ..All in Java may be too many, so they will have to go to sleep again if it weren't for me..)

In [3] page 177 McCabe points out that

The central message about the use of sync is that it makes for an excellenet way of resolving access contention for shared resources. On the other hand, sync is a perfectly terrible technique for coordinating multiple threads of activity. The reason is that there is no direct way of esatblishing a rendezvous of two or more threads with sync. For that we recommend looking at the go.mbox message communication library.

So, sync makes it possible to make thread-safe libraries.


Go! & Mailbox / Dropbox

First, what is a rendezvous? According to the Wikipedia disambiguation page it's "A communication method of Ada (programming language)". Going into the Ada page there's no mentioned of it (yet..). However, it is a place in code where the first one to arrive (be it sender or receiver) waits for the second to arrive. Then they exchange their data. Then both processes continue. The important things here are:

1. A rendezvous involves no message buffers
   (References to process local data are carried into the rendezvous)
2. A rendezvous involves blocking
   (But it's never busy-polled, and beware that this does not mean that less gets done! At the end of the day in any paradigm, when something isn't ready it isn't.)

I have discussed much of this in my blog 007 - and what it might be good for.

Ada's concurrency is based on C.A.R. Hoare's process algebra CSP (Communicating Sequential Processes). Just like Go's is! (Beware no exclamtion mark). Just like the first runnable language: occam. Just like like the formal language Promela. I say "based on", menaing they are all dialects.

So, I would need to investigate Go!'s mailbox. The concept is that a mailbox is shared, and that processes drop mail in a mailbox with a dropbox. There is one way to drop: use the post method. It is typed of course, but there is no way to block on it. So, the programmer who thinks that things get easier that way (sometimes it does!), just sends and forgets.

A Go! mailbox is for multiple writers, single reader (many to one). It handles coordination, but has specificly been designed not to handle synchronization. In CSP, those are the same things, since scheduling is driven by the rendezvous (or, in the speak I am used to: the channels drive the scheduling, or: the scheduler is just a channel handler (if it's not preemptive, which the model is neutral to)).

Since a Go! mailbox is for multiple writers, single reader, and since there is no addressing or placement, it is the use of them that governs the "addressing". In CSP, one communicates on a named channel (changed from the 1978 to the 1985 version, to better facilitate libraries), which could be not connected or connected or being sent on a channel (occam-pi and Go)). Also, the usage of them is not verified (onlike occam / occam-pi).

The Go! mailbox reader process may block. Blocking means that you don't have to busy-poll for data. A reader may instruct the mailbox to search in the mailbox for matching messages, and block if there isn't any.

This is nice! However, I fail to see the rendezvous in it.

Go! & perhaps some suggestions

I don't know Go! well, and am not aware of the language's application domain, but provided, as the book mentions, a rendezvous with the properties listed above are of any interest to its users, then I have some suggestion.

Observe that I don't want Go! to be equal to any other language!

The suggestion is to add more "symmetry" to Go! The occam realization of has input ALTs with guards, but not output ALTs. Promela has both, with guards. I believe that CSP describes both.

Go! has protected regions with sync with guards, this should be symmetric enough? But it has blocking on read of a mailbox, not blocking on send.

1. Blocking on sending: If I drop "any data" in a dropbox, it could block if the receiver does not need "any data". Or, if the receiver waits for a list of names, then block until somebody supplies it. This could make up an interesting type of  many-to-one "channel".

2. Return to known: occam has a way to directly identify where a reply is to be sent. In Go! it has to be coded. Occam does this by putting a many to one channel into an array of channels, and the receiver ALTs on that array. The index of the array falls out of the ALTing even if it's never sent by the sender, so the receiver knows where to send a reply.

3. Propagate guards into the mailbox system: I don't see in Go! that we could put an input guard into the mailbox. If a process wants to accept inputs from set A=[a,b,c,e,f], then if set B=[d] tries to dropbox, it would block. One event in A must happen before B (on perhaps a next round) would be triggered. Guards are constant when they are used.

Would this CSP stuff be interesting to put into an object oriented, functional, procedural and logic programming language with support for concurrency (Go!)? If yes, what would it be good for?

Disclaimer

This note has been written with most knowledge about the CSP type concurrency and some of its implementations. My knowledge about Go! is next to none. Therefore, there may be smart combinations of the concurrency related facets and the other primary citizens of the Go! language that could make this note in error. Please comment and I will change!

Another thing: my suggestions may well fail a verification if modeled in a formal language. Since I have moved things into the mailbox system and included more blocking, it could cause safetly and liveness property violations. In other words, it may not be possible to make a safe language with these features. I hope I am wrong!

References

[1] - Go! programming language, see http://en.wikipedia.org/wiki/Go!_(programming_language)

[2] - Go programming language, see http://en.wikipedia.org/wiki/Go_(programming_language)

[3] - Let's Go! Francis (Frank) G. McCabe (ISBN 0-9754449-1-3), 2007

[4] - Non-deterministic and random choice, a little about this at http://en.wikipedia.org/wiki/Promela#Case_Selection