  Probabilistic programming uses programs to express generative models whose
posterior probability is then computed by built-in inference engines. A
challenging goal is to develop general purpose inference algorithms that work
out-of-the-box for arbitrary programs in a universal probabilistic programming
language (PPL). The densities defined by such programs, which may use
stochastic branching and recursion, are (in general) nonparametric, in the
sense that they correspond to models on an infinite-dimensional parameter
space. However standard inference algorithms, such as the Hamiltonian Monte
Carlo (HMC) algorithm, target distributions with a fixed number of parameters.
This paper introduces the Nonparametric Hamiltonian Monte Carlo (NP-HMC)
algorithm which generalises HMC to nonparametric models. Inputs to NP-HMC are a
new class of measurable functions called "tree representable", which serve as a
language-independent representation of the density functions of probabilistic
programs in a universal PPL. We provide a correctness proof of NP-HMC, and
empirically demonstrate significant performance improvements over existing
approaches on several nonparametric examples.
