System F^ω with Coherent Implicit Resolution

2025/03/31 by Flesselle, Eugène
#FOS: Computer and information sciences #Programming Languages (cs.PL)

paper · doi:10.48550/arxiv.2503.23904

Abstract

We propose a calculus for modeling implicit programming that supports first-class, overlapping, locally scoped, and higher-order instances with higher-kinded types. We propose a straightforward generalization of the well-established System F^ω to implicit parameters, with a uniform treatment of type and term abstractions. Unlike previous works, we give a declarative specification of unambiguous, and thus coherent, resolution without introducing restrictions motivated by an algorithmic formulation of resolution.

Related

• Extended Report: The Implicit Calculus
• A generic imperative language for polynomial time
• Realizing Implicit Computational Complexity
• A program logic for higher-order procedural variables and non-local jumps
• On Quasi-Interpretations, Blind Abstractions and Implicit Complexity