We present a general framework for specifying and reasoning about syntax with bindings. Abstract binder types are modeled using a universe of functors on sets, subject to a number of operations that can be used to construct complex binding patterns and binding-aware datatypes, including non-well-founded and infinitely branching types, in a modular fashion. Despite not committing to any syntactic format, the framework is “concrete” enough to provide definitions of the fundamental operators on terms (free variables, alpha-equivalence, and capture-avoiding substitution) and reasoning and definition principles. This work is compatible with classical higher-order logic and has been formalized in the proof assistant Isabelle/HOL.
Bindings as Bounded Natural Functors -- slides from the POPL presentation (slides_BindingsAsBNFs.pdf) | 950KiB |
Wed 16 JanDisplayed time zone: Belfast change
Wed 16 Jan
Displayed time zone: Belfast change
13:45 - 14:51 | |||
13:45 22mTalk | Familial Monads and Structural Operational Semantics Research Papers Tom Hirschowitz Univ. Grenoble Alpes, Univ. Savoie Mont Blanc, CNRS, LAMA, 73000 Chambéry Link to publication DOI Media Attached File Attached | ||
14:07 22mTalk | Bindings as Bounded Natural Functors Research Papers Jasmin Blanchette Vrije Universiteit Amsterdam, Lorenzo Gheri Middlesex University London, Andrei Popescu Middlesex University, London, Dmitriy Traytel ETH Zurich Link to publication DOI Media Attached File Attached | ||
14:29 22mTalk | Categorical Combinatorics of Scheduling and Synchronization in Game Semantics Research Papers Paul-André Melliès CNRS and University Paris Diderot Link to publication DOI Media Attached File Attached |