Coercive Subtyping for Implicit Functorial Programming
Programming with typeclass-defined combinators like fmap allows programs a great deal of generality and concision, but programmers have to explicitly invoke combinators in the right places in order to get their programs to type check. In this paper, we propose inferring these operations using a coercive subtyping discipline and study the metatheory of the resulting algebra of coercions. For functors, we promote the fmap combinator of type $(A \to B) \to F A \to F B$ to a coercion $A \to B \leq F A \to F B$. We incorporate it into a monomorphic system of coercions for base types, arrow types, and functor types. We prove that the resulting system of coercions is coherent, meaning that all possible choices of coercions from $A$ to $B$ end up equivalent. The proof of the theorem is based on coherence by evaluation, an approach to coherence proofs based on the well-known technique of normalization by evaluation. All definitions and theorems in the paper are checked in Agda, which played a valuable role in the design of the system.
Sat 29 AugDisplayed time zone: Eastern Time (US & Canada) change
11:00 - 12:30 | |||
11:00 30mTalk | A Cost-Aware Probability Monad for Liquid HaskellRemote Haskell DOI Pre-print | ||
11:30 30mTalk | Coercive Subtyping for Implicit Functorial Programming Haskell Ryan Doenges Boston College, Caden Parajuli Boston College, Ayden Lamparski Boston College, Ke Wu Johns Hopkins University, Aaron Stump Boston College DOI | ||
12:00 10mTalk | Lightning Talk: Formalizing explicit alpha-equivalence Haskell Aaron Stump Boston College | ||
12:10 10mTalk | Lightning Talk: Programming with Extensible Recursive Datatypes Haskell J. Garrett Morris University of Iowa | ||
12:20 10mTalk | Lightning Talk: Testing smart contracts with QuickCheck Haskell John Hughes Chalmers University of Technology, Sweden | ||