{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T08:44:46Z","timestamp":1787561086353,"version":"build-2736575974"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2019,1,2]],"date-time":"2019-01-02T00:00:00Z","timestamp":1546387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100009193","name":"Royal Society","doi-asserted-by":"publisher","award":["University Research Fellowship"],"award-info":[{"award-number":["University Research Fellowship"]}],"id":[{"id":"10.13039\/501100009193","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Balliol College Oxford","award":["Career Development Fellowship"],"award-info":[{"award-number":["Career Development Fellowship"]}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/N007387\/1, EP\/M023974\/1"],"award-info":[{"award-number":["EP\/N007387\/1, EP\/M023974\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2019,1,2]]},"abstract":"<jats:p>We give an adequate denotational semantics for languages with recursive higher-order types, continuous probability distributions, and soft constraints. These are expressive languages for building Bayesian models of the kinds used in computational statistics and machine learning. Among them are untyped languages, similar to Church and WebPPL, because our semantics allows recursive mixed-variance datatypes. Our semantics justifies important program equivalences including commutativity.<\/jats:p>\n                  <jats:p>Our new semantic model is based on `quasi-Borel predomains'. These are a mixture of chain-complete partial orders (cpos) and quasi-Borel spaces. Quasi-Borel spaces are a recent model of probability theory that focuses on sets of admissible random elements. Probability is traditionally treated in cpo models using probabilistic powerdomains, but these are not known to be commutative on any class of cpos with higher order functions. By contrast, quasi-Borel predomains do support both a commutative probabilistic powerdomain and higher-order functions. As we show, quasi-Borel predomains form both a model of Fiore's axiomatic domain theory and a model of Kock's synthetic measure theory.<\/jats:p>","DOI":"10.1145\/3290349","type":"journal-article","created":{"date-parts":[[2019,1,4]],"date-time":"2019-01-04T08:33:51Z","timestamp":1546590831000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["A domain theory for statistical probabilistic programming"],"prefix":"10.1145","volume":"3","author":[{"given":"Matthijs","family":"V\u00e1k\u00e1r","sequence":"first","affiliation":[{"name":"Columbia University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ohad","family":"Kammar","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sam","family":"Staton","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,1,2]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/788018.788829"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.49"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"J. Adamek and J. Rosicky. 1994. Locally Presentable and Accessible Categories. Cambridge University Press.  J. Adamek and J. Rosicky. 1994. Locally Presentable and Accessible Categories. Cambridge University Press.","DOI":"10.1017\/CBO9780511600579"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209175"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2016.09.031"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2007.02.004"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951942"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158147"},{"key":"e_1_2_2_9_1","volume-title":"Axiomatic Domain Theory in Categories of Partial Maps","author":"Fiore Marcelo P.","unstructured":"Marcelo P. Fiore . 1996. Axiomatic Domain Theory in Categories of Partial Maps . Cambridge University Press . Marcelo P. Fiore. 1996. Axiomatic Domain Theory in Categories of Partial Maps. Cambridge University Press."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1994.316083"},{"key":"e_1_2_2_11_1","volume-title":"Proc. UAI","author":"Goodman Noah","year":"2008","unstructured":"Noah Goodman , Vikash Mansinghka , Daniel M Roy , Keith Bonawitz , and Joshua B Tenenbaum . 2008 . Church: a language for generative models . In Proc. UAI 2008. Noah Goodman, Vikash Mansinghka, Daniel M Roy, Keith Bonawitz, and Joshua B Tenenbaum. 2008. Church: a language for generative models. In Proc. UAI 2008."},{"key":"e_1_2_2_12_1","unstructured":"Noah Goodman and Andreas Stuhlm\u00fcller. 2014. Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org . Online book.  Noah Goodman and Andreas Stuhlm\u00fcller. 2014. Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org . Online book."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.23"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005137"},{"key":"e_1_2_2_15_1","unstructured":"Daniel Huang Greg Morrisett and Bas Spitters. 2018. An application of computable distributions to the semantics of probabilistic programs. (2018). arxiv:1806.07966.  Daniel Huang Greg Morrisett and Bas Spitters. 2018. An application of computable distributions to the semantics of probabilistic programs. (2018). arxiv:1806.07966."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/77350.77370"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(05)80216-6"},{"key":"e_1_2_2_18_1","volume-title":"Foundations of modern probability","author":"Kallenberg Olav","unstructured":"Olav Kallenberg . 2006. Foundations of modern probability . Springer . Olav Kallenberg. 2006. Foundations of modern probability. Springer."},{"key":"e_1_2_2_19_1","volume-title":"Random Measures, Theory and Applications. Probability Theory and Stochastic Modelling","author":"Kallenberg Olav","unstructured":"Olav Kallenberg . 2017. Random Measures, Theory and Applications. Probability Theory and Stochastic Modelling , Vol. 77 . Springer . Olav Kallenberg. 2017. Random Measures, Theory and Applications. Probability Theory and Stochastic Modelling, Vol. 77. Springer."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103698"},{"key":"e_1_2_2_21_1","volume-title":"Classical descriptive set theory","author":"Kechris Alexander","unstructured":"Alexander Kechris . 2012. Classical descriptive set theory . Vol. 156 . Springer Science & amp; Business Media. Alexander Kechris. 2012. Classical descriptive set theory. Vol. 156. Springer Science &amp; Business Media."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129509007555"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03034-5_17"},{"key":"e_1_2_2_24_1","first-page":"97","article-title":"Commutative monads as a theory of distributions","volume":"26","author":"Kock Anders","year":"2012","unstructured":"Anders Kock . 2012 . Commutative monads as a theory of distributions . Theory and Applications of Categories 26 , 4 (2012), 97 \u2013 131 . Anders Kock. 2012. Commutative monads as a theory of distributions. Theory and Applications of Categories 26, 4 (2012), 97\u2013131.","journal-title":"Theory and Applications of Categories"},{"key":"e_1_2_2_25_1","volume-title":"Mathematik Arbeitspapiere","author":"Lawson Jimmy D.","unstructured":"Jimmy D. Lawson . 1982. Valuations on continuous lattices . In Continuous Lattices and Related Topics, Rudolf-Eberhard H\u00f6ffman (Ed.). Mathematik Arbeitspapiere , Vol. 27 . Universitat Bremen , 204\u2013225. Jimmy D. Lawson. 1982. Valuations on continuous lattices. In Continuous Lattices and Related Topics, Rudolf-Eberhard H\u00f6ffman (Ed.). Mathematik Arbeitspapiere, Vol. 27. Universitat Bremen, 204\u2013225."},{"key":"e_1_2_2_26_1","volume-title":"A Functional\/Imperative Synthesis","author":"Levy Paul Blain","unstructured":"Paul Blain Levy . 2004. Call-By-Push-Value : A Functional\/Imperative Synthesis . Kluwer . Paul Blain Levy. 2004. Call-By-Push-Value: A Functional\/Imperative Synthesis. Kluwer."},{"key":"e_1_2_2_27_1","volume-title":"Perov","author":"Mansinghka Vikash K.","year":"2014","unstructured":"Vikash K. Mansinghka , Daniel Selsam , and Yura N . Perov . 2014 . Venture : a higher-order probabilistic programming platform with programmable inference. arXiv:1404.0099 (2014). http:\/\/arxiv.org\/abs\/1404.0099 Vikash K. Mansinghka, Daniel Selsam, and Yura N. Perov. 2014. Venture: a higher-order probabilistic programming platform with programmable inference. arXiv:1404.0099 (2014). http:\/\/arxiv.org\/abs\/1404.0099"},{"key":"e_1_2_2_28_1","volume-title":"Proc. MFPS 2018","author":"McDermott Dylan","year":"2018","unstructured":"Dylan McDermott and Ohad Kammar . 2018 . Factorisation systems for logical relations and monadic lifting in type-and-effect system semantics . Proc. MFPS 2018 (2018). To appear. Dylan McDermott and Ohad Kammar. 2018. Factorisation systems for logical relations and monadic lifting in type-and-effect system semantics. Proc. MFPS 2018 (2018). To appear."},{"key":"e_1_2_2_29_1","volume-title":"Domains and random variables. arXiv preprint arXiv:1607.07698","author":"Mislove Michael W","year":"2016","unstructured":"Michael W Mislove . 2016. Domains and random variables. arXiv preprint arXiv:1607.07698 ( 2016 ). Michael W Mislove. 2016. Domains and random variables. arXiv preprint arXiv:1607.07698 (2016)."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/77350.77353"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935317"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0052"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90044-5"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90003-1"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158148"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90095-B"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009852"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211062"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_32"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935313"},{"key":"e_1_2_2_42_1","volume-title":"On S-Finite Measures and Kernels. arXiv preprint arXiv:1810.01837","author":"V\u00e1k\u00e1r Matthijs","year":"2018","unstructured":"Matthijs V\u00e1k\u00e1r and Luke Ong . 2018. On S-Finite Measures and Kernels. arXiv preprint arXiv:1810.01837 ( 2018 ). Matthijs V\u00e1k\u00e1r and Luke Ong. 2018. On S-Finite Measures and Kernels. arXiv preprint arXiv:1810.01837 (2018)."},{"key":"e_1_2_2_43_1","volume-title":"Proc. AISTATS","author":"Wingate David","year":"2011","unstructured":"David Wingate , Andreas Stuhlm\u00fcller , and Noah Goodman . 2011 . Lightweight implementations of probabilistic programming languages via transformational compilation . In Proc. AISTATS 2011. David Wingate, Andreas Stuhlm\u00fcller, and Noah Goodman. 2011. Lightweight implementations of probabilistic programming languages via transformational compilation. In Proc. AISTATS 2011."},{"key":"e_1_2_2_44_1","volume-title":"Proc. AISTATS","author":"Wood Frank","year":"2014","unstructured":"Frank Wood , Jan Willem van de Meent, and Vikash Mansinghka. 2014. A new approach to probabilistic programming inference . In Proc. AISTATS 2014 . 1024\u20131032. Frank Wood, Jan Willem van de Meent, and Vikash Mansinghka. 2014. A new approach to probabilistic programming inference. In Proc. AISTATS 2014. 1024\u20131032."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3290349","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3290349","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:58:04Z","timestamp":1750193884000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3290349"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,2]]},"references-count":44,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2019,1,2]]}},"alternative-id":["10.1145\/3290349"],"URL":"https:\/\/doi.org\/10.1145\/3290349","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,2]]},"assertion":[{"value":"2019-01-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}