# The Symphony IDE

Formal Modelling for Systems of Systems

Go to our GitHub Profile

## Sieve

Author: Jim Woodcock

The prime number generator is based on the classic algorithm of the Sieve of Eratosthenes, but implemented in a dynamic systolic array. The example shows how to use concurrency, recursion, and hiding together in quite a subtle way to implement an infinite computation in a lazy, reactive behaviour. It shows how to encode the use of dynamic channel and process creation with tokens, important idioms in CML for this pattern for reconfigurable systems.

### Sieve.cml

``````-- Optimised sieve
--
-- Input: an integer n > 1
--
-- Let A be an array of boolean values indexed by integers 2 to n,
-- initially all set to true.
--
-- for i = 2,3,4,..., not exceeding sqrt(n)
--   if A[i] is true then
--     for j = i^2, i^2+1, i^2+2i,..., not exceeding n
--       A[j] := false
--
-- Output: all i such that A[i] is true

channels
ch: nat * nat
newch: nat
atfilter: nat * nat *nat
atsieve: nat * nat

process Primes =
begin
actions
Chans = i: nat @ newch!i -> Chans(i+1)

Filter = p,i,o: nat @
atfilter!p!i!o ->
while true do
ch.i?x ->
if x mod p <> 0
then
ch.o!x -> Skip

Sieve = p,c: nat @
atsieve!p!c ->
ch.c!p ->
newch?d ->
( ( Sieve(p+1,d) [|{|ch.d|}|] Filter(p,d,c) ) \\ {|ch.d|} )
@
Sieve(2,1) [|{|newch|}|] Chans(2)
end
``````