{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,25]],"date-time":"2026-09-25T04:23:47Z","timestamp":1790310227749,"version":"4.1.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T00:00:00Z","timestamp":1767830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100014013","name":"UKRI","doi-asserted-by":"crossref","award":["MR\/V024299\/1"],"award-info":[{"award-number":["MR\/V024299\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/X037029\/1"],"award-info":[{"award-number":["EP\/X037029\/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":[[2026,1,8]]},"abstract":"<jats:p>Bayesian probabilistic programming languages (BPPLs) let users denote statistical models as code while the interpreter infers the posterior distribution. The semantics of BPPLs are usually mathematically complex and unable to reason about desirable properties such as expected values and independence of random variables. To reason about these properties in a non-Bayesian setting, probabilistic separation logics such as PSL and Lilac interpret separating conjunction as probabilistic independence of random variables. However, no existing separation logic can handle Bayesian updating, which is the key distinguishing feature of BPPLs.<\/jats:p>\n                  <jats:p>\n                    To close this gap, we introduce Bayesian separation logic (\n                    <jats:sc>BaSL<\/jats:sc>\n                    ), a probabilistic separation logic that gives semantics to BPPL. We prove an internal version of Bayes\u2019 theorem using a result in measure theory known as the Rokhlin-Simmons disintegration theorem. Consequently,\n                    <jats:sc>BaSL<\/jats:sc>\n                    can model probabilistic programming concepts such as Bayesian updating, unnormalised distribution, conditional distribution, soft constraint, conjugate prior and improper prior while maintaining modularity via the frame rule. The model of\n                    <jats:sc>BaSL<\/jats:sc>\n                    is based on a novel instantiation of Kripke resource monoid via \ud835\udf0e-finite measure spaces over the Hilbert cube, and the semantics of Hoare triple is compatible with an existing denotational semantics of BPPL based on the category of s-finite kernels. Using\n                    <jats:sc>BaSL<\/jats:sc>\n                    , we then prove properties of statistical models such as the expected value of Bayesian coin flip, correlation of random variables in the collider Bayesian network, the posterior distributions of the burglar alarm model, a parameter estimation algorithm, and the Gaussian mixture model.\n                  <\/jats:p>","DOI":"10.1145\/3776696","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T18:59:43Z","timestamp":1767898783000},"page":"1557-1585","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Bayesian Separation Logic: A Logical Foundation and Axiomatic Semantics for Probabilistic Programming"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-4483-5841","authenticated-orcid":false,"given":"Shing Hin","family":"Ho","sequence":"first","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4161-985X","authenticated-orcid":false,"given":"Nicolas","family":"Wu","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2319-3242","authenticated-orcid":false,"given":"Azalea","family":"Raad","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-33143-6"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","unstructured":"Jialu Bao Simon Docherty Justin Hsu and Alexandra Silva. 2021a. A Bunched Logic for Conditional Independence. In 2021 36th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). 1\u201314. doi:10.1109\/LICS52264.2021.9470712","DOI":"10.1109\/LICS52264.2021.9470712"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3704894"},{"key":"e_1_3_2_5_1","unstructured":"Jialu Bao Marco Gaboardi Justin Hsu and Joseph Tassarotti. 2021b. A Separation Logic for Negative Dependence. CoRR abs\/2111.14917 (2021). arXiv:2111.14917 https:\/\/arxiv.org\/abs\/2111.14917"},{"key":"e_1_3_2_6_1","unstructured":"Gilles Barthe Justin Hsu and Kevin Liao. 2019. A Probabilistic Separation Logic. CoRR abs\/1907.10708 (2019). arXiv:1907.10708 https:\/\/arxiv.org\/abs\/1907.10708"},{"key":"e_1_3_2_7_1","volume-title":"Probability and measure","author":"Billingsley Patrick","year":"1995","unstructured":"Patrick Billingsley. 1995. Probability and measure (3. ed ed.). Wiley, New York [u.a.].","edition":"3"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","unstructured":"JohannesBorgstr\u00f6m Dal LagoUgo Andrew Gordon and Marcin Szymczak. 2016. A lambda-calculus foundation for universal probabilistic programming. SIGPLAN Not. 51 9 (Sept. 2016) 33\u201346. doi:10.1145\/3022670.2951942","DOI":"10.1145\/3022670.2951942"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1201\/b10905"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.30"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v076.i01"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-9574.00056"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3408998"},{"key":"e_1_3_2_14_1","doi-asserted-by":"crossref","unstructured":"Ulices Santa Cruz and Yasser Shoukry. 2022. NNLander-VeriF: A Neural Network Formal Verification Framework for Vision-Based Autonomous Aircraft Landing. arXiv:2203.15841[cs.LG] https:\/\/arxiv.org\/abs\/2203.15841","DOI":"10.1007\/978-3-031-06773-0_11"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","unstructured":"Marco Cusumano-Towner Feras Saad Alexander Lew Vikash 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 (PLDI 2019). 221\u2013236 doi:10.1145\/3314221.3314642","DOI":"10.1145\/3314221.3314642"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371125"},{"key":"e_1_3_2_17_1","unstructured":"David Fremlin. 2011. Measure Theory: Topological Measure Spaces. Volume 4. Torres Fremlin."},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129505004858"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1984.4767596"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593882.2593900"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","unstructured":"Chris Heunen Ohad Kammar Sam Staton and Hongseok Yang. 2017. A convenient category for higher-order probability theory (LICS\u201917). IEEE Press Article 77 12pages. doi:10.5555\/3329995.3330072","DOI":"10.5555\/3329995.3330072"},{"key":"e_1_3_2_22_1","unstructured":"Shing Hin Ho Nicolas Wu Azalea Raad. 2025. Bayesian Separation Logic. arXiv:2507.15530[cs.PL] https:\/\/arxiv.org\/abs\/2507.15530"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","unstructured":"Mathieu Huot Alexander Lew Vikash Mansinghka and Sam Staton. 2023. \u03c9PAP Spaces: Reasoning Denotationally About Higher-Order Recursive Probabilistic and Differentiable Programs. In 2023 38th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). 1\u201314. doi:10.1109\/LICS56636.2023.10175739","DOI":"10.1109\/LICS56636.2023.10175739"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1989.39173"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","unstructured":"Ralf Jung Robbert Krebbers Jacques-Henri Jourdan Ale\u0161 Bizjak Lars Birkedal and Derek Dreyer. 2018. Iris from the ground up: A modular foundation for higher-order concurrent separation logic. Journal of Functional Programming 28 (2018) ed20. doi:10.1017\/S0956796818000151","DOI":"10.1017\/S0956796818000151"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-14(4:6)2018"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90036-2"},{"key":"e_1_3_2_28_1","volume-title":"An Introduction","author":"Lee Peter M.","year":"2012","unstructured":"Peter M. Lee. 2012. Bayesian Statistics: An Introduction (4th ed.). Wiley Publishing.","edition":"4"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591226"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3661814.3662135"},{"key":"e_1_3_2_31_1","unstructured":"Carol Mak Fabian Zaiser and Luke Ong. 2021. Nonparametric Hamiltonian Monte Carlo. In Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research Vol. 139). PMLR 7336\u20137347. https:\/\/proceedings.mlr.press\/v139\/mak21a.html"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","unstructured":"Cristina Matache Sean Moss and Sam Staton. 2022. Concrete categories and higher-order recursion: With applications including probability differentiability and full abstraction (LICS\u201922). Article 57 14 pages.doi:10.1145\/3531130.3533370","DOI":"10.1145\/3531130.3533370"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1201\/9780429029608"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s43441-023-00515-3"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.2307\/421090"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","unstructured":"Peter Orbanz and Yee Teh. 2017. Bayesian Nonparametric Models. 107\u2013116. doi:10.1007\/978-1-4899-7687-1_928","DOI":"10.1007\/978-1-4899-7687-1_928"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2002.1029817"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290351"},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","DOI":"10.3934\/dcds.2012.32.2565"},{"key":"e_1_3_2_41_1","doi-asserted-by":"crossref","unstructured":"Natalia Slusarz Ekaterina Komendantskaya Matthew L. Daggitt and Robert Stewart. 2022. Differentiable Logics for Neural Network Training and Verification. arXiv:2207.06741[cs.AI] https:\/\/arxiv.org\/abs\/2207.06741","DOI":"10.1007\/978-3-031-21222-2_5"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_32"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108770750.003"},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290377"},{"key":"e_1_3_2_45_1","unstructured":"David Tolpin Jan-Willem van de Meent Hongseok Yang and Frank Wood. 2016. Design and Implementation of Probabilistic Programming Language Anglican. CoRR abs\/1608.05263 (2016). arXiv: 1608.05263http:\/\/arxiv.org\/abs\/1608.05263"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290349"},{"key":"e_1_3_2_47_1","unstructured":"Jan-Willem van de Meent Brooks Paige Hongseok Yang and Frank Wood. 2021. An Introduction to Probabilistic Programming. arXiv:1809.10756 [stat.ML] https:\/\/arxiv.org\/abs\/1809.10756"},{"key":"e_1_3_2_48_1","unstructured":"Matthijs V\u00e1k\u00e1r and Luke Ong. 2018. On S-Finite Measures and Kernels. arXiv:1810.01837 [math.PR] https:\/\/arxiv.org\/abs\/1810.01837"},{"key":"e_1_3_2_49_1","unstructured":"Noam Zilberstein Alexandra Silva and Joseph Tassarotti. 2024. Probabilistic Concurrent Reasoning in Outcome Logic: Independence Conditioning and Invariants. arXiv:2411.11662 [cs.LO] https:\/\/arxiv.org\/abs\/2411.11662"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3776696","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T13:40:01Z","timestamp":1784209201000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3776696"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":48,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2026,1,8]]}},"alternative-id":["10.1145\/3776696"],"URL":"https:\/\/doi.org\/10.1145\/3776696","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-07-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}