Constructions réactives en style trampoline

ReactiveML fournit un ensemble de constructions syntaxiques pour les proces-sus. La bibliothèque les met en œuvre sous forme de fonctions . Pour pouvoir être manipulé, un processus sera représenté le plus souvent par neu fonction “glaçon” (thunk). L’instruction d’exécutionrun sera donc réalisée simplement par la fonction let run p = p (). Nous noterons RML les fragments de code ReactiveML et TML (pour trampoline ML) ceux pour la bibliothèque.

Trampoline

Le style trampoline consiste à rendre explicite les continu ations aux endroits où
le processus est susceptible de se suspendre. Par exemple l’instructinothingpause indique

Exemples

Sieve
Le crible d’Ératosthène est un exemple classique de l’appro che réactive d’abord proposé dans le contexte d’un langage flot de données (Kahnet al., 1977). Le crible se
construit comme une chaîne de processus filter encadrés par un générateurintegers() d’un côté, un récepteur (output ) précédé d’un “étendeur”shift( ) de l’autre, comme illustré figure 2 qui montre l’état initial et après la création du filtre sur 2. Les nombres progressent d’une étape de la chaîne à chaque instant.
Détaillons chacun des processus (figure 3) :
– integers génère sur un signal la suite des entiers à partir de 2.
– filter filtre les multiples de son paramètre : il reçoit des entiers s ur son signal d’entrée et réemet ceux qu’il ne filtre pas sur son signal de sortie. La boucle infinie de RML est ici exprimée par la récursion.
– shift reçoit des entiers sur son signal d’entrée, crée un nouveau signal (appelés localement) et insère un processusfilter dans la chaîne à chaque nouveau nombre reçu (qui sera premier par construction de la chaîne). On utilise ici la fonction tail par.
– output , placé en fin de chaîne, est chargé de l’affichage du nombre premier qui a passé tous les filtres. Il termine le programme quand le nombre reçu atteint une valeur limite. L’appel à Mem .exit affiche la mémoire allouée dans le tas avant de terminer.
– sieve, processus initial qui amorce le système. On remarque l’utilisation du tail parn, similaire à tail par mais prenant une liste de processus en paramètre. start démarre les processus passés en paramètre (en RML le processus initial est fixé à la compilation).
Tous les signaux portant des entiers, le type passé au foncteur est simplement int. On note que la formulation des processus comme glaçons amène souvent une notation élégante et proche de celle de ReactiveML.
Elip position
Elip e un logiciel de simulation de protocole de routage pour réseaux ad’hoc, écrit en ReactiveML (Mandelet al., 2005). Chaque nœud du réseau est implémenté par un processus. Il a pu très facilement être porté sur TML.urS les 4300 lignes de code, seules 270 concernent les définitions de processus (au nombre de 11) et doivent donc être converties en style trampoline. Aucune difficulténotable n’a été rencontrée.
Le rogramme utilise 10 signaux, dont 4 non valués. Les autres portent des articles (types et node), une paire de flottants, un caractère ou un entier. Le module paramètre du foncteur sera donc le suivant :
module SV = struct
type t = SV Null (∗ signaux non valués∗)
| SV Pos of position
| SV Node of node
| SV Click of float × float
| SV Key of char
| SV Int of int
end
L’émission d’un signal devra utiliser le constructeur correspondant, par exemple emit click (SV Click (pos x , pos y )).

Réalisation de la bibliothèque

Nous décrivons ici les grandes lignes d’une version simplifiée de la bibliothèque. Le code détaillé est disponible sous forme d’un document “litterate programming” (Deleuze, 2009) montrant la mise en œuvre progressive des fo nctionnalités. La biblio-thèque complète comprend environ 500 lignes de code.
Principes
Les processus sont des fonctions glaçons retournant des val eurs de type coop indi-quant la raison de la suspension et la continuation éventuele.
type process = unit → coop and coop =
| Done
| Pause of process
| Wait of signal t × awproc
| Wait im of signal t × awproc
| Present of signal t × process × process
awproc (pour awaiting process) est le type des processus attendant l’arrivée d’un signal (sans se préoccuper des valeurs éventuelles portées), l’intégralité des valeurs émises sur le signal ou une seule des valeurs émises.sval t est le type somme des valeurs de signaux, paramètre du foncteur.
and awproc =
| No of (unit → coop)
| One of (sval t → coop)
| All of (sval t list → coop)
Les fonctions de suspension que nous avons vues précédemment consistent essen-tiellement à retourner une valeur de type coop (ispst indique si un signal a déjà été émis dans l’instant courant).
let term () = Done
let pause k = Pause k
let await s k = Wait (s , All k )
let await one s k = Wait (s , One k )
let await immediate s k = if ispst s then k () else Wait im (s , No k )
let await immediate one s k =
if ispst s then k (List .hd s .value) else Wait im (s , One k )
let present s k1 k2 = if ispst s then k1 () else Present (s , k1 , k2 )
Les processus sont stockés dans diverses listes :
– runq : processus en attente d’exécution sur l’instant,
– pauseq : processus en attente de l’instant suivant,
– à chaque signal sont associées trois listes present , await im et await contenant les processus en attente sur ce signal.
Au cours de chaque instant l’ordonnanceur (sched ) lance un à un les processus de la liste runq et récupère les continuations (dans des valeurs de typecoop) qu’il place dans la liste appropriée (pauseq si le processus a terminé l’instant, une liste d’attente associée à un signal si le processus attend ce signal, voir figure 4a). Si un processus émet un signal, les processus en attente immédiate (await im et present ) sur ce signal sont immédiatement replacés dansrunq.
L’instant se termine quand l’ordonnanceur trouve runq vide. Il exécute alors la fonction next instant qui transfère le contenu de pauseq dans runq ainsi que les processus qui ne doivent plus être en attente à l’instant suivant (await sur un signal présent,present sur un signal absent, figure 4b).