{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T05:21:09Z","timestamp":1776316869034,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,2,11]],"date-time":"2024-02-11T00:00:00Z","timestamp":1707609600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Royal Society University Research Fellowship"},{"name":"ERC Project BLAST, and AFOSR","award":["FA9550\u201321\u20131\u2013003"],"award-info":[{"award-number":["FA9550\u201321\u20131\u2013003"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,2,29]]},"abstract":"<jats:p>We spell out the paradigm of<jats:italic>exact conditioning<\/jats:italic>as an intuitive and powerful way of conditioning on observations in probabilistic programs. This is contrasted with likelihood-based<jats:italic>scoring<\/jats:italic>known from languages such as<jats:sc>Stan<\/jats:sc>. We study exact conditioning in the cases of discrete and Gaussian probability, presenting prototypical languages for each case and giving semantics to them. We make use of categorical probability (namely Markov and CD categories) to give a general account of exact conditioning, which avoids limits and measure theory, instead focusing on restructuring dataflow and program equations. The correspondence between such categories and a class of programming languages is made precise by defining the internal language of a CD category.<\/jats:p>","DOI":"10.1145\/3632170","type":"journal-article","created":{"date-parts":[[2023,11,11]],"date-time":"2023-11-11T09:38:20Z","timestamp":1699695500000},"page":"1-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Probabilistic Programming with Exact Conditions"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-1445-4508","authenticated-orcid":false,"given":"Dario","family":"Stein","sequence":"first","affiliation":[{"name":"Radboud University Nijmegen, The Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0141-8922","authenticated-orcid":false,"given":"Sam","family":"Staton","sequence":"additional","affiliation":[{"name":"University of Oxford, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2024,2,11]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"836","article-title":"Categories in control","volume":"30","author":"Baez John C.","year":"2015","unstructured":"John C. Baez and Jason Erbele. 2015. Categories in control. Theory Appl. Categ. 30 (2015), 836\u2013881. arxiv:1405.6881 [math.CT]","journal-title":"Theory Appl. Categ."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2020.123883"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","unstructured":"Filippo Bonchi Robin Piedeleu Pawel Sobocinski and Fabio Zanasi. 2019. Graphical affine algebra. 34th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201919) Vancouver BC Canada 1\u201312. DOI:10.1109\/LICS.2019.8785877","DOI":"10.1109\/LICS.2019.8785877"},{"key":"e_1_3_3_5_2","doi-asserted-by":"crossref","unstructured":"Filippo Bonchi Pawel Sobocinski and Fabio Zanasi. 2017. The calculus of signal flow diagrams I: Linear relations on streams. Information and Computation 252 (2017) 2\u201329.","DOI":"10.1016\/j.ic.2016.03.002"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v076.i01"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129518000488"},{"key":"e_1_3_3_8_2","unstructured":"Bryce Clarke Derek Elkins Jeremy Gibbons Fosco Loregian Bartosz Milewski Emily Pillmore and Mario Roman. 2020. Profunctor Optics a Categorical Update. (2020). arxiv:2001.07488."},{"key":"e_1_3_3_9_2","article-title":"Probabilistic (logic) programming concepts","author":"Raedt L. De","year":"2015","unstructured":"L. De Raedt and A. Kimming. 2015. Probabilistic (logic) programming concepts. Machine Learning 100 (2015), 5\u201347.","journal-title":"Machine Learning"},{"key":"e_1_3_3_10_2","article-title":"Multivariate statistics: A vector space approach","author":"Eaton Morris L.","year":"2007","unstructured":"Morris L. Eaton. 2007. Multivariate statistics: A vector space approach. Institute of Mathematical Statistics Lecture Notes - Monograph Series 53 (2007), 512.","journal-title":"Institute of Mathematical Statistics Lecture Notes - Monograph Series"},{"key":"e_1_3_3_11_2","volume-title":"Causal Theories: A Categorical Perspective on Bayesian Networks","author":"Fong Brendan","year":"2012","unstructured":"Brendan Fong. 2012. Causal Theories: A Categorical Perspective on Bayesian Networks. Ph. D. Dissertation. University of Oxford."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2020.107239"},{"key":"e_1_3_3_13_2","unstructured":"T. Fritz Tom\u00e1\u0161 Gonda P. Perrone and Eigil Fjeldgren Rischel. 2020. Representable Markov Categories and Comparison of Statistical Experiments in Categorical Probability 107\u2013239. https:\/\/arxiv.org\/abs\/2010.07416"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.32408\/compositionality-2-3"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/646794.704862"},{"key":"e_1_3_3_16_2","volume-title":"Computer Aided Verification 2016","author":"Gehr Timon","year":"2016","unstructured":"Timon Gehr, Sasa Misailovic, and Martin Vechev. 2016. PSI: Exact symbolic inference for probabilistic programs. In Computer Aided Verification 2016."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0092872"},{"issue":"1","key":"e_1_3_3_18_2","first-page":"62","article-title":"Monoidal Kleisli category as a background for information transformers theory","volume":"2","author":"Golubtsov Peter V.","year":"2002","unstructured":"Peter V. Golubtsov. 2002. Monoidal Kleisli category as a background for information transformers theory. Information Theory and Information Processing 2, 1 (2002), 62\u201384.","journal-title":"Information Theory and Information Processing"},{"key":"e_1_3_3_19_2","unstructured":"Noah D. Goodman and Andreas Stuhlm\u00fcller. 2014. The Design and Implementation of Probabilistic Programming Languages. Retrieved August 3 2021 from http:\/\/dippl.org"},{"key":"e_1_3_3_20_2","unstructured":"Noah D. Goodman and Joshua B. Tenenbaum. 2016. Probabilistic Models of Cognition. Retrieved March 26 2021 from http:\/\/probmods.org"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.01.001"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.343"},{"key":"e_1_3_3_23_2","volume-title":"Proceedings of the 15th International Conference on Quantum Physics and Logic 2018","author":"Huot Mathieu","year":"2018","unstructured":"Mathieu Huot and Sam Staton. 2018. Universal properties in quantum theory. In Proceedings of the 15th International Conference on Quantum Physics and Logic 2018."},{"key":"e_1_3_3_24_2","unstructured":"Infernet [n. d.]. Infer.NET Tutorial 3: Learning a Gaussian. https:\/\/dotnet.github.io\/infer\/userguide\/Learning%20a%20Gaussian%20tutorial.html"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129519000082"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","unstructured":"Jules Jacobs. 2021. Paradoxes of probabilistic programming: And how to condition on events of measure zero with infinitesimal probabilities. In Proceedings of the ACM on Programming Languages 5. (POPL\u201921) 1\u201326.","DOI":"10.1145\/3434339"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790423"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(91)90003-P"},{"key":"e_1_3_3_29_2","volume-title":"Foundations of Modern Probability","author":"Kallenberg Olav","year":"1997","unstructured":"Olav Kallenberg. 1997. Foundations of Modern Probability. Springer, New York."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103698"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","unstructured":"Steffen Lauritzen and Frank Jensen. 1999. Stable local computation with conditional Gaussian distributions. Statistics and Computing 11 (2001) 191\u2013203. DOI:10.1023\/A:1008935617754","DOI":"10.1023\/A:1008935617754"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00088-9"},{"key":"e_1_3_3_33_2","volume-title":"Categories for the Working Mathematician","author":"MacLane Saunders","year":"1971","unstructured":"Saunders MacLane. 1971. Categories for the Working Mathematician. Springer-Verlag. ix+262 pages. Graduate Texts in Mathematics, Vol. 5."},{"key":"e_1_3_3_34_2","unstructured":"T. Minka J. M. Winn J. P. Guiver Y. Zaykov D. Fabian and J. Bronskill. 2018. Infer.NET 0.3. Microsoft Research Cambridge. http:\/\/dotnet.github.io\/infer."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1989.39155"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90052-4"},{"key":"e_1_3_3_37_2","first-page":"1037","volume-title":"Proceedings of the 21st International Conference on Artificial Intelligence and Statistics","author":"Murray Lawrence","year":"2018","unstructured":"Lawrence Murray, Daniel Lund\u00e9n, Jan Kudlicka, David Broman, and Thomas Sch\u00f6n. 2018. Delayed sampling and automatic Rao-Blackwellization of probabilistic programs. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics. 1037\u20131046."},{"key":"e_1_3_3_38_2","volume-title":"Workshop on Program Transformations for Machine Learning","author":"Narayanan Praveen","year":"2019","unstructured":"Praveen Narayanan and Chung-chieh Shan. 2019. Applications of a disintegration transformation. In Workshop on Program Transformations for Machine Learning."},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.08.006"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129597002375"},{"key":"e_1_3_3_41_2","doi-asserted-by":"crossref","DOI":"10.1080\/00031305.1998.10480576","article-title":"Expect the unexpected from conditional expectation","author":"Proschan Michael A.","year":"1998","unstructured":"Michael A. Proschan and Brett Presnell. 1998. Expect the unexpected from conditional expectation. The American Statistician 52, 3 (1998), 248\u2013252.","journal-title":"The American Statistician"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12821-9_4"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009852"},{"key":"e_1_3_3_44_2","unstructured":"Toby St Clere Smithe. 2020. Bayesian Updates Compose Optically. arxiv:2006.01631 [math.CT] https:\/\/arxiv.org\/abs\/2006.01631"},{"key":"e_1_3_3_45_2","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/978-3-642-37075-5_26","volume-title":"Foundations of Software Science and Computation Structures","author":"Staton Sam","year":"2013","unstructured":"Sam Staton. 2013. An algebraic presentation of predicate logic. In Foundations of Software Science and Computation Structures, Frank Pfenning (Ed.). Springer, Berlin, 401\u2013417."},{"key":"e_1_3_3_46_2","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1007\/978-3-662-54434-1_32","volume-title":"Programming Languages and Systems","author":"Staton Sam","year":"2017","unstructured":"Sam Staton. 2017. Commutative semantics for probabilistic programming. In Programming Languages and Systems, Hongseok Yang (Ed.). Springer, Berlin, 855\u2013879."},{"key":"e_1_3_3_47_2","article-title":"The Beta-Bernoulli process and algebraic effects","author":"Staton Sam","year":"2018","unstructured":"Sam Staton, Dario Stein, Hongseok Yang, Nathanael Ackerman, Cameron Freer, and Daniel Roy. 2018. The Beta-Bernoulli process and algebraic effects. In Proceedings of 45th International Colloquium on Automata, Languages and Programming (ICALP \u201918). http:\/\/arxiv.org\/abs\/1802.09598","journal-title":"Proceedings of 45th International Colloquium on Automata, Languages and Programming (ICALP \u201918)"},{"key":"e_1_3_3_48_2","unstructured":"Dario Stein. 2021. GaussianInfer. https:\/\/github.com\/damast93\/GaussianInfer"},{"key":"e_1_3_3_49_2","volume-title":"Structural Foundations for Probabilistic Programming Languages","author":"Stein Dario","year":"2021","unstructured":"Dario Stein. 2021. Structural Foundations for Probabilistic Programming Languages. Ph. D. Dissertation. University of Oxford."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470552"},{"key":"e_1_3_3_51_2","unstructured":"Jan-Willem van de Meent Brooks Paige Hongseok Yang and Frank Wood. 2018. An Introduction to Probabilistic Programming. arxiv:1809.10756 [stat.ML]"},{"key":"e_1_3_3_52_2","doi-asserted-by":"crossref","unstructured":"Rajan Walia Praveen Narayanan Jacques Carette Sam Tobin-Hochstadt and Chung-chieh Shan. 2019. From high-level inference algorithms to efficient code. In Proceedings of the ACM on Programming Languages 3 (ICFP\u201919) 1\u201330.","DOI":"10.1145\/3341702"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/b105056"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632170","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632170","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:49:55Z","timestamp":1750286995000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,11]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2,29]]}},"alternative-id":["10.1145\/3632170"],"URL":"https:\/\/doi.org\/10.1145\/3632170","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,11]]},"assertion":[{"value":"2022-07-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}