The intrinsic and extrinsic views on types are unified by considering two categories: one of syntactic types and terms, and another of semantic types and derivations, and then a forgetful functor from the latter to the former. Following Melliès and Zeilberger’s Functors are Type Refinement Systems, we might attempt to provide a similar characterization for computational type theories with universes, but there are some wrinkles; I attempt to provide a partial resolution to these here.
In 1994, Per Martin-Löf wrote Analytic and Synthetic Judgement in Type Theory, in which he convincingly showed that undecidability phenomena should be understood in terms of synthetic judgement, and demonstrated how the judgements of one theory may be made the propositions of another.
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.
All posts…
