Crible d' Eratosthène en Erlang (nombres premiers)

Sur le wiki du langage GO de Google, se trouvait un exemple de proggramme qui utilisait le crible d' Eratosthène pour générer la liste des nombres premiers.

Cet exemple utilisait un chainage de filtre, le nombre à tester est injecté dans le premier filtre de la chaine. Chaque filtre teste le reste de la division de ce nombre par un nombre premier déjà trouvé. En cas d'échec, le filtre envoie le nombre à tester au filtre suivant ainsi de suite jusqu'au dernier filtre.

A la fin de ce dernier filtre, et en cas d'échec, le nombre est qualifié de premier et devient le filtre suivant en étant ajouté en bout de chaine.

La réalisation en GO commence par la création d'une fonction générateur.
Sous cette forme:

09    // Send the sequence 2, 3, 4, ... to channel 'ch'.
10    func generate(ch chan int) {
11        for i := 2; ; i++ {
12            ch <- i  // Send 'i' to channel 'ch'. 13        } 14    } 

Et ici une version plus élaborée:

10    func generate() chan int {
11        ch := make(chan int);
12        go func(){
13            for i := 2; ; i++ {
14                ch <- i  15            }  16        }();  17        return ch;  18    }     

En Erlang , le programme occupe plus de ligne. Il est de bonnes pratiques de scinder les programmes en composants de supervision et composants de traitement. J'ai aussi réalisé deux versions de la même fonction.

• generator_async/3 : Cette fonction envoie en flot continu la série de nombre.
• generator_sync/3 : Cette version n'envoie un nombre que sur demande du superviseur

Le superviseur lance le processus 'generateur' et va communiquer avec lui par un canal , comme en GO. En Erlang ou en Haskell ,les boucles for,while n'existent pas vraiment elles sont remplacées par des appels récursifs.


Le module principal superviseur:

-module (crible).
-export ([main/0,main2/0]).
loop2(Pid) ->
   receive
     ok -> ok; 
     Number -> io:format(" ~w~n",[Number]),
             Pid ! next,
             loop2(Pid)
   end.
loop() ->
   receive
   ok  ->  ok;
   Number -> io:format(" ~w~n",[Number]),
             loop()

 end.




main()->
_Pid =spawn(prime,generator_async,[self(),0,60000]),
loop(),
ok.
main2()->
Pid =spawn(prime,generator_sync,[self(),0,60000]),
Pid ! next ,
loop2(Pid).

Le module qui génère la suite des nombres:

-module (prime).
-export ([generator_async/3,generator_sync/3]).

generator_async(Canal,Compteur,Maximum) when Compteur == Maximum -> Canal ! ok;
generator_async(Canal,Compteur,Maximum) ->
Cpt= Compteur +1,
Canal ! Cpt,
generator_async(Canal,Cpt,Maximum).

generator_sync(Canal,Compteur,Compteur) -> Canal ! ok;
generator_sync(Canal,Compteur,Maximum) ->
Cpt= Compteur +1,
receive
next ->  Canal ! Cpt ,
      generator_sync(Canal,Compteur+1,Maximum)
end

J'ai utilisé ici une 'garde' dans la déclaration de fonction

generator_async(Canal,Compteur,Maximum) when Compteur == Maximum -> Canal ! ok;

C'est une condition de reconnaissance de la fonction.

Cette variante fait la même chose :

generator_sync(Canal,Compteur,Compteur) -> Canal ! ok;

Ici la variable Compteur est branchée avec le deuxième parametre d'appel de la fonction. Puis une autrre affectation de la variable Compteur est tentée avec le 3eme parametre. Si les deux valeurs sont égales le motif sera reconnu, sinon on passe à la forme d'appel suivante.

Ce système est basé sur le fait qu'il n'est pas possible de modifier le contenu d'une variable dans les langages fonctionnels.
ex : A=1 puis A=3 ou A=A+1

Pour debugger le programme en Erlang , il faut le compiler avec l'option :
erlc +debug_info

Puis lancer le shell Erlang (erl )

Sur le prompt lancer le debugger graphique par

debugger:start().

Choisir par le menu module, la liste des programmes à debugger.
Grace à ce système, il est possible de voir le contenu de messages ou l'état des variables.

Copie d'écran du debugger Erlang


Conclusion : La fonction qui utilise des echanges synchrones entre le superviseur et le composant générateur est 3 fois plus rapide que l'asynchrone.

Il est possible d'utiliser une seule ligne pour générer des séries de nombre par le système des listes "comprehensions". Ces listes injectent des données un peu à la manière de notre générateur.
Cela donnerait un ligne comme ca:

[ListePremier || Nombre <- Lists:seq(2,99999), is_prime_number(Nombre)].

Pour voir le post dans son contexte original http://germanlinux.blogspot.com/2009/11/crible-d-eratosthene-en-erlang-nombres.html