{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T00:31:13Z","timestamp":1768005073514,"version":"3.49.0"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T00:00:00Z","timestamp":1704153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-CE48-0014"],"award-info":[{"award-number":["ANR-19-CE48-0014"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["101034255"],"award-info":[{"award-number":["101034255"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,1,2]]},"abstract":"<jats:p>\n            Bayesian networks are graphical\n            <jats:italic toggle=\"yes\">first-order<\/jats:italic>\n            probabilistic models that allow for a compact representation of large probability distributions, and for efficient inference, both exact and approximate. We introduce a\n            <jats:italic toggle=\"yes\">higher-order<\/jats:italic>\n            programming language\u2014in the idealized form of a\n            <jats:italic toggle=\"yes\">\u03bb<\/jats:italic>\n            -calculus\u2014which we prove\n            <jats:italic toggle=\"yes\">sound and complete<\/jats:italic>\n            w.r.t. Bayesian networks: each Bayesian network can be encoded as a term, and conversely each (possibly higher-order and recursive) program of ground type\n            <jats:italic toggle=\"yes\">compiles<\/jats:italic>\n            into a Bayesian network.\n          <\/jats:p>\n          <jats:p>\n            The language allows for the specification of recursive probability models and hierarchical structures. Moreover, we provide a\n            <jats:italic toggle=\"yes\">compositional<\/jats:italic>\n            and\n            <jats:italic toggle=\"yes\">cost-aware<\/jats:italic>\n            semantics which is based on factors, the standard mathematical tool used in Bayesian inference. Our results rely on advanced techniques rooted into linear logic, intersection types, rewriting theory, and Girard\u2019s geometry of interaction, which are here combined in a novel way.\n          <\/jats:p>","DOI":"10.1145\/3632926","type":"journal-article","created":{"date-parts":[[2024,1,5]],"date-time":"2024-01-05T20:48:51Z","timestamp":1704487731000},"page":"2514-2546","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Higher Order Bayesian Networks, Exactly"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-8875-3595","authenticated-orcid":false,"given":"Claudia","family":"Faggian","sequence":"first","affiliation":[{"name":"IRIF, CNRS, Universit\u00e9 Paris Cit\u00e9, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8865-7942","authenticated-orcid":false,"given":"Daniele","family":"Pautasso","sequence":"additional","affiliation":[{"name":"University of Turin, Torino, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8762-8674","authenticated-orcid":false,"given":"Gabriele","family":"Vanoni","sequence":"additional","affiliation":[{"name":"IRIF, CNRS, Universit\u00e9 Paris Cit\u00e9, Paris, France"}]}],"member":"320","published-online":{"date-parts":[[2024,1,5]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414080.3414108"},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434332"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470726"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3547650"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1017\/S095679682000012X"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15205-4_30"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571244"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0037099"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1996.561458"},{"key":"e_1_3_1_11_1","unstructured":"Johannes Borgstr\u00f6m Ugo Dal Lago Andrew D. Gordon and Marcin Szymczak. 2015. A Lambda-Calculus Foundation for Universal Probabilistic Programming. CoRR abs\/1512.08990 (2015). arXiv:1512.08990 http:\/\/arxiv.org\/abs\/1512.08990"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59025-3_2"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.62"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17184-1_12"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3586050"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02011875"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19810270205"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2018.11.006"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434313"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009859"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-8(4:11)2012"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.02.001"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/507382.507385"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1574-6526(07)03011-8"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511811357"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129516000396"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","unstructured":"Thomas Dean and Keiji Kanazawa. 1989. A model for reasoning about persistence and causation Computational Intelligence 5 2 (1989) 142\u2013150. https:\/\/doi.org\/10.1111\/j.1467-8640.1989.tb00324.x 10.1111\/j.1467-8640.1989.tb00324.x arXiv:https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/j.1467-8640.1989.tb00324.x","DOI":"10.1111\/j.1467-8640.1989.tb00324.x"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exs025"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49498-1_9"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSCD.2023.8"},{"key":"e_1_3_1_31_1","article-title":"The Variable Elimination Algorithm as a Let-Term Rewriting","author":"Ehrhard Thomas","year":"2023","unstructured":"Thomas Ehrhard, Claudia Faggian, and Michele Pagani. 2023b. The Variable Elimination Algorithm as a Let-Term Rewriting. Talk presented at LAFI 2023.","journal-title":"Talk presented at LAFI 2023"},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535865"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-15(1:3)2019"},{"key":"e_1_3_1_34_1","unstructured":"Claudia Faggian Daniele Pautasso and Gabriele Vanoni. 2023. Higher-Order Bayesian Networks Exactly (Extended version). CoRR 2311.04651 (2023). https:\/\/arxiv.org\/abs\/2311.04651"},{"key":"e_1_3_1_35_1","first-page":"157","volume-title":"Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intelligence Conference, AAAI 98, IAAI 98, July 26-30","author":"Friedman Nir","year":"1998","unstructured":"Nir Friedman, Daphne Koller, and Avi Pfeffer. 1998. Structured Representation of Complex Stochastic Systems. In Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intelligence Conference, AAAI 98, IAAI 98, July 26-30, 1998, Madison, Wisconsin, USA, Jack Mostow and Chuck Rich (Eds.). AAAI Press \/ The MIT Press, 157\u2013164. http:\/\/www.aaai.org\/Library\/AAAI\/1998\/aaai98-022.php"},{"key":"e_1_3_1_36_1","doi-asserted-by":"crossref","unstructured":"W. R. Gilks A. Thomas and D. J. Spiegelhalter. 1994. A Language and Program for Complex Bayesian Modelling. Fournal of the Royal Statistical Society. Series D (The Statistician) 43 1 (1994) 169\u2013177. http:\/\/www.jstor.org\/stable\/2348941","DOI":"10.2307\/2348941"},{"key":"e_1_3_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)70271-4"},{"key":"e_1_3_1_38_1","first-page":"220","article-title":"Church: a language for generative models","author":"Goodman Noah D.","year":"2008","unstructured":"Noah D. Goodman, Vikash K. Mansinghka, Daniel M. Roy, Keith 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, fuly 9-12, 2008, David A. McAllester and Petri Myllym\u00e4ki (Eds.). 220\u2013229.","journal-title":"UAI 2008, Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence, Helsinki, Finland, fuly 9-12, 2008"},{"key":"e_1_3_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593882.2593900"},{"key":"e_1_3_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490421"},{"key":"e_1_3_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005137"},{"key":"e_1_3_1_42_1","unstructured":"Bart Jacobs. 2023. Structured Probabilitistic Reasoning. (2023). http:\/\/www.cs.ru.nl\/B.Jacobs\/PAPERS\/ProbabilisticReasoning.pdf"},{"key":"e_1_3_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17127-8_18"},{"key":"e_1_3_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2016.09.038"},{"key":"e_1_3_1_45_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108770750.010"},{"key":"e_1_3_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1795555"},{"key":"e_1_3_1_47_1","first-page":"740","volume-title":"Proceedings of the Fourteenth National Conference on Artificial Intelligence 1997, Providence, Rhode Island, USA","author":"Koller Daphne","year":"1997","unstructured":"Daphne Koller, David A. McAllester, and Avi Pfeffer. 1997. Effective Bayesian Inference for Stochastic Programs. In Proceedings of the Fourteenth National Conference on Artificial Intelligence 1997, Providence, Rhode Island, USA, Benjamin Kuipers and Bonnie L. Webber (Eds.). AAAI Press \/ The MIT Press, 740\u2013747."},{"key":"e_1_3_1_48_1","first-page":"302","volume-title":"UAI \u201997: Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, Brown University, Providence, Rhode Island, USA, August 1-3, 1997","author":"Koller Daphne","year":"1997","unstructured":"Daphne Koller and Avi Pfeffer. 1997. Object-Oriented Bayesian Networks. In UAI \u201997: Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, Brown University, Providence, Rhode Island, USA, August 1-3, 1997, Dan Geiger and Prakash P. Shenoy (Eds.). Morgan Kaufmann, 302\u2013313. https:\/\/dslpitt.org\/uai\/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=324&proceeding_id=13"},{"key":"e_1_3_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2013.36"},{"key":"e_1_3_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48959-2_17"},{"key":"e_1_3_1_51_1","author":"Mansinghka Vikash","year":"2014","unstructured":"Vikash Mansinghka, Daniel Selsam, and Yura Perov. 2014. Venture: a higher-order probabilistic programming platform with programmable inference. arXiv:1404.0099 [cs.AI]","journal-title":"Venture: a higher-order probabilistic programming platform with programmable inference"},{"key":"e_1_3_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2009.07.018"},{"key":"e_1_3_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2006.07.035"},{"key":"e_1_3_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1989.39155"},{"key":"e_1_3_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/1198020"},{"key":"e_1_3_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-72019-3_19"},{"key":"e_1_3_1_57_1","doi-asserted-by":"crossref","unstructured":"Sungwoo Park. 2003. A calculus for probabilistic languages. In Proceedings of TLDI\u201903: 2003 ACM SIGPLAN International Workshop on Types in Languages Design and Implementation New Orleans Louisiana USA January 18 2003. 38\u201349.","DOI":"10.1145\/604174.604180"},{"key":"e_1_3_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040320"},{"key":"e_1_3_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(86)90072-X"},{"key":"e_1_3_1_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/52121"},{"key":"e_1_3_1_61_1","unstructured":"Avi Pfeffer. 2016. Practical Probabilistic Programming (1st ed.). Manning Publications Co. USA."},{"key":"e_1_3_1_62_1","first-page":"538","volume-title":"Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence","author":"Pfeffer Avi","year":"2000","unstructured":"Avi Pfeffer and Daphne Koller. 2000. Semantics and Inference for Recursive Probability Models. In Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, Fuly 30 - August 3, 2000, Austin, Texas, USA, Henry A. Kautz and Bruce W. Porter (Eds.). AAAI Press \/ The MIT Press, 538\u2013544. http:\/\/www.aaai.org\/Library\/AAAI\/2000\/aaai00-082.php"},{"key":"e_1_3_1_63_1","first-page":"429","article-title":"Toward General Analysis of Recursive Probability Models","author":"Pless Daniel","year":"2001","unstructured":"Daniel Pless and George F. Luger. 2001. Toward General Analysis of Recursive Probability Models. In UAI \u201901: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, University of Washington, Seattle, Washington, USA, August 2-5, 2001. 429\u2013436.","journal-title":"UAI \u201901: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence"},{"key":"e_1_3_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/503272.503288"},{"key":"e_1_3_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08921-7_92"},{"key":"e_1_3_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158148"},{"key":"e_1_3_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32033-3_17"},{"key":"e_1_3_1_68_1","first-page":"1","article-title":"Compositional Semantics for Probabilistic Programs with Exact Conditioning","author":"Stein Dario","year":"2021","unstructured":"Dario Stein and Sam Staton. 2021. Compositional Semantics for Probabilistic Programs with Exact Conditioning. 2021 36th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS) (2021), 1\u201313","journal-title":"2021 36th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)"},{"key":"e_1_3_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290349"},{"key":"e_1_3_1_70_1","unstructured":"Jan-Willem van de Meent Brooks Paige Hongseok Yang and Frank Wood. 2018. An Introduction to Probabilistic Programming. CoRR abs\/1809.10756 (2018). arXiv:1809.10756 http:\/\/arxiv.org\/abs\/1809.10756"},{"key":"e_1_3_1_71_1","first-page":"1024","volume-title":"Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, Vol. 33)","author":"Wood Frank","year":"2014","unstructured":"Frank Wood, Jan Willem Meent, and Vikash Mansinghka. 2014. A New Approach to Probabilistic Programming Inference. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, Vol. 33), Samuel Kaski and Jukka Corander (Eds.). PMLR, Reykjavik, Iceland, 1024\u20131032. https:\/\/proceedings.mlr.press\/v33\/wood14.html"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632926","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:05:23Z","timestamp":1751659523000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,2]]},"references-count":70,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2024,1,2]]}},"alternative-id":["10.1145\/3632926"],"URL":"https:\/\/doi.org\/10.1145\/3632926","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,2]]},"assertion":[{"value":"2024-01-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}