I am pleased to make available the result of joint research with Darryl McAdams, our new paper Dependent Types for Pragmatics which is currently under review for publication in the *Journal of Logic, Language and Information*. I’d like to discuss a few aspects of the work which I consider important, lending additional emphasis to foundational aspects of type theory which I fear were lost in the presentation, which was meant for a general Linguistics audience.

The key idea of Observational Type Theory is to make the *propositional* equality coextensive with the equality which is validated under the standard semantics for Type Theory, which is the meaning explanations and their metamathematical counterpart, the realizability interpretation. Now, Extensional Type Theory is usually characterized in terms of typechecking (membership) being undecidable because the “true” equality is made to hold judgementally; but this is a deceptive characterization when applied to Computational Type Theory (Nuprl), since there are many types besides equality which may be given meaning explanations but which have an undecidable membership judgement.

Whilst the judgements of type theory are preferred to be analytic, the practice of operating a proof assistant is inherently and unavoidably synthetic, and is always accompanied by some manner of refinement and tactics: and so the question is never whether to use tactics, but rather how much pain one intends to experience in the process of using them: this is inextricable from the activity of proving.

I’m so pleased to be able to announce the first fruit of a joint project with David Christiansen and Darin Morrison, which is an interview of Peter Dybjer for The Type Theory Podcast. We spoke to Peter about QuickCheck-style testing and its relation to proofs and verification in type theory. Subscribe to the RSS feed or follow us on Twitter if you are interested in listening to discussions with researchers, because we have more to come.

Here I present an idea for a type theory which retains the benefits of wholesale adherence to the realizability interpretation à la Nuprl, and yet seems to maintain a better division of labor between operator and machine.

In my recent post I demonstrated a type-theoretic formulation of non-dependent record types as presheaves on a particular topological space \(X\) of keys given an assignment \(El_X : X\to\mathbf{Type}\). Today, I’ll construct more interesting records by endowing the key space with a non-discrete topology.

Family union types have existed for a few years in Extensional Type Theory à la Nuprl; here, I demonstrate a lightweight approach to adding them to Intensional Type Theory as an extension of Altenkirch, McBride, Swierstra’s OTT.

Let us define a record type as being given by a type \(X\) of **keys** and an interpretation function \(F\) which maps every key \(x:X\) to a type. We assume the existence of a powerset functor \(\mathcal{P}: \mathbf{Type}\to\mathbf{Type}\), which endows the discrete topology on \(X\). Then a record type is the product of the image of \(F\) over a subset of \(X\): \[
\mbox{for}\ U\subseteq X,\quad \mathsf{Rec}(U,F) :\equiv \prod_{s:U} F(s)
\]

All posts…