{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:10:39Z","timestamp":1760058639105,"version":"build-2065373602"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T00:00:00Z","timestamp":1744156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2220408"],"award-info":[{"award-number":["2220408"]}],"id":[{"id":"10.13039\/100000001","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":[[2025,4,9]]},"abstract":"<jats:p>\n            Probabilistic inference is fundamentally hard, yet many tasks require optimization on top of inference, which is even harder. We present a new\n            <jats:italic toggle=\"yes\">optimization-via-compilation<\/jats:italic>\n            strategy to scalably solve a certain class of such problems. In particular, we introduce a new intermediate representation (IR), binary decision diagrams weighted by a novel notion of\n            <jats:italic toggle=\"yes\">branch-and-bound semiring<\/jats:italic>\n            , that enables a scalable branch-and-bound based optimization procedure. This IR automatically\n            <jats:italic toggle=\"yes\">factorizes<\/jats:italic>\n            problems through program structure and\n            <jats:italic toggle=\"yes\">prunes<\/jats:italic>\n            suboptimal values via a straightforward branch-and-bound style algorithm to find optima. Additionally, the IR is naturally amenable to\n            <jats:italic toggle=\"yes\">staged compilation<\/jats:italic>\n            , allowing the programmer to query for optima mid-compilation to inform further executions of the program. We showcase the effectiveness and flexibility of the IR by implementing two performant languages that both compile to it: dappl and pineappl. dappl is a functional language that solves maximum expected utility problems with first-class support for rewards, decision making, and conditioning. pineappl is an imperative language that performs exact probabilistic inference with support for nested marginal maximum a posteriori (MMAP) optimization via staging.\n          <\/jats:p>","DOI":"10.1145\/3720500","type":"journal-article","created":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T13:48:26Z","timestamp":1744206506000},"page":"1546-1574","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Scaling Optimization over Uncertainty via Compilation"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-6170-6033","authenticated-orcid":false,"given":"Minsung","family":"Cho","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0494-7245","authenticated-orcid":false,"given":"John","family":"Gouwar","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8190-5412","authenticated-orcid":false,"given":"Steven","family":"Holtzen","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,4,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.46298\/LMCS-19(2:3)2023"},{"volume-title":"Foundations of probabilistic programming","author":"Barthe Gilles","key":"e_1_2_1_2_1","unstructured":"Gilles Barthe, Joost-Pieter Katoen, and Alexandra Silva. 2020. Foundations of probabilistic programming. Cambridge University Press."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3527310"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/EUSIPCO.2016.7760303"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the National Conference on Artificial Intelligence, 355\u2013362","author":"Boutilier Craig","year":"2000","unstructured":"Craig Boutilier, Raymond Reiter, Mikhail Soutchanski, and Sebastian Thrun. 2000. Decision-Theoretic, High-Level Agent Programming in the Situation Calculus. Proceedings of the National Conference on Artificial Intelligence, 355\u2013362."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCC.2007.913919"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Craig Chambers. 2002. Staged compilation. 1\u20138. https:\/\/doi.org\/10.1145\/503032.503045 10.1145\/503032.503045","DOI":"10.1145\/503032.503045"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.ARTINT.2007.11.002"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Minsung Cho John Gouwar and Steven Holtzen. 2025. Artifact to accompany \"Scaling Optimization Over Uncertainty via Compilation\". https:\/\/doi.org\/10.5281\/zenodo.14941338 10.5281\/zenodo.14941338","DOI":"10.5281\/zenodo.14941338"},{"key":"e_1_2_1_10_1","unstructured":"Minsung Cho John Gouwar and Steven Holtzen. 2025. Scaling Optimization Over Uncertainty via Compilation. arxiv:2502.18728. arxiv:2502.18728"},{"key":"e_1_2_1_11_1","volume-title":"International Conference on Artificial Intelligence and Statistics, AISTATS 2022","volume":"10208","author":"Choi YooJung","year":"2022","unstructured":"YooJung Choi, Tal Friedman, and Guy Van den Broeck. 2022. Solving Marginal MAP Exactly by Probabilistic Circuit Transformations. In International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (Eds.) (Proceedings of Machine Learning Research, Vol. 151). PMLR, 10196\u201310208. https:\/\/proceedings.mlr.press\/v151\/choi22b.html"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Edmund M. Clarke Thomas A. Henzinger Helmut Veith and Roderick Bloem (Eds.). 2018. Handbook of Model Checking. Springer. isbn:978-3-319-10574-1 https:\/\/doi.org\/10.1007\/978-3-319-10575-8 10.1007\/978-3-319-10575-8","DOI":"10.1007\/978-3-319-10575-8"},{"key":"e_1_2_1_13_1","unstructured":"Diarmaid Conaty Cassio P. de Campos and Denis Deratani Mau\u00e1. 2017. Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networks. http:\/\/auai.org\/uai2017\/proceedings\/papers\/109.pdf"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314642"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1613\/JAIR.989"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_31"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.3233\/FAIA200392"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462166"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.3115\/1073083.1073085"},{"key":"e_1_2_1_20_1","unstructured":"Owain Evans Andreas Stuhlm\u00fcller John Salvatier and Daniel Filan. 2017. Modeling Agents with Probabilistic Programs. http:\/\/agentmodels.org Accessed: 2025-2-20"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000076"},{"volume-title":"Categorical Aspects of Topology and Analysis","author":"Giry Mich\u00e8le","key":"e_1_2_1_22_1","unstructured":"Mich\u00e8le Giry. 1982. A categorical approach to probability theory. In Categorical Aspects of Topology and Analysis, B. Banaschewski (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 68\u201385. isbn:978-3-540-39041-1"},{"key":"e_1_2_1_23_1","volume-title":"UAI 2008, Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence","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. https:\/\/dslpitt.org\/uai\/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=1346&proceeding_id=24"},{"key":"e_1_2_1_24_1","unstructured":"Noah D Goodman and Andreas Stuhlm\u00fcller. 2014. The Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org Accessed: 2024-10-14"},{"key":"e_1_2_1_25_1","volume-title":"Nathwani","author":"Heckerman David E.","year":"1992","unstructured":"David E. Heckerman, Eric J. Horvitz, and Bharat N. Nathwani. 1992. Toward normative expert systems: Part I. The Pathfinder project. Methods of information in medicine, 31, 02 (1992), 90\u2013105."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81688-9_27"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428208"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/OPRE.50.1.100.17788"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/deca.1050.0020"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference","author":"Huang Jinbo","year":"2006","unstructured":"Jinbo Huang, Mark Chavira, and Adnan Darwiche. 2006. Solving MAP Exactly by Searching on Compiled Arithmetic Circuits. In Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA. AAAI Press, 1143\u20131148. http:\/\/www.aaai.org\/Library\/AAAI\/2006\/aaai06-179.php"},{"key":"e_1_2_1_31_1","unstructured":"Arindam Khaled Eric A. Hansen and Changhe Yuan. 2013. Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search. https:\/\/dslpitt.org\/uai\/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=2394&proceeding_id=29"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1017\/S147106842200014X"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V25I1.7852"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JAL.2016.11.031"},{"key":"e_1_2_1_35_1","volume-title":"International conference on Autonomous Agents and Multi-Agent Systems, AAMAS \u201914","author":"Kiselev Igor","year":"2014","unstructured":"Igor Kiselev and Pascal Poupart. 2014. Policy optimization by marginal-map probabilistic inference in generative models. In International conference on Autonomous Agents and Multi-Agent Systems, AAMAS \u201914, Paris, France, May 5-9, 2014, Ana L. C. Bazzan, Michael N. Huhns, Alessio Lomuscio, and Paul Scerri (Eds.). IFAAMAS\/ACM, 1611\u20131612. http:\/\/dl.acm.org\/citation.cfm?id=2616087"},{"key":"e_1_2_1_36_1","volume-title":"Probabilistic Graphical Models - Principles and Techniques","author":"Koller Daphne","year":"1886","unstructured":"Daphne Koller and Nir Friedman. 2009. Probabilistic Graphical Models - Principles and Techniques. MIT Press. isbn:978-0-262-01319-2 http:\/\/mitpress.mit.edu\/catalog\/item\/default.asp?ttype=2&tid=11886"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46029-2_13"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2203.15426"},{"key":"e_1_2_1_39_1","volume-title":"Qu\u00e9bec City","volume":"8855","author":"Lee Junkyu","year":"2014","unstructured":"Junkyu Lee, Radu Marinescu, and Rina Dechter. 2014. Applying Marginal MAP Search to Probabilistic Conformant Planning: Initial Results. In Statistical Relational Artificial Intelligence, Papers from the 2014 AAAI Workshop, Qu\u00e9bec City, Qu\u00e9bec, Canada, July 27, 2014 (AAAI Technical Report, Vol. WS-14-13). AAAI. http:\/\/www.aaai.org\/ocs\/index.php\/WS\/AAAIW14\/paper\/view\/8855"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V30I1.10420"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591290"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591226"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591280"},{"key":"e_1_2_1_44_1","volume-title":"Perov","author":"Mansinghka Vikash","year":"2014","unstructured":"Vikash Mansinghka, Daniel Selsam, and Yura N. Perov. 2014. Venture: a higher-order probabilistic programming platform with programmable inference. CoRR, abs\/1404.0099 (2014), arXiv:1404.0099. arxiv:1404.0099"},{"key":"e_1_2_1_45_1","volume-title":"Nesting Probabilistic Inference. CoRR, abs\/1112.3785","author":"Mantadelis Theofrastos","year":"2011","unstructured":"Theofrastos Mantadelis and Gerda Janssens. 2011. Nesting Probabilistic Inference. CoRR, abs\/1112.3785 (2011), arXiv:1112.3785. arxiv:1112.3785"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.IJAR.2015.03.007"},{"key":"e_1_2_1_47_1","volume-title":"An Introduction to Game Theory","author":"Osborne M.J.","year":"1956","unstructured":"M.J. Osborne. 2004. An Introduction to Game Theory. Oxford University Press. isbn:9780195681581 lccn:2003042981 https:\/\/books.google.com\/books?id=m4yMcgAACAAJ"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.24.11.1127"},{"key":"e_1_2_1_49_1","volume-title":"ProbLog: A Probabilistic Prolog and Its Application in Link Discovery. In IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence","author":"Raedt Luc De","year":"2007","unstructured":"Luc De Raedt, Angelika Kimmig, and Hannu Toivonen. 2007. ProbLog: A Probabilistic Prolog and Its Application in Link Discovery. In IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007, Manuela M. Veloso (Ed.). 2462\u20132467. http:\/\/ijcai.org\/Proceedings\/07\/Papers\/396.pdf"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018","author":"Rainforth Tom","year":"2018","unstructured":"Tom Rainforth. 2018. Nesting Probabilistic Programs. In Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018, Amir Globerson and Ricardo Silva (Eds.). AUAI Press, 249\u2013258. http:\/\/auai.org\/uai2018\/proceedings\/papers\/92.pdf"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2184319.2184345"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00092-1"},{"key":"e_1_2_1_53_1","volume-title":"Artificial Intelligence: A Modern Approach","author":"Russell Stuart","year":"2020","unstructured":"Stuart Russell and Peter Norvig. 2020. Artificial Intelligence: A Modern Approach (4th Edition). Pearson. isbn:9780134610993 http:\/\/aima.cs.berkeley.edu\/","edition":"4"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454078"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference","author":"Sang Tian","year":"2005","unstructured":"Tian Sang, Paul Beame, and Henry A. Kautz. 2005. Performing Bayesian Inference by Weighted Model Counting. In Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, Pennsylvania, USA, Manuela M. Veloso and Subbarao Kambhampati (Eds.). AAAI Press \/ The MIT Press, 475\u2013482. http:\/\/www.aaai.org\/Library\/AAAI\/2005\/aaai05-075.php"},{"key":"e_1_2_1_56_1","unstructured":"Scott Sanner et al. 2010. Relational dynamic influence diagram language (rddl): Language description. Australian National University."},{"key":"e_1_2_1_57_1","volume-title":"Barto","author":"Sutton Richard S.","year":"1998","unstructured":"Richard S. Sutton and Andrew G. Barto. 1998. Reinforcement learning - an introduction. MIT Press. isbn:978-0-262-19398-6 https:\/\/www.worldcat.org\/oclc\/37293240"},{"volume-title":"Multistage programming: its theory and applications","author":"Taha Walid Mohamed","key":"e_1_2_1_58_1","unstructured":"Walid Mohamed Taha. 1999. Multistage programming: its theory and applications. Oregon Graduate Institute of Science and Technology."},{"key":"e_1_2_1_59_1","volume-title":"The Random Conditional Distribution for Higher-Order Probabilistic Inference. CoRR, abs\/1903.10556","author":"Tavares Zenna","year":"2019","unstructured":"Zenna Tavares, Xin Zhang, Edgar Minaysan, Javier Burroni, Rajesh Ranganath, and Armando Solar-Lezama. 2019. The Random Conditional Distribution for Higher-Order Probabilistic Inference. CoRR, abs\/1903.10556 (2019), arXiv:1903.10556. arxiv:1903.10556"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23461-8_36"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1609\/SOCS.V6I1.18369"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V24I1.7755"},{"key":"e_1_2_1_63_1","volume-title":"Hansen","author":"Yuan Changhe","year":"2010","unstructured":"Changhe Yuan, XiaoJian Wu, and Eric A. Hansen. 2010. Solving Multistage Influence Diagrams using Branch-and-Bound Search. 691\u2013700. https:\/\/dslpitt.org\/uai\/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=2129&proceeding_id=26"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498677"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3720500","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3720500","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:14:35Z","timestamp":1760030075000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3720500"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,9]]},"references-count":64,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2025,4,9]]}},"alternative-id":["10.1145\/3720500"],"URL":"https:\/\/doi.org\/10.1145\/3720500","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2025,4,9]]},"assertion":[{"value":"2024-10-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}