In program analysis, unknown properties for terms are typically represented symbolically as variables. Bound constraints on these variables can then specify multiple optimisation goals for computer programs and nd application in areas such as type theory, security, alias analysis and resource reasoning. Resolution of bound constraints is a problem steeped in graph theory; interdependencies between the variables is represented as a constraint graph. Additionally, constants are introduced into the system as concrete bounds over these variables and constants themselves are ordered over a lattice which is, once again, represented as a graph. Despite graph algorithms being central to bound constraint solving, most approaches to program optimisation that use bound constraint solving have treated their graph theoretic foundations as a black box. Little has been done to investigate the computational costs or design e cient graph algorithms for constraint resolution. Emerging examples of these lattices and bound constraint graphs, particularly from the domain of language-based security, are showing that these graphs and lattices are structurally diverse and could be arbitrarily large. Therefore, there is a pressing need to investigate the graph theoretic foundations of bound constraint solving. In this thesis, we investigate the computational costs of bound constraint solving from a graph theoretic perspective for Information Flow Analysis (IFA); IFA is a sub- eld of language-based security which veri es whether con dentiality and integrity of classified information is preserved as it is manipulated by a program. We present a novel framework based on graph decomposition for solving the (atomic) bound constraint problem for IFA. Our approach enables us to abstract away from connections between individual vertices to those between sets of vertices in both the constraint graph and an accompanying security lattice which defines ordering over constants. Thereby, we are able to achieve significant speedups compared to state-of-the-art graph algorithms applied to bound constraint solving. More importantly, our algorithms are highly adaptive in nature and seamlessly adapt to the structure of the constraint graph and the lattice. The computational costs of our approach is a function of the latent scope of decomposition in the constraint graph and the lattice; therefore, we enjoy the fastest runtime for every point in the structure-spectrum of these graphs and lattices. While the techniques in this dissertation are developed with IFA in mind, they can be extended to other application of the bound constraints problem, such as type inference and program analysis frameworks which use annotated type systems, where constants are ordered over a lattice.

Esta dissertação estabelece a incompletude de um sistema formal cujas únicas constantes não-lógicas são 0 e s (respectivamente, o número natural 0 e a função sucessor segundo a interpretação standard), fundamentando-se, para tanto, em um teorema cuja prova necessita essencialmente da maquinária lógica de segunda-ordem e que foi designado de Teorema das Definições Recursivas. / We establish here the incompleteness of the formal system S2 for arithmetic_a formal system whose signature is {0, s}_by means of the Theorem of the Definition by Recursion (TDR). However, unlike the standard proofs of incompleteness, the proof of TDR, by virtue of restricted signature, uses essentially the power of second-order logic.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2014-10-13T19:12:35Z No. of bitstreams: 2 Dissertação - Bruno Rigonato Mundim - 2013.pdf: 1303876 bytes, checksum: 4f1bada6e1186d920d0d0bfcd28d47f1 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2014-10-13T20:49:48Z (GMT) No. of bitstreams: 2 Dissertação - Bruno Rigonato Mundim - 2013.pdf: 1303876 bytes, checksum: 4f1bada6e1186d920d0d0bfcd28d47f1 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-10-13T20:49:48Z (GMT). No. of bitstreams: 2 Dissertação - Bruno Rigonato Mundim - 2013.pdf: 1303876 bytes, checksum: 4f1bada6e1186d920d0d0bfcd28d47f1 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-09-02 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / By means of the Curry-Howard Correspondence Martin-Löf’s intuitionistic type theory claims that to define a proposition by laying down how its canonical proofs are formed is the same as to define a set by laying down how its canonical elements are formed; consequently a proposition can be seen as the set of its proofs. On the other hand, we find in this very same theory a distinction between the notions of set and of type, such that the difference of the latter in relation to the former consists in the fact that to form a type we do not need to present an exhaustive prescription for the formation of its objects; it is sufficient to just have a general notion of what would be an arbitrary object that inhabits such type. Thus we argue that we can extract two distinct notions of propositon from the intuitionistic type theory, one which treats propositions as types and another which treats propositions as sets. Such distinction will have some bearing on discussions concerning hypothetical demonstrations and conjecture’s formation. / A teoria intuicionista de tipos, de Martin-Löf, alega, à luz da correspondência Curry- Howard, que definir uma proposição por meio do estabelecimento de como as suas provas canônicas são formadas é o mesmo que definir um conjunto por meio do estabelecimento de como os seus elementos canônicos são formados, fazendo com que uma proposição possa ser vista como o conjunto de suas provas. Por outro lado, encontramos nessa mesma teoria uma distinção entre as noções de conjunto e tipo, sendo que a diferença deste em relação àquele consiste no fato de que para se formar um tipo não é preciso apresentar uma prescrição exaustiva da formação de seus objetos, basta se ter uma noção geral do que seria um objeto arbitrário que o habita. Tendo isso em conta, argumentamos que podemos extrair da teoria intuicionista de tipos duas concepções de proposição distintas, uma que considera proposições como tipos e outra que considera proposições como conjuntos. Tal distinção implicará em algumas considerações envolvendo questões sobre demonstrações hipotéticas e a formação de conjecturas.

Esta dissertação estabelece a incompletude de um sistema formal cujas únicas constantes não-lógicas são 0 e s (respectivamente, o número natural 0 e a função sucessor segundo a interpretação standard), fundamentando-se, para tanto, em um teorema cuja prova necessita essencialmente da maquinária lógica de segunda-ordem e que foi designado de Teorema das Definições Recursivas. / We establish here the incompleteness of the formal system S2 for arithmetic_a formal system whose signature is {0, s}_by means of the Theorem of the Definition by Recursion (TDR). However, unlike the standard proofs of incompleteness, the proof of TDR, by virtue of restricted signature, uses essentially the power of second-order logic.

Cette thèse traite deux problèmes concernant la théorie des représentations `-modulairesd’un groupe p-adique. Soit F un corps local non archimédien de caractéristique résiduelle pdifférente de `. Dans la première partie, on étudie la décomposition en blocs de la catégoriedes représentations lisses `-modulaires de GL(n; F) et de ses formes intérieures. On veutramener la description d’un bloc de niveau positif à celle d’un bloc de niveau 0 (d’un autregroupe du même type) en cherchant des équivalences de catégories. En utilisant la théoriedes types de Bushnell-Kutzko dans le cas modulaire et un théorème de la théorie descatégories, on se ramene à trouver un isomorphisme entre deux algèbres d’entrelacement.La preuve de l’existence d’un tel isomorphisme n’est pas complète car elle repose sur uneconjecture qu’on énonce et qui est prouvée pour plusieurs cas. Dans une deuxième partieon généralise la construction du groupe métaplectique et de la représentation de Weil dansle cas des représentations sur un anneau intègre. On construit une extension centrale dugroupe symplectique sur F par le groupe multiplicatif d’un anneau intègre et on prouvequ’il satisfait les mêmes propriétés que dans le cas des représentations complexes. / This thesis focuses on two problems on `-modular representation theory of p-adic groups.Let F be a non-archimedean local field of residue characteristic p different from `. In thefirst part, we study block decomposition of the category of smooth modular representationsof GL(n; F) and its inner forms.We want to reduce the description of a positive-levelblock to the description of a 0-level block (of a similar group) seeking equivalences of categories.Using the type theory of Bushnell-Kutzko in the modular case and a theorem ofcategory theory, we reduce the problem to find an isomorphism between two intertwiningalgebras. The proof of the existence of such an isomorphism is not complete because itrelies on a conjecture that we state and we prove for several cases. In the second part wegeneralize the construction of metaplectic group and Weil representation in the case ofrepresentations over un integral domain. We define a central extension of the symplecticgroup over F by the multiplicative group of an integral domain. We prove that it satisfiesthe same properties as in the complex case.

Cette thèse propose une repréesentation de la notion de type, avec un intérêt particulier pour les types d'ependants, en Ludique.La Ludique est une th'eorie introduite par Girard. Elle vient d'une fine analyse du fragment multiplicative, additive polarisé de la Logique Linéaire (MALL_p). Un des ses buts est de reconstruire la logique à partir de la notion d'intéraction. Un type est une classe d'objets qui se comportent de la m^eme fac{c}on par rapport aux autres objets. La notion de type est commune à plusieurs domaines comme la Théorie de la Calculabilité, la Sémantique des Jeux et la Théorie Intuitioniste de Types de Martin-Lof. Avec la terminologie de Martin-Lof, le termes canoniques d'un type sont les éléments primitives du type, c'est à dire les objets qui le caractérisent. Les termes non canoniques sont les termes obtenu appliquant une opération aux termes canoniques et une fois calculés donnent un terme canonique. Les termes sont vu comme des programmes et deux termes sont égaux quand leur calcul donne le même résultat, c'est à dire le même terme canonique. On introduit la notion de comportement principal, qui est bien adapté à la représentation des termes canoniques. On introduit aussi la notion de comportement séparable, qui nous donne un outil pour définir les fonctions de manière simple.On représente les nombres naturelles, les listes, les records, les fonctions dépendantes, les couples et on discutes les records dépendantes.On se focalise après sur la Théorie de Martin-Lof pour proposer une représentation de certaines types de base et constructions. / This thesis proposes a representation of the notion of type, with a particular interest on dependent types, in Ludics.Ludics is a theory introduced by Girard cite{LocSol}. It comes from a fine analysis of the multiplicative, additive fragment of polarized Linear Logic (MALL_p). One of its aim is to reconstruct logic from the notion of interaction. A type is a class of objects that behave in the same way with respect to other objects.The notion of type is common to several domains as Computation Theory, Game Semantics and Martin-Lof's Intuitionistic Type Theory.Using the terminology of Martin-Lof, the canonical terms of a type are the primitive elements of the type, that is the objects that characterize it. The non-canonical terms are the terms obtained by applying some operations on canonical terms and that once computed give a canonical term. Terms are seen as programs and two terms are equal when their computation gives the same result, that is the same canonical term.We introduce the notion of principal behaviour, that is well-suited to represent canonical terms. We introduce also the notion of separable behaviour, that gives us a tool to define functions in a simple way.We represent natural numbers, lists, records, dependent functions, pairs and discuss dependent record types. We focus then on Martin-Lof's Type Theory and propose a representation for some basic types and constructions.

Both dependent types and linear types have their desirable properties. Department types can express functional dependencies of inputs and outputs, while linear types offer control over the use of computational resources. Combining these two systems have been difficult because of their different interpretations of context presence of variables. Quantitative Type Theory (QTT) combines dependent types and linear types by using a semiring to track the kind of use of every resource. We extend QTT with the additive pair and additive unit types, express the complete QTT rules in bidirectional form, and then present our interpreter of a simple language based on QTT. 1

In programming languages, record types give a universe of discourse (via so-called Σ-types); parameterised record types fix parts of that universe ahead of time (via Π-types), and algebraic datatypes give us first-class syntax (via W-types), which can then be used to program, e.g., evaluators and optimisers. A frequently-encountered issue in library design for statically-typed languages is that, for example, the algebraic datatype implementing the first-class view of the language induced by a record declaration cannot be defined by simple reference to the record type declaration, nor to any common “source”. This leads to unwelcome repetition, and to maintenance burdens. Similarly, the “unbundling problem” concerns similar repetition that arises for variants of record types where some fields are turned into parameters. The goal of this thesis is to show how, in dependently-typed languages (DTLs), algebraic datatypes and parameterised record types can be obtained from a single pragmatic declaration within the dependently-typed language itself, without using a separate “module language”. Besides this practical shared declaration interface, which is extensible in the language, we also find that common data structures correspond to simple theories. Put simply, the thesis is about making tedious and inexpressible patterns of programming in DTLs (dependently typed languages) become mechanical and expressible. The situations described above occur frequently when working in a dependently-typed language, and it is reasonable enough to have the computer handle them. We develop a notion of contexts that serve as common source for definitions of algebraic datatype and of parameterised record types, and demonstrate a “language” of “package operations” that enables us to avoid the above-mentioned replication that pervades current library developments. On the one hand, we demonstrate an implementation of that language as integrated editor functionality — this makes it possible to directly emulate the different solutions that are employed in current library developments, and refactor these into a shape that uses single declaration of contexts, thus avoiding the usual repetition that is otherwise required for provision of record types at different levels of parameterisation and of algebraic datatypes. On the other hand, we will demonstrate that the power of dependently-typed languages is sufficient to implement such package operations in a statically-typed manner within the language; using this approach will require adapting to the accordingly-changed library interfaces. Although our development uses the dependently-typed programming language Agda throughout, we emphasise that the idea is sufficiently generic to be implemented in other DTLs. / Thesis / Doctor of Philosophy (PhD) / There are things we want to use from various perspectives, our tools show that this is possible without any duplication and in a practical and efficient fashion.

Prouver l’équivalence de programmes écrits dans un langage fonctionnel avec références est un problème notoirement difficile. L’objectif de cette thèse est de proposer un système logique dans lequel de telles preuves peuvent être formalisées, et dans certains cas inférées automatiquement. Dans la première partie, une méthode générique d’extension de la théorie des types dépendants est proposée, basée sur une interprétation du forcing vu comme une traduction de préfaisceaux de la théorie des types. Cette extension dote la théorie des types de constructions récursives gardées, qui sont utilisées ensuite pour raisonner sur les références d’ordre supérieure. Dans une deuxième partie, nous définissons une sémantique des jeux nominale opérationnelle pour un langage avec références d’ordre supérieur. Elle marie la structure catégorique de la sémantique des jeux avec une représentation sous forme de traces de la dénotation des programmes, qui se calcule de manière opérationnelle et dispose donc de bonnes propriétés de modularité. Cette sémantique nous permet ensuite de prouver la complétude de relations logiques à la Kripke définit de manière directe, via l’utilisation de types récursifs gardés, sans utilisation de la biorthogonalité. Une telle définition directe nécessite l’utilisation de mondes omniscient et un contrôle fin des locations divulguées. Finalement, nous introduisons une logique temporelle qui donne un cadre pour définir ces relations logiques à la Kripke. Nous ramenons alors le problème de l’équivalence contextuelle à la satisfiabilité d’une formule de cette logique générée automatique, c’est à dire à l’existence d’un monde validant cette formule. Sous certaines conditions, cette satisfiabilité peut être décidée via l’utilisation d’un solveur SMT. La complétude de notre méthode devrait permettre d’obtenir des résultats de décidabilité pour l’équivalence contextuelle de certains fragment du langage considéré, en fournissant un algorithme pour construire de tels mondes. / Proving program equivalence for a functional language with references is a notoriously difficult problem. The goal of this thesis is to propose a logical system in which such proofs can be formalized, and in some cases inferred automatically. In the first part, a generic extension method of dependent type theory is proposed, based on a forcing interpretation seen as a presheaf translation of type theory. This extension equips type theory with guarded recursive constructions, which are subsequently used to reason on higher-order references. In the second part, we define a nominal game semantics for a language with higher-order references. It marries the categorical structure of game semantics with a trace representation of denotations of programs, which can be computed operationally and thus have good modularity properties. Using this semantics, we can prove the completeness of Kripke logical relations defined in a direct way, using guarded recursive types, without using biorthogonality. Such a direct definition requires omniscient worlds and a fine control of disclosed locations. Finally, we introduce a temporal logic which gives a framework to define these Kripke logical relations. The problem of contextual equivalence is then reduced to the satisfiability of an automatically generated formula defined in this logic, i.e. to the existence of a world validating this formula. Under some conditions, this satisfiability can be decided using a SMT solver. Completeness of our methods opens the possibility of getting decidability results of contextual equivalence for some fragments of the language, by giving an algorithm to build such worlds.

This thesis represents an attempt to improve the state of the art in our ability tounderstand and check object protocols, with a particular emphasis on concurrent pro-grams. Object protocols are the patterns of use imposed on clients of APIs in object-oriented programs. We show through an empirical study of open-source object-oriented programs that object protocols are quite common. We then present “Sync-or-Swim,” a methodology and suite of accompanying tools for checking at compile-time that object protocols are used and implemented correctly. This methodology isbased upon the existing access permissions method of alias control, which is hereextended to be sound in the face of shared-memory concurrency. The analysis isformalized as a type system for an object-oriented calculus, and then proven to befree from false-negatives using a proof of type safety. The type system is extendedwith parametric polymorphism, or “generics,” in order to increase its ability to checkcommonly occurring patterns. An implementation of the approach, a static analysisfor programs written in the Java programming language, is presented. This imple-mentation was used to perform a series of case studies whose goal was to evaluatethe ease of use, expressiveness and ability to verify commonly occurring patterns.These case studies are presented. Next, an approach and an associated tool for in-ferring access permission annotations is presented. This inference tool can reducethe burden of using our protocol-checking approach by automatically inferring therequired typing annotations. This inference is built upon a system of probabilisticconstraints, which allows the easy encoding of heuristics. Finally, an optimization ofsoftware transactional memory runtimes is presented. This optimization is enabledby the typing annotations required to use the concurrent protocol checker and canremove some of the overhead typically associated with transactional memory sys-tems. As a result of the work presented in this thesis, it is possible to guarantee theabsence of certain API usage errors even in concurrent programs, and to do so witha low burden on programmers. By adhering to such an approach, programmers canproduce more reliable software.