Linear Types with Dynamic Multiplicities in Dependent Type Theory (Functional Pearl)Remote
We construct a linear type system inside dependent type theory. For this, we equip the output type of a program with a bag containing copies of each of the input variables. We call the number of copies of an input variable its multiplicity. We then characterise a dependent type which ensures that a program uses exactly the given multiplicity of each input variable. While our system is not closed under linear function types, we can program in the resulting system in a practical way using usual dependent functions, which we demonstrate by constructing standard programs on lists such as folds, unfolds and sorting algorithms. Since our linear type system is deeply embedded in a functional language, we can moreover dynamically compute multiplicities, which allows us to capture that a program uses a varying number of copies of some input depending on the other inputs. We can thereby give precise types to many functional programs that cannot be typed in systems with static multiplicities.
Wed 15 OctDisplayed time zone: Perth change
13:40 - 15:20 | Types and SpecificationsICFP Papers / JFP First Papers at Orchid West Chair(s): Dominic Orchard University of Cambridge; University of Kent | ||
13:40 25mTalk | McTT: A Verified Kernel for a Proof Assistant ICFP Papers Junyoung Jang McGill University, Antoine Gaulin McGill University, Jason Z. S. Hu Amazon, Brigitte Pientka McGill University DOI Media Attached | ||
14:05 25mTalk | Linear Types with Dynamic Multiplicities in Dependent Type Theory (Functional Pearl)Remote ICFP Papers Maximilian Doré University of Oxford DOI Pre-print | ||
14:30 25mPaper | Binary search—think positive JFP First Papers DOI | ||
14:55 25mTalk | Teaching Software Specification (Experience Report) ICFP Papers DOI | ||