programmation_reactive.tex

\chapter{Programmation réactive}

Au cours du chapitre sur la programmation temporisée hors temps, nous
avons introduit un modèle algébrique des flux temporisés. Avec ce
modèle, nous pouvons définir un média temporisé par composition de
médias plus simples et application de transformations.

C'est-à-dire que la valeur de retour sera produite au fur et à mesure que
le paramètre sera disponible.

Ce chapitre traite principalement de l'implémentation du moteur
réactif dans langage de programmation fonctionnel pure.


\section{Introduction}

Considérons un rendu quelconque composé de notes de musique placées
dans le temps. concentrons nous sur une de ces notes en particulier,
ainsi que le terme algébrique qui l'a placé là. Il n'y a aucune
corrélation entre l'instant où est joué cette note et la position du
terme qui en est à l'origine. Donc il n'est pas possible de calculer
le rendu d'un média temporisé avant d'en connaître l'intégralité.

Dans le cas réactif, nous souhaitons calculer le rendu d'une
transformation de manière paresseuse. L'entrée n'est connu que jusqu'à
l'instant présent, et nous souhaitons qu'à chaque instant, le rendu ait
été calculé jusqu'à l'instant présent.

Produire une sortie partielle à partir d'une entrée partielle n'est
possible que pour une certaine classe de fonction. Il y a plusieurs
moyens de décrire cette classe.

Par exemple, nous pouvons exprimer la contrainte à travers les
dépendances fonctionnelles. Considérons l'ensemble des valeurs et
délais qui compose la liste temporisée de sortie. Chacune de ses
valeurs, à été calculée à partir d'un ensemble de valeurs de la liste
d'entrée. Cette fonction pourra être évaluée en temps réel si et
seulement si, quelque soit l'entrée, l'intégralité des valeurs
d'entrée dont dépendent chaque valeur de sortie lui sont antérieur.

Ou bien encore, nous pouvons donner un critère dénotationnel de cette
famille. Si nous définissions la coupure d'un média temporisé
$p\downarrow t$ qui va extraire le préfixe d'une liste temporisée $p$
jusqu'à une date $t$. Une fonction $f$ appartiendra à la classe de
fonction réactive si pour tout $p$ et tout $t$, $f(p\downarrow t) =
f(p) \downarrow t$. Autrement dit, pour tout $p$, tout $t$, et tout
$t'>t$, $f(p\downarrow t)\downarrow t = f(p\downarrow t')\downarrow
t$. C'est-à-dire qu'étant fixé un temps $t$, connaissance de l'entrée
postérieure à $t$ n'implique aucun changement sur la sortie antérieure
à $t$. La sémantique de $\downarrow$ est précisément le
\hsi{prefixQList} que nous avons défini sur les listes temporisées.

Non seulement nous voulons appliquer des fonction à des listes
temporisées de média $v$ qui ne sont pas encore totalement définies,
mais nous voulons aussi être réactif sur les valeurs $v$ elles
mêmes. Par exemple, si un musicien joue une note $n$, et que le le
système doit enrichir cette note de sa quinte $q(n)$, ce dernier soit
commencer à jouer cette quinte avant même de savoir quand cette note
$n$ va se terminer.

En entrée, une fonction réactive va prendre comme paramètre une tuile
décomposable en $\headT$ et $\tailT$, et produire une tuile.


Ces difficultés sont résolues en autorisant des durées inconnues
explicites, et que chaque application d'une fonction sur une paramètre
partiellement connu soit gelé jusqu'au dernier moment.

\section{Implémentation}
Ce chapitre va principalement parler de l'implémentation d'un moteur
réactif purement fonctionnel.

À l'interface d'entrée de ce moteur réactif, nous allons considérer
des valeurs temporisées $v$ qui sont émises entre deux marques. Ces
marques sont \hsi{On} et \hsi{Off}. C'est très proche de l'encodage de
la musique en \verb,MIDI,, c'est-à-dire un flux de \verb,NoteOn, et
\verb,NoteOff, qui marquent le début et la fin de chaque note. Si nous
considérons les évènement \hsi{On} et \hsi{Off} pour chaque note, cela
forme un mot bien parenthésé.

L'étage d'entrée va transformer cette entrée en une tuile de valeurs
temporisées. Il s'agit là du type des valeurs qui seront manipulées
programme que nous allons exécuter :

\begin{haskellnoinline}
data Atom d v = Atom d v  
\end{haskellnoinline}


\subsection{Listes temporisées et tuiles}

Nous allons utiliser un type proche de celui que nous avons défini au
chapitre précédant, les liste temporisées réactives. Ici en revanche,
tous les délais seront strictement positifs. 

Nous ajoutons aux \hsi{QList} un constructeur \hsi{RQRec}. Le sens de
ce constructeur deviendra plus clair par la suite, il permet de
retarder l'application d'une fonction. C'est-à-dire ajouter de la
paresse à la paresse.

\begin{haskellnoinline}
data RQList d iv v where
  RQEnd :: RQList d iv v
  RQList :: [Atom d v] -> d -> RQlist d iv v -> RQList d iv v
  RQRec :: Updatable p d iv =>
    (p -> RQList d iv v) -> p -> RQList d iv v
\end{haskellnoinline}

Concernant les tuiles, nous allons les implémenter d'une manière
similaire à celle du chapitre précédent. La seule différente est que
nous devons ajouter un offset éventuellement négatif au premier
élément. En effet, nous ne l'autorisons pas dans la \hsi{RQList}.

\begin{haskellnoinline}
data Tile d iv v = Tile { duration :: d,
                          offset :: d,
                          content :: RQList d iv v
                        }
\end{haskellnoinline}


\begin{haskellnoinline}
toRQList :: (Num d, Ord d) => Tile d iv v -> RQList d iv v
toRQList (Tile d ad q) = case compare 0 ad of
  LT -> RQList [] ad q
  EQ -> Q
  GT -> dropQ (-ad) q
\end{haskellnoinline}

\noindent Si jamais une tuile contient des évènements antérieur à son
marqueur d'entrée, ceux ci sont simplement ignorés, nous considérons
le média coupé à 0.


Nous présentons maintenant le premier composant du cœur du moteur
réactif : la définition d'une entrée explicite construite au gré de la
réception des évènement start et stop. Cette entrée est construite à
la volée grâce au type de donnée suivant :

\begin{haskellnoinline}
data InQList d iv where
  InQList :: [(d,iv)] -> d -> InQList d iv ->  InQList d iv
  InQUndef :: InQList d iv
  InQEnd ::  InQList d iv
\end{haskellnoinline}

\noindent Le constructeur \hsi{InQUndef} permet d'expliciter que la
suite d'une entrée est toujours inconnue.

\noindent Voilà la transformation des qlist d'entrée aux qlist
réactives, utilisée en interne :

\begin{haskellnoinline}
inputToRQ :: InQList d iv -> RQList d iv iv
inputToRQ (InQList ial d iq) =
  RQList al d (RQRec inputToQ iq)
inputToRQ InQEnd = RQEnd
inputToRQ InQUndef = error "Causality error"  
\end{haskellnoinline}

Nous pouvons observer qu'un appel à \hsi{inputToRQ InQUndef} créé une
erreur d'exécution. En effet, dans notre implémentation, un tel appel
est le symptôme d'un problème de causalité, c'est-à-dire que le
programme a eu besoin de données qui n'étaient pas encore disponibles.

\noindent Profitons de cette définition pour enfin aborder le
constructeur \hsi{RQRec} du type \hsi{RQList d iv v}.

\begin{haskellnoinline}
  RQRec :: Updatable p d iv =>
    (p -> RQList d iv v) -> p -> RQList d iv v
\end{haskellnoinline}

\noindent Les paramètres sont une fonction \hsi{f} d'un type \hsi{p}
dans les qlist réactives ainsi qu'une valeur \hsi{a} de type
\hsi{p}. Ce constructeur permet de \og{}geler\fg{} l'application
\hsi{f a} jusqu'à ce que cette valeur soit devenue indispensable. Le
but est de retarder cette application aussi longtemps qu'il y a des
valeurs indéfinies dans le paramètre \hsi{a} de type \hsi{p}. La
classe \hsi{Updatable p d iv} présenté ci-dessous est celle des types
\hsi{p} qui contiennent des valeurs \hsi{iv} temporisée sur \hsi{d}
qui peuvent être mises à jour.

\subsection{Valeur congelée et updatable}

Le type \hsi{UpdateData} contient les informations nécessaire à la
mise à jour des valeurs.

\begin{haskellnoinline}  
type UpdateData d iv = (d->d, InQList d iv -> InQList d iv)

class Updatable p d iv where
  update :: UpdateData d iv -> p -> p
\end{haskellnoinline}

\noindent  Le terme de gauche
(\hsi{d->d}) est une fonction du temps dans le temps, qui décrit
comment le temps à évoluer depuis la dernière mise à jour. Cette
fonction est appliquée sur toutes les durées non échues dans la valeur
\hsi{Updatable}. Le terme de droite permet la mise à jour de
\hsi{InQUndef}, c'est-à-dire l'injection dans la valeur de type
\hsi{p} des valeurs nouvellement reçues.

\begin{haskellnoinline}
instance Updatable (InQList d iv) d iv where
  update  (f,nq) (InQList al d q) =
    InQList (fmap (\(d1,v1) -> (f d1,v1)) al)
            (f d) 
            (update (f,nq) q)
  update  (_,_) InQEnd = InQEnd
  update  (_,nq) InQUndef = nq InQUndef  
\end{haskellnoinline}

\noindent La toute dernière clause est la raison pour laquelle le type
des valeurs d'entrée \hsi{iv} est omniprésent. En effet, c'est à cet
endroit que sont \og{}injectée\fg{} les valeurs fraichement arrivées.
Une valeur de type \hsi{InQList} est encapsulé dans un constructeur
\hsi{RQRec} par la fonction \hsi{inputToQ}. Si nous voulons pouvoir
effectuer un \og{}update\fg{} sur cette \hsi{RQList}, il faut pouvoir
prouver que dans le constructeur \hsi{RQRec}, le paramètre de type
\hsi{p} vérifie \hsi{Updatable p d iv}. Il faut donc que ces valeurs
apparaissent dans le type de \hsi{RQList}.



\begin{haskellnoinline}
instance Updatable (QList d iv v) d iv where
  update _ QEnd = QEnd
  update (f,nq) (QList al d q) =
    QList (update (f,nq) al) (f d) (update (f,nq) q)
  update (f,nq) (QRec g p) = QRec g (update (f,nq) p)
\end{haskellnoinline}


Nous pouvons définir l'instance \hsi{Updatable} sur tous les types
dont nous aurions besoin pour écrire des fonctions de transformations
de l'entrée. Par exemple, pour écrire des fonctions qui prennent plus
d'un paramètre, nous pouvons définir les instances sur les n-uplets :

\begin{haskellnoinline}
instance (Updatable p1 d iv,
          Updatable p2 d iv) =>
  Updatable (p1,p2) d iv where
    update u (p1,p2) = (update u p1, update u p2)

instance (Updatable p1 d iv,
          Updatable p2 d iv,
          Updatable p3 d iv) =>
  Updatable (p1,p2,p3) d iv where
    update u (p1,p2,p3) = (update u p1, update u p2, update u p3)
\end{haskellnoinline}



\noindent Quelques types de base, pour lesquels il n'y a rien à faire,
mais d'un point de vue génie logiciel, il est précieux de pouvoir les
traiter comme les autres.

\begin{haskellnoinline}
instance Updatable Integer d iv where
  update _ = id

instance Updatable Bool d iv where
  update _ = id

instance Updatable Int d iv where
  update _ = id
...
\end{haskellnoinline}


\noindent Tous les foncteurs (les listes, maybe…) :

\begin{haskellnoinline}
instance (Functor f, Updatable p d iv) =>
  Updatable (f p) where
    update u f = fmap (update u) f
\end{haskellnoinline}

\begin{remarque}
  Cette instance n'est peut être pas celle que nous souhaitons sur
  certains foncteurs, par exemple \hsi{Either a b}. En effet, ce
  dernier type est fonctoriel sur la valeur de type \hsi{b}. Utilisant
  un paramètre de ce type, nous pourions souhaiter qu'à la fois
  \hsi{a} et \hsi{b} soient \hsi{Updatable}.
\end{remarque}


\section{Les durées}

Comme mentionné, les durées dont nous avons besoin doivent supporter
des durées inconnues, ansi que des opérations arithmétiques sur ces
durées. Nous proposons de l'implémenter comme des fonctions affines
sur des variables de deux types :

\begin{haskellnoinline}
data ID v = ValueID v
          | DelayID Integer
\end{haskellnoinline}

\noindent Le constructeur \hsi{ValueID} représente la durée d'une
valeur temporisée, et \hsi{DelayID} représente l'attente entre deux
réception de valeurs temporisées.

Les durées sont des fonctions affines des variables.

\begin{haskellnoinline}
data Affine d id = Affine d [(d,id)]
\end{haskellnoinline}

Ce type de donnée encode des expression de la forme : $$o + c_1 \times
x_1 + c_2 \times x_2 + \ldots + c_n \times x_n$$
\noindent où $o$ est une constante, les $c_i$ sont des coefficents et
les $x_i$ des variables.

Sur ces fonctions affines nous définissons en plus de l'addition un
produit partiel, à savoir la multiplication par une constante :

\begin{haskellnoinline}  
multAF :: (Eq d, Num d) =>
  Affine d i -> Affine d i -> Affine d i
multAF (Affine 0 []) _ = (Affine 0 [])
multAF _ (Affine 0 []) = (Affine 0 [])
multAF (Affine d1 []) (Affine d2 l2) =
    Affine (d1*d2) (fmap (\(d,i) -> (d1*d,i) l2)
multAF (Affine d1 l1) (Affine d2 []) =
    Affine (d1*d2) (fmap (\(d,i) -> (d2*d,i) l1)
multAF _ _ = error "Affine product undefined"
\end{haskellnoinline}

\subsection{Le temps qui passe}

L'arrivée d'un nouvel ensemble de valeurs temporelle génère une
nouvelle entrée qui va remplacer l'obsolète \hsi{InQUndef}. Cette
entrée est de la forme :

$$\mathrm{InQList~}[(X_{i,j},v_{i,j})_{j\in{}J_i}]~Y_i~\mathrm{InQUndef}$$

\noindent où :

\begin{description}
\item[i] est le rang de la salve de valeurs temporisées,
\item[j] est le rang de la valeur au sein de la salve,
\item[$v_{i,j}$] est la $j$-ième valeur de la $i$-ième salve,
\item[$X_{i,j}$] est la durée $j$-ième valeur de la $j$-ième salve,
\item[$Y_i$] est le délai qui sépare la salve de rang $i$ de celle à
  venir, de rang $i+1$.
\end{description}


Afin de pouvoir faire des tests sur les durées même si celles si ne
sont pas complêtement définies, les variables dans la fonction affines
ne représentent pas la totalité de la durée, mais plutôt leur durée
restante. C'est-à-dire que les durées sont mesurées à partir de
l'instant présent. Ces mises à jours se font de deux façon :


Lorsqu'un temps $\delta_t$ c'est écoulé, nous remplaçons toute les
variables $X$ par $\delta_t + X$.

\begin{haskellnoinline}
shiftAffine :: (Eq d, Num d,Ord i) => d -> Affine d i -> Affine d i
shiftAffine _ (Affine dd []) = Affine dd []
shiftAffine d (Affine dd l) =
  Affine (foldl (+) dd (fmap (\(di,i) -> di * d)) l
\end{haskellnoinline}

\noindent De cette manière, 


Et lorsqu'une durée d'entrée arrive à échéance, il suffit simplement
de la supprimer de la fonction affine, c'est-à-dire mettre la variable
à 0.

\begin{haskellnoinline}
setToZeroAffine :: (Num d,Ord i) => i -> Affine d i -> Affine d i
setToZeroAffine i (Affine dd ld) =
  Affine dd (filter (\(_,x) -> x /= i) ld)
\end{haskellnoinline}

\noindent Nous filtrons la liste des variables pour enlever celles qui
sont dans la listes $l$ de variables échues.

Ce faisant, toutes les durées inconnues sont nécessairement positives
et cela autorise un traitement relativement simple des fonctions
affines.

\section{Évènements, états réactifs et boucle}

Le back-end que nous avons implémenté utilise des évènements à
l'interface. Plus spécifiquement, des mots bien parenthésé de
valeurs. Le type des évènements est le suivant :

\begin{haskellnoinline}
data Event v = On v
             | Off v
\end{haskellnoinline}

La conversion des entrées avec timestamp dans le types \hsi{InQList}
est gérée par le cœur du noyau que nous allons exposer ci-après. Il
est basé sur la notion d'état réactif. Un tel état est initialisé par
une fonction $f$ sur les tuiles (interprété comme une fonction sur les
listes temporisées réactives). Et cet état sera manipuler par une
boucle qui converti le flux temporisé d'évènements d'entrée en un flux
temporisé de sortie en utilisant la définition donnée par la fonction
$f$.


Le type encodant les états réactifs est défini par :

\begin{haskellnoinline}
type Dur d = Affine d ID
data QState d iv v =
  QState { rank :: Int,
           date :: d,
           outputQList :: RQList (Dur d) iv v,
           currentOutputValue :: [(Dur d, v)]
         }
\end{haskellnoinline}


\begin{haskellnoinline}
initQState f =
  let g q = toQList (f (Tile 0 0 (inputToQ q)))
  in QState 0 0 (QRec g InQUndef) []
\end{haskellnoinline}

Le premier paramètre de \hsi{QState} est le rang de la dernière salve
de valeur temporelle reçues. Le second paramètre est le timestamp
courant, le troisième est la sortie, cette valeur sera évaluée au fur
et à mesure que l'entrée arrivera. Et le dernière paramètre est la
liste des valeurs de sortie qui sont actives et qui attendent leur
clôture. 

La boucle réactive consiste en une procédure lancée à chaque nouvelle
réception d'évènements. Cette procédure peut être décrite par la
séquence des tâches suivantes :

\begin{enumerate}
\item mise à jour de la \hsi{RQlist} de la sortie et des valeurs en
  cours de production en fonction du temps écoulé depuis la dernière
  mise à jour,
\item création de la nouvelle salve d'évènement (évènements \hsi{On}) et remplacement de la
  valeur \hsi{InQUndef},
\item affectation définitive des variables dont les \hsi{Off} correspondant ont été reçus,
\item éventuellement, effectuer l'application de fonction du
  constructeur \hsi{RQRec}, suppression des \hsi{Atom} de la sortie
  programmée avec les insertion correspondance dans la liste de
  sortie,
\item produire les évènement \hsi{On} et \hsi{Off} correspondants, en les retirant de la liste de sortie,
\item et, enfin, si besoin, programmer un nouveau réveil.
\end{enumerate}

En d'autre mots, la fonction sur les tuiles $f$ a été transformée en
un programme réactif en temps réel qui agit sur les évènements.

% 
% \section{Implémentation}
% 
% Reprennons la définition des \hsi{QList} que nous avons proposé au
% chapitre~\ref{chapitre:tuile_temporelle}. Nous allons maintenant
% l'étendre pour prendre en compte le cas réactif. Concrètement, cela
% revient à avoir des valeurs non encore connues au sein de la
% structures. Il nous faut rajouter un constructeur pour le cas où le
% reste n'est pas encore connu.
% 
% 
% \todo{data RQList t v = ...}
% 
% Le nouveau constructeur \hsi{RQFreeze t v} rend deux services. Tout
% d'abord, il permet de marquer que le reste n'est pas encore
% connu. Ensuite, comme nous utilisons la programmation fonctionnelle
% pure, nous ne pouvons pas effectuer d'effets de bords, c'est-à-dire
% que nous ne pouvons pas modifier une valeur qui a déjà été capturée
% par une fonction. Ce constructeur permet donc de retarder
% l'évaluation, tout préservant l'accessibilité des valeurs qui ne sont
% pas encore pleinnement définies. Et ce, afin de pouvoir les mettre à
% jour, d'où le nom de la classe \hsi{Updateable}.
% 
% 
% \subsection{Variables}
% 
% 
% 
% 
% \subsection{Les valeurs temporisées}
% 
% Les valeurs sont encodées par des évènements. Dans un souci de
% simplicité, nous allons considérer qu'elle sont constante par
% morceaux. Nous allons encoder les valeurs temporisées par des paires
%  d'évènements marquant le début et la fin de la production d'une valeur
% $v$.
% 
% \haskellcode{TAG_data_event}
% 
% % \haskellcode{TAG_instance_functor_event}
% 
% Nous allons supposer dans la suite que toutes les tuiles sont bien
% formées. C'est-à-dire que pour chaque valeur \hsi{v}, la sous séquence
% des évènements qui portent la valeur \hsi{v} forme un mot bien
% parenthésé.
% 
% 
% % La programmation réactive est une extension de la programmation
% % temporisée que nous avons vu plus tôt. Il s'agit toujours de procéder
% % à la synthèse, d'un média temporisé mais cette fois le média ne dépend
% % pas seulement des entrées d'un programme, mais également d'un autre
% % média temporisé. Jusque-là rien de nouveaux. Mais nous souhaitons
% % également que le programme réactif ait des propriétés sémantique qui
% % font qu'il est capable de produire sa sortie à temps.
% % 
% % Nous allons équiper les médias temporisés d'un ordre bien choisi qui
% % fait que cette propriété s'exprime par une propriété de monotonie de
% % la fonction entre son domaine et son co-domaine.
% % 
% % 
% % Intuitivement, l'idée est qu'un programme réactif ne doive jamais
% % produire de média dans le passé, ou bien, exprimé dans l'autre sens,
% % que l'état de la sortie d'un programme à un instant $t$ ne doit
% % dépendre que de l'état l'entrée à l'instant $t$ (ou antérieur).
% % 
% % Programmation \emph{On-time}.
% % 
% % Les fonctions tuilées sont définies en trois parties.
% % 
% % Parser l'entrée, et expliciter la dépendance fonctionnelle pour
% % produire la sortie
% % 
% % 
% % \section{Causalité}
% % 
% % \section{Expressivité}
% % 
% % \section{Implémentation}
% % 
% % Une implémentation a été réalisée, elle est décrite dans le papier
% % \cite{AJ16}.
% % 
% % \subsection{Freeze}
% % 
% % \subsection{Moteur d'exécution}
% % 
% % 
% % 
% % 
%