Global ETD Search

21	Développement systématique et sûreté d’exécution en programmation parallèle structurée / Systematic development and safety of execution in structured parallel programming Gesbert, Louis 05 March 2009 (has links) Exprimer le parallélisme dans la programmation de manière simple et performante est un défi auquel l'informatique fait face, en raison de l'évolution actuelle des architectures matérielles. BSML est un langage permettant une programmation parallèle de haut niveau, structurée, qui participe à cette recherche. En s'appuyant sur le coeur du langage existant, cette thèse propose d'une part des extensions qui en font un langage plus général et plus simple (traits impératifs tels que références et exceptions, syntaxe spécifique...) tout en conservant et étendant sa sûreté (sémantiques formelles, système de types...) et d'autre part une méthodologie de développement d'applications parallèles certifiées / Finding a good paradigm to represent parallel programming in a simple and efficient way is a challenge currently faced by computer science research, mainly due to the evolution of machine architectures towards multi-core processors. BSML is a high level, structured parallel programming language that takes part in the research in an original way. By building upon existing work, this thesis extends the language and makes it more general, simple and usable with added imperative features such as references and exceptions, a specific syntax, etc. The existing formal and safety characteristics of the language (semantics, type system...) are preserved and extended. A major application is given in the form of a methodology for the development of fully proved parallel programs Parallélisme Programmation de haut niveau Programmation fonctionnelle Sémantique Sûreté des langages Preuves de programmes Typage BSP Parallelism High level programming Functional programmins Semantics Safety of programs Program proofs Type systems BSP
22	A synchronous functional language with integer clocks / Un langage synchrone fonctionnel avec horloges entières Guatto, Adrien 07 January 2016 (has links) Cette thèse traite de la conception et implémentationd’un langage de programmation pour les systèmes detraitement de flux en temps réel, comme l’encodagevidéo. Le modèle des réseaux de Kahn est bien adaptéà ce domaine et y est couramment utilisé. Dans cemodèle, un programme consiste en un ensemble deprocessus parallèles communicant à travers des filesmono-producteur, mono-consommateur. La force dumodèle réside en son déterminisme.Les langages synchrones fonctionnels comme Lustresont dédiés aux systèmes embarqués critiques. Un programmeLustre définit un réseau de Kahn synchronequi peut être exécuté avec des files bornées et sans blocage.Cette propriété est garantie par un système detypes dédié, le calcul d’horloge, qui établit une échellede temps globale à un programme. Cette échelle detemps globale est utilisée pour définir les horloges, sé-quences booléennes indiquant pour chaque file, et àchaque pas de temps, si un processus produit ou consommeune donnée. Cette information sert non seulementà assurer la synchronie mais également à générerdu logiciel ou matériel à état fini.Nous proposons et étudions les horloges entières, unegénéralisation des horloges booléennes autorisant desentiers naturels arbitrairement grands. Les horlogesentières décrivent la production ou consommation deplusieurs valeurs depuis une même file au cours d’uninstant. Nous les utilisons pour définir la constructiond’échelle de temps locale, qui peut masquer despas de temps cachés par un sous-programme au contexteenglobant.Ces principes sont intégrés à un calcul d’horloge pourun langage fonctionnel d’ordre supérieur. Nous étudionsses propriétés et prouvons en particulier que lesprogrammes bien typés ne bloquent pas. Nous compilonsles programmes typés vers des circuits numériquessynchrones en adaptant le schéma de générationde code dirigé par les horloges de Lustre. L’informationde typage contrôle certains compromis entre temps etespace dans les circuits générés. / This thesis addresses the design and implementationof a programming language for real-time streaming applications,such as video decoding. The model of Kahnprocess networks is a natural fit for this area and hasbeen used extensively. In this model, a program consistsin a set of parallel processes communicating via singlereader, single writer queues. The strength of the modellies in its determinism.Synchronous functional languages such as Lustre arededicated to critical embedded systems. A Lustre programdefines a synchronous Kahn process network, thatis, which can be executed using finite queues and withoutdeadlocks. This is enforced by a dedicated type system,the clock calculus, which establishes a global timescale throughout a program. The global time scale isused to define clocks: per-queue boolean sequences indicating,for each time step, whether a process producesor consumes a token in the queue. This information isused both for enforcing synchrony and for generatingfinite-state software or hardware.We propose and study integer clocks, a generalizationof boolean clocks featuring arbitrarily big natural numbers.Integer clocks model the production or consumptionof several values from the same queue in the courseof a time step. We then rely on integer clocks to definethe local time scale construction, which may hide timesteps performed by a sub-program from the surroundingcontext.These principles are integrated into a clock calculus fora higher-order functional language. We study its properties,proving among other results that well-typed programsdo not deadlock. We adjust the clock-directedcode generation scheme of Lustre to generate finite-statedigital synchronous circuits from typed programs. Thetyping information controls certain trade-offs betweentime and space in the generated circuits. Langages de programmation fonctionnels Langages de programmation synchrones Systèmes de types Compilation Circuits numériques synchrones Functional programming languages Synchronous programming languages Type systems Compilation Digital synchronous circuits 004
23	Metaprogramming Program Analyzers Guannan Wei (16650384) 28 July 2023 (has links) <p>Static program analyzers are vital tools to produce useful insights about programs without executing these programs. These insights can be used to improve the quality of programs, e.g., detecting defects in programs, or optimizing programs to use fewer resources. However, building static program analyzers that are simultaneously sound, performant, and flexible is notoriously challenging.</p> <p>This dissertation aims to address this challenge by exploring the potential of applying correct-by-construction metaprogramming techniques to build static program analyzers. Metaprogramming techniques manipulate and transform programs as data objects. In this thesis, we consider static program analyzers as the objects to be manipulated or transformed. We show that metaprogramming techniques can improve our understanding, the construction, flexibility, and performance of program analyzers.</p> <p>We first study the inter-derivation of abstract interpreters. Using off-the-shelf program transformation techniques such as refunctionalization, we demonstrate that big-step abstract interpreters can be mechanically derived from their small-step counterparts, thus building a functional correspondence between two different styles of abstract interpretation.</p> <p>To build high-performance program analyzers, we exploit the first Futamura projection to build compilers for abstract interpretation and symbolic execution. The first Futamura projection states that specializing an interpreter with respect to an input program is a process equivalent to compilation, thus providing a practical way to repurpose interpreters for compilation and code generation. We systematically apply this idea to build program-analysis compilers by writing analyzers as staged interpreters using higher-level abstractions. The staged interpreter can be used for generating sound and performant analysis code given a specific input program. Moreover, the approach enables using abstractions without regret: by using higher-level program abstractions, the analyzer can be written in a way that is close to its high-level specification (e.g. big-step operational semantics), and by compilation, the analyzer is performant since it does not need to pay the runtime overhead of using these abstraction mechanisms.</p> <p>We also develop novel type systems that track sharing and separation in higher-order imperative languages. Such type systems are useful both for general-purpose programming languages and for optimization of domain-specific metaprograms such as those program-analysis compilers.</p> <p><br></p> Automated software engineering Programming languages Metaprogramming Static Analysis Tools Type systems Compilers & Tools Interpreters (Computer programs) Symbolic Execution Abstract Interpretation Code Generation
24	Solutions de rang k et invariants de Riemann pour les systèmes de type hydrodynamique multidimensionnels Huard, Benoit 10 1900 (has links) Dans ce travail, nous adaptons la méthode des symétries conditionnelles afin de construire des solutions exprimées en termes des invariants de Riemann. Dans ce contexte, nous considérons des systèmes non elliptiques quasilinéaires homogènes (de type hydrodynamique) du premier ordre d'équations aux dérivées partielles multidimensionnelles. Nous décrivons en détail les conditions nécessaires et suffisantes pour garantir l'existence locale de ce type de solution. Nous étudions les relations entre la structure des éléments intégraux et la possibilité de construire certaines classes de solutions de rang k. Ces classes de solutions incluent les superpositions non linéaires d'ondes de Riemann ainsi que les solutions multisolitoniques. Nous généralisons cette méthode aux systèmes non homogènes quasilinéaires et non elliptiques du premier ordre. Ces méthodes sont appliquées aux équations de la dynamique des fluides en (3+1) dimensions modélisant le flot d'un fluide isentropique. De nouvelles classes de solutions de rang 2 et 3 sont construites et elles incluent des solutions double- et triple-solitoniques. De nouveaux phénomènes non linéaires et linéaires sont établis pour la superposition des ondes de Riemann. Finalement, nous discutons de certains aspects concernant la construction de solutions de rang 2 pour l'équation de Kadomtsev-Petviashvili sans dispersion. / In this work, the conditional symmetry method is adapted in order to construct solutions expressed in terms of Riemann invariants. Nonelliptic quasilinear homogeneous systems of multidimensional partial differential equations of hydrodynamic type are considered. A detailed description of the necessary and sufficient conditions for the local existence of these types of solutions is given. The relationship between the structure of integral elements and the possibility of constructing certain classes of rank-k solutions is discussed. These classes of solutions include nonlinear superpositions of Riemann waves and multisolitonic solutions. This approach is generalized to first-order inhomogeneous hyperbolic quasilinear systems. These methods are applied to the equations describing an isentropic fluid flow in (3+1) dimensions. Several new classes of rank-2 and rank-3 solutions are obtained which contain double and triple solitonic solutions. New nonlinear and linear superpositions of Riemann waves are described. Finally, certain aspects of the construction of rank-2 solutions through an application to the dispersionless Kadomtsev-Petviashvili equation are discussed. Invariants de Riemann Riemann invariants Systèmes de type hydrodynamique Hydrodynamic type systems Méthodes de réductions par symétries Symmetry methods Symétries conditionelles Conditional symmetries Solutions de rang k Rank-k solutions
25	Solutions de rang k et invariants de Riemann pour les systèmes de type hydrodynamique multidimensionnels Huard, Benoit 10 1900 (has links) Dans ce travail, nous adaptons la méthode des symétries conditionnelles afin de construire des solutions exprimées en termes des invariants de Riemann. Dans ce contexte, nous considérons des systèmes non elliptiques quasilinéaires homogènes (de type hydrodynamique) du premier ordre d'équations aux dérivées partielles multidimensionnelles. Nous décrivons en détail les conditions nécessaires et suffisantes pour garantir l'existence locale de ce type de solution. Nous étudions les relations entre la structure des éléments intégraux et la possibilité de construire certaines classes de solutions de rang k. Ces classes de solutions incluent les superpositions non linéaires d'ondes de Riemann ainsi que les solutions multisolitoniques. Nous généralisons cette méthode aux systèmes non homogènes quasilinéaires et non elliptiques du premier ordre. Ces méthodes sont appliquées aux équations de la dynamique des fluides en (3+1) dimensions modélisant le flot d'un fluide isentropique. De nouvelles classes de solutions de rang 2 et 3 sont construites et elles incluent des solutions double- et triple-solitoniques. De nouveaux phénomènes non linéaires et linéaires sont établis pour la superposition des ondes de Riemann. Finalement, nous discutons de certains aspects concernant la construction de solutions de rang 2 pour l'équation de Kadomtsev-Petviashvili sans dispersion. / In this work, the conditional symmetry method is adapted in order to construct solutions expressed in terms of Riemann invariants. Nonelliptic quasilinear homogeneous systems of multidimensional partial differential equations of hydrodynamic type are considered. A detailed description of the necessary and sufficient conditions for the local existence of these types of solutions is given. The relationship between the structure of integral elements and the possibility of constructing certain classes of rank-k solutions is discussed. These classes of solutions include nonlinear superpositions of Riemann waves and multisolitonic solutions. This approach is generalized to first-order inhomogeneous hyperbolic quasilinear systems. These methods are applied to the equations describing an isentropic fluid flow in (3+1) dimensions. Several new classes of rank-2 and rank-3 solutions are obtained which contain double and triple solitonic solutions. New nonlinear and linear superpositions of Riemann waves are described. Finally, certain aspects of the construction of rank-2 solutions through an application to the dispersionless Kadomtsev-Petviashvili equation are discussed. Invariants de Riemann Riemann invariants Systèmes de type hydrodynamique Hydrodynamic type systems Méthodes de réductions par symétries Symmetry methods Symétries conditionelles Conditional symmetries Solutions de rang k Rank-k solutions
26	Vortices, Painlevé integrability and projective geometry Contatto, Felipe January 2018 (has links) GaugThe first half of the thesis concerns Abelian vortices and Yang-Mills theory. It is proved that the 5 types of vortices recently proposed by Manton are actually symmetry reductions of (anti-)self-dual Yang-Mills equations with suitable gauge groups and symmetry groups acting as isometries in a 4-manifold. As a consequence, the twistor integrability results of such vortices can be derived. It is presented a natural definition of their kinetic energy and thus the metric of the moduli space was calculated by the Samols' localisation method. Then, a modified version of the Abelian–Higgs model is proposed in such a way that spontaneous symmetry breaking and the Bogomolny argument still hold. The Painlevé test, when applied to its soliton equations, reveals a complete list of its integrable cases. The corresponding solutions are given in terms of third Painlevé transcendents and can be interpreted as original vortices on surfaces with conical singularity. The last two chapters present the following results in projective differential geometry and Hamiltonians of hydrodynamic-type systems. It is shown that the projective structures defined by the Painlevé equations are not metrisable unless either the corresponding equations admit first integrals quadratic in first derivatives or they define projectively flat structures. The corresponding first integrals can be derived from Killing vectors associated to the metrics that solve the metrisability problem. Secondly, it is given a complete set of necessary and sufficient conditions for an arbitrary affine connection in 2D to admit, locally, 0, 1, 2 or 3 Killing forms. These conditions are tensorial and simpler than the ones in previous literature. By defining suitable affine connections, it is shown that the problem of existence of Killing forms is equivalent to the conditions of the existence of Hamiltonian structures for hydrodynamic-type systems of two components.
27	Réalisabilité et paramétricité dans les systèmes de types purs / Realizability and parametricity in Pure Type Systems Lasson, Marc 20 November 2012 (has links) Cette thèse porte sur l’adaptation de la réalisabilité et la paramétricité au cas des types dépendants dans le cadre des Systèmes de Types Purs. Nous décrivons une méthode systématique pour construire une logique à partir d’un langage de programmation, tous deux décrits comme des systèmes de types purs. Cette logique fournit des formules pour exprimer des propriétés des programmes et elle offre un cadre formel adéquat pour développer une théorie de la réalisabilité au sein de laquelle les réalisateurs des formules sont exactement les programmes du langage de départ. Notre cadre permet alors de considérer les théorèmes de représentation pour le système T de Gödel et le système F de Girard comme deux instances d'un théorème plus général.Puis, nous expliquons comment les relations logiques de la théorie de la paramétricité peuvent s'exprimer en terme de réalisabilité, ce qui montre que la logique engendrée fournit un cadre adéquat pour développer une théorie de la paramétricité du langage de départ. Pour finir, nous montrons comment cette théorie de la paramétricité peut-être adaptée au système sous-jacent à l'assistant de preuve Coq et nous donnons un exemple d'application original de la paramétricité à la formalisation des mathématiques. / This thesis focuses on the adaptation of realizability and parametricity to dependent types in the framework of Pure Type Systems. We describe a systematic method to build a logic from a programming language, both described as pure type systems. This logic provides formulas to express properties of programs and offers a formal framework that allows us to develop a theory of realizability in which realizers of formulas are exactly programs of the starting programming language. In our framework, the standard representation theorems of Gödel's system T and Girard's system F may be seen as two instances of a more general theorem. Then, we explain how the so-called « logical relations » of parametricity theory may be expressed in terms of realizability, which shows that the generated logic provides an adequate framework for developping a general theory of parametricity. Finally, we show how this parametricity theory can be adapted to the underlying type system of the proof assistant Coq and we give an original example of application of parametricity theory to the formalization of mathematics. Réalisabilité Paramétricité Relation logique Systèmes de types purs Types dépendants Théorie des types Isomorphisme de curry-howard Lambda-calcul Calcul des constructions Coq Assistants de preuve Realizability Parametricity Logical relation Pure type systems Dependant type Type theory Curry-howard isomoprhism Lambda-calculus Calculus of constructions Coq Proof assistants
28	Programming tools for intelligent systems Considine, Breandan 04 1900 (has links) Les outils de programmation sont des programmes informatiques qui aident les humains à programmer des ordinateurs. Les outils sont de toutes formes et tailles, par exemple les éditeurs, les compilateurs, les débogueurs et les profileurs. Chacun de ces outils facilite une tâche principale dans le flux de travail de programmation qui consomme des ressources cognitives lorsqu’il est effectué manuellement. Dans cette thèse, nous explorons plusieurs outils qui facilitent le processus de construction de systèmes intelligents et qui réduisent l’effort cognitif requis pour concevoir, développer, tester et déployer des systèmes logiciels intelligents. Tout d’abord, nous introduisons un environnement de développement intégré (EDI) pour la programmation d’applications Robot Operating System (ROS), appelé Hatchery (Chapter 2). Deuxièmement, nous décrivons Kotlin∇, un système de langage et de type pour la programmation différenciable, un paradigme émergent dans l’apprentissage automatique (Chapter 3). Troisièmement, nous proposons un nouvel algorithme pour tester automatiquement les programmes différenciables, en nous inspirant des techniques de tests contradictoires et métamorphiques (Chapter 4), et démontrons son efficacité empirique dans le cadre de la régression. Quatrièmement, nous explorons une infrastructure de conteneurs basée sur Docker, qui permet un déploiement reproductible des applications ROS sur la plateforme Duckietown (Chapter 5). Enfin, nous réfléchissons à l’état actuel des outils de programmation pour ces applications et spéculons à quoi pourrait ressembler la programmation de systèmes intelligents à l’avenir (Chapter 6). / Programming tools are computer programs which help humans program computers. Tools come in all shapes and forms, from editors and compilers to debuggers and profilers. Each of these tools facilitates a core task in the programming workflow which consumes cognitive resources when performed manually. In this thesis, we explore several tools that facilitate the process of building intelligent systems, and which reduce the cognitive effort required to design, develop, test and deploy intelligent software systems. First, we introduce an integrated development environment (IDE) for programming Robot Operating System (ROS) applications, called Hatchery (Chapter 2). Second, we describe Kotlin∇, a language and type system for differentiable programming, an emerging paradigm in machine learning (Chapter 3). Third, we propose a new algorithm for automatically testing differentiable programs, drawing inspiration from techniques in adversarial and metamorphic testing (Chapter 4), and demonstrate its empirical efficiency in the regression setting. Fourth, we explore a container infrastructure based on Docker, which enables reproducible deployment of ROS applications on the Duckietown platform (Chapter 5). Finally, we reflect on the current state of programming tools for these applications and speculate what intelligent systems programming might look like in the future (Chapter 6). Kotlin Docker Génie logiciel Software engineering Apprentissage automatique Machine learning Mathématiques appliquées Applied mathematics Langages de programmation Programming languages Outils de programmation Programming tools Systèmes de type Type systems Différenciation automatique Automatic differentiation Tests automatisés Automated testing Systémes embarqués Embedded systems Systèmes intelligents Intelligent systems Machines virtuelles Virtual machines ROS Metamorphic testing Programmation différenciable Differentiable programming Programmation probabiliste Probabilistic programming Programmation fonctionnelle Functional programming Compilateurs Compilers Generative modeling Modélisation générative Rétropropagation Backpropagation Fuzzing Test métamorphique Test de propriété Metamorphic testing Property-based testing Analyse statique Static analysis Moteur de production Build automation Intégration continue Continuous integration

Search results