“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 206 — #216
i
i
i
i
i
i
i
i
206
4
• La programmation concurrente dataflow
Le filtrage d’un flot
Un transformateur simple est le filtre qui transmet les éléments du flot d’entrée qui
satisfont une condition donnée. Une manière simple de construire un filtre est d’appeler
la fonction Filter dans son propre fil. Cette fonction prend une liste d’entrée et
une fonction booléenne et calcule une liste de sortie qui ne contient les éléments de la
liste d’entrée qui satisfont la fonction. Voici un transformateur qui ne transmet que les
éléments qui sont des entiers impairs :
local Xs Ys S in
thread Xs={Generate 0 150000} end
thread Ys={Filter Xs IsOdd} end
thread S={Sum Ys 0} end
{Browse S}
end
où IsOdd est une fonction booléenne d’un argument qui est vraie uniquement pour
les entiers impairs :
fun {IsOdd X} X mod 2 \= 0 end
La figure 4.10 montre cette technique. Cette figure étend la notation graphique avec
une flèche pointillée, qui représente une valeur qui n’est pas un flot.
S={Sum Ys 0}
Xs=0|1|2|3|...
Ys=1|3|5|...
Consommateur
Ys={Filter Xs IsOdd}
Xs={Generate 0 150000}
IsOdd
Producteur
Filtre
Figure 4.10 Le filtrage d’un flot.
Le crible d’Ératosthène
Nous définissons un pipeline qui implémente le crible d’Ératosthène, un algorithme
pour générer des nombres premiers. La sortie du crible est un flot qui ne contient
que des nombres premiers. Le programme s’appelle un « crible » parce qu’il fait des
filtrages successifs qui enlèvent les nombres non premiers des flots, pour ne laisser que
des nombres premiers. Les filtres sont créés dynamiquement quand on en a besoin. Le
producteur génère un flot d’entiers consécutifs qui commence par 2. Le crible prend
le premier élément du flot et crée un filtre pour enlever les multiples de cet élément.