# Posts in the category Type theory

### A general definition of dependent type theories

- 14 September 2020
- Publications, Type theory

The preprint version of the paper A general definition of dependent type
theories has finally appeared on the arXiv! Over three
years ago Peter Lumsdaine invited me to work on the
topic, which I gladly accepted, and dragged my student Philipp
Haselwarter into it. We set out to give *an* answer to
the queation:

What is type theory, precisely?

At least for me the motivation to work on such a thankless topic came from Vladimir
Voevodsky, who would ask the question to type-theoretic audiences. Some took him to be a
troll and others a newcomer who just had to learn more type theory. I was among the
latter, but eventually the question got through to me – I could point to any number of
*specific* examples of type theories, but not a comprehensive and mathematically precise
definition of the *general* concept.

It is too easy to dismiss the question by claiming that type theory is an open-ended concept which therefore cannot be completely captured by any mathematical definition. Of course it is open-ended, but it does not follow at all that we should not even attempt to define it. If geometers were equally fatalistic about the open-ended notion of space we would never have had modern geometry, topology, sheaves – heck, half of 20th century mathematics would not be there!

Of course, we are neither the first nor the last to give a definition of type theory, and that is how things should be. We claim no priority or supremacy over other definitions and views of type theory. Our approach could perhaps be described as "concrete" and "proof-theoretic":

- We wanted to
*stay close to traditional syntax*. - We gave a
*complete*and*precise*definition. - We aimed for a level of generality that allows useful meta-theory of a wide range of type theories.

One can argue each of the above points, and we have done so among ourselves many times. Nevertheless, I feel that we have accomplished something worthwhile – but the ultimate judges will be our readers, or lack of them. You are kindly invited to take a look at the paper.

**Download PDF:** `arxiv.org/pdf/2009.05539.pdf`

I should not forget to mention that Peter, with modest help from Philipp and me,
formalized almost the entire paper in Coq! See the repository
`general-type-theories`

at
GitHub.

Here are the slides with speaker notes for the talk *What is an explicit bijection* which I gave at the 31st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2019). It was the "outsider" talk, where they invite someone to tell them something outside of their area.

So how does one sell homotopy type theory to people who are interested in combinatorics? That is a tough sell. I used my MathOverflow question "What is an explicit bijection?" to give a stand-up comedy introduction, after which I plunged into type theory. I am told I plunged a little too hard. For instance, people asked "why are we doing this" because I did not make it clear enough that we are trying to make a distinction between "abstractly exists" and "concretely constructed". Oh well, it’s difficult to explain homotopy type theory in 50 minutes. Anyhow, I hope you can get something useful from the slides.

Download slides: what-is-an-explicit-bijection.pdf

Video recording of the lecture is now available.

→ continue reading (2 comments)### A course on homotopy (type) theory

- 08 May 2019
- Type theory, Teaching

This semester my colleague Jaka Smrekar and I are teaching a graduate course on homotopy theory and homotopy type theory. The first part was taught by Jaka and was a nice review of classical homotopy theory leading up to Quillen model categories. In the second part I am covering basic homotopy type theory.

The course materials are available at the GitHub repository `homotopy-type-theory-course`

. The homotopy type theory lectures are also recorded on video.

### Spartan type theory

- 11 December 2017
- Type theory, Talks, Tutorial

The slides from the talk “Spartan type theory”, given at the School and Workshop on Univalent Mathematics.

**Download slides with speaker notes: Spartan Type Theory [PDF]**

I am about to give an invited talk at the Computability and Complexity in Analysis 2016 conference (yes, I am in the south of Portugal, surrounded by loud English tourists, but we *are* working here, in a basement no less). Here are the slides, with extensive speaker notes, comment and questions are welcome.

**Slides:** hott-reals-cca2016.pdf

### A HoTT PhD position in Ljubljana

- 22 November 2014
- Eff, Type theory, Programming, Teaching

I am looking for a PhD student in mathematics. Full tuition & stipend will be provided for a period of three years, which is also the official length of the programme. The topic of research is somewhat flexible and varies from constructive models of homotopy type theory to development of a programming language for a proof assistant based on dependent type theory, see the short summary of the Effmath project for a more detailed description.

The candidate should have as many of the following desiderata as possible, and at the very least a master’s degree (or an equivalent one):

- a master’s degree in mathematics, with good knowledge of computer science
- a master’s degree in computer science, with good knowledge of mathematics
- experience with functional programming
- experience with proof assistants
- familiarity with homotopy type theory

The student will officially enrol in October 2015 at the University of Ljubljana. No knowledge of Slovene is required. However, it is possible, and even desirable, to start with the actual work (and stipend) earlier, as soon as in the spring of 2015. The candidates should contact me by email as soon as possible. Please include a short CV and a statement of interest.

**Update 2015-03-28:** the position has been taken.

### Seemingly impossible constructive proofs

- 08 May 2014
- Computation, Constructive math, Guest post, Type theory

In the post Seemingly impossible functional programs, I wrote increasingly efficient Haskell programs to realize the mathematical statement

$\forall p : X \to 2. (\exists x:X.p(x)=0) \vee (\forall x:X.p(x)=1)$

for $X=2^\mathbb{N}$, the Cantor set of infinite binary sequences, where $2$ is the set of binary digits. Then in the post A Haskell monad for infinite search in finite time I looked at ways of systematically constructing such sets $X$ with corresponding Haskell realizers of the above *omniscience principle*.

In this post I give examples of infinite sets $X$ and corresponding constructive *proofs* of their omniscience that are intended to be valid in Bishop mathematics, and which I have formalized in Martin-Löf type theory in Agda notation. This rules out the example $X=2^\mathbb{N}$, as discussed below, but includes many interesting infinite examples. I also look at ways of constructing new omniscient sets from given ones. Such sets include, in particular, ordinals, for which we can find minimal witnesses if any witness exists.

Agda is a dependently typed functional programming language based on Martin-Löf type theory. By the Curry-Howard correspondence, Agda is also a language for formulating mathematical theorems (types) and writing down their proofs (programs). Agda acts as a thorough referee, only accepting correct theorems and proofs. Moreover, Agda can run your proofs. Here is a graph of the main Agda modules for this post, and here is a full graph with all modules.

→ continue reading (1 comment)### Brazilian type checking

- 06 May 2014
- Type theory, Talks

I just gave a talk at “Semantics of proofs and certified mathematics”. I spoke about a new proof checker Chris Stone and I are working on. The interesting feature is that it has both kinds of equality, the “paths” and the “strict” ones. It is based on a homotopy type system proposed by Vladimir Voevodsky. The slides contain talk notes and explain why it is “Brazilian”.

**Download slides:** brazilian-type-checking.pdf

**GitHub repository:** https://github.com/andrejbauer/tt

**Abstract:** Proof assistants verify that inputs are correct up to judgmental equality. Proofs are easier and smaller if equalities without computational content are verified by an oracle, because proof terms for these equations can be omitted. In order to keep judgmental equality decidable, though, typical proof assistants use a limited definition implemented by a fixed equivalence algorithm. While other equalities can be expressed using propositional identity types and explicit equality proofs and coercions, in some situations these create prohibitive levels of overhead in the proof.

Voevodsky has proposed a type theory with two identity types, one propositional and one judgmental. This lets us hypothesize new judgmental equalities for use during type checking, but generally renders the equational theory undecidable without help from the user.

Rather than reimpose the full overhead of term-level coercions for judgmental equality, we propose algebraic effect handlers as a general mechanism to provide local extensions to the proof assistant’s algorithms. As a special case, we retain a simple form of handlers even in the final proof terms, small proof-specific hints that extend the trusted verifier in sound ways.

→ continue reading (5 comments)### Univalent foundations subsume classical mathematics

- 13 January 2014
- Type theory, Logic, Tutorial

A discussion on the homotopytypetheory mailing list prompted me to write this short note. Apparently a mistaken belief has gone viral among certain mathematicians that Univalent foundations is somehow limited to constructive mathematics. This is false. Let me be perfectly clear:

*Univalent foundations subsume classical mathematics!*

The next time you hear someone having doubts about this point, please refer them to this post. A more detailed explanation follows.

→ continue reading (24 comments)### The elements of an inductive type

- 28 August 2013
- Constructive math, Type theory, Tutorial

In the HoTT book issue 460 a question by *gluttonousGrandma* (where do people get these nicknames?) once more exposed a common misunderstanding that we tried to explain in section 5.8 of the book (many thanks to Bas Spitters for putting the book into Google Books so now we can link to particular pages). Apparently the following belief is widely spread, and I admit to holding it a couple of years ago:

An inductive type contains exactly those elements that we obtain by repeatedly using the constructors.

If you believe the above statement you should keep reading. I am going to convince you that the statement is unfounded, or that at the very least it is preventing you from understanding type theory.

→ continue reading (29 comments)### The HoTT book

- 20 June 2013
- Constructive math, General, Type theory, News, Publications

The HoTT book is finished!

Since spring, and even before that, I have participated in a great collaborative effort on writing a book on Homotopy Type Theory. It is finally finished and ready for public consumption. You can get the book freely at http://homotopytypetheory.org/book/. Mike Shulman has written about the contents of the book, so I am not going to repeat that here. Instead, I would like to comment on the socio-technological aspects of making the book, and in particular about what we learned from open-source community about collaborative research.

→ continue reading (10 comments)### How to implement dependent type theory III

- 29 November 2012
- Type theory, Programming, Software, Tutorial

I spent a week trying to implement higher-order pattern unification. I looked at couple of PhD dissertations, talked to lots of smart people, and failed because the substitutions were just getting in the way all the time. So today we are going to bite the bullet and implement de Bruijn indices and explicit substitutions.

The code is available on Github in the repository andrejbauer/tt (the `blog-part-III`

branch).

### How to implement dependent type theory II

- 11 November 2012
- Type theory, Programming, Software, Tutorial

I am on a roll. In the second post on how to implement dependent type theory we are going to:

- Spiff up the syntax by allowing more flexible syntax for bindings in functions and products.
- Keep track of source code locations so that we can report
*where*the error has occurred. - Perform normalization by evaluation.

### How to implement dependent type theory I

- 08 November 2012
- Type theory, Programming, Software, Tutorial

I am spending a semester at the Institute for Advanced Study where we have a special year on Univalent foundations. We are doing all sorts of things, among others experimenting with type theories. We have got some real experts here who know type theory and Coq inside out, and much more, and they’re doing crazy things to Coq (I will report on them when they are done). In the meanwhile I have been thinking how one might implement dependent type theories with undecidable type checking. This is a tricky subject and I am certainly not the first one to think about it. Anyhow, if I want to experiment with type theories, I need a small prototype first. Today I will present a very minimal one, and build on it in future posts.

Make a guess, how many lines of code does it take to implement a dependent type theory with universes, dependent products, a parser, lexer, pretty-printer, and a toplevel which uses line-editing when available?

→ continue reading (8 comments)### A hott thesis

- 23 August 2012
- Type theory, News, Tutorial

Egbert Rijke successfully defended his master thesis in Utrecht a couple of weeks ago. He published it on the *Homotopy type theory* blog (here is a direct link to the PDF file (revised)). The thesis is well written and it contains several new results, but most importantly, it is a gentle yet non-trivial introduction to homotopy type theory. If you are interested in the topic but do not know where to start, Egbert’s thesis might be perfect for you. As far as I know it is the first substantial piece of text written *in* (informal) homotopy type theory.

What I find most amazing about the work is that Egbert does not have to pretend to be a homotopy type theorist, like us old folks. His first contact with type theory *was* homotopy type theory, which impressed on his mind a new kind of geometric intuition about $\Pi$’s, $\Sigma$’s and $\mathrm{Id}$’s. If we perform enough such experiments on young bright students, strange things will happen.