The Sieve demo (start/DRAFT)

To show some features of CCastle, I use ‘the sieve’, short for the Sieve of Eratosthenes. An old, well known, algorithm to find prime numbers; with impliciet concurrency.

With an almost trivial implementation, many “CC concepts” can be shown. In only a handful of lines….

The design

We only need tree simple components as shown below, and a main component (not shown). We also use two protocols, that are given below.

The elements of the sieve

CCastle use “components” [1] as main decomposition. Each kind of component can be instantiated multiple times; sometimes called a element, or also just component. This is very like “classes” and “objects” in OO [2].

Let’s introduce the those components

Generator

This component generates just numbers, which will be tested for prime (see below). As primes are always integer bigger then one; it output is the stream stream of numbers: 2,3,4, …

Sieve (on prime)

We use a (growing) chain of sieve-elements. Each one is the same; except for the sieving-constant –a already found prime. That number is set when instantiating the element.

Each Sieve tries to divide each incoming number to its own, sieve-constant. When the modulo isn’t zero, we call it a coprime (relative to the already tested primes) and send downstream. When it can be divided, the number is clearly not prime and ignored

Finder

Each number that comes out of the chain of sieves is a prime (that is the algorithm; see Wikipedia for details). It is collected by the finder. For each found prime, an extra sieve (element) is created and added to the chain. This kind of shifts the finder to the right (aka downstream)

In some implementations that is the responsibility of the finder (therefore sometimes calls “head”). In a variant, the ‘main’ component is caring that load.

Communication

protocol StartSieve : Protocol {
     kind: event;
     runTo(int:max);
}

protocol SimpleSieve : Protocol {
     kind: event;
     input(int:try);
}

This version has one main change: the SimpleSieve now inherits from SlowStart

protocol StartSieve : Protocol {
     kind: event;
     runTo(int:max);
}

protocol SimpleSieve : SlowStart(1) {
     input(int:try);
}

Aside of that, the kind: event line is gone, as it inherited from SlowStart

SimpleSieve.try(newPrime) on self.generator.found
{
   ...
   // When ``Sieve(2)`` is made (alias: s)
   self.generator.outlet = s2.try;
   self.generator.outlet.queue.removeLimit();
   ...
   // Simular for other ``Sieve’s``
   self.lastSieve.coprime = s.try;
   self.lastSieve.coprime.queue.removeLimit();
   ...
}

CCastle uses “protocols” to communicate between components. There are several kind of protocols; we use the ‘event’ kind here. Two ports can be connected when both use the same protocol.

Notice, that a protocol is not the same as an API in most language’s. A fundamenta concept of Concurrent//Connected Components (ToDo)/CCastle is the strict seperation between outside and inside

StartSieve

The StartSieve protocol signals to start sieving (so generating numbers), and when to stop. This “max” number is the maximal number to be tried, and does not need to be a prime.

Currently, the is no way to specify the number of primes to be found.

SimpleSieve

In this variant [3], we use an event-based protocol, that just hold one event (read: a message), that carries the integer to be tried.

In the Original version, it was a basic Protocol. Which worked fine until we studied the another machinery: LibDispatch, and it become clear we had a Heisenbugs! (See there for details.)
Now, we use an improved version, where we use a simple push-back algorithm by inheriting from SlowStart. This adds a queue to the model, that limits (slows down) the sender to a maximum number of (unhandled) events; in this case that is initially: only one event SlowStart(1).

Note

Without going into details, it important to realize the queue is only added in the model! Depending on the The Machinery (ToDo) it will probably not exist in the computer-code.
For example, the DirectCall machinery will never need, not use this queue

It also shows normal Castle-programmer can focus on the functional aspect of the protocol. The SimpleSieve doesn’t need any extra message to controll this SlowStart (or sliding windows, as is also know) algorithm. That is fully handled in a generic base-protocol.
Additionally, the even more technical aspect of how to send events between (CC) components are completely hidden. As long as both components use the same protocol it will work. ref:TheMachinery will make sure that both components use the same technical details on both ends.

Main

All the components (or elements) above have to created (statically or dynamically) by an top-level component, which is usually called “main”. However the name is not special (like in C/C++), it’s more a convention (like in Python).

XXXX

The Code

Moat (interfaces)

component Generator : Component {
  port StartSieve<in>:controll;
  port SimpleSieve<out>:outlet;
  port SimpleSieve<in>:collect;
}

component Sieve(onPrime:int) : Component {
  port SimpleSieve<in>:try;
  port SimpleSieve<out>:coprime;
}

component Finder : Component {
  port SimpleSieve<in>:newPrime;
  port SimpleSieve<out>:found;
}

Castle (implementation)

implement Generator {
  int maxValue;

StartSieve.newMax(max) on self.controll
{
  self.maxValue := max;
}

StartSieve.runTo(max) on self.controll
{
  int i;

  self.maxValue := max;
  i:=0;
  while (i < self.maxValue) {
    self.outlet.input(i);
  }
}

SimpleSieve.input(foundPrime) on .collect
{
  static int count:=0;
  count :+= 1;
  printf("Generator: Collected prime (no %s): %8i\n", count, foundPrime);
}
} //@end Generator

implement Sieve {
  int myPrime;

-init(onPrime:int)
{
  super.init();                                                           //note 'super' acts as a port
  self.myPrime := onPrime;
}

SimpleSieve.input(try) on .try
{
  if ( (try % self.myPrime) !=0 ) {
    self.coprime.input(try);
  }
}
} //@end Sieve

implement Finder {

SimpleSieve.input(foundPrime) on self.newPrime
{
  // Send out the newPrime,
  self.found.input(foundPrime);
}
} //@end Finder

implement Main {
  sub generator;
  sub finder;
  alias lastSieve;         // The list of Sieve's grow dynamicly!; keep track of the last one

-init()
{
  self := super.init();

  .generator := Generator.new();
  .finder    := Finder.new();

  .generator.outlet = .finder.newPrime; // Initially, there aren't any Sieves
  self.lastSieve := Ground; // Not needed, as it is default. But is clearifies the code below
}

// We have build the sievelist (and reconnect) on a newly found prime ..
SimpleSieve.try(newPrime) on self.generator.found
{
  alias s;

  // Extent the sieve-list ...
  s:= Sieve.new(newPrime);
  s.coprime = self.finder.newPrime;
  if (not self.lastSieve == Ground) {              // .lastSieve == Ground, so not connected, so we have the first Sieve to connect to .generator
    self.generator.outlet = s.try;
    self.generator.outlet.queue.removeLimit();
  } else {
    self.lastSieve.coprime = s.try;
    self.lastSieve.coprime.queue.removeLimit();
  }
  .lastSieve := s;

  self.generator.collect.input(newPrime);   // forward the prime to the Generator
}

powerOn() on self.power
{
  int max := 10;

  self.generator.runTo(max);
}
} //@end Main

Footnotes