The Fire Triangle: How to Mix Substitution, Dependent Elimination, and Effects
There is a critical tension between substitution, dependent elimination and effects in type theory. In this paper, we crystallize this tension in the form of a no-go theorem that constitutes the fire triangle of type theory.
To release this tension, we propose ∂CBPV, an extension of call-by-push-value (CBPV) —a general calculus of effects—to dependent types.
Then, by extending to ∂CBPV the well-known decompositions of call-by-name and call-by-value into CBPV, we show why, in presence of effects, dependent elimination must be restricted in call-by-name, and substitution must be restricted in call-by-value.
To justify ∂CBPV and show that it is general enough to interpret many kinds of effects, we define various effectful syntactic translations from ∂CBPV to Martin-Löf type theory: the reader, weaning and forcing translations.
Thu 23 JanDisplayed time zone: Saskatchewan, Central America change
10:30 - 11:35 | Types and EffectsResearch Papers at Ile de France II (IDF II) Chair(s): Dominique Devriese Vrije Universiteit Brussel | ||
10:30 21mTalk | Binders by Day, Labels by Night: Effect Instances via Lexically Scoped Handlers Research Papers Dariusz Biernacki University of Wrocław, Maciej Piróg University of Wrocław, Piotr Polesiuk University of Wrocław, Filip Sieczkowski University of Wrocław Link to publication DOI Media Attached | ||
10:51 21mTalk | The Fire Triangle: How to Mix Substitution, Dependent Elimination, and Effects Research Papers Link to publication DOI Media Attached | ||
11:13 21mTalk | SyTeCi: Automating Contextual Equivalence for Higher-Order Programs with References Research Papers Guilhem Jaber LS2N, Université de Nantes Link to publication DOI Media Attached |