We present a modular semantic account of Bayesian inference algorithms for probabilistic programming languages, as used in data science and machine learning. Sophisticated inference algorithms are often explained in terms of composition of smaller parts. However, neither their theoretical justification nor their implementation reflects this modularity. We show how to conceptualise and analyse such inference algorithms as manipulating intermediate representations of probabilistic programs using higher-order functions and inductive types, and their denotational semantics. Semantic accounts of continuous distributions use measurable spaces. However, our use of higher-order functions presents a substantial technical difficulty: it is impossible to define a measurable space structure over the collection of measurable functions between arbitrary measurable spaces that is compatible with standard operations on those functions, such as function application. We overcome this difficulty using quasiBorel spaces, a recently proposed mathematical structure that supports both function spaces and continuous distributions. We define a class of semantic structures for representing probabilistic programs, and semantic validity criteria for transformations of these representations in terms of distribution preservation. We develop a collection of building blocks for composing representations. We use these building blocks to validate common inference algorithms such as Sequential Monte Carlo and Markov Chain Monte Carlo. To emphasize the connection between the semantic manipulation and its traditional measure theoretic origins, we use Kock's synthetic measure theory. We demonstrate its usefulness by proving a quasi-Borel counterpart to the MetropolisHastings-Green theorem. Additional Key Words and Phrases: quasi-Borel spaces, synthetic measure theory, Bayesian inference, applied category theory, commutative monads, Kock integration, initial algebra semantics, sigma-monoids Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).  One of the key challenges in Bayesian data analysis is to develop or find an efficient algorithm for estimating the posterior distribution of a probabilistic model with respect to a given data set. This posterior distribution combines prior knowledge encoded in the model and information present in the data set consistently according to the rules of probability theory, but its mathematical definition often involves integration or summation over a large index set and does not yield to an efficient computation strategy immediately. A data scientist typically has to make one of the suboptimal decisions: she has to consult a large body of specialised research in order to pick an algorithm suitable for her model, or to change the model so that it falls into one of those cases with efficient known algorithms for posterior inference, or to face the challenge directly by developing a new algorithm for herself. Recent probabilistic programming languages aim to resolve this dilemma. They include constructs for describing probability distributions and conditioning, and enable data scientists to express sophisticated probabilistic models as programs. More importantly, they come with the implementation of multiple algorithms for performing posterior inference for models and data sets expressed in the languages. The grand vision is that by using these languages, a data scientist no longer has to worry about the choice or design of such an inference algorithm but focuses on the design of an appropriate model, instead. In this paper, we provide a denotational validation of inference algorithms for higher-order probabilistic programming languages, such as Church [Goodman et al. 2008] , Anglican [Wood et al. 2014] and Venture . The correctness of these algorithms is subtle. The early version of the lightweight Metropolis-Hastings algorithm had a bug because of an incorrect acceptance ratio [Wingate et al. 2011] . The correctness often relies on intricate interplay between facts from probability theory and those from programming language theory. Moreover, correctness typically requires stronger results from probability theory than those used for the usual R n case in the machine-learning community (e.g., Green's measure-theoretic justification of Markov Chain Monte Carlo rather than the usual one for R n based on density functions). Our starting point is the body of existing results on validating inference algorithms for probabilistic programs [Borgström et al. 2016; Hur et al. 2015] . Those earlier results tend to be based on operational semantics, and often (not always) focus on first-order programs. By working in a modular way with monads, denotational semantics and higher-order functions, we are able to validate sophisticated inference algorithms, such as resample-move Sequential Monte Carlo [Doucet and Johansen 2011] , that are complex yet modular, being composed of smaller reusable components, by combining our semantic analysis of these components. The probabilistic programming language considered in the paper includes continuous distributions, which means that semantic accounts of them or their inference algorithms need to use measure theory and Lebesgue integration. Meanwhile, our semantic account uses a meta-language with higher-order functions for specifying and interpreting intermediate representations of probabilistic programs that are manipulated by components of inference algorithms. Such higher-order functions let us achieve modularity and handle higher-order functions in the target probabilistic programming language. These two features cause a tension because it is impossible to define a measurable space structure over the collection of measurable functions between arbitrary measurable
One example is a recent denotational validation of SMC in probabilistic programming given byŚcibior et al. REF .
Denotational validation of higher-order Bayesian inference
PACMPL
Computer Science