Church: A language for generative models

Formal languages for probabilistic modeling enable re-use, modularity, and descriptive clarity, and can foster generic inference tech-niques. We introduce Church, a universal language for describing stochastic generative processes. Church is based on the Lisp model of lambda calculus, containing a pure Lisp as its deterministic subset. The semantics of Church is defined in terms of evaluation his-tories and conditional distributions on such histories. Church also includes a novel lan-guage construct, the stochastic memoizer, which enables simple description of many complex non-parametric models. We illus-trate language features through several ex-amples, including: a generalized Bayes net in which parameters cluster over trials, infi-nite PCFGs, planning by inference, and var-ious non-parametric clustering models. Fi-nally, we show how to implement query on any Church program, exactly and approxi-mately, using Monte Carlo techniques.