Invited talks

Gilles Barthe. Computer-aided cryptography

Abstract: The goal of computer-aided cryptography is to develop tools that help the rigorous design and analysis of cryptographic constructions. Over the years, the focus of computer-aided cryptography has expanded from analysis of cryptographic protocols in the symbolic model to include new goals. Most notably, these goals include analyzing cryptographic primitives and protocols in the computational model, and reasoning about implementations. In this talk, I will illustrate how existing techniques from program verification and program synthesis can be used for achieving a number of goals in computer-aided cryptography.

Andrej Bauer. The troublesome reflection rule

Abstract: The equality reflection rule states that propositionally equal terms are judgmentally equal. It is generally frowned upon, as it makes type checking undecidable. Nevertheless, it would be useful to have a workable implementation of a type theory with equality reflection, for instance to tackle Voevodsky's Homotopy Type System. The difficulties created by equality reflection are numerous. It destroys the structural rules of exchange and strengthening, η-reductions cannot be performed without explicit typing annotations in the terms, and injectivity of type constructors becomes an unreasonable expectation. In the talk I shall discuss the design and implementation of a type theory with reflection which works around these complications, while still being a useful tool.

Peter Selinger. Types for quantum computing

Abstract: Static type systems are meant to guarantee the absence of certain run-time errors. Quantum computing comes with new kinds of run-time errors, for example attempted violations of the no-cloning property of quantum mechanics. Therefore, quantum computing is potentially interesting from a type-theoretic point of view. In this talk, I will talk about the quantum lambda calculus, a strongly typed functional quantum programming language that has been around for about a decade, and Quipper, a more practical language that is currently implemented as a Haskell EDSL. I will outline some of the challenges involved in creating a type-safe version of Quipper.


Joachim Kock. Polynomial functors: a general framework for induction and substitution

Abstract: The starting point for this tutorial will be the Seely correspondence between (extensional) dependent type theory and locally cartesian closed categories, such as the category of sets. Under this correspondence, polynomial functors provide semantics for generic data types, and their initial algebras provide semantics for W-types (wellfounded trees). While trees in this approach are defined inductively, it is also possible to define trees combinatorially, directly as certain multivariate polynomial endofunctors. This leads to an alternative characterisation of initial algebras, namely as operations for the free monad on a polynomial endofunctor. The monad itself has important structure not seen at the level of initial algebras, namely the monad multiplication, which always encodes a notion of substitution. I will finish with some outlook regarding the role of polynomial monads (which are essentially operads) to encode and manipulate combinatorial and algebraic structures, and the need for groupoids and higher groupoids to really unleash the power of this formalism -- also in intensional type theory.

Peter LeFanu Lumsdaine. Higher inductive types: what we understand, what we don't

Abstract: HITs were introduced in 2011, following the Oberwolfach mini-workshop on HoTT, as a rather speculative array of new type-constructors, essentially generalising inductive definitions to give (homotopically) higher-dimensional types in the most simple-minded way possible.

Four years later, where do we stand on them? I will survey what we now know about them (or at least, as much of that as I know).

Well-understood: logical consequences. One aspect has worked out as well as anyone could have hoped: their logical consequences within the theory. As mostly developed during the IAS special year, the conjunction of HITs and uxnivalence allows the "synthetic" redevelopment of much of classical abstract homotopy theory within type theory.

Moderately understood: semantics. The semantics has taken longer to get to grips with, but a reasonable understanding is now emerging. The rough ideas are clear, but technicalities related to stability and coherence remain more troublesome than one might expect.

Mike Shulman and I have given models of a restricted range of HITs in a reasonable range of homotopy-theoretic settings (including simplicial sets), using local universes (Lumsdaine, Warren 2015) to obtain stability. On the other hand, Thierry Coquand and collaborators (Bezem, Cohen, Huber, Norsberg) have given models of a wider range of HITs in the cubical set model; and these models are strictly stable by construction, so that the added overhead of local universes is not required.

Little-understood: proof theory. The proof-theoretic aspects of HITs, however, are quite unsatisfactorily understood. Most obviously, we still have no fully general scheme of higher inductive definitions (in the sense of, say, the general inductive definitions of the Calculus of Inductive Constructions). Moreover, even for simple higher inductive types, when taken with judgemental computation rules, we do not understand the effects on proof-theoretic properties such as normalisation, confluence, decidability of typing.

Interesting progress on these issues has appeared recently in the cubical type theories of Altenkirch, Brunerie, Coquand, Licata, and others.

Tarmo Uustalu
Last update 17 April 2015