Tech talk: From Substitution to Semantics for a Family of Substructural Type Systems
Time: 2021-02-11 09:30-10:30 ((UTC00:00) Edinburgh
Video of the talk: https://youtu.be/sMWOQNfYIUw
Speaker: James Wood, Strathclyde U
Abstract: The metatheory of simple type systems presented using de Bruijn indices is well understood. We know to follow the principle that variable binding is the only interaction between the context and typing rules other than the variable rule. From this, we get that the syntax is suitably functorial over its context and traversals of syntax follow from environments being stable with respect to newly bound variables [0]. However, linear type systems appear to violate this principle, for example with contexts being split and half the variables going out of scope. In this talk, I will show that the principle can be suitably refined so as to cover a wide range of calculi which are sensitive to variable usage. The principle can be made formal, which allows for a level of automation demonstrated in our Agda implementation [1].
[0] A Type and Scope Safe Universe of Syntaxes with Binding: Their Semantics and Proofs. Guillaume Allais, Robert Atkey, James Chapman, Conor McBride, James McKinna.
https://arxiv.org/abs/2001.11001
[1] https://github.com/laMudri/generic-lr
Comments are closed
Comments to this thread have been closed by the post author or by an administrator.