153 research outputs found
A Modal Analysis of Metaprogramming, Revisited (Invited Talk)
No full textMetaprogramming is the art of writing programs that produce or manipulate other programs. This opens the possibility to eliminate boilerplate code and exploit domain-specific knowledge to build high-performance programs. Unfortunately, designing language extensions to support type-safe multi-staged metaprogramming remains very challenging.
In this talk, we outline a modal type-theoretic foundation for multi-staged metaprogramming which supports the generation and the analysis of polymorphic code. It has two main ingredients: first, we exploit contextual modal types to describe open code together with the context in which it is meaningful; second, we model code as a higher-order abstract syntax (HOAS) tree within a context. These two ideas provide the appropriate abstractions for both generating and pattern matching on open code without committing to a concrete representation of variable binding and contexts.
Our work is a first step towards building a general type-theoretic foundation for multi-staged metaprogramming which on the one hand enforces strong type guarantees and on the other hand makes it easy to generate and manipulate code. This will allow us to exploit the full potential of metaprogramming without sacrificing reliability of and trust in the code we are producing and running
Mechanizing Meta-Theory in Beluga (Invited Talk)
No full textMechanizing formal systems, given via axioms and inference rules, together with proofs about them plays an important role in establishing trust in formal developments. In this talk, I will survey the proof environment Beluga. To specify formal systems and represent derivations within them, Beluga provides a sophisticated infrastructure based on the logical framework LF; in particular, its infrastructure not only supports modelling binders via binders in LF, but extends and generalizes LF with first-class contexts to abstract over a set of assumptions, contextual objects to model derivations that depend on assumptions, and first-class simultaneous substitutions to relate contexts. These extensions allow us to directly support key and common concepts that frequently arise when describing formal systems and derivations within them.
To reason about formal systems, Beluga provides a dependently typed functional language for implementing inductive proofs about derivations as recursive functions on contextual objects following the Curry-Howard isomorphism. Recently, the Beluga system has also been extended with a totality checker which guarantees that recursive programs are well-founded and correspond to inductive proofs and an interactive program development environment to support incremental proof / program construction. Taken together these extensions enable direct and compact mechanizations. To demonstrate Beluga's strength, we develop a weak normalization proof using logical relations. The Beluga system together with examples is available from http://complogic.cs.mcgill.ca/beluga
Front Matter, Table of Contents, Preface, Steering Committee, Program Committee, External Reviewers, Organising Commitee
No full textFront Matter, Table of Contents, Preface, Steering Committee, Program Committee, External Reviewers, Organising Commite
Functional Programming With Higher-order Abstract Syntax and Explicit Substitutions
No full textAbstractThis paper sketches a foundation for programming with higher-order abstract syntax and explicit substitutions based on contextual modal type theory [Aleksandar Nanevski, Frank Pfenning, and Brigitte Pientka. Contextual modal type theory. submitted, 2005]. Contextual modal types not only allows us to cleanly separate the representation of data objects from computation, but allow us to recurse over data objects with free variables. In this paper, we extend these ideas even further by adding first-class contexts and substitutions so that a program can pass and access code with free variables and an explicit environment, and link them in a type-safe manner. We sketch the static and operational semantics of this language, and give several examples which illustrate these features
Lincx: a linear logical framework with first-class contexts
No full textLinear logic provides an elegant framework for modelling stateful, imperative and con- current systems by viewing a context of assumptions as a set of resources. However, mech- anizing the meta-theory of such systems remains a challenge, as we need to manage and reason about mixed contexts of linear and intuitionistic assumptions. We present Lincx, a contextual linear logical framework with first-class mixed contexts. Lincx allows us to model (linear) abstract syntax trees as syntactic structures that may depend on intuitionistic and linear assumptions. It can also serve as a foundation for reasoning about such structures. Lincx extends the linear logical framework LLF with first-class (linear) contexts and an equational theory of context joins that can otherwise be very tedious and intricate to develop. This work may be also viewed as a generalization of contextual LF that supports both intuitionistic and linear variables, functions, and assumptions. We describe a decidable type-theoretic foundation for Lincx that only characterizes canonical forms and show that our equational theory of context joins is associative and commu- tative. Finally, we outline how Lincx may serve as a practical foundation for mechanizing the meta-theory of stateful systems.La logique linéaire represente une structure élégante pour modeler des systèmes im- pératifs, concurrents et avec des systèmes a états, en représentant un contexte d'hypothèses comme une collection de ressources. Cependant, la mécanisation de la métathéorie de ces systèmes demeure un défi, puisque nous devons gérer et raisonner à propos de contextes d'hypothèses mixtes linéaires et intuitionistiques. Nous présentons Lincx, une structure logique linéaire et contextuelle avec des contextes mixtes de première classe. Lincx nous permet d'établir des modèles (linéaires) d'arbres de syntaxe abstraits en tant que structures syntactiques qui peuvent dependre d'hypothèses intuitionistiques et linéaires. Lincx peut également servir de fondation pour raisonner à propos de telles structures. Lincx étend la structure logique linéaire LLF avec des contextes (linéaires) de premier ordre et une théorie d'equations d'assemblage de contextes qui peut autrement être très fastidieux et complexe à développer. Cet oeuvre peut également être perçu comme une généralisation du LF contextuel qui supporte les fonctions, les hypothéses et les variables intuitionistiques et linéaires. Nous décrivons une fondation de la théorie des types décidable pour Lincx qui ne décrit que les formes canoniques et montrons que notre theorie d'équations d'assemblage de contextes est associative et commutative. Finalement, nous donnons un aperçu de comment Lincx peut servir de fondation pratique pour la mécanisation de la métathéorie de systèmes à états
Verified Given Clause Procedures
No full textResolution and superposition provers rely on the given clause procedure to saturate clause sets. Using Isabelle/HOL, we formally verify four variants of the procedure: the well-known Otter and DISCOUNT loops as well as the newer iProver and Zipperposition loops. For each of the variants, we show that the procedure guarantees saturation, given a fair data structure to store the formulas that wait to be selected. Our formalization of the Zipperposition loop clarifies some fine points previously misunderstood in the literature
Well-Founded Recursion over Contextual Objects
No full textWe present a core programming language that supports writing well-founded structurally recursive functions using simultaneous pattern matching on contextual LF objects and contexts. The main technical tool is a coverage checking algorithm that also generates valid recursive calls. To establish consistency, we define a call-by-value small-step semantics and prove that every well-typed program terminates using a reducibility semantics. Based on the presented methodology we have implemented a totality checker as part of the programming and proof environment Beluga where it can be used to establish that a total Beluga program corresponds to a proof
Index-Stratified Types
No full textWe present Tores, a core language for encoding metatheoretic proofs. The novel features we introduce are well-founded Mendler-style (co)recursion over indexed data types and a form of recursion over objects in the index language to build new types. The latter, which we call index-stratified types, are analogue to the concept of large elimination in dependently typed languages. These features combined allow us to encode sophisticated case studies such as normalization for lambda calculi and normalization by evaluation. We prove the soundness of Tores as a programming and proof language via the key theorems of subject reduction and termination
Relating System F and Lambda2: A Case Study in Coq, Abella and Beluga
No full textWe give three formalisations of a proof of the equivalence of the usual, two-sorted presentation of System F and its single-sorted pure type system (PTS) variant Lambda2. This is established by reducing the typability problem of F to Lambda2 and vice versa. A key challenge is the treatment of variable binding and contextual information. The formalisations all share the same high level proof structure using relations to connect the type systems. They do, however, differ significantly in their representation and manipulation of variables and contextual information. In Coq, we use pure de Bruijn indices and parallel substitutions. In Abella, we use higher-order abstract syntax (HOAS) and nominal constants of the ambient reasoning logic. In Beluga, we also use HOAS but within contextual modal type theory. Our contribution is twofold. First, we present and compare a collection of machine-checked solutions to a non-trivial theoretical result. Second, we propose our proof as a benchmark, complementing the POPLmark and ORBI challenges by testing how well a given proof assistant or framework handles complex contextual information involving multiple type systems
- …
