Type inference is essential for programming languages, yet complete
and global inference quickly becomes undecidable in the presence of rich type
systems like System~F. Pierce and Turner proposed local type
inference (LTI) as a scalable,
partially annotated alternative by relying on information local to
applications. While LTI has been widely adopted in practice, there
are significant gaps between theory and practice, with its theory
being underdeveloped and specifications for LTI being complex and restrictive.
We propose \emph{Local Contextual Type Inference}, a principled
redesign of LTI grounded in contextual typing—a recent formalism
which captures type information flow. We present \emph{Contextual
System~F} (Fc), a variant of System~F with implicit and
first-class polymorphism. We formalize Fc using a declarative
type system, prove soundness, completeness, and
decidability, and introduce matching subtyping as a bridge between
declarative and algorithmic inference. This work offers the first
mechanized treatment of LTI, while at the same time removing
important practical restrictions and also demonstrating the power of
contextual typing in designing robust, extensible and simple to
implement type inference algorithms.
Wed 14 JanDisplayed time zone: Brussels, Copenhagen, Madrid, Paris change
14:00 - 15:40 | |||
14:00 25mTalk | Extensible Data Types with Ad-Hoc Polymorphism POPL Matthew Toohey University of Toronto, Yanning Chen University of Toronto, Ara Jamalzadeh University of Toronto, Ningning Xie University of Toronto DOI Pre-print | ||
14:25 25mTalk | Let Generalization, Polymorphic Recursion, and Variable Minimization in Boolean-Kinded Type Systems POPL Joseph Zullo Purdue University DOI | ||
14:50 25mTalk | Local Contextual Type Inference POPL Xu Xue University of Hong Kong, Chen Cui University of Hong Kong, Shengyi Jiang The University of Hong Kong, Bruno C. d. S. Oliveira University of Hong Kong DOI | ||
15:15 25mTalk | Typing Strictness POPL Daniel Sainati University of Pennsylvania, Joseph W. Cutler University of Pennsylvania, Benjamin C. Pierce University of Pennsylvania, Stephanie Weirich University of Pennsylvania DOI | ||