We define a new denotational semantics for a first-order probabilistic programming language in terms of probabilistic event structures. The semantics adequately models the language, in the sense that the usual measure-theoretic semantics of a program can be recovered from its event structure representation.

Moreover it is intensional: occurrences of sampling and conditioning are recorded as explicit events, partially ordered according to the dependencies between the corresponding variables. This information can be leveraged for MCMC inference: we prove correct a version of single-site Metropolis-Hastings with ‘incremental recomputation’: the proposal kernel takes into account those dependencies in order to avoid performing some of the redundant sampling.