The MIT Category Theory Seminar is now online, in live streaming!
MIT Category Theory Seminar
2020/03/19
©Spifong
Speaker: Paolo Perrone
Title: Composing partial evaluations.
This is a joint work with the ACT 2019 "Partial evaluations" group (Tobias Fritz, Carmen Constantin, Martin Lundfall, Brandon Shapiro)
Abstract:
We all know that the sum 1+2+4 can be evaluated to 7. What is less known, but just as easy, is that 1+2+4 can be also *partially* evaluated to 3+4. We say that the formal expressions 1+2+4 and 3+4 are related by a partial evaluation. This notion can be generalized from natural numbers to algebras over an arbitrary monad, and sometimes it gives known constructions (such as the factorization of natural numbers, and conditional expectations in measure theory).
A more difficult problem is the following. Given three formal expressions s, t and u, suppose that s and t are related by a partial evaluation, and that t and u are as well. Can we conclude that s and u are directly related by a "composite" partial evaluation? Perhaps surprisingly, the answer is not always positive, and almost never easy to get.
We can solve this problem in a number of cases borrowing methods from homotopy theory. Partial evaluations can be seen as edges between formal expressions, forming the 1-dimensional skeleton of a canonical simplicial set called the bar construction. The geometry of this simplicial set can say a lot about when and how partial evaluations compose.
This way we can show, for example, that a composite partial evaluation always exists for the case of cartesian and weakly cartesian monads.