Computing the output distribution of a discrete probabilistic program (a process known as exact inference) can be very slow if implemented naively. A common solution is to use efficient representations of probability distributions as trees of random variables.

We have developed a new semantic model for probabilistic programming that captures this kind of optimization. The model is compositional, making it easy to explain why the optimization is correct with respect to the standard semantics of probabilistic programming.

In this talk, I will explain the construction in detail. The key idea is to decompose the probabilistic effect into two effects: name generation (for creating new random variables) and read-only state (for branching on sampled values). The main technical challenge is to correctly combine the monadic semantics of call-by-value for the first effect with call-by-name for the second.

This is based on a joint work with Aurore Alcolei, Simon Castellan, and Tom Hirschowitz.