Lazy categorical semantics of discrete probabilistic programming

Abstract

A lazy program interpreter postpones computation until the result is actually needed. This is typically more efficient than an eager (or call-by-value) interpreter, but the semantics is not generally the same.
In this talk I will discuss a new categorical semantics of lazy evaluation for algebraic effects, that relies on a subtle combination of name generation and read-only state. This semantic model suggests better intermediate representations of sum and product types in a lazy interpreter.
The practical motivation for this work is a real-world application of probabilistic programming, in which large algebraic data types cause significant performance issues. As I will explain, since probabilistic programming is described by an affine monad, one can use lazy evaluation to speed up the computation without affecting the semantics.
This is joint work with Simon Castellan (Inria, France).