Coalgebra for the working programming languages researcher
Coalgebra is a young research field that grew out of the Theory B community in the late 90’s. It started out as a mathematical framework to study different types of state-based systems in a uniform way. A lot of the early results on Coalgebra had roots in Category Theory and were purely theoretical in nature.
As the field grew, more application areas became evident. For instance, the study of different families of automata and equivalence procedures, or the foundations of (typed) languages that included fixpoint operators. Slowly (but steadily!), coalgebraic techniques found a place in the programming language and verification communities. Interestingly, and perhaps of greater importance for the coalgebra community, the challenges provided by PL work generated different research directions for coalgebra.
In this talk, I will present a primer on coalgebraic techniques, and revisit some work in programming languages in which these played a key role. I will argue that the use of category theory, coalgebra, and other traditional theory techniques are not only useful to provide foundational insights in the design of programming languages and semantics, but can also play a key role in the development of efficient algorithms. I will conclude with a few research directions in which this interplay of programming languages and theory research might provide new challenges, and hopefully novel solutions, for both communities.
Alexandra Silva is a theoretical computer scientist whose main research focuses on semantics of programming languages and modular development of algorithms for computational models. A lot of her work uses the unifying perspective offered by coalgebra, a mathematical framework established in the last decades. Alexandra is currently a Professor at Cornell University, and she was previously a Professor of Algebra, Semantics, and Computation at University College London. Previously, she was an assistant professor in Nijmegen and a post-doc at Cornell University, with Prof. Dexter Kozen, and a PhD student at the Dutch national research center for Mathematics and Computer Science (CWI), under the supervision of Prof. Jan Rutten and Dr. Marcello Bonsangue. She was the recipient of an ERC Consolidator in 2020, the Royal Society Wolfson Award 2019, Needham Award 2018, the Presburger Award 2017, the Leverhulme prize 2016, and an ERC starting Grant in 2015.