{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T15:38:32Z","timestamp":1787067512197,"version":"build-2736575974"},"reference-count":121,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T00:00:00Z","timestamp":1736208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,1,7]]},"abstract":"<jats:p>\n                    <jats:italic toggle=\"yes\">Imprecise probability<\/jats:italic>\n                    is concerned with uncertainty about which probability distributions to use. It has applications in robust statistics and machine learning.\n                  <\/jats:p>\n                  <jats:p>We look at programming language models for imprecise probability. Our desiderata are that we would like our model to support all kinds of composition, categorical and monoidal; in other words, guided by dataflow diagrams. Another equivalent perspective is that we would like a model of synthetic probability in the sense of Markov categories.<\/jats:p>\n                  <jats:p>Imprecise probability can be modelled in various ways, with the leading monad-based approach using convex sets of probability distributions. This model is not fully compositional because the monad involved is not commutative, meaning it does not have a proper monoidal structure. In this work, we provide a new fully compositional account. The key idea is to name the non-deterministic choices. To manage the renamings and disjointness of names, we use graded monads. We show that the resulting compositional model is maximal and relate it with the earlier monadic approach, proving that we obtain tighter bounds on the uncertainty.<\/jats:p>","DOI":"10.1145\/3704890","type":"journal-article","created":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T05:48:42Z","timestamp":1736401722000},"page":"1596-1626","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Compositional Imprecise Probability: A Solution from Graded Monads and Markov Categories"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-7121-8095","authenticated-orcid":false,"given":"Jack","family":"Liell-Cock","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0141-8922","authenticated-orcid":false,"given":"Sam","family":"Staton","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,1,9]]},"reference":[{"key":"e_1_3_2_2_2","article-title":"Diagrammatic Reasoning about Probability and Nondeterminism","author":"Abou-Saleh F.","year":"2016","unstructured":"F. Abou-Saleh, K.-H. Cheung, and j. Gibbons. 2016. Diagrammatic Reasoning about Probability and Nondeterminism. In Proc. PPS 2016.","journal-title":"Proc. PPS 2016"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632903"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54108-7_2"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-11(1:3)2015"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-48935-1_3"},{"key":"e_1_3_2_7_2","unstructured":"A. Appel and V. Kosoy. 2020. Basic inframeasure theory. LessWrong. https:\/\/www.lesswrong.com\/posts\/YAa4qcMyoucRS2Ykr\/basic-inframeasure-theory."},{"key":"e_1_3_2_8_2","unstructured":"A. Appel and V. Kosoy. 2021. Inframeasures and domain theory. LessWrong. https:\/\/www.lesswrong.com\/posts\/vrbidMiczaoHBhZGp\/inframeasures-and-domain-theory."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2024.107676"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1863597.1863607"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","unstructured":"L. Aslett F. Coolen and j. Bock. 2022. Uncertainty in Engineering: Introduction to Methods and Applications. https:\/\/doi.org\/10.1007\/978-3-030-83640-5 10.1007\/978-3-030-83640-5","DOI":"10.1007\/978-3-030-83640-5"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2016.09.031"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1257\/aer.20130930"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jebo.2019.04.009"},{"key":"e_1_3_2_15_2","unstructured":"j. Bernoulli. 1713. Ars conjectandi opus posthumum. Thurneysen."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785673"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CALCO.2021.11"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1088"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2023.24"},{"key":"e_1_3_2_20_2","unstructured":"M. Caprio S. Dutta K. j. jang V. Lin R. Ivanov O. Sokolsky and I. Lee. 2024. Credal Bayesian Deep Learning. arXiv:2302.09656 [cs.LG]"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(93)90035-R"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","unstructured":"G. L. Cattani M. P. Fiore and G. Winskel. 1998. A Theory of Recursive Domains with Applications to Concurrency. In Proc. LICS 1998. https:\/\/doi.org\/10.1109\/LICS.1998.705658 10.1109\/LICS.1998.705658","DOI":"10.1109\/LICS.1998.705658"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1093\/restud\/rdad072"},{"key":"e_1_3_2_24_2","unstructured":"K.-H. Cheung. 2017. Distributive Interaction of Algebraic Effects. Ph. D. Dissertation. University of Oxford. https:\/\/ora.ox.ac.uk\/objects\/uuid:66106628-0a71-4564-bc34-c398db766818"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","unstructured":"j. R. B. Cockett. 1993. Introduction to distributive categories. Math. Struct. Comput. Sci. 3 3 (1993) 277\u2013307. https:\/\/doi.org\/10.1017\/S0960129500000232 10.1017\/S0960129500000232","DOI":"10.1017\/S0960129500000232"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","unstructured":"P.-L. Curien R. Garner and M. Hofmann. 2014. Revisiting the categorical interpretation of dependent type theory. Theoretical Computer Science 546 (August 2014) 99\u2013119. https:\/\/doi.org\/10.1016\/j.tcs.2014.03.003 10.1016\/j.tcs.2014.03.003","DOI":"10.1016\/j.tcs.2014.03.003"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","unstructured":"F. Dahlqvist L. Parlant and A. Silva. 2018. Layer by layer \u2013 combining monads. In Proc. ICTAC 2018. https:\/\/doi.org\/10.1007\/978-3-030-02508-3_9 10.1007\/978-3-030-02508-3_9","DOI":"10.1007\/978-3-030-02508-3_9"},{"key":"e_1_3_2_28_2","unstructured":"S. Dash. 2024. A Monadic Theory of Point Processes. Ph. D. Dissertation. University of Oxford."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","unstructured":"S. Dash Y. Kaddar H. Paquet and S. Staton. 2023. Affine monads and lazy structures for Bayesian programming. In Proc. POPL 2023. https:\/\/doi.org\/10.1145\/3571239 10.1145\/3571239","DOI":"10.1145\/3571239"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","unstructured":"S. Dash and S. Staton. 2020. A monad for probabilistic point processes. In Proc. ACT 2020. https:\/\/doi.org\/10.4204\/EPTCS.333.2 10.4204\/EPTCS.333.2","DOI":"10.4204\/EPTCS.333.2"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","unstructured":"S. Dash and S. Staton. 2021. Monads for Measurable Queries in Probabilistic Databases. In Proc. MFPS 2021. https:\/\/doi.org\/10.4204\/EPTCS.351.3 10.4204\/EPTCS.351.3","DOI":"10.4204\/EPTCS.351.3"},{"key":"e_1_3_2_32_2","unstructured":"D. 'davidad\u2019 Dalrymple. 2024. Safeguarded AI: constructing safety by design. ARIA Programme Thesis. https:\/\/www.aria.org.uk\/wp-content\/uploads\/2024\/01\/ARIA-Safeguarded-AI-Programme-Thesis-V1.pdf."},{"key":"e_1_3_2_33_2","unstructured":"D. 'davidad\u2019 Dalrymple j. Skalse Y. Bengio S. Russell M. Tegmark S. Seshia S. Omohundro C. Szegedy B. Goldhaber N. Ammann A. Abate j. Halpern C. Barrett D. Zhao T. Zhi-Xuan j. Wing and j. Tenenbaum. 2024. Towards Guaranteed Safe AI: A Framework for Ensuring Robust and Reliable AI Systems. arXiv:2405.06624 [cs.AI]"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0060438"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","unstructured":"P. Di Gianantonio and A. Edalat. 2024. A Cartesian Closed Category for Random Variables. In Proc. LICS 2024. https:\/\/doi.org\/10.1145\/3661814.3662126 10.1145\/3661814.3662126","DOI":"10.1145\/3661814.3662126"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","unstructured":"E. Di Lavore and M. Rom\u00e1n. 2023. Evidential Decision Theory via Partial Markov Categories. In Proc. LICS 2023. https:\/\/doi.org\/10.1109\/LICS56636.2023.10175776 10.1109\/LICS56636.2023.10175776","DOI":"10.1109\/LICS56636.2023.10175776"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","unstructured":"B. Eckman and P. j. Hilton. 1961. Structure maps in group theory. Fundamenta Mathematicae 50 (1961) 207\u2013221. https:\/\/doi.org\/10.4064\/fm-50-2-207-221 10.4064\/fm-50-2-207-221","DOI":"10.4064\/fm-50-2-207-221"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","unstructured":"B. Eckmann and P. j. Hilton. 1962. Group-like Structures in General Categories I: Multiplications and Comultiplications. Math. Ann. 145 3 (june 1962) 227\u2013255. https:\/\/doi.org\/10.1007\/BF01451367 10.1007\/BF01451367","DOI":"10.1007\/BF01451367"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.2172\/809606"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","unstructured":"B. Fong D. Spivak and R. Tuy\u00e9ras. 2021. Backprop as Functor: A Compositional Perspective on supervised Learning. In Proc. LICS 2019. https:\/\/doi.org\/10.1109\/LICS.2019.8785665 10.1109\/LICS.2019.8785665","DOI":"10.1109\/LICS.2019.8785665"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","unstructured":"T. Fritz. 2020. A synthetic approach to Markov kernels conditional independence and theorems on sufficient statistics. Adv. Math. 370 (2020). https:\/\/doi.org\/10.1016\/j.aim.2020.107239 10.1016\/j.aim.2020.107239","DOI":"10.1016\/j.aim.2020.107239"},{"key":"e_1_3_2_42_2","unstructured":"T. Fritz and P. Perrone. 2018. A Criterion for Kan Extensions of Lax Monoidal Functors. (2018). arxiv:1809.10481."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","unstructured":"T. Fritz and P. Perrone. 2019. A Probability Monad as the Colimit of Spaces of Finite Samples. Theory and Applications of Categories 34 (2019). https:\/\/doi.org\/10.48550\/arXiv.1712.05363 10.48550\/arXiv.1712.05363","DOI":"10.48550\/arXiv.1712.05363"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","unstructured":"M. Gaboardi S. Katsumata D. Orchard and T. Sato. 2021. Graded Hoare logic and its categorical semantics. In Proc. ESOP 2021. https:\/\/doi.org\/10.1007\/978-3-030-72019-3_9 10.1007\/978-3-030-72019-3_9","DOI":"10.1007\/978-3-030-72019-3_9"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","unstructured":"B. Gavranovic. 2024. Fundamental Components of Deep Learning: A category-theoretic approach. Ph. D. Dissertation. Strathclyde University. https:\/\/doi.org\/10.48550\/arXiv.2403.13001 10.48550\/arXiv.2403.13001","DOI":"10.48550\/arXiv.2403.13001"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","unstructured":"j. Goubault-Larrecq. 2007. Continuous previsions. In Proc. CSL 2007. https:\/\/doi.org\/10.1007\/978-3-540-74915-8_40 10.1007\/978-3-540-74915-8_40","DOI":"10.1007\/978-3-540-74915-8_40"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","unstructured":"j. Goubault-Larrecq. 2008. Prevision Domains and Convex Powercones. In Proc. FOSSACS 2008. https:\/\/doi.org\/10.1007\/978-3-540-78499-9_23 10.1007\/978-3-540-78499-9_23","DOI":"10.1007\/978-3-540-78499-9_23"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","unstructured":"A. Goy and D. Petrisan. 2020. Combining probabilistic and non-deterministic choice via weak distributive laws. In LICS 2020. https:\/\/doi.org\/10.1145\/3373718.3394795 10.1145\/3373718.3394795","DOI":"10.1145\/3373718.3394795"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","unstructured":"C. Hermida and R. Tennent. 2012. Monoidal indeterminates and categories of possible worlds. Theoretical Computer Science 430 (2012). https:\/\/doi.org\/10.1016\/j.entcs.2009.07.083 10.1016\/j.entcs.2009.07.083","DOI":"10.1016\/j.entcs.2009.07.083"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","unstructured":"C. Heunen O. Kammar S. Staton and H. Yang. 2017. A convenient category for higher-order probability theory. In Proc. LICS 2017. https:\/\/doi.org\/10.1109\/LICS.2017.8005137 10.1109\/LICS.2017.8005137","DOI":"10.1109\/LICS.2017.8005137"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1002\/0471725250"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","unstructured":"B. jacobs. 1994. Semantics of weakening and contraction. Ann. Pure & Appl. Logic 69 1 (1994) 73\u2013106. https:\/\/doi.org\/10.1016\/0168-0072(94)90020-5 10.1016\/0168-0072(94)90020-5","DOI":"10.1016\/0168-0072(94)90020-5"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","unstructured":"B. jacobs. 2008. Coalgebraic Trace Semantics for Combined Possibilitistic and Probabilistic Systems. In Proc. CMCS 2008. https:\/\/doi.org\/10.1016\/j.entcs.2008.05.023 10.1016\/j.entcs.2008.05.023","DOI":"10.1016\/j.entcs.2008.05.023"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","unstructured":"B. jacobs. 2018. From probability monads to commutative effectuses. j. Log. Algebr. Methods Program. 94 (2018) 200\u2013237. https:\/\/doi.org\/10.1016\/j.jlamp.2016.11.006 10.1016\/j.jlamp.2016.11.006","DOI":"10.1016\/j.jlamp.2016.11.006"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","unstructured":"B. jacobs. 2021. From multisets over distributions to distributions over multisets. In Proc. LICS 2021. https:\/\/doi.org\/10.1109\/LICS52264.2021.9470678 10.1109\/LICS52264.2021.9470678","DOI":"10.1109\/LICS52264.2021.9470678"},{"key":"e_1_3_2_56_2","unstructured":"B. jacobs. 2023. Structured Probabilistic Reasoning. Available from the author's homepage. Draft book."},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","unstructured":"B. jacobs A. Kissinger and F. Zanasi. 2019. Causal Inference by String Diagram Surgery. In Proc. FOSSACS 2019. https:\/\/doi.org\/10.1007\/978-3-030-17127-8_18 10.1007\/978-3-030-17127-8_18","DOI":"10.1007\/978-3-030-17127-8_18"},{"key":"e_1_3_2_58_2","unstructured":"A. javanmardi D. Stutz and E. H\u00fcllermeier. 2024. Conformalized Credal Set Predictors. arXiv:2402.10723 [stat.ML]"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","unstructured":"X. jia B. Lindenhovius M. W. Mislove and V. Zamdzhiev. 2021. Commutative Monads for Probabilistic Programming Languages. In Proc. LICS 2021. 1\u201314. https:\/\/doi.org\/10.1109\/LICS52264.2021.9470611 10.1109\/LICS52264.2021.9470611","DOI":"10.1109\/LICS52264.2021.9470611"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","unstructured":"C. jones and G. D. Plotkin. 1989. A probabilistic powerdomain of evaluations. In Proc. LICS 1989. 186\u2013195. https:\/\/doi.org\/10.1109\/LICS.1989.39173 10.1109\/LICS.1989.39173","DOI":"10.1109\/LICS.1989.39173"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","unstructured":"O. Kammar and G. D. Plotkin. 2012. Algebraic foundations for effect-dependent optimisations. In Proc. POPL 2012. 349\u2013360. https:\/\/doi.org\/10.1145\/2103656.2103698 10.1145\/2103656.2103698","DOI":"10.1145\/2103656.2103698"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","unstructured":"S. Katsumata. 2014. Parametric effect monads and semantics of effect systems. In Proc. POPL 2014. https:\/\/doi.org\/10.1145\/2535838.2535846 10.1145\/2535838.2535846","DOI":"10.1145\/2535838.2535846"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","unstructured":"K. Keimel. 2005. Topological Cones: Foundations for a Domain Theoretical Semantics Combining Probability and Nondeterminism. In MFPS 2005. https:\/\/doi.org\/10.1016\/j.entcs.2005.11.066 10.1016\/j.entcs.2005.11.066","DOI":"10.1016\/j.entcs.2005.11.066"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","unstructured":"K. Keimel and G. D. Plotkin. 2017. Mixed powerdomains for probability and nondeterminism. Log. Methods Comput. Sci. 13 (2017). https:\/\/doi.org\/10.23638\/LMCS-13(1:2)2017 10.23638\/LMCS-13(1:2)2017","DOI":"10.23638\/LMCS-13(1:2)2017"},{"key":"e_1_3_2_65_2","unstructured":"G. M. Kelly. 1982. Basic Concepts of Enriched Category Theory. CUP."},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","unstructured":"F. H. Knight. 1921. Risk uncertainty and profit. Houghton Miffiin. https:\/\/doi.org\/10.1017\/CBO9780511817410.005 10.1017\/CBO9780511817410.005","DOI":"10.1017\/CBO9780511817410.005"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","unstructured":"A. Kock. 1970. Monads on symmetric monoidal closed categories. Arch. Math. 21 (1970) 1\u201310. https:\/\/doi.org\/10.1007\/BF01220868 10.1007\/BF01220868","DOI":"10.1007\/BF01220868"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","unstructured":"A. Kock. 1971. Bilinearity and cartesian closed monads. Math. Scand. 29 2 (1971). https:\/\/doi.org\/10.7146\/math.scand.a-11042 10.7146\/math.scand.a-11042","DOI":"10.7146\/math.scand.a-11042"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","unstructured":"A. Kock. 1972. Strong Functors and Monoidal Monads. Arch. Math 23 1 (December 1972) 113\u2013120. https:\/\/doi.org\/10.1007\/BF01304852 10.1007\/BF01304852","DOI":"10.1007\/BF01304852"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","unstructured":"A. Kock. 2012. Commutative monads as a theory of distributions. Theory Appl. Categ. 26 4 (2012) 97\u2013131. https:\/\/doi.org\/10.48550\/arXiv.1108.5952 10.48550\/arXiv.1108.5952","DOI":"10.48550\/arXiv.1108.5952"},{"key":"e_1_3_2_71_2","unstructured":"V. Kosoy and A. Appel. 2021. Infra-Bayesian physicalism: A formal theory of naturalized induction. AI Alignment Forum. Available at https:\/\/www.alignmentforum.org\/posts\/gHgs2e2J5azvGFatb\/infra-bayesian-physicalism-a-formal- theory-of-naturalized."},{"key":"e_1_3_2_72_2","unstructured":"D. Kozen and A. Silva. 2024. Multisets and Distributions. Springer Cham 168\u2013187. https:\/\/doi.org\/10.1007\/978-3-031- 61716-4_11 10.1007\/978-3-031- 61716-4_11"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","unstructured":"D. Krpel\u00edk and T. Basu. 2021. Introduction to Imprecise Probabilities. Chapter 13 35\u201379. https:\/\/doi.org\/10.1007\/978-3-030-60166-9_2 10.1007\/978-3-030-60166-9_2","DOI":"10.1007\/978-3-030-60166-9_2"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","unstructured":"S. Kura. 2020. Graded algebraic theories. In Proc. FOSSACS 2020. https:\/\/doi.org\/10.1007\/978-3-030-45231-5_21 10.1007\/978-3-030-45231-5_21","DOI":"10.1007\/978-3-030-45231-5_21"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","unstructured":"j. Laird G. Manzonetto G. McCusker and M. Pagani. 2013. Weighted Relational Models of Typed Lambda-Calculi. In Proc. LICS 2013. https:\/\/doi.org\/10.1109\/LICS.2013.36 10.1109\/LICS.2013.36","DOI":"10.1109\/LICS.2013.36"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","unstructured":"P. B. Levy. 2007. Amb Breaks Well-Pointedness Ground Amb Doesn't. In Proc. MFPS 2007. https:\/\/doi.org\/10.1016\/j.entcs.2007.02.036 10.1016\/j.entcs.2007.02.036","DOI":"10.1016\/j.entcs.2007.02.036"},{"key":"e_1_3_2_77_2","unstructured":"P. B. Levy. 2019. Locally graded categories. Slides available from the author's webpage."},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","unstructured":"P. B. Levy j. Power and H. Thielecke. 2003. Modelling environments in call-by-value programming languages. Inform. Comput. 185 (2003). https:\/\/doi.org\/10.1016\/S0890-5401(03)00088-9 10.1016\/S0890-5401(03)00088-9","DOI":"10.1016\/S0890-5401(03)00088-9"},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","unstructured":"A. K. Lew M. F. Cusumano-Towner B. Sherman M. Carbin and V. K. Maninghka. 2020. Trace Types and Denotational Semantics for Sound Programmable Inference in Probabilistic Languages. In Proc. POPL 2020. https:\/\/doi.org\/10.1145\/3371087 10.1145\/3371087","DOI":"10.1145\/3371087"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","unstructured":"j. Li j. Aytac P. johnson-Freyd A. Ahmed and S. Holtzen. 2024. A Nominal Approach to Probabilistic Separation Logic. In Proc. LICS 2024. https:\/\/doi.org\/10.1145\/3661814.3662135 10.1145\/3661814.3662135","DOI":"10.1145\/3661814.3662135"},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","unstructured":"S. Liang P. Hudak and M. jones. 1995. Monad transformers and modular interpreters. In Proc. POPL 1995. https:\/\/doi.org\/10.1145\/199448.199528 10.1145\/199448.199528","DOI":"10.1145\/199448.199528"},{"key":"e_1_3_2_82_2","doi-asserted-by":"publisher","unstructured":"S. Mac Lane. 1998. Categories for the Working Mathematician. Springer. https:\/\/doi.org\/10.1007\/978-1-4757-4721-8 10.1007\/978-1-4757-4721-8","DOI":"10.1007\/978-1-4757-4721-8"},{"key":"e_1_3_2_83_2","doi-asserted-by":"crossref","unstructured":"D. McDermott. 2019. Reasoning about effectful programs and evaluation order. Ph. D. Dissertation. University of Cambridge.","DOI":"10.1007\/978-3-030-17184-1_9"},{"key":"e_1_3_2_84_2","doi-asserted-by":"publisher","unstructured":"D. McDermott and T. Uustalu. 2022. Flexibly Graded Monads and Graded Algebras. In Proc. MPC 2022. https:\/\/doi.org\/10.1007\/978-3-031-16912-0_4 10.1007\/978-3-031-16912-0_4","DOI":"10.1007\/978-3-031-16912-0_4"},{"key":"e_1_3_2_85_2","doi-asserted-by":"publisher","DOI":"10.1007\/b138392"},{"key":"e_1_3_2_86_2","doi-asserted-by":"publisher","unstructured":"A. K. McIver and C. Morgan. 2001. Partial correctness for probabilistic demonic programs. Theoret. Comput. Sci. 266 (2001) 513\u2013541. https:\/\/doi.org\/10.1016\/S0304-3975(00)00208-5 10.1016\/S0304-3975(00)00208-5","DOI":"10.1016\/S0304-3975(00)00208-5"},{"key":"e_1_3_2_87_2","doi-asserted-by":"publisher","unstructured":"M. Mio. 2014. Upper-Expectation Bisimilarity and \u0141ukasiewicz mu-Calculus. In Proc. FOSSACS 2014. https:\/\/doi.org\/10.1007\/978-3-642-54830-7_22 10.1007\/978-3-642-54830-7_22","DOI":"10.1007\/978-3-642-54830-7_22"},{"key":"e_1_3_2_88_2","doi-asserted-by":"publisher","unstructured":"M. Mio R. Sarkis and V. Vignudelli. 2021. Combining Nondeterminism Probability and Termination: Equational and Metric Reasoning. In Proc. LICS 2021. https:\/\/doi.org\/10.1109\/LICS52264.2021.9470717 10.1109\/LICS52264.2021.9470717","DOI":"10.1109\/LICS52264.2021.9470717"},{"key":"e_1_3_2_89_2","doi-asserted-by":"publisher","unstructured":"M. Mio and V. Vignudelli. 2020. Monads and Quantitative Equational Theories for Nondeterminism and Probability. In Proc. CONCUR 2020. https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2020.28 10.4230\/LIPIcs.CONCUR.2020.28","DOI":"10.4230\/LIPIcs.CONCUR.2020.28"},{"key":"e_1_3_2_90_2","doi-asserted-by":"publisher","unstructured":"M. W. Mislove j. Ouaknine and j. Worrell. 2003. Axioms for Probability and Nondeterminism. In Proc. EXPRESS 2003. https:\/\/doi.org\/10.1016\/j.entcs.2004.04.019 10.1016\/j.entcs.2004.04.019","DOI":"10.1016\/j.entcs.2004.04.019"},{"key":"e_1_3_2_91_2","doi-asserted-by":"publisher","unstructured":"E. Moggi. 1989. Computational Lambda-Calculus and Monads. In Proc. LICS 1989. 14\u201323. https:\/\/doi.org\/10.1109\/LICS.1989.39155 10.1109\/LICS.1989.39155","DOI":"10.1109\/LICS.1989.39155"},{"key":"e_1_3_2_92_2","doi-asserted-by":"publisher","unstructured":"E. Moggi. 1991. Notions of computation and monads. Information and Computation (1991). https:\/\/doi.org\/10.1016\/0890-5401(91)90052-4 10.1016\/0890-5401(91)90052-4","DOI":"10.1016\/0890-5401(91)90052-4"},{"key":"e_1_3_2_93_2","doi-asserted-by":"publisher","unstructured":"D. Orchard P. Wadler and H. EadesIII. 2020. Unifying graded and parameterised monads. In Proc. MSFP 2020. https:\/\/doi.org\/10.4204\/EPTCS.317.2 10.4204\/EPTCS.317.2","DOI":"10.4204\/EPTCS.317.2"},{"key":"e_1_3_2_94_2","unstructured":"Y. Oren V. Vadocz M. T. j. Spaan and W. B\u00f6hmer. 2024. Epistemic Monte Carlo Tree Search. arXiv:2210.13455 [cs.LG]"},{"key":"e_1_3_2_95_2","doi-asserted-by":"publisher","unstructured":"E. Pavlidis I. Paya D. Peel and C. Siriopoulos. 2011. Nonlinear dynamics in economics and finance and unit root testing. The European journal of Finance (August 2011). https:\/\/doi.org\/10.1080\/1351847X.2011.607006 10.1080\/1351847X.2011.607006","DOI":"10.1080\/1351847X.2011.607006"},{"key":"e_1_3_2_96_2","doi-asserted-by":"publisher","unstructured":"P. Perrone. 2023. Markov Categories and Entropy. IEEE Transactions on Information Theory (2023). https:\/\/doi.org\/10.1109\/TIT.2023.3328825 10.1109\/TIT.2023.3328825","DOI":"10.1109\/TIT.2023.3328825"},{"key":"e_1_3_2_97_2","doi-asserted-by":"publisher","unstructured":"D. Petrisan and R. Sarkis. 2021. Semialgebras and Weak Distributive Laws. In Proc. MFPS 2021. https:\/\/doi.org\/10.4204\/EPTCS.351.14 10.4204\/EPTCS.351.14","DOI":"10.4204\/EPTCS.351.14"},{"key":"e_1_3_2_98_2","doi-asserted-by":"publisher","unstructured":"M. Pir\u00f3g and S. Staton. 2017. Backtracking with cut via a distributive law and left-zero monoids. j. Functional Programming 27 (2017). https:\/\/doi.org\/10.1017\/S0956796817000077 10.1017\/S0956796817000077","DOI":"10.1017\/S0956796817000077"},{"key":"e_1_3_2_99_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139084673"},{"key":"e_1_3_2_100_2","doi-asserted-by":"publisher","unstructured":"G. Plotkin and j. Power. 2003. Algebraic operations and generic effects. Appl. Categ. Structures 11 1 (2003) 69\u201394. https:\/\/doi.org\/10.1023\/A:1023064908962 10.1023\/A:1023064908962","DOI":"10.1023\/A:1023064908962"},{"key":"e_1_3_2_101_2","doi-asserted-by":"publisher","unstructured":"G. D. Plotkin and j. Power. 2002. Notions of Computation Determine Monads. In Proc. FOSSACS 2002. https:\/\/doi.org\/10.1007\/3-540-45931-6_24 10.1007\/3-540-45931-6_24","DOI":"10.1007\/3-540-45931-6_24"},{"key":"e_1_3_2_102_2","doi-asserted-by":"publisher","unstructured":"j. Power. 2006. Generic models for computational effects. Theor. Comput. Sci. 364 2 (2006) 254\u2013269. https:\/\/doi.org\/10.1016\/j.tcs.2006.08.006 10.1016\/j.tcs.2006.08.006","DOI":"10.1016\/j.tcs.2006.08.006"},{"key":"e_1_3_2_103_2","doi-asserted-by":"publisher","unstructured":"A. B. Romanowska and j. D. H. Smith. 2002. Modes. World Scientific. https:\/\/doi.org\/10.1142\/4953 10.1142\/4953","DOI":"10.1142\/4953"},{"key":"e_1_3_2_104_2","doi-asserted-by":"publisher","unstructured":"D. Shiebler. 2021. Categorical Stochastic Processes and Likelihood. Compositionality 3 (April 2021). Issue 1. https:\/\/doi.org\/10.32408\/compositionality-3-1 10.32408\/compositionality-3-1","DOI":"10.32408\/compositionality-3-1"},{"key":"e_1_3_2_105_2","doi-asserted-by":"publisher","unstructured":"A. Simpson. 2017. Probability Sheaves and the Giry Monad. In Proc. CALCO 2017. https:\/\/doi.org\/10.4230\/LIPIcs.CALCO.2017.1 10.4230\/LIPIcs.CALCO.2017.1","DOI":"10.4230\/LIPIcs.CALCO.2017.1"},{"key":"e_1_3_2_106_2","doi-asserted-by":"publisher","unstructured":"A. Simpson. 2024. Equivalence and Conditional Independence in Atomic Sheaf Logic. In Proc. LICS 2024. https:\/\/doi.org\/10.1145\/3661814.3662132 10.1145\/3661814.3662132","DOI":"10.1145\/3661814.3662132"},{"key":"e_1_3_2_107_2","doi-asserted-by":"publisher","unstructured":"S. Staton. 2017. Commutative Semantics for Probabilistic Programming. In Proc. ESOP 2017. 855\u2013879. https:\/\/doi.org\/10.1007\/978-3-662-54434-1_32 10.1007\/978-3-662-54434-1_32","DOI":"10.1007\/978-3-662-54434-1_32"},{"key":"e_1_3_2_108_2","doi-asserted-by":"publisher","unstructured":"S. Staton D. Stein H. Yang N. L. Ackerman C. E. Freer and D. M. Roy. 2018. The Beta-Bernoulli process and algebraic effects. In Proc. ICALP 2018. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.141 10.4230\/LIPIcs.ICALP.2018.141","DOI":"10.4230\/LIPIcs.ICALP.2018.141"},{"key":"e_1_3_2_109_2","doi-asserted-by":"crossref","unstructured":"D. Stein and R. Samuelson. 2024. A Categorical Treatment of Open Linear Systems. arXiv:2403.03934 [cs.LO]","DOI":"10.46298\/lmcs-21(3:11)2025"},{"key":"e_1_3_2_110_2","doi-asserted-by":"publisher","unstructured":"D. Stein and S. Staton. 2021. Compositional Semantics for Probabilistic Programs with Exact Conditioning. In Proc. LICS 2021. https:\/\/doi.org\/10.1109\/LICS52264.2021.9470552 10.1109\/LICS52264.2021.9470552","DOI":"10.1109\/LICS52264.2021.9470552"},{"key":"e_1_3_2_111_2","unstructured":"D. Stutz A. G. Roy T. Matejovicova P. Strachan A. T. Cemgil and A. Doucet. 2023. Conformal prediction under ambiguous ground truth. arXiv:2307.09302 [cs.LG]"},{"key":"e_1_3_2_112_2","unstructured":"Z. Tavares j. Koppel X. Zhang R. Das and A. Solar-Lezama. 2021. A language for counterfactual generative models. In Proc. ICML 2021. 10173\u201310182."},{"key":"e_1_3_2_113_2","unstructured":"T. Uustalu. 2010. Strong relative monads. In Proc. CMCS 2010."},{"key":"e_1_3_2_114_2","doi-asserted-by":"publisher","unstructured":"M. V\u00e1k\u00e1r O. Kammar and S. Staton. 2019. A domain theory for statistical probabilistic programming. In Proc. POPL 2019 Vol. 3. 36:1\u201336:29. https:\/\/doi.org\/10.1145\/3290349 10.1145\/3290349","DOI":"10.1145\/3290349"},{"key":"e_1_3_2_115_2","unstructured":"j.-W. van de Meent B. Paige H. Yang and F. Wood. 2018. An Introduction to Probabilistic Programming. (2018). arXiv:1809.10756 [stat.ML]"},{"key":"e_1_3_2_116_2","doi-asserted-by":"publisher","unstructured":"G. van Heerdt j. Hsu j. Ouaknine and A. Silva. 2018. Convex Language Semantics for Nondeterministic Probabilistic Automata. In Proc. ICTAC 2018. https:\/\/doi.org\/10.1007\/978-3-030-02508-3_25 10.1007\/978-3-030-02508-3_25","DOI":"10.1007\/978-3-030-02508-3_25"},{"key":"e_1_3_2_117_2","doi-asserted-by":"publisher","unstructured":"D. Varacca and G. Winskel. 2006. Distributing probability over non-determinism. Math. Structures Comput. Sci. (2006) 87\u2013113. https:\/\/doi.org\/10.1017\/S0960129505005074 10.1017\/S0960129505005074","DOI":"10.1017\/S0960129505005074"},{"key":"e_1_3_2_118_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-60166-9"},{"key":"e_1_3_2_119_2","doi-asserted-by":"publisher","unstructured":"P. Vicig. 2008. Financial Risk Measurement with Imprecise Probabilities. Int. j. Approx. Reasoning 49 1 (September 2008) 159\u2013174. https:\/\/doi.org\/10.1016\/j.ijar.2007.06.009 10.1016\/j.ijar.2007.06.009","DOI":"10.1016\/j.ijar.2007.06.009"},{"key":"e_1_3_2_120_2","doi-asserted-by":"publisher","unstructured":"P. Walley. 1991. Statistical Reasoning with Imprecise Probabilities. Chapman and Hall. https:\/\/doi.org\/10.1007\/978-1-4899-3472-7 10.1007\/978-1-4899-3472-7","DOI":"10.1007\/978-1-4899-3472-7"},{"key":"e_1_3_2_121_2","unstructured":"R. Wood. 1976. Indical methods for relative categories. Ph. D. Dissertation. Dalhousie University."},{"key":"e_1_3_2_122_2","unstructured":"M. A. Zanger W. B\u00f6hmer and M. T. j. Spaan. 2023. Diverse Projection Ensembles for Distributional Reinforcement Learning. arXiv:2306.07124 [cs.LG]"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3704890","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3704890","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T10:15:24Z","timestamp":1770200124000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3704890"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,7]]},"references-count":121,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2025,1,7]]}},"alternative-id":["10.1145\/3704890"],"URL":"https:\/\/doi.org\/10.1145\/3704890","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,7]]},"assertion":[{"value":"2024-07-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}