Lors de l'exécution des applications à base d'objets, plusieurs millions d'objets peuvent être créés, utilisés et enfin détruits s'ils ne sont plus référencés. Néanmoins, des dysfonc- tionnements peuvent apparaître, quand des objets qui ne sont plus utilisés ne peuvent être détruits car ils sont référencés. De tels objets gaspillent la mémoire principale et les ap- plications utilisent donc davantage de mémoire que ce qui est effectivement requis. Nous affirmons que l'utilisation du gestionnaire de mémoire virtuel du système d'exploitation ne convient pas toujours, car ce dernier est totalement isolé des applications. Le système d'exploitation ne peut pas prendre en compte ni le domaine ni la structure des applications. De plus, les applications n'ont aucun moyen de contrôler ou influencer la gestion de la mémoire virtuelle. Dans cette thèse, nous présentons Marea, un gestionnaire de mémoire virtuelle piloté par les applications à base d'objets. Il constitue une solution originale qui permet aux développeurs de gérer la mémoire virtuelle au niveau applicatif. Les développeurs d'une application peuvent ordonner à notre système de libérer la mémoire principale en trans- férant les objets inutilisés, mais encore référencés vers une mémoire secondaire (telle qu'un disque dur). En plus de la description du modèle et des algorithmes sous-jacents à Marea, nous présentons notre implémentation dans le langage Pharo. Notre approche a été validée à la fois qualitativement et quantitativement. Ainsi, nous avons réalisés des expérimentations et des mesures sur des applications grandeur-nature pour montrer que Marea peut réduire l'empreinte mémoire de 25% et jusqu'à 40%.

Ces dernières années ont vu l'émergence d'assistants interactifs de preuves riches en fonctionnalités et d'une grande maturité d'implémentation, ce qui a permis l'essor des grosses formalisations de résultats papier et la résolution de conjectures célèbres. Mais autant d'assistants de preuves reposent sur presque autant de logiques comme fondements théoriques. Cousineau et Dowek (2007) proposent le λΠ-calcul modulo comme un cadre universel cible pour tous ces environnement de démonstration. Nous montrons dans cette thèse comment ce formalisme particulièrement simple admet une implémentation d'un vérificateur de taille modeste mais pour autant modulaire et efficace, à la correction de laquelle on peut réduire la cohérence de systèmes tout entiers. <p> Un nombre croissant de preuves dépendent de calculs intensifs comme dans la preuve du théorème des quatre couleurs de Gonthier (2007). Les méthodologies telles que SSReflect et les outils attenants privilégient les preuves contenant de nombreux petits calculs plutôt que les preuves purement déductives. L'encodage de preuves provenant d'autres systèmes dans le λΠ-calcul modulo introduit d'autres calculs encore. Nous montrons comment gérer la taille de ces calculs en interprétant les preuves tout entières comme des programmes fonctionnels, que l'on peut compiler vers du code machine à l'aide de compilateurs standards et clé-en-main. Nous employons pour cela une variante non typée de la normalisation par évaluation (NbE), et montrons comment optimiser de précédentes formulation de celle-ci. <p> Au travers d'une seule petite modification à l'interprétation des termes de preuves, nous arrivons aussi à une représentation des preuves en syntaxe abstraite d'ordre supérieur (HOAS), qui admet naturellement un algorithme de typage sans aucun contexte de typage explicite. Nous généralisons cet algorithme à tous les systèmes de types purs (PTS). Nous observons que cet algorithme est une extension à un cadre avec types dépendants de l'algorithme de typage des assistants de preuves de la famille HOL. Cette observation nous amène à développer une architecture à la LCF pour une large classe de PTS, c'est à dire une architecture où tous les termes de preuves sont corrects par construction, a priori donc, et n'ont ainsi pas besoin d'être vérifié a posteriori. Nous prouvons formellement en Coq un théorème de correspondance entre les système de types sans contexte et leur pendant standard avec contexte explicite. Ces travaux jettent un pont entre deux lignées historiques d'assistants de preuves : la lignée issue de LCF à qui nous empruntons l'architecture du noyau, et celle issue de Automath, dont nous héritons la notion de types dépendants. <p> Les algorithmes présentés dans cette thèse sont au coeur d'un nouveau vérificateur de preuves appelé Dedukti et ont aussi été transférés vers un système plus mature : Coq. En collaboration avec Dénès, nous montrons comment étendre la NbE non typée pour gérer la syntaxe et les règles de réduction du calcul des constructions inductives (CIC). En collaboration avec Burel, nous généralisons des travaux précédents de Cousineau et Dowek (2007) sur l'encodage dans le λΠ-calcul modulo d'une large classe de PTS à des PTS avec types inductifs, motifs de filtrage et opérateurs de point fixe.

Modern software systems, in particular distributed ones, are everywhere around us and are at the basis of our everyday activities. Hence, guaranteeing their correctness, consistency and safety is of paramount importance. Their complexity makes the verification of such properties a very challenging task. It is natural to expect that these systems are reliable and above all usable. i) In order to be reliable, compositional models of software systems need to account for consistent dynamic reconfiguration, i.e., changing at runtime the communication patterns of a program. ii) In order to be useful, compositional models of software systems need to account for interaction, which can be seen as communication patterns among components which collaborate together to achieve a common task. The aim of the Ph.D. was to develop powerful techniques based on formal methods for the verification of correctness, consistency and safety properties related to dynamic reconfiguration and communication in complex distributed systems. In particular, static analysis techniques based on types and type systems appeared to be an adequate methodology, considering their success in guaranteeing not only basic safety properties, but also more sophisticated ones like, deadlock or livelock freedom in a concurrent setting. The main contributions of this dissertation are twofold. i) On the components side: we design types and a type system for a concurrent object-oriented calculus to statically ensure consistency of dynamic reconfigurations related to modifications of communication patterns in a program during execution time. ii) On the communication side: we study advanced safety properties related to communication in complex distributed systems like deadlock-freedom, livelock-freedom and progress. Most importantly, we exploit an encoding of types and terms of a typical distributed language, session π-calculus, into the standard typed π-calculus, in order to understand the expressive power of concurrent calculi with structured communication primitives and how they stand with respect to the standard typed concurrent calculi, namely (variants) of typed π-calculus. Then, we show how to derive in the session π-calculus basic properties, like type safety or complex ones, like progress, by encoding.

Certains environnements ont besoin de plusieurs compilateurs, par exemple un pour le système d'exploitation, supportant la norme C/C++ complète, et l'autre pour les applications, qui supporte éventuellement un sous-ensemble de la norme, mais capable de fournir plus de performance. Le maintien de plusieurs compilateurs pour une plateforme cible représente un effort considérable. Il est donc plus facile d'implémenter et de maintenir un seul outil responsable des optimisations particulières au processeur ciblé. Il nous faut alors un moyen de relier ces compilateurs à l'optimiseur, de préférence, en gardant au passage certaines structures de données internes aux compilateurs qui, soit prendraient du temps, soit seraient impossible à reconstruire à partir du code assembleur par exemple. Dans cette thèse, nous introduisons Tirex, une représentation textuelle intermédiaire pour échanger des informations de bas niveau, déjà dépendantes de la cible, entre les compilateurs, les optimiseurs et les autres outils de la chaîne de compilation. Notre représentation contient un flot d'instructions du processeur cible, mais garde également la structure explicite du programme et supporte la forme SSA (Static Single Assignment). Elle est facilement extensible et très flexible, ce qui permet de transmettre toute donnée jugée importante à l'optimiseur. Nous construisons Tirex par extension de MinIR, une représentation intermédiaire elle-même basée sur un encodage YAML des structures du compilateur. Nos extensions de Tirex comprennent: l'abaissement de la représentation au niveau du processeur cible, la conservation du flot de données du programme, ainsi que l'ajout d'informations sur les structures de boucles et les dépendances de données. Nous montrons que Tirex est polyvalent et peut être utilisé dans une variété d'applications différentes, comme par exemple un environnement d'exécution virtuel (VEE),et fournit une base forte pour un environnement d'analyse du programme. Dans le cadre d'un VEE, nous présentons un interprèteur de la forme SSA et un compilateur just-in-time (JIT). Nous montrons comment l'interprétation d'une représentation au niveau du processeur cible élimine la plupart des problèmes liés à l'exécution en mode mixte. Nous explorons également les questions liées à l'interprétation efficace d'une représentation de programme sous la forme SSA. / Some environments require several compilers, for instance one for the operating system, supporting the full C/C++ norm, and one for the applications, potentially supporting less but able to derive more performance. Maintaining different compilers for a target requires considerable effort, thus it is easier to implement and maintain target-dependent optimizations in a single, external tool. This requires a way of connecting these compilers with the target-dependent optimizer, preferably passing along some internal compiler data structures that would be time-consuming, difficult or even impossible to reconstruct from assembly language for instance. In this thesis we introduce Tirex, a Textual Intermediate Representation for EXchanging target-level information between compilers, optimizers an different tools in the compilation toolchain. Our intermediate representation contains an instruction stream of the target processor, but still keeps the explicit program structure and supports the SSA form(Static Single Assignment). It is easily extensible and highly flexible, which allows any data to be passed for the purpose of the optimizer. We build Tirex by extending the existing Minimalist Intermediate Representation (MinIR), itself expressed as a YAML textual encoding of compiler structures. Our extensions in Tirex include: lowering the representation to a target level, conserving the program data stream, adding loop scoped information and data dependencies. Tirex is currently produced by the Open64 and the LLVM compilers, with a GCC producer under work. It is consumed by the Linear Assembly Optimizer (LAO), a specialized, target-specific, code optimizer. We show that Tirex is versatile and can be used in a variety of different applications, such as a virtual execution environment (VEE), and provides strong basis for a program analysis framework. As part of the VEE, we present an interpreter for a Static Single Assignment (SSA) form and a just-in-time (JIT) compiler. We show how interpreting a target-level representation eliminates most of the complexities of mixed-mode execution. We also explore the issues related to efficiently interpreting a SSA form program representation.

La vérification déductive de programmes consiste à annoter des programmes par une spécification, c'est-à-dire un ensemble de formules logiques décrivant le comportement du programme, et à prouver que les programmes vérifient bien leur spécification. Des outils tels que la plate-forme Why prennent en entrée un programme et sa spécification et calculent des formules logiques telles que, si elles sont prouvées, le programme vérifie sa spécification. Ces formules logiques peuvent être prouvées automatiquement ou à l'aide d'assistants de preuve.Lorsqu'un programme est écrit dans un langage supportant les alias de pointeurs, c'est-à-dire si plusieurs variables peuvent désigner la même case mémoire, alors le raisonnement sur le programme devient particulièrement ardu. Il est nécessaire de spécifier quels pointeurs peuvent être égaux ou non. Les invariants des structures de données, en particulier, sont plus difficiles à vérifier.Cette thèse propose un système de type permettant de structurer la mémoire de façon modulaire afin de contrôler les alias de pointeurs et les invariants de données. Il est basé sur les notions de région et de permission. Les programmes sont ensuite interprétés vers Why de telle façon que les pointeurs soient séparés au mieux, facilitant ainsi le raisonnement. Cette thèse propose aussi un mécanisme d'inférence permettant d'alléger le travail d'annotation des opérations de régions introduites par le langage. Un modèle est introduit pour décrire la sémantique du langage et prouver sa sûreté. En particulier, il est prouvé que si le type d'un pointeur affirme que celui-ci vérifie son invariant, alors cet invariant est effectivement vérifié dans le modèle. Cette thèse a fait l'objet d'une implémentation sous la forme d'un outil nommé Capucine. Plusieurs exemples ont été écrits pour illustrer le langage, et ont été vérifié à l'aide de Capucine. / Deductive verification consists in annotating programs by a specification, i.e. logic formulas which describe the behavior of the program, and prove that programs verify their specification. Tools such as the Why platform take a program and its specification as input and compute logic formulas such that, if they are valid, the program verifies its specification. These logic formulas can be proven automatically or using proof assistants.When a program is written in a language supporting pointer aliasing, i.e. if several variables may denote the same memory cell, then reasoning about the program becomes particularly tricky. It is necessary to specify which pointers may or may not be equal. Invariants of data structures, in particular, are harder to maintain.This thesis proposes a type system which allows to structure the heap in a modular fashion in order to control pointer aliases and data invariants. It is based on the notions of region and permission. Programs are then translated to Why such that pointers are separated as best as possible, to facilitate reasoning. This thesis also proposes an inference mechanism to alleviate the need to write region operations introduced by the language. A model is introduced to describe the semantics of the language and prove its safety. In particular, it is proven that if the type of a pointer tells that its invariant holds, then this invariant indeed holds in the model. This work has been implemented as a tool named Capucine. Several examples have been written to illustrate the language, and where verified using Capucine.

Afin de prévoir les rendements ou réduire la consommation d’intrants nous pouvons, en exploitant les données expérimentales, créer des modèles mathématiques afin de simuler la croissance des cultures en fonction des caractéristiques de l’environnement. Dans cette optique, cette thèse s’intéresse particulièrement aux modèles dits ”mécanistes”.Des premières tentatives, dans les années 70, à nos jours, il y a eu pléthore de nouveaux modèles créés, à différentes échelles, afin d’étudier certains phénomènes dans les cultures ou au sein des plantes. On peut par exemple citer : CERES, STICS, APSIM, LNAS pour les modèles dits de culture ou LIGNUM, ADEL, GreenLab, MAppleT, pour les modèles dits structure-fonction.Ces modèles nécessitent d’être créés et évalués en conduisant une analyse rigoureuse possédant de nombreuses étapes et dont chacune est composée de plusieurs algorithmes complexes. Cette étude devrait s’inscrire dans une démarche dite de bonnes pratiques de modélisation, ”Good Modelling Practices”. On peut citer comme fonctionnalités : l’analyse de sensibilité, l’estimation paramétrique, l’analyse d’incertitude, l’assimilation de données, la sélection de modèles, le contrôle optimal ... En fonction de la configuration du cas, chacune de ces fonctionnalités peut faire appel à un grand nombre d’algorithmes avec chacun des caractéristiques propres. On retrouve dans l’état de l’art des plateformes qui s’occupent souvent d’une fonctionnalité mais très rarement qui s’attaquent à l’ensemble de la chaîne de travail.Cette thèse propose une formalisation des modèles dynamiques stochastiques (cadre adapté à la modélisation des plantes), de méthodes et algorithmes statistiques dédiés à leur étude et de l’interfaçage entre les modèles et les algorithmes dans cette chaîne de travail. Nous en déduisons la conception d’un système informatique (ou plateforme logicielle) permettant d’aider les modélisateurs, ou plutôt les équipes de modélisation tant l’activité est complexe et transverse, afin de créer et valider des modèles agronomiques par le truchement d’un langage dédié et d’outils statistiques associés. Le système facilite ainsi l’écriture des modèles, leur analyse de sensibilité, leur identification paramétrique et leur évaluation à partir de données expérimentales, leur optimisation. Notre domaine d’étude est au coeur de ”l’agronomie quantitative”, qui combine à la fois agronomie, modélisation, statistiques et informatique. Nous décrirons les types de modèles mathématiques pris en compte et comment nous les traduisons sur machine afin de permettre des simulations. Puis nous passerons en revue le flux de travail général ainsi que les algorithmes utilisés afin de montrer la conduite générale des études qui sont désormais plus facilement et rapidement faisables. Ce flux sera testé sur plusieurs cas d’étude, en particulier pour les modèles LNAS et STICS. Finalement, nous ouvrirons sur la possibilité d’injecter ces études dans une base de connaissance générale, ou ontologie, avec un langage dédié avant de conclure sur les perspectives du travail développé pour la communauté et notamment celles en termes de plateformes à destination des modélisateurs en général et des utilisateurs des modèles agronomiques en particulier. / In agriculture, in order to predict crop yield or to reduce inputs, mathematical models of plant growth open new perspectives by simulating crop growth in interaction with the environment. In this thesis we will particularly focus on ”mechanistic” models based on the description of ecophysiological and archictectural processes in plants.Since the first attempts, in the seventies, the scientific community has created a large number of models with va- rious objectives : for instance, CERES, STICS, APSIM, LNAS as crop models and LIGNUM, ADEL, GreenLab, MAppleT as functional-structural models.These models have to be designed and evaluated with a rigourous process in several steps, according to what is usually described as ”good modelling practices”. The methods involved in the different steps are : sensitivity and uncertainty analysis, parameter estimation, model selection, data assimilation, optimal control ... According to the configuration of the study case, various algorithms can be used at each of these steps. The state-of-the-art software systems generally focus on one aspect of the global workflow, but very few focus on the workflow itself and propose the whole chain of mathematical methodologies adapted to the type of models and configurations faced in plant growth modelling : stochastic and nonlinear dynamical models involving a lot of processes and parameters, heterogeneous and irregular system observations.This thesis considers the formalization of stochastic dynamical models, of statistical methods and algorithms dedicated to their study and of the interface between models and algorithms to generate the analysis workflow. We deduce the conception of a software platform which allows modelers (or more exactly modelling teams, since the activity is quite complex) to create and validate crop/plant models by using a single language and dedicated statistical tools. Our system facilitates model design, sensitivity and uncertainty analysis, parameter estimation and evaluation from experimental data and optimization.Our research is at the heart of ”quantitative agronomy” which combines agronomy, modeling, statistics and computer science. We describe and formalize the type of models faced in agronomy and plant sciences and how we simulate them. We detail the good modelling practices workflow and which algorithms are available at all steps. Thanks to this formalization and tools, model studies can be conducted in an easier and more efficient way. It is illustrated on several test cases, particularly for the LNAS and STICS models. Based on this conception and results, we also discuss the possibility to deduce an ontology and a domain-specific language in order to improve the communication between experts. Finally, we conclude about the perspectives in terms of community platforms, first generally for modellers, and second more specifically in quantitative agronomy.

Québec Université Laval, Bibliothèque 2016

Québec Université Laval, Bibliothèque 2015

La progression rapide de la technologie a donné lieu à un panorama riche et varié de dispositifs numériques : caméra, téléphones mobiles, GPS, tablettes tactiles, liseuses numériques, robots, télévisions, éléments de domotique... La majorité de ces appareils sont aujourd'hui connectés à Internet. Et en plus de leurs fonctionnalités principales, ils permettent à leur propriétaire de rester en contact avec " le monde " à l'aide de logiciels de communication, de personnages virtuels ou de robots. Tous ces dispositifs numériques fonctionnent indépendamment les uns des autres. La question qui se pose est de savoir si ces dispositifs numériques doivent être coordonnés afin de partager certaines informations et effectuer certaines actions ensembles. Cette collaboration entre les dispositifs numériques est gérée par le Compagnon Artificiel qui est en contact permanent avec un utilisateur par les biais des divers dispositifs numériques. Une architecture modulaire ArCo permettant de mettre en place un Compagnon Artificiel a été réalisée dans le cadre de ce travail. Les dispositifs numériques sont gérés par des modules spécifiques, créés grâce à un cadriciel MICE (Machines Interaction Control in their Environment). L'utilisateur final du système peut programmer des scenarii d'interaction, qui indiquent les actions que doivent effectuer les dispositifs numériques, grâce à une interface de programmation visuelle AmbiProg. Chaque scénario est interprété par un module AmbiLive. Les conflits d'accès aux dispositifs numériques sont gérés par un module AmbiCop. Un ensemble d'évaluations a permis de valider expérimentalement l'architecture ArCo et de répondre à des problématiques d'interaction homme-machine.

Tout le monde a déjà rencontré la fonctionnalité ``Undo/Redo' qui permet de se balader dans les versions précédentes d'un document. Bien que le versioning -- sauver et parcourir plusieurs versions d'entités données -- est nécessaire pour beaucoup d'applications, il est difficile de l'implémenter facilement et efficacement en temps et en espace utilisés. Dans cette thèse, nous présentons un système de versioning efficace et expressif pour les langages orientés objet. <p><p>Nous commencons par développer un modèle qui permet au développeur de sélectionner avec précision les parties intéressantes de son système qui seront sauvegardées à des moments clefs. Ce modèle permet de parcourir facilement les différentes versions enregistrées et de faire cohabiter aisément les parties versionnées avec les parties non sélectionnées par le développeur. Ce modèle est de plus compatible avec trois types de versioning (linear, backtracking et branching versioning) qui permettent des opérations diverses sur la ligne du temps, comme supprimer toutes les versions après une version donnée ou créer une nouvelle branche à partir d'une ancienne version. <p><p>Ensuite nous développons les structures efficaces en temps et en espace qui implémentent ce modèle dans un monde réel. Basées sur les travaux de Driscoll et al. elles sont adaptées aux spécificités de chaque type de versioning. <p><p>Nous montrons ensuite comment ce système peut être intégré concrètement dans un langage orienté object. Plus précisément, nous montrons comment notre système peut être intégré de façon transparente pour le développeur grâce à des outils tels que les aspects ou la transformation de bytecodes. <p><p>Pour valider nos propos, nous avons implémenté notre système dans les langages de programmation Smalltalk et Java. Nous montrons des applications réelles qui l'utilisent, telles que les post-conditions à états et le problème du planar point location. <p><p>Nous terminons cette thèse par évaluer l'efficacité de notre implémentation en effectuant des benchmarks détaillés en Smalltalk et en Java. Nous avons notamment étudié l'espace pris par nos structures données et le temps d'éxecution de chaque opération de versioning. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished