Search papers, labs, and topics across Lattice.
This paper critiques existing higher-order unification methods in dependently typed languages, highlighting their failure to handle functions defined by case analysis due to limitations in pattern-based fragments. The authors propose a novel integration of dependent pattern matching into the unification process, demonstrated through a prototype implementation that collects and resolves delayed unification constraints. Their approach successfully infers solutions that current systems like Rocq and Lean cannot, indicating a significant advancement in unifying type inference and pattern matching compilation.
Current higher-order unification methods miss key functions defined by case analysis, but integrating dependent pattern matching reveals solutions that existing systems overlook.
We revisit the role of higher-order unification in dependently typed languages and identify a fundamental limitation of existing pattern-based fragments: their inability to synthesize functions defined by case analysis. Even simple and ubiquitous constraints arising from type inference, particularly from use of induction principles, fall outside the expressive power of Miller patterns and their modern extensions. We observe that such constraints naturally correspond to definitions by dependent pattern matching. Motivated by this correspondence, we propose integrating dependent pattern matching into the unification process. We present a prototype implementation of a small dependently typed language that collects delayed unification constraints and resolves them via a pattern matching compiler. Our approach successfully infers solutions that are rejected by current systems such as Rocq and Lean, suggesting a new direction for unification that unifies type inference and pattern matching compilation.
