[ANN] Hoare's CSP paper in Go

[Thomas Kappler]

Hi gophers,

Tony Hoare's paper 1978 paper "Communicating sequential processes" is one of the great influential papers in Computer Science. I had heard about it at uni, forgot about it, then re-discovered it as one of the inspirations for Go. The best way to really grok something is to do it, so I implemented all examples from Hoare's paper in Go. This code is supposed to be purely educational and is not intended for practical use.

The godoc has more info and comments for each section: http://godoc.org/github.com/thomas11/csp. Clicking the headers takes you directly to the code.

-- Thomas

[Jim Whitehead II]

Cheers for this, very relevant to my work! Do you have any plans to write things up further, or post it to a more permanent location? I'd love to cite the work in one of the early chapters of my thesis.

- Jim

-- Thomas

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Thomas Kappler]

On Sunday, April 7, 2013 8:48:34 PM UTC+2, Jim Whitehead wrote:

Cheers for this, very relevant to my work! Do you have any plans to write things up further, or post it to a more permanent location? I'd love to cite the work in one of the early chapters of my thesis.

Thanks! Not sure if I'll expand much more, but I'll write a short post on my website soon. Will let you know when it's up!

- Thomas

[John Nagle]

P and V, and bounded buffers, predate Hoare's paper. They're from
earlier work by Dijkstra from the 1960s. See

http://www.cs.utexas.edu/~EWD/transcriptions/EWD01xx/EWD123.html

Implementing P and V on top of channels is kind of backwards. Channels
themselves are usually implemented in terms of P and V.

Here's an implementation of P, V and bounded buffers from 1972:

http://www.fourmilab.ch/documents/univac/fang/hsource/scheduler.asm.html
(part of http://www.fourmilab.ch/documents/univac/fang/)

This is in UNIVAC 1108 Assembler. John Walker wrote those in
1972. 8 machine instructions, and no system calls, for P in the
non-blocking case.

Further down in the same file are the bounded buffer operations,
which do what Go channels do, in very few machine instructions.
A bounded buffer is two P/V type semaphores and a buffer. Notice
how few instructions each operation requires.

Go's "sync" primitives (http://golang.org/pkg/sync/) are perhaps
too high level. Everything there could be implemented in terms
of P, V, and PMAY (the non-blocking form). Get those right and
make them fast, and everything else falls into place. Many
modern implementations botch this by making a system call for
a non-blocking semaphore lock.

UNIVAC Exec 8 had user threads (they were called "activities")
from 1967, long before other operating systems. It also supported
shared memory multiprocessors. So concurrency had to be
managed properly in parallel programs. UNIX was originally
single thread per process and single-CPU, and DOS didn't even
have a dispatcher. The growth of UNIX (and DOS) made
people forget how to do this.

John Nagle

[John Nagle]

On 4/7/2013 11:25 AM, Thomas Kappler wrote:

[Thomas Kappler]

Please ignore the other reply I accidentally sent from my work email.

On Sunday, April 7, 2013 11:57:32 PM UTC+2, John Nagle wrote:

   P and V, and bounded buffers, predate Hoare's paper. They're from
earlier work by Dijkstra from the 1960s.

John, unfortunately I don't know what P and V are in this context nor how your reply relates to my post. Could you elaborate?

My intention was merely to implement Hoare's paper in Go in order to fully understand it.

- Thomas

[Andreas Krennmair]

Just one comment: in S31_COPY, you signal the end by sending a 0. The idiomatic way to signal end-of-transmission on a channel in Go is to close the channel with close(east).

Regards,

Andreas

On Sun, Apr 7, 2013 at 8:25 PM, Thomas Kappler <tkap...@gmail.com> wrote:

-- Thomas

[chris dollin]

On 8 April 2013 09:54, <thomas....@nhumi.com> wrote:

What are you referring to here? Unfortunately I can't see what P and V are and how they relate to Hoare's paper.

P & V are the basic semaphore operations:

http://en.wikipedia.org/wiki/Semaphore_%28programming%29

--
Chris "allusive" Dollin

[Peter Weinberger]

The 1108 was a wonderful machine (at least in my dim memory).  The assembly language was natural (meaning I found it easy to write), and Exec 8 was interactive (of course they called it time-sharing).

[James Bardin]

On Sunday, April 7, 2013 5:57:32 PM UTC-4, John Nagle wrote:

   P and V, and bounded buffers, predate Hoare's paper. They're from
earlier work by Dijkstra from the 1960s.  See

http://www.cs.utexas.edu/~EWD/transcriptions/EWD01xx/EWD123.html

Implementing P and V on top of channels is kind of backwards. Channels
themselves are usually implemented in terms of P and V.

Also, the goroutine for the S52_Semaphore is a busy-loop; both select blocks have an empty default, and may not yield at all (it times out on play.golang.org).

[John Nagle]

On 4/8/2013 1:54 AM,

thomas....@nhumi.com wrote:
>
>
> On Sunday, April 7, 2013 11:57:32 PM UTC+2, John Nagle wrote:
>>

>> On 4/7/2013 11:25 AM, Thomas Kappler wrote:
>>> Hi gophers,
>>>
>>> Tony Hoare's paper 1978 paper "Communicating sequential processes" is
>> one
>>> of the great influential papers in Computer Science. I had heard about
>> it
>>> at uni, forgot about it, then re-discovered it as one of the
>> inspirations
>>> for Go. The best way to really grok something is to do it, so I
>> implemented

>>> all examples from Hoare's paper in Go. ...

>>
>> P and V, and bounded buffers, predate Hoare's paper. They're from
>> earlier work by Dijkstra from the 1960s. See
>>
>

> What are you referring to here? Unfortunately I can't see what P and V are
> and how they relate to Hoare's paper.

See lines 572-575 of the code you wrote, where you implemented P and V:

// > "Problem: To implement an integer semaphore, S, shared among an array
// X(i:I..100) of client processes. Each process may increment the
// semaphore by S!V() or decrement it by S!P(), but the latter command must
// be delayed if the value of the semaphore is not positive."

https://github.com/thomas11/csp/blob/master/csp.go#L632

John Nagle

[Thomas Kappler]

Ah, of course. Was a little dense here. I am familiar with Dijkstra's semaphores, but P and V didn't click.

I agree that implementing a semaphore on top of channels, which are (probably) implemented using semaphores, makes no sense in practice. My goal here was simply to follow Hoare in exploring how the concurrency primitives might be used to do so, as an intellectual exercise if you will.

 Thanks for the clarification and the background information.

- Thomas

[Thomas Kappler]

On Monday, April 8, 2013 5:53:04 PM UTC+2, James Bardin wrote:

Also, the goroutine for the S52_Semaphore is a busy-loop; both select blocks have an empty default, and may not yield at all (it times out on play.golang.org).

Thanks for the report. I see now that the implementation is broken. Of course it was the one without a test...

I just pushed a new version with a single select in the goroutine's for loop.

- Thomas

 

[John Nagle]

On 4/8/2013 10:09 AM, Thomas Kappler wrote:
> On Monday, April 8, 2013 5:53:04 PM UTC+2, James Bardin wrote:
>
>>
>> Also, the goroutine for the S52_Semaphore is a busy-loop; both select
>> blocks have an empty default, and may not yield at all (it times out on
>> play.golang.org).
>>
>
> Thanks for the report. I see now that the implementation is broken. Of
> course it was the one without a test...

If you want to implement P and V, look at the code for WaitGroup.

http://golang.org/src/pkg/sync/waitgroup.go

That's very similar to P and V.

A good exercise is to implement P and V with atomic operations
such that there are no system calls for the non-blocking cases.
That's useful to have.

John Nagle

[John Nagle]

On 4/7/2013 7:58 PM, John Nagle wrote:
> On 4/7/2013 11:25 AM, Thomas Kappler wrote:
>> Hi gophers,
>>
>> Tony Hoare's paper 1978 paper "Communicating sequential processes" is one
>> of the great influential papers in Computer Science. I had heard about it
>> at uni, forgot about it, then re-discovered it as one of the inspirations
>> for Go. The best way to really grok something is to do it, so I implemented
>> all examples from Hoare's paper in Go. This code is supposed to be purely
>> educational and is not intended for practical use.
>>
>> The godoc has more info and comments for each section:
>> http://godoc.org/github.com/thomas11/csp. Clicking the headers takes you
>> directly to the code.
>>
>> -- Thomas
>
> P and V, and bounded buffers, predate Hoare's paper. They're from
> earlier work by Dijkstra from the 1960s. See
>
> http://www.cs.utexas.edu/~EWD/transcriptions/EWD01xx/EWD123.html
>
> Implementing P and V on top of channels is kind of backwards. Channels
> themselves are usually implemented in terms of P and V.

....

> Go's "sync" primitives (http://golang.org/pkg/sync/) are perhaps
> too high level. Everything there could be implemented in terms
> of P, V, and PMAY (the non-blocking form). Get those right and
> make them fast, and everything else falls into place. Many
> modern implementations botch this by making a system call for
> a non-blocking semaphore lock.

That's the real point I'm making here. P and V, if implemented
properly, are both very fast and provide a basis for all the other
operations, including bounded buffers.

Optimal P and V implementations are platform-dependent. You
can build them using atomic increment, compare and swap, or test
and set. But you need to choose one of those that's very fast
on the target platform, and this varies with target platform.
They often require instructions which compilers usually don't
emit, so they're usually written in assembler. But not
many instructions; these are short, very carefully written bits of
assembler.

After a V, even one that doesn't wake up anything, it's necessary
on some platforms to perform a memory fence operation to sync caches.

Once you have P and V, you're above the machine level,
don't have to worry about that stuff again, and can write portably
in a high level language. Get P and V right, and critical section
overhead is very low. POSIX or Win32 locking primitives have
much higher overhead.

John Nagle

[Ian Lance Taylor]

The way the Go runtime is structured, the functions in sync can't be
pure assembler code, because on the slow path they need to interact
with the Go scheduler.

The functions that are pure assembly are the ones in sync/atomic.

Ian