  We present an exact Bayesian inference method for discrete statistical
models, which can find exact solutions to a large class of discrete inference
problems, even with infinite support and continuous priors. To express such
models, we introduce a probabilistic programming language that supports
discrete and continuous sampling, discrete observations, affine functions,
(stochastic) branching, and conditioning on discrete events. Our key tool is
probability generating functions: they provide a compact closed-form
representation of distributions that are definable by programs, thus enabling
the exact computation of posterior probabilities, expectation, variance, and
higher moments. Our inference method is provably correct and fully automated in
a tool called Genfer, which uses automatic differentiation (specifically,
Taylor polynomials), but does not require computer algebra. Our experiments
show that Genfer is often faster than the existing exact inference tools PSI,
Dice, and Prodigy. On a range of real-world inference problems that none of
these exact tools can solve, Genfer's performance is competitive with
approximate Monte Carlo methods, while avoiding approximation errors.
