Practical Inference for Type-Based Termination in a Polymorphic Setting

摘要

We introduce a polymorphic λ-calculus that features inductive types and that enforces termination of recursive definitions through typing. Then, we define a sound and complete type inference algorithm that computes a set of constraints to be satisfied for terms to be ty-pable. In addition, we show that Subject Reduction fails in a naive use of typed-based termination for a λ-calculus a la Church, and we propose a general solution to this problem.