-
Chapter
Counting Successes: Effects and Transformations for Non-deterministic Programs
We give a simple effect system for non-deterministic programs, tracking static approximations to the number of results that may be produced by each computation. A relational semantics for the effect system est...
-
Chapter and Conference Paper
The Proof Assistant as an Integrated Development Environment
We discuss the potential of doing program development, code generation, application-specific modelling, and verification entirely within a proof assistant.
-
Chapter and Conference Paper
Proof-Relevant Logical Relations for Name Generation
Pitts and Stark’s ν-calculus is a paradigmatic total language for studying the problem of contextual equivalence in higher-order languages with name generation. Models for the ν-calculus that validate basic equiv...
-
Article
Strongly Typed Term Representations in Coq
There are two approaches to formalizing the syntax of typed object languages in a proof assistant or programming language. The extrinsic approach is to first define a type that encodes untyped object expressions ...
-
Chapter and Conference Paper
Adding Equations to System F Types
We present an extension of System F with types for term-level equations. This internalization of the rich equational theory of the polymorphic lambda calculus yields an expressive core language, suitable for f...
-
Chapter and Conference Paper
Some Domain Theory and Denotational Semantics in Coq
We present a Coq formalization of constructive ω-cpos (extending earlier work by Paulin-Mohring) up to and including the inverse-limit construction of solutions to mixed-variance recursive domain equations, and t...
-
Chapter and Conference Paper
Undoing Dynamic Ty** (Declarative Pearl)
We propose undoable versions of the projection operations used when programs written in higher-order statically-typed languages interoperate with dynamically typed ones, localizing potential runtime errors to ...
-
Chapter and Conference Paper
Abstracting Allocation
We introduce a Floyd-Hoare-style framework for specification and verification of machine code programs, based on relational parametricity (rather than unary predicates) and using both step-indexing and a novel...
-
Chapter and Conference Paper
Reading, Writing and Relations
We give an elementary semantics to an effect system, tracking read and write effects by using relations over a standard extensional semantics for the original language. The semantics establishes the soundness ...
-
Chapter and Conference Paper
Shrinking Reductions in SML.NET
One performance-critical phase in the SML.NET compiler involves rewriting intermediate terms to monadic normal form and performing non-duplicating β-reductions. We present an imperative algorithm for this simplif...
-
Chapter and Conference Paper
A Typed, Compositional Logic for a Stack-Based Abstract Machine
We define a compositional program logic in the style of Floyd and Hoare for a simple, typed, stack-based abstract machine with unstructured control flow, global variables and mutually recursive procedure calls...
-
Chapter and Conference Paper
Relational Reasoning in a Nominal Semantics for Storage
We give a monadic semantics in the category of FM-cpos to a higher-order CBV language with recursion and dynamically allocated mutable references that may store both ground data and the addresses of other refe...
-
Chapter and Conference Paper
Modern Concurrency Abstractions for C#
Polyphonic C# is an extension of the C# language with new asynchronous concurrency constructs, based on the join calculus. We describe the design and implementation of the language and give examples of its use in...
-
Chapter and Conference Paper
Monads and Effects
A tension in language design has been between simple semantics on the one hand, and rich possibilities for side-effects, exception handling and so on on the other. The introduction of monads has made a large s...
-
Chapter and Conference Paper
A term calculus for Intuitionistic Linear Logic
In this paper we consider the problem of deriving a term assignment system for Girard's Intuitionistic Linear Logic for both the sequent calculus and natural deduction proof systems. Our system differs from pr...
-
Chapter and Conference Paper
Linear λ-calculus and categorical models revisited
