Densities of Almost Surely Terminating Probabilistic Programs are
  Differentiable Almost Everywhere
  We study the differential properties of higher-order statistical
probabilistic programs with recursion and conditioning. Our starting point is
an open problem posed by Hongseok Yang: what class of statistical probabilistic
programs have densities that are differentiable almost everywhere? To formalise
the problem, we consider Statistical PCF (SPCF), an extension of call-by-value
PCF with real numbers, and constructs for sampling and conditioning. We give
SPCF a sampling-style operational semantics a la Borgstrom et al., and study
the associated weight (commonly referred to as the density) function and value
function on the set of possible execution traces. Our main result is that
almost-surely terminating SPCF programs, generated from a set of primitive
functions (e.g. the set of analytic functions) satisfying mild closure
properties, have weight and value functions that are almost-everywhere
differentiable. We use a stochastic form of symbolic execution to reason about
almost-everywhere differentiability. A by-product of this work is that
almost-surely terminating deterministic (S)PCF programs with real parameters
denote functions that are almost-everywhere differentiable. Our result is of
practical interest, as almost-everywhere differentiability of the density
function is required to hold for the correctness of major gradient-based
inference algorithms.
