{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T20:31:07Z","timestamp":1792787467556,"version":"4.5.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T00:00:00Z","timestamp":1775779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"Austrian Science Fund","award":["10.55776\/PIN3275223"],"award-info":[{"award-number":["10.55776\/PIN3275223"]}],"id":[{"id":"https:\/\/ror.org\/013tf3c58","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Austrian Research Promotion Agency (FFG), federal states of Styria, Upper Austria and Tyrol","award":["886385"],"award-info":[{"award-number":["886385"]}],"id":[{"id":"https:\/\/ror.org\/028jc0449","id-type":"ROR","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,4,10]]},"abstract":"<jats:p>It is commonly known that any Bayesian network can be implemented as a probabilistic program, but the reverse direction is not so clear. In this work, we address the open question to what extent a probabilistic program with user-labelled sample statements and while loops \u2013 features found in languages like Gen, Turing, and Pyro \u2013 can be represented graphically. To this end, we extend existing operational semantics to support these language features. By translating a program to its control-flow graph, we define a sound static analysis that approximates the dependency structure of the random variables in the program. As a result, we obtain a static factorisation of the implicitly defined program density, which is equivalent to the known Bayesian network factorisation for programs without loops and constant labels, but constitutes a novel graphical representation for programs that define an unbounded number of random variables via loops or dynamic labels. We further develop a sound program slicing technique to leverage this structure to statically enable three well-known optimisations for the considered program class: we reduce the variance of gradient estimates in variational inference and we speed up both single-site Metropolis Hastings and sequential Monte Carlo. These optimisations are proven correct and empirically shown to match or outperform existing techniques.<\/jats:p>","DOI":"10.1145\/3798223","type":"journal-article","created":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T14:33:43Z","timestamp":1775831623000},"page":"653-680","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Static Factorisation of Probabilistic Programs with User-Labelled Sample Statements and While Loops"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-6704-5903","authenticated-orcid":false,"given":"Markus","family":"B\u00f6ck","sequence":"first","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8619-1271","authenticated-orcid":false,"given":"J\u00fcrgen","family":"Cito","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,4,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","unstructured":"George K Baah Andy Podgurski and Mary Jean Harrold. 2008. The probabilistic program dependence graph and its application to fault diagnosis. In Proceedings of the 2008 international symposium on Software testing and analysis. 189\u2013200. doi:10.1145\/1390630.1390654","DOI":"10.1145\/1390630.1390654"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108770750"},{"key":"e_1_3_2_4_2","unstructured":"Ryan Bernstein. 2019. Static analysis for probabilistic programs. arXiv preprint arXiv:1909.05076 (2019)."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.7916\/D5Y3-6F17"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","unstructured":"Ryan Bernstein Matthijs V\u00e1k\u00e1r and Jeannette Wing. 2020. Transforming probabilistic programs for model checking. In Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference. 149\u2013159. doi:10.1145\/3412815.3416896","DOI":"10.1145\/3412815.3416896"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/3322706.3322734"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","unstructured":"Markus B\u00f6ck Michael Schr\u00f6der and J\u00fcrgen Cito. 2024. Language-Agnostic Static Analysis of Probabilistic Programs. In Proceedings of the 39th IEEE\/ACM International Conference on Automated Software Engineering. 78\u201390. doi:10.1145\/3691620.3695031","DOI":"10.1145\/3691620.3695031"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19718-5_5"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951942"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","unstructured":"Markus B\u00f6ck. 2026. Static Factorisation of Probabilistic Programs With User-Labelled Sample Statements and While Loops. doi:10.5281\/zenodo.18482696","DOI":"10.5281\/zenodo.18482696"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17184-1_12"},{"issue":"6","key":"e_1_3_2_13_2","article-title":"Sublinear approximate inference for probabilistic programs","volume":"1050","author":"Chen Yutian","year":"2014","unstructured":"Yutian Chen, Vikash Mansinghka, and Zoubin Ghahramani. 2014. Sublinear approximate inference for probabilistic programs. stat 1050 (2014), 6.","journal-title":"stat"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3437-9_1"},{"key":"e_1_3_2_15_2","volume-title":"Engineering a compiler","author":"Cooper Keith D","year":"2011","unstructured":"Keith D Cooper and Linda Torczon. 2011. Engineering a compiler. Elsevier."},{"key":"e_1_3_2_16_2","unstructured":"Marco Cusumano-Towner Alexander K Lew and Vikash K Mansinghka. 2020. Automating involutive MCMC using probabilistic and differentiable programming. arXiv preprint arXiv:2007.09871 (2020)."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/AAI28791178"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","unstructured":"Marco F Cusumano-Towner Feras A Saad Alexander K Lew and Vikash K Mansinghka. 2019. Gen: a general-purpose probabilistic programming system with programmable inference. In Proceedings of the 40th acm sigplan conference on programming language design and implementation. 221\u2013236. doi:10.1145\/3314221.3314642","DOI":"10.1145\/3314221.3314642"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371125"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632926"},{"key":"e_1_3_2_21_2","first-page":"1682","volume-title":"International conference on artificial intelligence and statistics","author":"Ge Hong","year":"2018","unstructured":"Hong Ge, Kai Xu, and Zoubin Ghahramani. 2018. Turing: a language for flexible probabilistic inference. In International conference on artificial intelligence and statistics. PMLR, 1682\u20131690."},{"key":"e_1_3_2_22_2","first-page":"220","volume-title":"UAI 2008, Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence, Helsinki, Finland, July 9-12, 2008","author":"Goodman Noah D.","year":"2008","unstructured":"Noah D. Goodman, Vikash K. Mansinghka, Daniel M. Roy, Kallista A. Bonawitz, and Joshua B. Tenenbaum. 2008. Church: a language for generative models. In UAI 2008, Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence, Helsinki, Finland, July 9-12, 2008, David A. McAllester and Petri Myllym\u00e4ki (Eds.). AUAI Press, 220\u2013229."},{"key":"e_1_3_2_23_2","unstructured":"Noah D Goodman and Andreas Stuhlm\u00fcller. 2014. The Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org. Accessed: 2025-3-20."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2593882.2593900"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3290348"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3490421"},{"key":"e_1_3_2_27_2","unstructured":"John L Hennessy and David A Patterson. 2011. Computer architecture: a quantitative approach. Elsevier."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005137"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428208"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594303"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.FSTTCS.2015.475"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/1795555"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.38"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371084"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371087"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591290"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","unstructured":"Daniel Lund\u00e9n Johannes Borgstr\u00f6m and David Broman. 2021. Correctness of Sequential Monte Carlo Inference for Probabilistic Programming Languages.. In ESOP. 404\u2013431. doi:10.1007\/978-3-030-72019-3_15","DOI":"10.1007\/978-3-030-72019-3_15"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008929526011"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-72019-3_16"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","unstructured":"Vikash K Mansinghka Ulrich Schaechtle Shivam Handa Alexey Radul Yutian Chen and Martin Rinard. 2018. Probabilistic programming with programmable inference. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation. 603\u2013616. doi:10.1145\/3192366.3192409","DOI":"10.1145\/3192366.3192409"},{"key":"e_1_3_2_41_2","article-title":"Factorie: Probabilistic programming via imperatively defined factor graphs","volume":"22","author":"McCallum Andrew","year":"2009","unstructured":"Andrew McCallum, Karl Schultz, and Sameer Singh. 2009. Factorie: Probabilistic programming via imperatively defined factor graphs. Advances in Neural Information Processing Systems 22 (2009).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_42_2","first-page":"1352","volume-title":"IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30 - August 5, 2005","author":"Milch Brian","year":"2005","unstructured":"Brian Milch, Bhaskara Marthi, Stuart Russell, David A. Sontag, Daniel L. Ong, and Andrey Kolobov. 2005. BLOG: Probabilistic Models with Unknown Objects. In IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30 - August 5, 2005, Leslie Pack Kaelbling and Alessandro Saffiotti (Eds.). Professional Book Center, 1352\u20131359."},{"key":"e_1_3_2_43_2","first-page":"238","volume-title":"International Workshop on Artificial Intelligence and Statistics","author":"Milch Brian","year":"2005","unstructured":"Brian Milch, Bhaskara Marthi, David Sontag, Stuart Russell, Daniel L Ong, and Andrey Kolobov. 2005. Approximate inference for infinite contingent Bayesian networks. In International Workshop on Artificial Intelligence and Statistics. PMLR, 238\u2013245."},{"key":"e_1_3_2_44_2","unstructured":"Tom Minka. 2012. Infer. NET 2.5. http:\/\/research.microsoft.com\/infernet (2012)."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.ARCONTROL.2018.10.013"},{"key":"e_1_3_2_46_2","unstructured":"John Paisley David Blei and Michael Jordan. 2012. Variational Bayesian inference with stochastic search. arXiv preprint arXiv:1206.6430 (2012)."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-72019-3_19"},{"key":"e_1_3_2_48_2","first-page":"814","volume-title":"Artificial intelligence and statistics","author":"Ranganath Rajesh","year":"2014","unstructured":"Rajesh Ranganath, Sean Gerrish, and David Blei. 2014. Black box variational inference. In Artificial intelligence and statistics. PMLR, 814\u2013822."},{"key":"e_1_3_2_49_2","first-page":"28","volume-title":"Artificial Intelligence and Statistics","author":"Ritchie Daniel","year":"2016","unstructured":"Daniel Ritchie, Andreas Stuhlm\u00fcller, and Noah Goodman. 2016. C3: Lightweight incrementalized MCMC for probabilistic programs using continuations and callsite caching. In Artificial Intelligence and Statistics. PMLR, 28\u201337."},{"key":"e_1_3_2_50_2","article-title":"Sticking the landing: Simple, lower-variance gradient estimators for variational inference","volume":"30","author":"Roeder Geoffrey","year":"2017","unstructured":"Geoffrey Roeder, Yuhuai Wu, and David K Duvenaud. 2017. Sticking the landing: Simple, lower-variance gradient estimators for variational inference. Advances in Neural Information Processing Systems 30 (2017).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","unstructured":"Feras A Saad Martin C Rinard and Vikash K Mansinghka. 2021. SPPL: probabilistic programming with fast exact symbolic inference. In Proceedings of the 42nd acm sigplan international conference on programming language design and implementation. 804\u2013819. doi:10.1145\/3453483.3454078","DOI":"10.1145\/3453483.3454078"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.7717\/PEERJ-CS.55"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","unstructured":"Adrian Sampson Pavel Panchekha Todd Mytkowicz Kathryn S McKinley Dan Grossman and Luis Ceze. 2014. Expressing and verifying probabilistic assertions. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation. 112\u2013122. doi:10.1145\/2594291.2594294","DOI":"10.1145\/2594291.2594294"},{"key":"e_1_3_2_54_2","article-title":"Gradient estimation using stochastic computation graphs","volume":"28","author":"Schulman John","year":"2015","unstructured":"John Schulman, Nicolas Heess, Theophane Weber, and Pieter Abbeel. 2015. Gradient estimation using stochastic computation graphs. Advances in neural information processing systems 28 (2015).","journal-title":"Advances in neural information processing systems"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","unstructured":"Sam Staton Hongseok Yang Frank Wood Chris Heunen and Ohad Kammar. 2016. Semantics for probabilistic programming: higher-order functions continuous distributions and soft constraints. In Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science. 525\u2013534. doi:10.1145\/2933575.2935313","DOI":"10.1145\/2933575.2935313"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23461-8_36"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3290349"},{"key":"e_1_3_2_58_2","unstructured":"Jan-Willem van de Meent Brooks Paige Hongseok Yang and Frank Wood. 2018. An introduction to probabilistic programming. arXiv preprint arXiv:1809.10756 (2018)."},{"key":"e_1_3_2_59_2","first-page":"770","volume-title":"Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics","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 Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings, 770\u2013778."},{"key":"e_1_3_2_60_2","first-page":"3637","volume-title":"Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016","author":"Wu Yi","year":"2016","unstructured":"Yi Wu, Lei Li, Stuart Russell, and Rastislav Bod\u00edk. 2016. Swift: Compiled Inference for Probabilistic Programming Languages. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, Subbarao Kambhampati (Ed.). IJCAI\/AAAI Press, 3637\u20133645."},{"key":"e_1_3_2_61_2","first-page":"1068","volume-title":"Artificial Intelligence and Statistics","author":"Yang Lingfeng","year":"2014","unstructured":"Lingfeng Yang, Patrick Hanrahan, and Noah Goodman. 2014. Generating efficient MCMC kernels from probabilistic programs. In Artificial Intelligence and Statistics. PMLR, 1068\u20131076."},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889774"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798223","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T11:22:32Z","timestamp":1790421752000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798223"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,10]]},"references-count":61,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2026,4,10]]}},"alternative-id":["10.1145\/3798223"],"URL":"https:\/\/doi.org\/10.1145\/3798223","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,10]]},"assertion":[{"value":"2025-10-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-17","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}