  We describe Venture, an interactive virtual machine for probabilistic
programming that aims to be sufficiently expressive, extensible, and efficient
for general-purpose use. Like Church, probabilistic models and inference
problems in Venture are specified via a Turing-complete, higher-order
probabilistic language descended from Lisp. Unlike Church, Venture also
provides a compositional language for custom inference strategies built out of
scalable exact and approximate techniques. We also describe four key aspects of
Venture's implementation that build on ideas from probabilistic graphical
models. First, we describe the stochastic procedure interface (SPI) that
specifies and encapsulates primitive random variables. The SPI supports custom
control flow, higher-order probabilistic procedures, partially exchangeable
sequences and ``likelihood-free'' stochastic simulators. It also supports
external models that do inference over latent variables hidden from Venture.
Second, we describe probabilistic execution traces (PETs), which represent
execution histories of Venture programs. PETs capture conditional dependencies,
existential dependencies and exchangeable coupling. Third, we describe
partitions of execution histories called scaffolds that factor global inference
problems into coherent sub-problems. Finally, we describe a family of
stochastic regeneration algorithms for efficiently modifying PET fragments
contained within scaffolds. Stochastic regeneration linear runtime scaling in
cases where many previous approaches scaled quadratically. We show how to use
stochastic regeneration and the SPI to implement general-purpose inference
strategies such as Metropolis-Hastings, Gibbs sampling, and blocked proposals
based on particle Markov chain Monte Carlo and mean-field variational inference
techniques.
