5.1 Sieve of Eratosthenes

The problem here is to find all the prime numbers less than or equal to k. We do it with a Felix "circuit" of fibres and s-channels.

The control token exchanged along the s-channels consists of a number and a list of candidate primes.

  typedef il_t = int * list[int];

A client filters multiples of the number from the list to produce a new list and, as long as there's a "next" filtering to apply, spawns a new client for that.

If there aren't any more filterings to be applied, the client transfers control back to the server.

  proc client (x:ischannel[il_t], y:oschannel[il_t])
  {
    var p, l = read x;
    l = List::filter (fun (e:int) => (e%p != 0 or e/p == 1)) l;
    var r = List::find (fun (e:int) => e > p) l;
    match r with 
    | #None => 
      write$ y, (0, l); //We're done
    | Some x => 
      inp,out:=#mk_ioschannel_pair[il_t];
      spawn_fthread { client (inp, y); };
      write$ out, (x, l);
    endmatch;
  }

The server seeds the computation by generating a range of integers from 2..(k + 1) and spawns a client to filter those that are multiples of 2.

  proc sieve (k:int)
  {
    inp,out:=#mk_ioschannel_pair[il_t];
    spawn_fthread { client (inp, out); };
  
    var l = List::range (2, (k + 1));
    write$ out, (2, l);
  
    val i, res = read inp;
    println$ "Primes: " + str (res);
  }

The whole process begins by calling the server with a value for k.

  val k = 1000; //Run with FLX_MIN_MEM=500 (MB) for k=5000
  sieve k;

For k = 100 you should observe output something like:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97