Intrinsically Typed Syntax, a Logical Relation, and the Scourge of the Transfer Lemma
Intrinsically typed syntax is an important and popular method for mechanized reasoning about programming languages. We explore the limits of this method in the setting of finitely-stratified System F using the Agda proof assistant. This system supports elegant definitions of denotational semantics as well as big-step operational semantics based on intrinsically typed syntax. While its syntactic metatheory (i.e., type soundness) works well, we demonstrate that its semantic metatheory poses technical challenges, by defining a logical relation and proving its fundamental lemma. Our logical relation connects a denotational semantics with an operational one, which exposes issues with transfer lemmas as well as minor issues with universe polymorphism.
Fri 6 SepDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
14:00 - 15:30 | |||
14:00 22mTalk | Modal Mu-Calculus for Free in Agda TyDe | ||
14:22 22mTalk | First-class Algebraic Presentations with Elaborator Reflection (Extended Abstract) TyDe File Attached | ||
14:45 22mTalk | Normalizable types TyDe Stefan Monnier Université de Montréal | ||
15:07 22mTalk | Intrinsically Typed Syntax, a Logical Relation, and the Scourge of the Transfer Lemma TyDe Hannes Saffrich University of Freiburg, Peter Thiemann University of Freiburg, Germany, Marius Weidner University of Freiburg |