Le manuscrit présente une partie des travaux de recherche que j'ai effectués au cours des dix dernières années. Je me suis focalisé en particulier sur la présentation du calcul de réécriture comme un formalisme théorique permettant de donner la sémantique dynamique et statique de toute une famille de langages basés sur le filtrage, les règles et les stratégies de réécriture. Je présente le calcul de réécriture général ainsi que plusieurs instances et extensions, en mettant l'accent sur l'expressivité et sur les propriétés de ces calculs. Je montre en particulier que l'intégration uniforme des mécanismes de bases de la réécriture et du lambda-calcul permet une définition précise du processus de réécriture sous des stratégies ainsi que des encodages, typés ou non, de différents formalismes similaires. Je présente dans ce manuscrit des systèmes de types développés dans l'optique d'un formalisme théorique pour le typage dans des langages de programmation à base de règles et je ne discute que brièvement les systèmes de types dépendants étudiés dans une perspective logique. Le filtrage et l'application de substitutions obtenues comme résultat sont des opérations réalisées au niveau méta du calcul de réécriture mais une version explicite permet leur manipulation modulaire et efficace au niveau objet du calcul. Cette version explicite du calcul est étendue avec des structure de graphe permettant de représenter explicitement le partage et les cycles. Je propose également un formalisme général permettant d'exprimer différents calculs à motif et une méthodologie qui met en évidence les points clés permettant d'obtenir la confluence de ces calculs.

La programmation distribuée est une tâche difficile. Elle a énormément gagné en importance avec le développement des réseaux qui supportent un nombre croissant exponentiellement d'applications. Les systèmes distribués fournissent des fonctionnalités assurées par les noeuds qui forment un réseau et échangent des données et services, éventuellement par le biais de messages. La provenance du service n'est souvent pas pertinente, alors que sa fiabilité est essentielle. Notre objectif est de fournir un nouveau modèle de communication qui permet de spécifier intentionnellement lequel service est demandé, et non les noeuds qui le fournissent. Cette spécification intentionnelle des échanges offre un potentiel pour faciliter la programmation distribuée, garantir la persistance des données dans les messages et la résilience des systèmes, qui constituent le sujet de cette thèse. Nous proposons donc un cadre qui supporte des messages avec destinations intentionnelles, qui sont évaluées uniquement à la volée au fur et à mesure du déplacement des messages. Nous introduisons un langage, Questlog, qui gère les destinations intentionnelles. Contrairement aux langages à base de règles existants pour les réseaux, comme Datalog, qui suivent le mode push, Questlog permet d'exprimer des stratégies complexes afin de récupérer de manière récursive des données distribuées en mode pull. Le langage fonctionne sur une machine virtuelle qui s'appuie sur un SGBD. Nous démontrons l'approche avec des exemples pris dans deux domaines: (i) les architectures orientées données, où une classe restreinte d'applications client-serveur sont distribuées de manière transparente sur les systèmes pair-à-pair basés sur une DHT, (ii) les réseaux de capteurs sans fil, où un protocole de groupement des noeuds en clusters virtuels est proposé pour agréger les données. Dans ce protocole, les chefs des clusters sont élus à l'aide des destinations intentionnelles. Nos simulations sur la plate-forme QuestMonitor montrent que cette approche offre une simplicité, une modularité aux protocoles, ainsi qu'une fiabilité accrue.

Ce mémoire présente un langage déclaratif de description de scénarios et de modèles d’attaques, ainsi qu’un moteur de détection qui lui est associé. Le langage s’inspire fortement de l’état de l’art dans le domaine des IDS (système de détection d’intrusions) et il s’approprie les qualités de plusieurs de ses références telles que LTL, Snort, Lambda, ou Chronicle. Il représente aussi une évolution majeure de la première version introduite dans un précédent travail, dans le sens où nous avons introduit de nouveaux opérateurs, nous avons associé une sémantique formelle au langage, ainsi qu’un système de règles de réécriture permettant le calcul d’une forme normale ; nous offrons aussi la possibilité de définir des modèles d’attaques. Les modèles étant différents des scénarios, le comportement du moteur de détection a été enrichi, augmentant l’expressivité du langage par rapport à sa version initiale.

Les travaux de recherche effectués dans cette thèse s'inscrivent dans le cadre du projet 81/2 qui développe des structures de données et de contrôle expressives et efficaces pour la simulation de systèmes dynamiques. L' objectif de ce travail est de concevoir, étudier et développer des représentations dynamiques de l'espace dans un cadre déclaratif.<br>Nos travaux ont consisté à introduire dans 81/2 deux nouvelles structures de données, les GBF et les amalgames, en proposant une formalisation et en étudiant leur implémentation. Les GBF permettent de représenter des espaces réguliers et homogènes, tandis que les amalgames permettent de construire, par calcul, des espaces hétérogènes et ad-hoc. Ces deux nouvelles notions trouvent directement leur application dans le domaine de la simulation des systèmes hautement dynamiques (comme par exemple les processus de croissance en biologie). Elles trouvent aussi une application directe en informatique classique, en fournissant un nouveau cadre théorique pour 1) la spéciffication, l'analyse et l' implémentation de données récursives (les GBF permettent en particulier de considérer les arbres et les tableaux dans le même cadre théorique) ; 2) la conception et la formalisation des nouveaux mécanismes de programmation incrémentielle qui commencent à apparaître dans des langages tels que Java (les amalgames permettent en particulier de conjuguer à la fois un mécanisme d' instanciation par capture implicite et d'extension des programmes). GBF et amalgames sont d'abord étudiés pour eux-mêmes puis sont introduits et intégrés au langage déclaratif 81/2 pour donner lieu à la déffinition du langage 81/2D .<br>Nous avons montré, par de nombreux exemples signifficatifs, la pertinence des choix effectués. Ceux- ci mettent en évidence le gain en expressivité apporté par l'enrichissement de la notion d'espace, et des primitives permettant la déffinition d'objets sur ces espaces. Les notions de GBF et d'amalgame permettent la déffinition, de façon extrêmement concise, de structures de données régulières et irrégulière, dans un cadre déclaratif, et ouvrent de nouvelles voies pour la paramétrisation et la construction incrémentielle de programmes.

From declarative programming languages to synthetic biology.

La construction de programmes nécessite l'utilisation d'outils adaptés. Un outil particulier est le langage de programmation. Les langages logico-fonctionnels sont des langages de programmation dits déclaratifs qui se basent sur les notions mathématiques de fonction et de prédicat. Ce fondement théorique solide facilite à la fois la description d'un système à un niveau proche de la spécification ainsi que la validation de programmes. Néanmoins, les concepts sous-jacents aux langages logico-fonctionnels sont insuffisants pour la description aisée de systèmes complexes qui nécessitent l'interactivité, la concurrence et la distribution. Pour la modélisation de ces systèmes, la notion de processus a été introduite. Dans le contexte des algèbres de processus, un processus est caractérisé par les actions qu'il est capable d'exécuter. Cependant, les langages fondés uniquement sur les algèbres de processus doivent être étendus afin d'éviter le codage de fonctions et de prédicats en termes de processus. Dans cette thèse nous proposons un modèle de calcul qui intègre la programmation concurrente et déclarative. Nous suggérons de modéliser un système par un ensemble de composants. Chacun de ces composants comporte un programme déclaratif, appelé store, et un ensemble de processus interagissant par l'exécution d'actions. De plus, un composant peut contenir de nouvelles actions définissables par le programmeur. L'interaction entre composants est fondée sur le même principe, c.-à.-d. un processus peut exécuter des actions sur les stores des autres composants. Les différents composants d'un système peuvent utiliser des langages déclaratifs différents pour la description de leurs stores respectifs, ce qui nécessite la traduction des valeurs communiquées. Nous donnons une sémantique compositionnelle ainsi qu'une analyse de la confidentialité pour les processus d'un composant, et présentons les principes d'un prototype implanté

Ces travaux s'inscrivent dans le projet MGS qui étudie l'apport de notions topologique dans les langages de programmation. Nous étudions et développons les notions de collection topologique (un ensemble de valeurs muni d'une relation de voisinage) et de transformation (une fonction définie par des règles de réécriture utilisant la notion de voisinage). Ces notions apportent un point de vue unifié sur les structures de données, une extension de la définition des fonction par cas et un cadre alternatif à la notion de polytypisme, sans se limiter aux types de données algébriques. Dans cette thèse, nous développons : -un algorithme générique de filtrage ; -un schéma d'évaluation d'ordre supérieur ; -un système de types traitant les collections hétérogènes, les transformations polytypiques et doté d'inférence automatique ; -l'utilisation du typage pour la compilation ; -de nombreux exemples validant la pertinence des choix effectués.