Sound and Complete Bidirectional Typechecking for Higher-Rank Polymorphism with Existentials and Indexed Types
Sound and Complete Bidirectional Typechecking for Higher-Rank Polymorphism with Existentials and Indexed Types
复制标题
DOI：
10.1145/3290322
复制
发表时间：
2019-01-01
影响因子：
1.8
通讯作者：
Krishnaswami, Neelakantan R.
中科院分区：
文献类型：
--
作者：
Dunfield, Joshua;Krishnaswami, Neelakantan R.
双向类型检查（Bidirectional typechecking），其中术语要么合成一个类型，要么针对一个已知类型进行检查，由于其对各种类型系统的适用性、错误报告以及易于实现而变得流行。遵循证明论的原则，双向类型可以应用于许多类型构造。索引类型（广义代数数据库）的双向方法背后的原则不太清楚。建立在证明理论的平等待遇，我们给出了一个声明性规范的基础上聚焦类型。这种方法允许使用声明性规则来覆盖模式匹配，以及使用聚焦子类型判断来支持第一类存在类型。我们使用细化类型来避免在我们的术语语法中显式地传递相等性证明，使我们的演算类似于Haskell和OCaml等语言。我们还扩展了一个明确的规则推导时，类型是主要的声明性规范，使我们能够给一个完整的声明性规范丰富的类型系统与显着的类型推断。我们还给出了一组算法类型规则，并证明了它是健全的和完整的声明系统。证明需要一些技术创新，包括以相互递归的方式证明可靠性和完整性。
Bidirectional typechecking, in which terms either synthesize a type or are checked against a known type, has become popular for its applicability to a variety of type systems, 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 similar to languages such as Haskell and OCaml. We also extend the declarative specification with an explicit rules for deducing when a type is principal, permitting us to give a complete declarative specification 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.