New Draft: Sound and Complete Bidirectional Typechecking for Higher-Rank Polymorphism and Indexed Types

Together with Joshua Dunfield, I have a new draft on bidirectional type inference to announce:

Sound and Complete Bidirectional Typechecking for Higher-Rank Polymorphism and Indexed Types

Bidirectional typechecking, in which terms either synthesize a type or are checked against a known type, has become popular for its scalability, its error reporting, and its ease of implementation. Following principles from proof theory, bidirectional typing can be applied to many type constructs. The principles underlying a bidirectional approach to indexed types (generalized algebraic datatypes) are less clear. Building on proof-theoretic treatments of equality, we give a declarative specification of typing based on focalization. This approach permits declarative rules for coverage of pattern matching, as well as support for first-class existential types using a focalized subtyping judgment. We use refinement types to avoid explicitly passing equality proofs in our term syntax, making our calculus close to languages such as Haskell and OCaml. An explicit rule deduces when a type is principal, leading to reliable substitution principles for a rich type system with significant type inference.

We also give a set of algorithmic typing rules, and prove that it is sound and complete with respect to the declarative system. The proof requires a number of technical innovations, including proving soundness and completeness in a mutually-recursive fashion.

If you are very interested in the details, we have a long (153 pages!) technical report with all of the proofs.

Don't be put off by the proofs, though -- the algorithmic type system is only modestly more complex than our earlier paper on bidirectional typechecking, and this go-around we add a lot of new features, such as intersection types, existential types, GADT-style equality constraints, and a full account of how to do pattern matching (including coverage checking) with all of these features.

Logically speaking, the punchline of the paper is that proof theory knows of two formulations of equality -- the Martin-Lof identity type, and the Girard/Schroeder-Heister equality. (Hilariously, these two notions of equality are not the same.) Furthermore, GADTs work exactly like the Girard/Schroeder-Heister equality. Everything things works uncannily well, and our rules (even the algorithmic ones) are much simpler than many of the rules you'll find in the literature.