Church: a language for generative models

TLDR

Formal languages for probabilistic modeling promote re‑use, modularity, and clarity, enabling generic inference techniques. The authors introduce Church, a universal language for describing stochastic generative processes. Church, built on Lisp lambda calculus, defines semantics through evaluation histories and conditional distributions, incorporates a stochastic memoizer for non‑parametric models, and supports exact and approximate queries via Monte Carlo methods, illustrated by examples such as generalized Bayes nets, infinite PCFGs, and planning by inference.

Abstract

Formal languages for probabilistic modeling enable re-use, modularity, and descriptive clarity, and can foster generic inference techniques. 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 histories and conditional distributions on such histories. Church also includes a novel language construct, the stochastic memoizer, which enables simple description of many complex non-parametric models. We illustrate language features through several examples, including: a generalized Bayes net in which parameters cluster over trials, infinite PCFGs, planning by inference, and various non-parametric clustering models. Finally, we show how to implement query on any Church program, exactly and approximately, using Monte Carlo techniques.