A Tour Of Go Language

Welcome » NERWous C » Examples

1. Go Concurrency
2. Fibonacci Example
3. Mutex Example

---

Go Concurrency

The Go language is an open-source programming language created by Google in 2009. It supports concurrency via Goroutines and channels. The NERWous C equivalents are pel constructs, and mel entities.

---

Fibonacci Example

The Fibonacci sequence appears frequently in mathematics, computer algorithms, and biology settings.

Go Implementation:

The Go language Fibonacci example displays the first 10 Fibonacci numbers (i.e. 0, 1, 1, 2, 3, 5, 8, 13, 21,34). This implementation is copied from the Tour Of Go tutorial:

package main
import (
 "fmt"
)
func fibonacci(n int, c chan int) {
 x, y := 0, 1
 for i := 0; i < n; i++ {
  c <- x
  x, y = y, x+y
 }
 close(c)
}

func main() {
 c := make(chan int, 10)
 go fibonacci(cap(c), c)
 for i := range c {
  fmt.Println(i)
 }
}

The Go example has main creating the channel c then forking a light-threaded task via the go command to run the fibonacci function in concurrency. The fibonacci task feeds the channel c whenever it has computed the next number for the sequence. The main task waits on the channel c for any new value to show it on the console via the Println command.

NERWous C Implementations:

We will do several versions of the NERWous C implementations to illustrate different features of the language.

Version 1:
Version 1 follows closely the Go implementation by replacing the Goroutine and Go channel with the pel and mel constructs of NERWous C:

/* VERSION 1 */
void main () {
  <mel> int c;
  <!> fibonacci (10, c);
  for (int i=0; i<10; ++i)
    printf ("%d", <?>c);
}
int fibonacci (int n, mel int c) {
  int x = 0, y = 1;
  for (int i = 0; i < n; ++i ) {
    <?>c = x;
    x = y; y = x + y;
  }
  <close>c;
}

The mel variable c is shared between the main task and the fibonacci task. The main task is the reader and the fibonacci the writer. When main tries to read out from the mel c and the fibonacci has not generated a value for it, main will wait at the mel wait operator <?>. When the mel channel c is filled, main reads out that value and makes the mel c empty again.

The fibonacci task needs the mel channel c to be empty so that it can deposit the x value. If the reader main is slow in removing the previous value, the fibonacci writer has to wait at the mel wait operator <?>.

Although the main and fibonacci tasks run in concurrency, they work in lock step due to the synchronizing chock point at the mel channel c. To possibly increase the concurrency, we can add buffering to the mel c:

<mel buffer=10> int c;

Version 2:
In the second version, we will drop the mel variable c and use the return value of the pel task as the communication channel.

/* VERSION 2 */
void main () {
  <pel> p = <!>fibonacci (10);
  for (int i=0; i<10; ++i)
    printf ("%d", <?>p);
}
int fibonacci (int n) {
  int x = 0, y = 1;
  for (int i = 0; i < n; ++i ) {
    <release> x;
    x = y; y = x + y;
  }
}

The return value of a pel task is a read-only mel. Via the <release> statement, the pelled task "streams" values to any task that is waiting on that return value channel. Unlike Version 1 where the main task depends on the mel entity to be filled, the main task in Version 2 uses the sequence number to make sure it does not process stale values.

Version 3:
The third version builds on the second version by having the main task keeps checking the released value of the fibonacci task until this task ends itself.

/* VERSION 3 */
void main () {
  <pel> p = <!> fibonacci (10);
  while ( 1 ) {
    try { printf ("%d", <?>p); }
    catch (p<ENDED>) break;
  }
}
int fibonacci (int n) {
  int x = 0, y = 1;
  for (int i = 0; i < n; ++i ) {
    <release> x;
    x = y; y = x + y;
  }
}

When the fibonacci task runs off its last statement, it will end itself. This triggers the ENDED exception at the main task which uses it to break out of the infinite while ( 1 ) loop.

---

Mutex Example

The Go language support the concept of a mutex for mutual exclusive access to shared data. A Go language block of code can be executed in mutual exclusion by being surrounding with a Lock and Unlock calls.

Go Implementation:

The Go implementation is taken from Tour of Go tutorial:

package main

import (
 "fmt"
 "sync"
 "time"
)

// SafeCounter is safe to use concurrently.
type SafeCounter struct {
 v   map[string]int
 mux sync.Mutex
}

// Inc increments the counter for the given key.
func (c *SafeCounter) Inc(key string) {
 c.mux.Lock()
 // Lock so only one goroutine at a time can access the map c.v.
 c.v[key]++
 c.mux.Unlock()
}

// Value returns the current value of the counter for the given key.
func (c *SafeCounter) Value(key string) int {
 c.mux.Lock()
 // Lock so only one goroutine at a time can access the map c.v.
 defer c.mux.Unlock()
 return c.v[key]
}

func main() {
 c := SafeCounter{v: make(map[string]int)}
 for i := 0; i < 1000; i++ {
  go c.Inc("somekey")
 }

 time.Sleep(time.Second)
 fmt.Println(c.Value("somekey"))
}

NERWous C Implementations:

NERWous C is the NERW Concurrency Model grafted on the C language, and the C language does not have native support for map nor string. The following NERWous C language implementations make use of a simple array with integer as index. This will not diminish the discussion on Mutex which is the focus here.

Version 1:

/* VERSION 1 */
#include "keys.h"
<mel>int SafeCounter[NUMKEYS];

void Inc (int somekey) {
   <?>SafeCounter[somekey] {
      SafeCounter[somekey]++;
      <checkout replace>;
   }
}

void main () {
   for (int i=0; i<NUMKEYS; ++i)
      <?>SafeCounter[i] = 0;

   int somekey = random(0, NUMKEYS);
   for (int i=0; i<1000; ++i) {
      <!>Inc (somekey);
   }
   sleep (1000);
   printf ("%d", <?>SafeCounter[somekey]);
}

In the first version, we first declare SafeCounter as a global mel array that can contain NUMKEYS items. The value of NUMKEYS come from the include file keys.h.

The main task runs a serial loop to initialize to 0 each of the item of SafeCounter. It then generates a random number between 0 inclusive and NUMKEYS exclusive via a custom function random (which we do not show the implementation). The main task then runs a second serial loop for 1000 iterations. In each iteration, it forks a new task via the pel construct to run the Inc function in parallel.

Inside the Inc function, the deceptively simple auto-increment means a read of the value of the mel entity SafeCounter[somekey], increment that value, and write that value back to the mel entity. Since the read and write must be atomic, all the mentioned operations must be inside a mel reader zone for mutual exclusion. When an Inc task is in the exclusive zone, all the other Inc tasks that needs access to the same SafeCounter[somekey] entity, must queue up in that entity's queue.

The first Inc task that comes to the reader zone can see that the conditions to get into the zone are satisfied. These conditions are the mel entity is valued and that value is not stale. These conditions are made satisfactory by the main task when it initializes all the items in the SafeCounter array to zero.

After doing the auto-increment using the local eponymous variable SafeCount[somekey], the Inc task writes back that value to the shared mel entity via the <checkout replace> operation. Without the replace attribute, the default checkout behavior is to remove the value from the mel entity. This would cause all the waiting Inc tasks to wait forever since there is no new writer task to deposit a fresh value to the mel entity to satisfy the reader zone entry condition.

Back to the main task, we see that it wants to display the final value of SafeCount[somekey]. Since it does not know when all the pelled Inc tasks will all finish, it sleeps for 1 empirical second. To access the mel value at that time, the main task just use the mel read statement <?>SafeCounter[somekey]. There is no need for using a mel read exclusive zone since a NERWous C mel read natively enforces mutual exclusion.

Version 2:
Let's revise the above implementation. Since NERWous C supports inline code blocks, we can drop the Inc function and move its work inside the main task:

/* VERSION 2 */
#include "keys.h"
<mel>int SafeCounter[NUMKEYS];

void main () {
   for (int i=0; i<NUMKEYS; ++i)
      <?>SafeCounter[i] = 0;

   int somekey = random(0, NUMKEYS);
   for (int i=0; i<1000; ++i) {
      <!> <?>SafeCounter[somekey] {
      SafeCounter[somekey]++;
      <checkout replace>;
      }
   }
   sleep (1000);
   printf ("%d", <?>SafeCounter[somekey]);
}

Version 3:
Since auto-increment (and decrement) are frequently used operations, NERWous C supports shortcuts that skip mentioning the explicit use of the mel read zone:

/* VERSION 3 */
#include "keys.h"
<mel>int SafeCounter[NUMKEYS];

void main () {
   for (int i=0; i<NUMKEYS; ++i)
      <?>SafeCounter[i] = 0;

   int somekey = random(0, NUMKEYS);
   for (int i=0; i<1000; ++i)
      <!> <?>SafeCounter[somekey]++;

   sleep (1000);
   printf ("%d", <?>SafeCounter[somekey]);
}

Version 2 and 3 are the same. In both Versions, the mel entity is replaced in place, thus preserving its sequence number. The next task that accesses the mel entity will see a new value but the same sequence number. Sequence numbers are used to prevent re-processing of stale values. This is not an issue with the Mutex example here, since each pelled task that does the auto-increment goes through the SafeCounter[somekey] mel entity once and does not do loops. Loops are where stale values can be encountered.

Version 4:
In the previous versions, we have a sleep operation because we want to display the final value of SafeCounter[somekey], but since the auto-increment tasks run in parallel, we don't know when they all finish. The one second is an empirical value that seems to work in the running environment. (If it does not, just increment it until it does.) NERWous C supports a pel-for loop that allows us to remove the sleep operation:

/* VERSION 4 */
#include "keys.h"
<mel>int SafeCounter[NUMKEYS];

void main () {
   for (int i=0; i<NUMKEYS; ++i)
      <?>SafeCounter[i] = 0;

   int somekey = random(0, NUMKEYS);
   <begin> { for (int i=0; i<1000; ++i)
      <!> <?>SafeCounter[somekey]++;
   } <? ENDED>;

   printf ("%d", <?>SafeCounter[somekey]);
}

Encapsulating the for loop inside the begin-wait-ended block ensures that all pelled tasks in the for loop have ended before the programming flow continues. When main issues the printf command in Version 4, it is assured that all auto-increment tasks are done and the mel entity SafeCounter[somekey] contains the final value.

Version 5 (Serial):
There is no NERWous C Version 5. Version 4 is as compact as it can be. However notice that if we strip out the NERWous C pel and mel constructs, we end up with the correspondent C program:

/* VERSION 5(Serial)  */
#include "keys.h"
int SafeCounter[NUMKEYS];

void main () {
   for (int i=0; i<NUMKEYS; ++i)
      SafeCounter[i] = 0;

   int somekey = random(0, NUMKEYS);
   for (int i=0; i<1000; ++i)
      SafeCounter[somekey]++;

   printf ("%d", SafeCounter[somekey]);
}

Sometimes, with NERWous C, by sprinkling some <?> and <!> here and there, we transform a serial program into a concurrent program without much ado.

---

Previous Next Top