Any views expressed within media held on this service are those of the contributors, should not be taken as approved or endorsed by the University, and do not necessarily reflect the views of the University in respect of any particular issue.

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:

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.




Report this page

To report inappropriate content on this page, please use the form below. Upon receiving your report, we will be in touch as per the Take Down Policy of the service.

Please note that personal data collected through this form is used and stored for the purposes of processing this report and communication with you.

If you are unable to report a concern about content via this form please contact the Service Owner.

Please enter an email address you wish to be contacted on. Please describe the unacceptable content in sufficient detail to allow us to locate it, and why you consider it to be unacceptable.
By submitting this report, you accept that it is accurate and that fraudulent or nuisance complaints may result in action by the University.