programmation_spatiale.tex

\chapter{Programmation Spatiale}
\label{chapitre:tuile_graphique}

Dans ce chapitre, nous allons aborder la programmation spatiale,
c'est-à-dire la programmation de programme dont l'exécution a des
effets de bord sur un espace. Notre approche peut être illustrée de
manière plutôt simple en analysant la sémantique de programmes tortue
LOGO qui permettent de définir des dessins en programmant les
mouvements d'une tortue. Nous appellerons ses programmes
\og{}programmes tortue \fg.

Nous pouvons observer que les programmes tortue agissent à la fois sur
l'espace des positions possibles du crayon et sur les figures qui sont
dessinées. Ensemble, les positions et les dessins forment un état qui
est finalement transformé par les programmes

Les actions sur les positions sont appelés mouvements, les actions
sur les figures sont appelés dessins, ensembles ils forment le modèle
sémantique des programmes tortue que l'on cherche à définir.

Il se trouve que ce langage de dessins offre une vue pertinente sur la
sémantique mathématiquement bien définie que nous proposons.

\section{Un langage graphique historique}

Le langage LOGO et plus spécifiquement la programmation graphique
tortue LOGO a été dévellopé dans un but éducatif. Concrètement, il
conciste à programmer les déplacements d'une tortue équipée d'un
crayon. Les traces de ce crayon étant la sémantique du programme. La
tortue LOGO est la fonctionnalité la plus connue du langage LOGO.

\noindent Cette tortue peut simplement avancer, tourner, poser son
crayon, et lever son crayon.

% LOGO en quelques mots, l'histoire, la syntaxe, des exemples de
% programmes

\section{Syntaxe}

Le langage de la tortue logo dans sa forme minimale que nous allons
étudier ici consiste en trois primitives et d'un opérateur de composition.

\begin{description}  
\item{\verb,TogglePen,} lève le stylo s'il est posé sur la feuille, le pose sinon,
\item{\verb,Walk d,} avance d'une distance $d$ (qui peut être négative),
\item{\verb,Turn a,} pivote l'un angle $a$.
\item{\verb,P1 ; P2,} composition  \verb,P1, et \verb,P2, de manière séquentielle.
\end{description}

\begin{remarque}
Nous préférons substituer aux instructions \haskellinline{PenUp} et
\haskellinline{PenDown} présentes dans les implémentations standard de
LOGO, une seule instruction \haskellinline{TogglePen}. La différence
tient au fait que \haskellinline{TogglePen} est réversible,
contrairement à \haskellinline{PenUp} et \haskellinline{PenDown}.
Cela nous permettra plus tard de former un groupe.
\end{remarque}



Le code suivant implémente les type nécessaire à la représentation
d'un programme et de la sémantique d'un programme :

\haskellcode{TAG_data_instruction_turtle}

Très simplement, le type \haskellinline{Instruction} a trois
constructeurs différents dont la sémantique intuitive est décrite plus
haut. Et la composition séquentielle de ces instructions est
implémentée par l'utilisation d'une liste, ce qui est fait dans le
type \haskellinline{Program}. Plus formellement, les programmes sont
implémentés par le monoïde libre formé sur l'alphabet des
instructions, cet alphabet est virtuellement infini à cause de la
présence de paramètres dans $\mathbb{R}$ pour \haskellinline{Forward}
et $\mathbb{R}/2\pi\mathbb{R}$ pour \haskellinline{Turn}.



\begin{exemple}{Dessiner un triangle.}
En supposant que dans l'état initial la tortue a le crayon
baissé, le programme suivant dessine un triangle équilatéral de côté
1.
  
\haskellcode{TAG_logo_exemple_triangle}

\end{exemple}


\section{Déplacements, Dessins, et Sémantique}


Défini par des listes d'actions de base, les programmes tortue
forment un monoïde où la composition séquentielle des programmes est
modélisé par la concaténation de listes. Visant la définition d'un
modèle sémantique compositionnel pour ces programmes, nous cherchons
donc un monoïde sémantique.


La tortue effectue à des déplacements en changeant de position, et des
dessins en créant de nouveaux traits de crayon. Ces deux choses
constituent les éléments de notre sémantique.


Formellement, la position de la tortue est définie par un triplet
composé d'un booléen (vrai quand le crayon est en position basse, et
faux sinon), un vecteur à 2 dimensions (les coordonnées du crayon dans
le plan), et un angle (l'orientation de la tortue).  Le type
\haskellinline{Move} est le type des déplacements, c'est une fonction
des états de la tortue dans les états de la tortue, c'est-à-dire
qu'une instance calcule un état final étant donné un état
initial. C'est-à-dire une fonction qui transforme les états.


\haskellcode{TAG_data_point_state_move}


\noindent Une figure est définie par un ensemble de segments, c'est-à-dire un ensemble de paire de points. Comme la tortue ne lit jamais un
dessin, mais produit à dessin à partir d'une position donnée, les
dessins prennent une position comme paramètre.

\haskellcode{TAG_data_dessin}


In fine, la sémantique d'un programme sera encodé par une paire
\haskellinline{Semantics} formée d'un déplacement (le déplacement
global de la tortue) et d'une figure (un ensemble de segments). Le
type \haskellinline{Draw} quant à lui, est habité par des fonctions
des états de tortue dans les dessins (les ensemble de segments,
modélisés ici par une liste de paire de points), les fonctions
instances de \haskellinline{Draw} calculent une figure étant donné un
état initial.
%


\haskellcode{TAG_data_sem}

%\haskellcode{TAG_data_line_init}
%%




\noindent Le type de l'état d'un programme sera encodé ainsi :

\haskellcode{TAG_data_state_init}

Nous en profitons pour déclarer la sémantique du programme vide, qui
formée à partir de la fonction identité pour les déplacements, et la
fonction constante qui renvoie une liste vide de lignes pour le
dessin, ainsi que l'état initial de la tortue. Ces valeurs sont tout à
fait arbitraires. Elle commence
aux coordonnées $(0,0)$ de la feuille, regardant dans la direction
$0$, et le crayon posé.
\noindent L'état des programmes est défini comme une paire composée
d'une position et d'une figure, et les sémantiques de programme d'une
paire composée d'un déplacement et d'un dessin.


Nous pouvons maintenant définir deux nouvelles fonctions. La première
est \haskellinline{applySemantics}, elle va appliquer la sémantique d'un
programme à l'état du programme. La seconde permettra de calculer
effectivement une figure à partir d'un programme.



\haskellcode{TAG_function_applys}

\noindent Dans les paramètre de la fonction, \haskellinline{m} est la fonction
de déplacement engendré par la sémantique, et \haskellinline{p} la
position initiale dans l'état. La position résultante est donc
\haskellinline{m p}. Pour la figure, \haskellinline{f} est la figure
présente dans la sémantique, et \haskellinline{d} est de type
\haskellinline{Drawing = Position -> Figure}, donc,
\haskellinline{d p} est le dessin décrit par la sémantique à partir de
la position \haskellinline{p} de la tortue.


\noindent Grâce à cette fonction, nous pouvons maintenant calculer une figure à
partir d'un programme :


\haskellcode{TAG_run_semantics}

% \haskellcode{TAG_function_runProgram}
% 
% La variable \haskellinline{ls} est la liste des sémantiques de chaque
% instructions du programme. La fonction \haskellinline{foldl}
% ``replie'' cette liste utilisant \haskellinline{applySemantics}, à
% partir de l'état initial \haskellinline{initState}.  L'appel à
% \haskellinline{snd} permet de récupérer la seule figure.


\noindent La généralisation de ces constructions présentées plus bas peut
sembler inutilement théorique, cependant, elle présente un mérite,
comme nous allons le voir, cela se généralise très bien dans une
grande variété de contexte de programmation de média temporels.  Nous
allons donc réécrire ce code en prenant soin d'exhiber les structures
mathématiques cachée derrière les types et fonctions que nous
utilisons.

\section{Implémentation du monoïde sémantique}

Comme mentionné plus haut, nous cherchions un monoïde
sémantique. Finalement, nous avons trouvé trois monoïdes et non un
seul. Le dernier, le monoïde sémantique des programmes est obtenu
grâce à une combinaison des deux premiers : les déplacements, et les
dessins.

\haskellcode{TAG_instance_monoid_move}
\haskellcode{TAG_instance_monoid_figure}
\haskellcode{TAG_instance_monoid_draw}


\noindent Les monoïdes définis ci-dessus, nous pouvons définir le
monoïde des sémantiques de programmes comme des paires de déplacements
et de dessins, et ils sont combinés de la façon suivante :


\haskellcode{TAG_instance_monoid_semantics}

\noindent Pour les déplacements, l'application séquentielle de deux
programmes tortue combine les déplacements définis par ces
programmes. En ce qui concerne les dessins, l'expression ci-dessus dit
que pour une position donnée \haskellinline{p}, la première figure
\haskellinline{d1 ; p} est dessinée, ensuite, la tortue se déplace à
la position \haskellinline{m1 ; p}, position à partir de laquelle elle
effectue le second dessin \haskellinline{d2 ; (m1 ; p)} par-dessus le
premier. Il s'agit en effet de la sémantique de la composition
séquentielle que nous recherchions.

\noindent Maintenant, nous pouvons vérifier que pour toute sémantique
de programme tortue \haskellinline{s1} et \haskellinline{s2}, nous
avons :

\begin{haskellnoinline}
property1 s1 s2 =
  applyS (s1 <> s2) == applyS s1 <> applyS s2
\end{haskellnoinline}


Ceci découle des similarités que nous pouvons observer entre les
définitions des fonctions \haskellinline{applyS} et la composition
\haskellinline{<>} du monoïde sémantique.





\subsection{Implémentation des déplacement et des dessins}

Jusque-là, nous avons définis les types et les combinateurs pour
composer les sémantiques des programmes tortue. Ces types sont basés
sur la décomposition de nos valeurs sémantiques en déplacements et
dessins. Il reste donc à rendre explicite ces déplacements et ces
dessins associés aux actions de base pour avoir un modèle sémantique
des programmes tortue complet.


La fonction \haskellinline{semMove} va calculer le changement d'état de la
tortue induit par l'évaluation de chacune des instructions :

\haskellcode{TAG_function_semantic_move}


\noindent De la même manière, la fonction \haskellinline{semDraw}, va calculer le dessin
engendré par chacune des instructions. C'est-à-dire une liste vide de
segment dans tous les cas, sauf s'il s'agit d'avancer (ou reculer)
avec le crayon posé sur la feuille :


\haskellcode{TAG_function_semantic_draw}

\noindent La fonction \haskellinline{instructionToSemantics} calcule simplement
la sémantique d'une instruction, réutilisant les deux fonctions
précédemment définie.

\haskellcode{TAG_function_instruction_to_semantic}


\noindent La sémantique des dessins d'un programme tortue est définie
comme étant la seconde projection de la sémantique complète du
programme.

\haskellcode{TAG_function_program_to_semantic}



\noindent La fonction \haskellinline{mconcat} est une fonction qui
évalue une composition dans un monoïde dont les termes sont les
éléments d'une liste.
\haskellcode{TAG_function_mconcat}



\noindent Observons que la sémantique des dessins des programmes tortue
est légèrement plus complexe à définir que la sémantique des
déplacements parce qu'elle dépend de la position qui peut être modifiée
par les déplacements. Au demeurant, cela correspond à une notion bien
connue en algèbre appelée le produit semi-directe
\ref{intro_math:produit_sd}.



\noindent Cette sémantique est compositionnelle dans le sens où pour tout
programme \haskellinline{p1} et \haskellinline{p1}, nous avons :

\begin{haskellnoinline}
property_morphism1 =  semantics neutral == neutral
\end{haskellnoinline}

\begin{haskellnoinline}
property_morphism2 p1 p2 =
  semantics (p1 <> p2) == semantics p1 <> semantics p2
\end{haskellnoinline}





En effet, la fonction \haskellinline{semantics} est l'unique morphisme
du monoïde (libre) des programmes tortue dans la sémantique
tortue induit par \haskellinline{(move i, draw i)} sur les actions
élémentaires.


\subsection{Remarque sur les déplacements basique de la tortue}

À première vue, on peut penser que la tortue évolue fondamentalement
dans l'espace en 2 dimensions définis par les coordonnées $(x,y)$ de
chaque position. Cependant, la capacité à tourner suggère que la
tortue peut aussi agir sur l'espace lui-même, c'est-à-dire sa base 2D
sous-jacente.

En effet, en combinant les mouvements de base de la tortue (avancer et
tourner), il est possible de définir toute les transformations
isométrique et préservant les orientations de l'espace 2D
sous-jacent. C'est-à-dire toute les transformations générée par des
translation et des rotations arbitraires.


Étendue des mouvements de base additionnels, la sémantique de la
tortue capture les isométries arbitraires (en ajoutant par exemple la
réflexion sur l'axe $x$), les bijections affines arbitraires (en
ajoutant la réflexion et les contractions/vitesse d'avance non nulles
sur l'axe $x$), ou même les transformations affines arbitraires (la
projection de l'espace 2D entier sur une ligne, en effectuant une
contraction nulle sur l'axe $x$ \footnote{les déplacements ne forment
  alors plus un groupe}. De la même manière, il est aussi possible
d'ajouter des transformations non linéaires, le fait qu'elles soient
réversibles conditionne le fait que déplacements forment un groupe.


Cette observation joue un rôle clé lors qu'il s'agit d'étendre les
mouvements de la tortue vers des espaces plus vastes ou bien dans la
dimension du temps.





\section{Monoïde Sémantique revisité}


Nous avons vu plus que les monoïdes (ou même simplement les
semi-groupes) jouent un rôle central dans la définition de la
sémantique tortue. De plus, la plupart des définitions sémantiques
sont génériques. Les fonctions comme \hsi{moveI}, \hsi{drawI} et
\hsi{semantics} sont définies en terme d'action basique
\hsi{Instruction}.

Ceci suggère que la sémantique tortue repose sur des structures encore
plus générales et méritent donc d'être rendues explicites.  Dans cette
section, nous étudions plus en profondeur les constructions génériques
qui ont été --- bien qu'implicitement --- appliqué et les plutôt
riches propriétés mathématiques que ces constructions satisfont.



\noindent Pour revenir à la sémantique tortue, nous déclarons
simplement :
%

\haskellcode{TAG_instance_action_move_draw}

Et nous pouvons donc redéfinir l'instance de monoïde ainsi :

\haskellcode{TAG_instance_monoid_semantics_with_action}

\noindent En fait, nous aurions tout aussi bien pu définir le type par
\hsi{PSD Move Draw}, \hsi{PSD} étant défini dans l'introduction en section
\ref{intro_math:produit_sd}. C'est-à-dire le monoïde formé par le
produit semi-direct de \hsi{Move} et \hsi{Draw}.


In fine, nous avons abstrait la sémantique des programmes tortue ainsi :


\begin{itemize}
\item Un monoïde $M$ représente les déplacements de la tortue
\item Un monoïde $D$ représente les dessins faits
\item Une action de $M$ sur $D$ implémente les transformations des
  dessins induits par les déplacements de la tortue
\item Les paires $(M\times{}D)$ encodent les sémantiques des programmes
\item Le produit semi-direct de $(M\times{}D)$ calculent la
  composition séquentielle de deux programmes.
\end{itemize}


\subsection{Monoïde inversif}

Jusque-là, nous n'avons pas utilisé le fait que les déplacements sont
réversibles. C'est-à-dire qu'il ne s'agit pas seulement d'un monoïde,
mais d'un groupe.
Il apparaît alors que ces propriétés ouvrent la voie à une transformation
des programmes tortue, appelée \hsi{inverse} qui a, à l'équivalence
sémantique près, des propriétés intéressantes.

Procéduralement, l'inverse d'un programme peut être vu comme le même
programme, mais exécuté de la fin au début. La figure réalisée sera
exactement la même, mais la position initiale de la tortue d'un
programme \hsi{p} sera la position finale de la tortue du programme
\hsi{inverse p}, il en va de même pour les positions respectivement
finales et initiales.


\noindent La fonction suivante permet de calculer les inverse de
chaque instruction du langage :
\haskellcode{TAG_function_invI}

\noindent Maintenant, nous pouvons faire des programmes une instance
de semi-groupes inversifs. Le programme inverse de \hsi{p} est \hsi{p}
exécuté en partant de la fin remontant à son début, tout en exécutant
l'inverse de chacune des instructions.

\haskellcode{TAG_instance_logo_inverse}


\noindent Maintenant, chacun peut vérifier que pour tout programme
\hsi{p}, le programme \hsi{p} et le programme \hsi{} sémantique :

\begin{haskellnoinline}
propertyInverse1 p = 
  semantics p == semantics (p <> inverse p <> p)
\end{haskellnoinline}

\noindent Il en va de même pour les programmes \hsi{inverse p} :

\begin{haskellnoinline}
propertyInverse2 p = 
  semantics (inverse p) == semantics (inverse p <> p <> inverse p)
\end{haskellnoinline}

Du coté sémantique, nous avons :

\begin{haskellnoinline}
inverseSemantics (m,d) = (inverse m, act (inverse m) d)
\end{haskellnoinline}


\subsection{\label{spat:monoid_reset}Monoïde avec reset}

Comme nous l'avons évoqué dans le chapitre d'introduction aux théories
utilisées en section \ref{subsec:monoid_reset}, il est malaisé de donner une
sémantique intuitive aux inverses dans le cas général. Et il se trouve
que dans bien des cas, nous nous servons des inverses uniquement pour
créer des idempotents, qui sont les éléments qui nous intéressent vraiment.

L'autre avantage des monoïdes avec reset, est que nous n'avons plus
besoin que les déplacements dont nous nous servons aient une structure
de groupe. En fait, il suffit qu'il s'agisse d'un monoïde.






\noindent le semi-groupe inversif décrit plus haut induit une nouvelle
transformation de programme appelée l'opération de $\reset$, qui est
également intéressante. Cette opération est définissable même dans le
cas où l'on considère un monoïde de déplacements non réversible, et,
comme nous allons voir, il se comporte comme un opérateur \hsi{fork},
permettant des évaluations concurrentes.

Plus précisément, nous définissons \hsi{resetP} sur les programmes
tortue par :

\haskellcode{TAG_logo_function_resetp}

%\begin{displaymath}
%{resetP}\mathbin{::}{Program}\;{d}\to {Program}\;{d}
%\\
%{resetP}\;{p}\mathrel{=}{p}\mathbin{{\Diamond}}{inverse}\;{p}
%\end{displaymath}
%



\noindent En exécutant le programme \hsi{p <> inverse p}, la tortue
exécute les instructions spécifiée par \hsi{p} en produisant une
figure, et ensuite exécute l'inverse de ses action dans l'ordre
inverse, reproduisant l'exacte même figure, tout en revenant à sa
position initiale.  En d'autre mots, le programme \hsi{resetP p}
décrit un double traçage de la figure, un dans un sens par \hsi{p}, et
dans l'autre sens par \hsi{inverse p}, fait un déplacement dans un
sens, puis dans l'autre.

Au niveau sémantique, cette redondance peut être évitée en faisant
comme suit.

Étant donné la sémantique \hsi{(m,d) = semantics p} d'un programme
\hsi{p}, qui dit que la tortue doit effectuer le mouvement \hsi{m}
tout en dessinant \hsi{d}, nous pouvons vérifier que :

\hsi{(neutral,d)  = semantics (resetP p)}.

\noindent Autrement dit, le programme \hsi{resetP p}
peut être également lu comme : quelle que soit la position initiale,
envoyer une copie de la tortue courante effectuer le dessin désiré et
disparaît après avoir terminé, et la tortue initiale attend là pour
exécuter les instructions suivantes. C'est-à-dire que nous pouvons
définir l'instance suivante :

\haskellcode{TAG_logo_instance_semantics}

Ceci nous apprends au moins deux choses. La première, c'est que la
fonction \hsi{resetP} agit comme une sorte d'opérateur \hsi{fork} qui
permet l'évaluation parallèle, la seconde, c'est qu'implémenter le
reset au niveau sémantique est plus efficace, et peut être défini même
dans le cas de déplacements non réversibles.



%In semigroup theory, \ensuremath{{inverseP}\;{p}} is called the
%semigroup inverse of \ensuremath{{p}}. This leads us to the definition
%of the class of inverse semigroups.
%
%\begin{displaymath}
%\mathbf{class}\;{Semigroup}\;{m}\Rightarrow {InverseSemigroup}\;{m}\;\mathbf{where}
%\\
%{inverse}\mathbin{::}{m}\to {m}
%\\
%{norder}\mathbin{::}({Eq}\;{m})\Rightarrow {m}\to {m}\to {Bool}
%\\
%{norder}\;{m}\;{n}\mathrel{=}{m}==({m}\mathbin{{\Diamond}}{inverse}\;{m}\mathbin{{\Diamond}}{n})
%\end{displaymath}



% C'est maintenant que l'on en arrive à la partie la plus intéressante
% du code, la fonction \verb,composeSemantics, va calculer la sémantique
% de deux programmes composé séquentiellement. Si nous avons deux
% sémantiques \haskellinline{(m1,d1)} et \haskellinline{(m2,d2)}, le
% mouvement résultant de leur composition consistera à d'abord effectuer
% le mouvement \haskellinline{m1}, et ensuite celui de
% \haskellinline{m2}, c'est-à-dire la composé \haskellinline{m2 . m1}.
% Pour ce qui concerne les dessin, la tortue va effectuer
% \haskellinline{d1} à partir de sa position courante, puis elle va se
% déplacer du mouvement engendré par le premier programme
% (\haskellinline{m1}), puis enfin seulement, elle dessinera
% \haskellinline{d2}. Le dessin résultant est donc \haskellinline{\s ->
%   d1 s ++ (d2 . m1) s} :
% 
% \haskellcode{TAG_function_compose_semantics}
% 
% Enfin, nous pouvons calculer la sémantique d'un programme en combinant
% dans l'ordre (grâce au \haskellinline{foldl}) la sémantique de chacune
% des instruction (calculée grâce au \haskellinline{map}). Pour obtenir
% le dessin il suffit ensuite de ce donner l'état initial à la fonction
% de dessin calculée par \haskellinline{semantics}. La fonction
% \haskellinline{drawing} lance ce calcul à partir de l'état initial et
% récupère le dessin produit.
% 
% \haskellcode{TAG_function_program_to_semantic}
% 
% Nous voyons apparaître un produit semi-direct des déplacements par les
% dessins dans la fonction \haskellinline{composeSemantics}. C'est
% autour de ce produit que s'articulera la section suivante.
% 
% Ici nous allons formaliser la sémantique décrite ci dessus à l'aide du
% produit semi-direct.
% 
% 
% Nous allons considérer un monoïde idempotent $\drolecrochet{D,+,0}$
% qui représentera les dessins. La somme $+$ de deux dessin est leur
% superposition, et l'idempotence est la propriété $d+d=d$, autrement
% dit, ajouter un dessin à lui même ne change pas ce dessin.
% 
% Nous allons également considérer le groupe des rotations et
% translations de l'espace en deux dimensions
% $\drolecrochet{G,\times,1}$. Ainsi que l'action de ce groupe sur le
% monoïde $D$, la sémantique de $g \times{} d$ avec $d\in{}D$ et
% $g\in{}G$, est simplement l'application de la transformation $g$ sur
% le dessin $d$.
% 
% Le produit semi-directe de $(G \times D)$ permet de modéliser les
% sémantiques des programmes que nous décrivions plus haut.







%\begin{definition}
%  Nous définissons un dessin à partir d'un espace $E$, et d'un
%  ensemble de couleur $C$, par une fonction totale $E \rightarrow C$
%  qui associe à chaque point de l'espace sa couleur, nous notons ce type $D_E$
%\end{definition}
%
%Nous allons commencer par l'espace de dimension $0$. Ici, l'espace est
%réduit à un unique point (un 0-uplet, $E^0$) , un dessin en dimension
%$0$ est donc défini uniquement par une couleur.




% \begin{definition}
%   Un mouvement dans un espace $E$ est une fonction continue de
%   $[0;1]$ dans $E \times E$, qui à chaque point de $[0;1]$ associe
%   $(p,d)\in E^2$ où $p$ est une position et $d$ est une direction.
% \end{definition}
%
%
%\begin{definition}
%  Soit $d$ un dessin dans $E^N$, et $m$ un mouvement dans $E^{N+1}$,
%  nous pouvons alors construire l'extrusion de $D$ dans $E^{N+1}$ par $M$ ainsi.
%
%  $$\bigcup\limits_{x=0}^{1} \mathrm{transandrotate}~(\mathrm{lift}~(d~x))~(m~x)$$  
%\end{definition}
%
%La fonction $\mathrm{lift}$ est une fonction de type $D_N \rightarrow
%D_{N+1}$ qui prend en paramètre un dessin dans un espace de dimension
%$N$ et va le placer dans un espace de dimension $N+1$.
%
%La fonction $\mathrm{transandrotate}$ est une fonction de type $E^N
%\times E^N \rightarrow D_{E^N} \rightarrow D_{E^N}$, elle prend un
%dessin dans un espace de dimension $N$ pour le placer dans l'espace de
%dimension $N+1$, à la position et dans la direction donnée.
%
%La fonction $\mathrm{transandrotate}$ est une action du groupe des
%paires position et direction sur les dessins.




\section{Sémantique monadique induite}

Jusque-là, notre langage de programmation de tortue est
essentiellement basée sur des listes construites à partir d'un
alphabet paramétré (les actions de base), doté de propriété
mathématiques riches, mais pas encore clairement exploitables.

Par exemples, les conditionnelles, boucles, et affectation de
variables font défaut pour dessiner des figures complexes. De plus,
concrètement dessiner des figures nécessite de faire des actions
d'entrée/sortie, tout ceci nous conduit à encapsuler la sémantique de
notre langage dans des monades.


\subsection{Sémantique de la monade de dessin}

Implémenté par-dessus Haskell, notre proposition de langage hérite de
toute l'infrastructure logicielle proposée par Haskell. Cependant,
combiner les fonctions Haskell et les programme tortue n'est pas très
pratique. En effet, le produit monoïdal \hsi{<>} ressemble peu à de
la programmation.

Par ailleurs, la discussion plus haut sur les monoïdes avec
reset (voir section \ref{spat:monoid_reset}) et l'extension possible aux déplacements
non réversibles suggère que nos programmes devraient être définis
directement au niveau de la sémantique comme une paire composée d'un
déplacement et d'un dessin. Il faut cependant prendre garde
l'utilisation mémoire pour ne pas devoir stocker un état inutilement
lourd. 


L'approche monadique (et la \emph{do-notation}) propose un mécanisme
simple et efficace pour ce problème. Il se trouve que la bibliothèque
\emph{Prelude} d'Haskell offre un moyen facile d'encapsuler un monoïde
dans une monade.


L'instance suivante, définie dans la bibliothèque de base d'Haskell
peut être utilisée dans le cas qui nous occupe.

\haskellcode{TAG_instance_monad_pair}

\haskellcode{TAG_logo_type_msemantics}

Ceci nous permet de (re)définir les déplacements de base comme des
actions monadiques :

\haskellcode{TAG_logo_code_instructions_msemantics}

\noindent grâce à la fonction de chargement \hsi{load} définie par :

\haskellcode{TAG_logo_function_load_run}

Grâce à cette construction, notre tortue hérite de la \emph{do-notation}.

\begin{exemple}
  Voilà un code dessinant un triangle :
  
  \haskellcode{TAG_logo_exemple_triangle_monadique}
\end{exemple}


\subsection{Sémantique de la monade IO de dessin}

Visualiser les dessins sur l'écran nécessite une fonction
supplémentaire dont le code dépendra de la bibliothèque graphique qui
fera les appels nécessaires à cette bibliothèque pour effectivement
faire le dessin. Nous allons donc supposer que nous avons une fonction
\hsi{render :: Figure -> IO ()}.


Nous en déduisons que la sémantique des programmes tortue logo peuvent
être vu comme des actions d'entrée/sortie qui prennent en paramètre
une position et qui produisent un dessin tout en renvoyant la position
courante. Donc, le type des déplacements dans l'espace peut être
implémenté par :


\haskellcode{TAG_logo_type_iosemantics}

%\haskellcode{TAG_instance_monad_IO_pair}
\haskellcode{TAG_logo_instance_monad_iosemantics}

\noindent Nous remarquons que l'instance sur \hsi{IOPair} est très
similaire à celle sur les paires. La seule différence est le fait que
la paire est encapsulée dans une monade \hsi{IO}.

\noindent Maintenant, grâce à la fonction \hsi{render}, nous pouvons
élever le monoïde sémantique de la tortue dans l'\hsi{IOSemantics}.


\haskellcode{TAG_logo_fun_liftsemantics}

\noindent ou bien la monade sémantique dans la sémantique \hsi{IO} :


\haskellcode{TAG_logo_fun_liftmsemantics}

\noindent plusieurs égalités pourraient être écrites dans le but de valider ses définitions, par exemple, nous pouvons vérifier que nous avons :

\begin{haskellnoinline}
liftMSemantics (load p) == liftS (semantics p)
\end{haskellnoinline}


La chose importante est que le monoïde, la monade, ou la monade IO
sont trois approches pour définir des sémantiques équivalentes.


\begin{remarque}
  Le rendu instruction par instruction peut être utile suivant le
  contexte de programmation, par exemple le live-coding. Cependant,
  pour un rendu en deux dimensions ou en trois dimensions d'images
  complexes, it peut être plus avantageux d'accumuler dans un état les
  commandes de dessin de sorte de pouvoir calculer tout le rendu en
  une seule fois.
\end{remarque}


\section{\label{tuile_graphique_animation}Extension temporisée}

%Cette construction peut paraître très \emph{ad hoc}, mais elle prend
%tout son sens dès que nous remarquons qu'elle n'a rien de particulier
%par rapport à ce que nous avons fait jusque là. En effet, nous pouvons
%définir la même composition, et tous nos concepts de tortue qui
%applique des transformation à son environnement se transposent
%parfaitement bien à l'extension temporisée. En effet, nous pouvons
%considérer les transformation linéaire et réversible de notre échelle
%temporelles (changement d'échelle, déplacement, etc.).
%
%En effet, exactement de la même manière que nous avons construit un
%monoïde inversif à l'aide du monoïde des dessins, et du groupe des
%bijection de l'espace dans l'espace. Nous pouvons construire le
%monoïde inversifs de notre extension tortue temporisée à l'aide du
%monoïde des fonctions du temps dans les dessins, et du groupe des
%bijection du temps dans le temps. 
%
%Comme nous l'avons vu dans le chapitre sur l'introduction
%\ref{intro_math:produit_sd} des concepts mathématique que nous allions
%utiliser, nous pouvons construire un monoïde inversif à l'aide d'un
%monoïde inversif, d'une action de groupe et d'un groupe (dans des
%ensembles compatibles).
%
%Nous avons donc :
%
%\begin{itemize}
%\item Le groupe des bijections du temps dans le temps,
%\item l'action de ce groupe sur les animations (la simple composition
%  de fonction),
%\item le monoïde inversif des dessins.
%\end{itemize}


%La sémantique du produit que nous obtenons avec cette construction est
%très similaire à celle que nous avions dans le chapitre sur la
%programmation temporelle \ref{chapitre:tuile_temporelle}, les \og
%déplacements \fg{} de la tortue représentent des déplacement dans le
%temps. Les différences majeures avec ce que nous avons fait plus tôt
%est que le monoïde ici induit aussi un déplacement dans l'espace. Dit
%autrement, un élément de ce monoïde induit à la fois un déplacement
%dans le temps et dans l'espace. Une autre manière de voir les choses
%est de remarque que nous pouvons déplacer les déplacement dans
%l'espace dans le groupe $(t\to (t,de))$ et retrouver le même monoïde
%inversif.
%
%
%Comme nous pouvons nous y attendre, un élément $\inv{x}$ défait les
%transformations de $x$.
%
% En notant $t$ l'échelle temporelle, $e$ l'espace, et $d$ les dessins, le monoïde sous-jacent ressemble à :
% 
% $$D=(e\to{}e, e\to{}d)$$
% 
% Nous construisons donc le monoïde :
% 
% 
% \begin{align*}
% (t\to{}t,t\to{}D) = (t\to{}t,t\to{}(e\to{}e,e\to{}d) & ~~~~~ (t_1,a_1) \cdot (t_2,a_2) = (t_1 \cdot t_2,\lambda t. (a_1(t_1~t)) \cdot (a_2~t)) \\
% (t\to{}t, t\to{}e\to{}e, t\to{} e\to{}d) & \\
% (t\to{}(t,e\to{}e),t\to{}e\to{}d) & \\
% \end{align*}
% 


Pour l'instant, notre tortue est capable d'effectuer des figures dans
un espace à deux dimensions, et donc, effectuer des dessins en 2
dimensions. Nous pouvons maintenant proposer une extension pour
réaliser des animations en 2 dimensions. Les outils algébriques que
nous avons proposé jusque-là peuvent être utilisés.


\subsection{Animation}

Au niveau sémantique, l'extension de notre tortue à la dimension
temporelle est assez facile. Il s'agit d'une construction proche celle
présentée au chapitre~\ref{chapitre:tuile_temporelle}. La principale
différence est que nous ne chercherons pas à définir un groupe de
transformation temporelle, pour avoir in fine un monoïde
inversif. Nous auront simplement un monoïde avec reset.

\noindent Nous définissons le type :

\haskellcode{TAG_logo_type_animation}

\noindent Une valeur $a$ de ce type est une fonction qui associe à chaque valeur
de l'échelle temporelle $d$ un dessin.


\noindent L'interprétation prêtée à un élément \hsi{a::Animation} est
la suivante. Le déplacement effectué et la figure dessinée à un
instant \hsi{t} est définie par \hsi{a t}. 

Dès lors, nous pouvons écrire une fonction de rendue qui va permettre
de calculer l'animation.


\haskellcode{TAG_logo_function_runa}

Cette dernière dessine simplement la figure spécifiée par l'animation
à chaque instant.

\noindent En effet, comme \hsi{Semantics} est un monoïde, les animations peuvent
elles aussi vu comme un monoïde en définissant :

\haskellcode{TAG_logo_instance_monoide_animation}


\noindent Ce code est juste donné pour mémoire car ce n'est qu'une
spécialisation de l'instance générique sur les fonctions sur un
monoïde

  
\begin{exemple}
  Chaque figure \hsi{f} peut être changée en animation en définissant
  simplement \hsi{liftA f = const (id, const f)}. C'est-à-dire le
  programme qui affiche la figure à n'importe quel instant et à
  n'importe quelle position.

  \noindent Nous avons alors : \hsi{liftA (f <> f') == liftA f <> liftA f'}

  \noindent Observons qu'avec des animations et des déplacements arbitraire, le
  monoïde de composition de deux animation défini ci dessus n'est pas
  triviale, car il ne s'agit pas de la simple superposition de deux
  animations.  
\end{exemple}

\begin{remarque}
  La figure produite par \hsi{(a <> a') t} a chaque instant \hsi{t}
  n'est pas dans le cas général les superpositions des figures
  produites par \hsi{a t} et \hsi{a' t}. La position dans l'espace à
  partir de laquelle la tortue dessine \hsi{a' t} est celle à laquelle
  la tortue termine le dessin \hsi{a t}.
\end{remarque}

Il en il en découle que la composition de deux animation à partir de
la même position nécessite un reset qui peut être défini par :

\haskellcode{TAG_logo_instance_resettable_animation}

\noindent Cette construction hérite de l'instance sur le type
\hsi{Semantics}. La superposition temporisée de \hsi{a} et \hsi{a'} au
même instant et à la même position peut être définie par \hsi{reset a <> a'}.
  


\subsection{Déplacement temporels}

En terme sémantique, l'animation du type défini plus haut autorise
d'ores et déjà la définition de toute animation en deux
dimensions. Cependant, en terme de programmation temporelle, ce n'est
pas très pratique. Nous pouvons souhaiter un ensemble de fonction qui
permet d'effectuer des opérations simple sur tous les programme
temporisé de manière générique. Par exemple, démarrer une animation à
un instant donné, la terminer à un instant donné, ou la jouer
uniquement entre deux instants. Nous pouvons également souhaiter
pouvoir modifier la vitesse d'une animation. Et, plus important
encore, nous pouvons vouloir composer des animations sur le temps.

\noindent Ces observations nous conduisent à la définition d'une notion de
déplacement temporel, ainsi que son type, et monoïde associé.

\haskellcode{TAG_logo_type_tmove}

% \noindent L'usage du type \hsi{Maybe t} comme co-domaine peut sembler maladroit à
% première vue. Cependant, c'est finalement ainsi qu'il est le plus
% élégant de pouvoir ``bloquer'' le temps tout en préservant la
% propriété qu'un instant a une durée 0. En effet, en bloquant le temps,
% aucune valeur d'instant ne sera donnée.


\haskellcode{TAG_logo_instance_monoid_tmove}



%\begin{remarque}    
%  L'instance de monoïde est une généralisation de la composition de
%  fonction reversée, c'est-à-dire \hsi{flip (.)} en Haskell,
%  c'est-à-dire \hsi{\f g x -> g (f x)}.
%
%  Cela est nécessaire car pour définir le semi-groupe à l'aide du
%  produit semi-direct, nous avons besoin d'une action à gauche. 
%\end{remarque}

\begin{exemple}
  Le premier exemple de déplacement temporisé sont les fonctions de
  délais de forme \hsi{\t -> Just (t + d)} pour une constante
  \hsi{d}. Autrement dit, cette fonction permet de modéliser le fait
  que déplacement de la tortue dure \hsi{d} unité de temps.

  La composition monoïdale des délais se comporte comme nous
  l'espérons, les délais sont bien sommés~:
  

  \begin{haskellnoinline}
    (\t -> Just (t + d)) <> (\t -> Just (t + d')) ===
      \t -> Just (t + d + d')
  \end{haskellnoinline}

  Beaucoup d'autres exemples de déplacements temporels peuvent être
  définis. Par exemple, les étirements temporels d'un facteur \hsi{f},
  c'est-à-dire de la forme \hsi{\t -> Just (t * f)}. Ces fonctions permettent de
  compresser le temps si $f < 1$, ou bien étirer le temps si
  $f>=1$. Comme nous l'avons évoqué dans la
  partie~\ref{sec:propriete_sem_mult} cette construction souffre d'une
  dépendance à l'unité choisie.
\end{exemple}


\subsection{Extension sémantique temporelle}

L'extension temporelle de notre type tortue sémantique est obtenue en
appairant les déplacements temporels et les animations.

\haskellcode{TAG_logo_type_textention}

\noindent Le monoïde des déplacements temporels agit sur les animations
par l'action :

\haskellcode{TAG_instance_action_tmove_animation}

\noindent Ici, dans le cas où l'application est stoppée par un
déplacement temporel, l'animation ne produit plus que la figure vide.

Maintenant, grâce à la construction du produit semi-direct, nous avons :

\haskellcode{TAG_logo_instance_monoid_textension}

\noindent Exactement comme nous l'avons évoqué plus haut à propos du
type \hsi{Semantics}, ici, l'instance de monoïde du type
\hsi{TExtension} est parfaitement isomorphe à celle de \hsi{PSD TMove Animation}.


\noindent toutes ces instances sont données comme un rappel. Le reset
est également étendu à l'extension temporisée (et aux animations
sous-jacentes) avec l'instance suivante :

\haskellcode{TAG_logo_instance_resettable_textension}

\noindent Elle permet de superposer deux animations encapsulées au
même instant, à la même vitesse, et à la même position. Notons que
cette implémentation est exactement la même que sur le type
\hsi{Semantics}. Nous pouvons par ailleurs vérifier que nous
satisfaisons la propriété :


\begin{haskellnoinline}
reset (d, a) <> (d', a') == (d', reset a <> a')
\end{haskellnoinline}


\noindent pour tous les déplacements temporels \hsi{d} et \hsi{d'} et
toutes les animations \hsi{a} et \hsi{a'}.


Exécuter une sémantique temporelle à partir d'un instant donné \hsi{t}
et étant donné une position dans l'espace \hsi{p} peut être fait grâce
à la fonction :

\haskellcode{TAG_logo_function_runTS}

\noindent qui explicite le fait qu'un déplacement temporel \hsi{d}
dans la sémantique temporelle de \hsi{(d,a)} affecte seulement les
animations qui seront combinée à droite de \hsi{(d,a)}. Ceci
généralise à la dimension temporelle le fait que les déplacements
spatiaux effectué par un programme tortue en deux dimensions \hsi{p}
affecte les dessins réalisés par les programmes combinés à droite de
\hsi{p}, comme nous l'illustrons dans les exemples suivant.



\begin{exemple}
  Toute animation \hsi{a} peut être encapsulée simplement par une
  sémantique temporelle en prenant :

\begin{haskellnoinline}
liftTS a = TExt (Just, a)      
\end{haskellnoinline}

\noindent Alors la propriété \hsi{liftTS (a <> a') = liftTS a <>
  liftTS a'} est vérifiée.

  Comme premier exemple d'application, retarder une animation \hsi{a}
  de \hsi{d} unités de temps peut être réalisé grâce à
  \hsi{delay d <> liftTS a} avec


\begin{haskellnoinline}
delay d = TExt (\t -> Just (t + d), neutral)
\end{haskellnoinline}
  
  \noindent Un second exemple d'application, modifier la vitesse d'un facteur
  \hsi{f} d'une animation peut être fait à l'aide de la fonction :
  \hsi{stretch f <> liftTS a} avec

\begin{haskellnoinline}
stretch f = TExt (\t -> Just (t * f), neutral)
\end{haskellnoinline}
  
  \noindent Rassembler éléments sémantiques temporels qui n'agissent que sur la
  dimension temporelle nous conduit à définir l'ensemble de fonctions
  suivante.
\end{exemple}


\haskellcode{TAG_logo_fonction_temporelles}


Parmi les fonctions définies plus haut, la fonction \hsi{liftTM}
permet d'encapsuler n'importe quelle transformation temporelle dans le
monoïde temporel, de sorte que les fonctions \hsi{delay} et
\hsi{stretch} se comportent comme nous l'avons illustré plus haut.

Les fonctions \hsi{start} et \hsi{stop} permettent de démarrer ou
d'arrêter un média à un instant fixé arbitrairement. La fonction
dérivée \hsi{play} permet de jouer une animation entre les instants
donnés en paramètre.



%
%Timed moves form an instance of timed monoid:
% %
%\begin{displaymath}
%\mathbf{instance}\;{TimedMonoid}\;({TMove}\;{d})\;{d}\;\mathbf{where}
%\\
%{liftTM}\mathrel{=}{id}
%\\
%{start}\;{d}\;
%{t}\mathrel{=}\mathbf{if}\;({t}\mathbin{<}\mathrm{0})\;\mathbf{then}\;{Nothing}\;\mathbf{else}\;{d}\;{t}
%\\
%{stop}\;{d}\;{t}\mathrel{=}\mathbf{if}\;({t}\mathbin{>}\mathrm{0})\;\mathbf{then}\;{Nothing}\;
%\mathbf{else}\;{d}\;{t}
%\end{displaymath}
%
%\noindent 
%The timed monoid instance of timed semantic extension follows
%from the above as it uniformly derives from the timed monoid instance 
%of timed moves\footnote{The \ensuremath{{ScopedTypeVariables}} option, necessary to
%  remove any ambiguity on the type of \ensuremath{{mempty}} has been omitted in
%  this instance.}.
% %
%\begin{displaymath}
%\mathbf{instance}\;{TimedMonoid}\;({TExtension}\;{d})\;{d}\;\mathbf{where}
%\\
%{liftTM}\;{d}\mathrel{=}({d},{mempty})
%\\
%{start}\;({d},{a})\mathrel{=}({d},{act}\;({start}\;{mempty})\;{a})
%\\
%{stop}\;({d},{a})\mathrel{=}({d},{act}\;({stop}\;{mempty})\;{a})
%\end{displaymath}
% %%% $
\begin{exemple}
  Chacun peut vérifier qu'en exécutant la sémantique temporisée
  \hsi{play 0 d (liftTS f)} va dessiner la figure \hsi{f} de l'instant
  0 jusqu'à l'instant \hsi{d}, n'effectuant aucun dessin en dehors de
  cet intervalle.
\end{exemple}


\begin{remarque}
  Nous pouvons montrer que le monoïde des sémantiques temporisées
  générée par les délais, start, et stop, ainsi que des animations
  arbitraire n'est pas un monoïde inversif.

  Il pourrait être changé en un monoïde inversif en propageant les
  coupures temporelles induite par start et stop. Cependant, une telle
  propagation des coupures temporelle ne semble pas souhaitable. En
  effet, la composition de sémantique temporisée calcule en fait une
  sorte d'enveloppe temporelle des animations temporisée à la manière
  des enveloppes spatiales sont calculée dans Diagrams~\cite{Y12}.  
\end{remarque}


\begin{remarque}
  Il existe une notion d'identité partielle sur notre ensemble
  temporisé \hsi{d} qui peut être défini par des fonctions
  \hsi{p :: d -> Maybe d} tel que si \hsi{p t == Just t'},
  alors \hsi{t==t'}.
  Vue comme une fonction partielle, une identité partielle est
  essentiellement définie par son domaine.

  Maintenant, comme exemple d'une enveloppe temporelle implicite, nous
  pouvons vérifier que pour toute identité partielle \hsi{d1},
  \hsi{d2}, pour toute animation \hsi{a1} et \hsi{a2}, nous avons

  \hsi{TExt (d1,a1) <> TExt (d2,a2) == TExt (d, a1 <> a2)} où \hsi{d}
  est l'unique identité partielle définie par l'union des domaines de
  \hsi{d1} et \hsi{d2}.
\end{remarque}



\section{Extension à la troisième dimension}

%Enfin, dans cette dernière partie, nous soulignons le fait que tout ce
%que nous avons développé plus tôt pour les dessins en deux dimensions
%est aussi valable dans un espace en trois dimensions.
%
%Dans une première version, nous pouvons considérer la simple extension
%de l'espace. Nous remarquons alors que nous ne somme capable que de
%tracer des squelettes en trois dimensions. À l'instar des dessins en
%deux dimensions.

Notre tortue est maintenant spatio-temporelle, elle dessine des
figures en deux dimensions dans le temps. Maintenant nous allons
étendre l'espace de dessin pour pouvoir effectuer des figures en
trois dimensions composées de surfaces. Encore une fois, les outils
algébriques développés plus haut sont réutilisable dans ce but.


\subsection{L'extrusion de la tortue 3D}

Il y a beaucoup de possibilité pour définir un langage de
programmation de dessin en trois dimensions. Poursuivant l'idée que
les dessins doivent être définis en termes de combinaison de position
du stylo de la tortue et de déplacement, une possibilité est de
définir les surfaces en trois dimensions par l'extrusion : une
technique connue de synthèse de dessin en trois dimensions qui permet
de créer des surfaces 3D en déplaçant dans l'espace une courbe en deux
dimensions changeante.

Plus précisément, dans le cas en deux dimensions, nous observons que
les figures sont dessinées par ``extrusion'' des positions de la
tortue qui définissent des points (quand le stylo et posé sur la
feuille) en des segments. Étendre les position des tortues vers un
espace en trois dimensions avec des courbes en deux dimensions simple
comme ``pointe'' de stylo de la tortue nous conduit vers le langage de
programmation désiré.

Les points sont représentés par des vecteurs de taille 3, encodant les
coordonnées cartésienne :

\haskellcode{TAG_logo_type_point3d}

\noindent Nous nous limitons aux transformation linéaire de cet
espace. Ces fonctions affines peuvent êtres encodées par la paire
suivante :


\haskellcode{TAG_logo_type_affine3d}

\noindent Ces transformations affines se composent de la façon suivante. Nous
pouvons voir apparaître le produit semi-directe des matrices sur les
vecteurs :

\haskellcode{TAG_logo_instance_monoid_affine3d}

\noindent L'inverse est donc défini comme nous l'avons vu en
section~\ref{intro_math:produit_sd}~:

\haskellcode{TAG_instance_inverse_affine3d}

\noindent Ensuite, limitant les pointes de stylo de la tortue dans
notre exemple aux cercles d'un rayon donné, Les instructions de base et
les programmes tortue en trois dimensions sont définies par :

\haskellcode{TAG_logo_type_penshape_and_program}

\noindent Les mouvements de la tortue en trois dimensions sont définies
par des transformations affines arbitraire de l'espace 3D sous-jacent
(l'instruction \hsi{Transform}). L'extrusion est effectuée entre deux
instructions \hsi{Pen} non vides séparée par une ou plusieurs
instructions \hsi{Transform} qui sont implicitement composée. Ceci
nous autorise à définir des mouvements complexes en en composants des
plus simples, réalisant l'extrusion seulement quand le mouvement est
défini.


\begin{exemple}
  Comme programme d'exemple, nous pouvons donner :
  
  \haskellcode{TAG_logo_exemple_cylinder}

  \noindent Maintenant, comme il devrait devenir plus clair avec la
sémantique par extrusion détaillée plus bas, l'expression
\hsi{cylinder r l} spécifie un cylindre de rayon \hsi{r} et de hauteur
\hsi{l} sur l'axe $z$.
\end{exemple}


L'instance de monoïde inversif est un peu différente du cas en deux
dimensions, au niveau des instructions :

\haskellcode{TAG_logo_instance_P3D_inverse}

\noindent La différence tient au fait que dans le cas en deux
dimension, c'était de déplacement qui générait le trait, alors qu'en
trois dimension, nous marquons les deux extrémités.

\subsection{Position 3D et scène}

Nous allons appeler \emph{Scène} un ensemble de figures en trois
dimensions placées dans un espace en trois dimensions. Nous allons
définir les scènes par :

\haskellcode{TAG_logo_type_scene}

Une position en trois dimension décrit la dernière forme du crayon, sa
transformation affine associé, ainsi que la transformation courante. Une
scène qui décrit un ensemble de triangles

Une fois encore, les scènes héritent de la structure de monoïde des
ensembles avec l'union comme produit, et l'ensemble vide comme neutre.

\subsection{Déplacement en 3D, Dessins et types sémantiques}

Les déplacements en trois dimensions et dessins sont définis de
manière similaires à ceux dans le cas à deux dimensions. 
\haskellcode{TAG_logo_move3d}

\haskellcode{TAG_logo_drawing3d}


avec une action de semi-groupe similaire et le produit
semi-direct dérivé pour la sémantique, définis par :


\haskellcode{TAG_logo_instance_action_move3d_draw3d}

Le monoïde sémantique est formé grâce au produit semi-directe du
groupe des déplacements et des dessins en trois dimensions~:

\haskellcode{TAG_logo_semantics3d}

\begin{remarque}
  Les éléments du types \hsi{Move3D} n'appartiennent pas forcement à un
  groupe.
\end{remarque}

\subsection{Exécuter un programme tortue en trois dimensions}

En ce qui concerne l'exécution, nous définissons la sémantique des
déplacements et des dessins pour les actions de base de la tortue par :


\haskellcode{TAG_logo_instruction_sem}


\noindent avec la fonction \hsi{extrude} définie par :

\haskellcode{TAG_logo_function_extrude_1}

\noindent dans le cas où à la dernière position, la pointe du crayon
est vide :

\haskellcode{TAG_logo_function_extrude_2}

\noindent dans le cas où à la première et à la dernière position du
crayon, il y a un rayon nul, c'est-à-dire que les deux définissent un
point, \footnote{c'est-à-dire en ajoutant un segment de longueur
  nulle} :

\haskellcode{TAG_logo_function_extrude_3}


\noindent dans le cas où à la position précédente la pointe du crayon
avait un rayon nul, c'est-à-dire s'il définissait un simple point, et
\haskellcode{TAG_logo_function_extrude_4}


\noindent dans le cas où la pointe du crayon courante a un rayon nul
et donc défini un point seul :

\haskellcode{TAG_logo_function_extrude_5}

\noindent dans le cas où la dernière et la présente pointe de crayon
sont des ellipses avec un rayon non nul.


Les fonctions \hsi{span3D}, \hsi{tube3D} et \hsi{cospan3D} permet la
triangulation des surfaces définies par extrusion d'une position vers
une autre. Leur sémantique est définie de manière informelle dans la
figure~\ref{fig:prog_spatiale_span_tube_cospan}

\begin{figure}[h]
  \center
\noindent\includegraphics[width = \textwidth
%,height=2.3cm
]{figures/Drawing.pdf}
\caption{\label{fig:prog_spatiale_span_tube_cospan}Exemple de
  triangulation effectué respectivement grâce aux fonctions
  \hsi{span3D}, \hsi{tube3D} and \hsi{cospan3D}.}
\vskip -0.7cm
\end{figure}

\section{Résumé de la construction}

Cette construction concistant en le produit semi-directe d'un groupe
et d'un monoïde inversif, est très régulière. elle permet de produire
des monoïdes inversifs de plus en plus complexes.

\noindent Finalement, nous pouvons voir le groupe comme un contexte
duquel va dépendre la valeur associée dans le monoïde inversif.

Nous pouvons donc créer un espace dont le temps s'écoule différement
suivant l'endroit où l'on s'y trouve. Et, réciproquement, un temps qui
déforme l'espace différement suivant l'instant.

Nous remarquons aussi qu'il n'y a pas de limite à la richesse de
l'espace dont les transformations vont former le groupe. En
particulier, cela peut être des informations sur le contenu tuilé,
l'élément du monoïde inversif. Cependant, cela n'est pas possible avec
le produit semi-direct, en effet, il n'y a transfert d'information que
du groupe vers le monoïde inversif.

\section{Prototype}

Nous avons réalisé une implémentation des concepts explorés ici. Elle
est décrite en détails dans le papier\cite{AJ17}.


Il s'agit d'une bibliothèque permettant de programmer des dessins
animés en trois dimensions, et qui permet de se déplacer dedans à
grâce aux interfaces d'entrée de l'ordinateur, joystick, souris,
clavier\ldots


Le code source est disponible ici :
\url{https://github.com/OctopusFarm/Octopus}.


\section{Conclusion}

Dans ce chapitre, dans un souci de simplicité, nous avons fixé le type
permettant de représenter le temps, le type de la mesure dans
l'espace, le repaire de l'espace (orthogonal et orthonormé). Certains
de ces choix limitent l'expressivité autorisée par le modèle. Mais
nous pouvons abstraire tous ces types. La structure qui équipe notre
construction dépend des structures qui équipent tous ces types
dépendent.



Nous proposons donc une approche formelle pour définir (et
implémenter) un modèle sémantique de média temporisés basé sur les
concepts théoriques des semi-groupes.

La principale nouveauté de notre approche est de rendre explicite
l'usage des produits semi-directs. Ceci permet, en particulier de
combiner au sein d'une structure de semi-groupe inversif à la fois les
déplacements (spatiaux et temporels) ainsi que les dessins.

À notre connaissance, la notion de produit semi-direct, bien que
dérivant de la notion d'action de monoïde qui est déjà utilisé dans la
bibliothèque \emph{Diagrams}~\cite{Y12}, n'a jamais été considérée
dans la programmation de média temporisés.