In our view, one of the key contributions of the probabilistic programming language Church is a class of constructs, called exchangeable random primitives (or XRPs for short), that can be used to extend the language with stochastic primitives whose implementations use stateful computation.
Surprisingly, XRPs are not mentioned in the paper introducing the language [GMRBT08] and are buried in the original implementation, dubbed MIT-Church. Despite being reimplemented and generalized in several languages descending from Church, XRPs are poorly documented and, as a result, poorly understood.
XRPs are built from three components: a sampler, an unsampler, and a scorer. We give a rigorous definition for the samplers of XRPs, and give a representation theorem characterizing their essential form and conditional independence structure. A formalization like the one we provide could serve as part of a foundation for deriving a semantics for Church programs with XRPs. A formalization of all three components of XRPs — including the unsampler and scorer — would be necessary to prove the correctness of the MCMC Church algorithm in the presence of XRPs. We highlight some challenges associated with formalizing the scorer. (We also have some ideas for circumventing these obstacles that do not appear in the paper but that we would be happy to discuss.) We are also looking forward to discussing semantic questions surrounding XRPs, especially those involving purity and referential transparency, and would be interested to learn of other possible connections between XRPs and the PL theory literature.
Extended abstract: eXchangeable Random Primitives by Nathanael L. Ackerman, Cameron E. Freer, and Daniel M. Roy
Related work by the authors:
[FR10] C. E. Freer and D. M. Roy. Posterior distributions are computable from predictive distributions. In: Proc. 13th Int. Conf. on Artificial Intelligence and Statistics (AISTATS 2010). Vol. 9. J. Machine Learning Research W&CP. 2010.
[FR12] C. E. Freer and D. M. Roy. Computable de Finetti measures. Ann. Pure Appl. Logic 163.5 (2012), pp. 530–546.
[GMRBT08] N. D. Goodman, V. K. Mansinghka, D. M. Roy, K. Bonawitz, and J. B. Tenenbaum. Church: A language for generative models. In: Proc. 24th Conf. on Uncertainty in Artificial Intelligence (UAI 2008). Corvalis, Oregon: AUAI Press, 2008, pp. 220–229.
[RMGT08] D. M. Roy, V. K. Mansinghka, N. D. Goodman, and J. B. Tenenbaum. A stochastic programming perspective on nonparametric Bayes. Nonparametric Bayesian Workshop, Int. Conf. on Machine Learning. 2008.