{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:06:34Z","timestamp":1784199994844,"version":"3.55.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,6,10]]},"abstract":"<jats:p>The selection monad on a set consists of selection functions. These select an element from the set, based on a loss (dually, reward) function giving the loss resulting from a choice of an element. Abadi and Plotkin used the monad to model a language with operations making choices of computations taking account of the loss that would arise from each choice. However, their choices were optimal, and they asked if they could instead be programmer provided.<\/jats:p>\n                  <jats:p>\n                    In this work, we present a novel design enabling programmers to do so. We present a version of algebraic effect handlers enriched by computational ideas inspired by the selection monad. Specifically, as well as the usual delimited continuations, our new kind of handlers additionally have access to choice\n                    <jats:italic toggle=\"yes\">continuations<\/jats:italic>\n                    , that give the possible future losses. In this way programmers can write operations implementing optimisation algorithms that are aware of the losses arising from their possible choices.\n                  <\/jats:p>\n                  <jats:p>\n                    We give an operational semantics for a higher-order model language\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mi>\u03bbC<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    , and establish desirable properties including progress, type soundness, and termination for a subset with a mild hierarchical constraint on allowable operation types. We give this subset a selection monad denotational semantics, and prove soundness and adequacy results. We also present a Haskell implementation and give a variety of programming examples.\n                  <\/jats:p>","DOI":"10.1145\/3729321","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"1766-1790","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Handling the Selection Monad"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8496-6096","authenticated-orcid":false,"given":"Gordon","family":"Plotkin","sequence":"first","affiliation":[{"name":"Google DeepMind, Mountain View, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5961-1493","authenticated-orcid":false,"given":"Ningning","family":"Xie","sequence":"additional","affiliation":[{"name":"Google DeepMind; University of Toronto, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470641"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-19(2:3)2023"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371106"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3689798"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40206-7_1"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2014.02.001"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45699-6_2"},{"key":"e_1_3_2_9_1","unstructured":"James Bradbury Roy Frostig Peter Hawkins Matthew James Johnson Chris Leary Dougal Maclaurin George Necula Adam Paszke Jake VanderPlas Skye Wanderman-Milne and Qiao Zhang. 2018. JAX: composable transformations of Python+NumPy programs. http:\/\/github.com\/google\/jax"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","unstructured":"Victor Carbune Thierry Coppey Alexander Daryin Thomas Deselaers Nikhil Sarda and Jay Yagnik. 2019. SmartChoices: Hybridizing Programming and Machine Learning. doi:10.48550\/ARXIV.1810.00619","DOI":"10.48550\/ARXIV.1810.00619"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796807006259"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129509990351"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2010.0471"},{"key":"e_1_3_2_14_1","unstructured":"Martin Escard\u00f3 and Paulo Oliva. 2015. The Herbrand Functional Interpretation of the Double Negation Shift. arXiv:1410.4353 [cs.LO] https:\/\/arxiv.org\/abs\/1410.4353"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13962-8_16"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13962-8_17"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863597.1863605"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90014-7"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-05318-5_1"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/174675.178047"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110257"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563445"},{"key":"e_1_3_2_23_1","volume-title":"Advances in Neural Information Processing Systems","author":"Goodfellow Ian","year":"2014","unstructured":"Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014. Generative Adversarial Nets. In Advances in Neural Information Processing Systems, Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (Eds.), Vol. 27. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2014\/file\/f033ed80deb0234979a61f95710dbe25-Paper.pdf"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3086952"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-21314-4_7"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-74558-4_3"},{"key":"e_1_3_2_27_1","unstructured":"Jules Hedges. 2015. The selection monad as a CPS transformation. arXiv:1503.06061 [cs.PL] https:\/\/arxiv.org\/abs\/1503.06061"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976022.2976033"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.03.013"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500590"},{"key":"e_1_3_2_31_1","unstructured":"Wiktor Kuchta. 2022. Normalisation for Algebraic Effect Handlers. Master\u2019s thesis. University of Wroclaw. Available at https:\/\/github.com\/wikku\/normalization-effect-handlers\/blob\/main\/fscd-term.pdf."},{"key":"e_1_3_2_32_1","unstructured":"Ugo Dal Lago Francesco Gavazzo and Alexis Ghyselen. 2022. On Reinforcement Learning Effect Handlers and the State Monad. arXiv:2203.15426 [cs.PL] https:\/\/arxiv.org\/abs\/2203.15426"},{"key":"e_1_3_2_33_1","volume-title":"Nouvelles m\u00e9thodes pour la d\u00e9termination des orbites des com\u00e8tes: avec un suppl\u00e9ment contenant divers perfectionnemens de ces m\u00e9thodes et leur application aux deux com\u00e8tes de 1805","author":"Legendre Adrien Marie","year":"1806","unstructured":"Adrien Marie Legendre. 1806. Nouvelles m\u00e9thodes pour la d\u00e9termination des orbites des com\u00e8tes: avec un suppl\u00e9ment contenant divers perfectionnemens de ces m\u00e9thodes et leur application aux deux com\u00e8tes de 1805. Courcier."},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","unstructured":"Daan Leijen. 2014. Koka: Programming with Row Polymorphic Effect Types. In Proceedings 5th Workshop on Mathematically Structured Functional Programming MSFP@ETAPS 2014 Grenoble France 12 April 2014 (EPTCS Vol. 153) Paul Blain Levy and Neel Krishnaswami (Eds.). 100\u2013126. doi:10.4204\/EPTCS.153.8","DOI":"10.4204\/EPTCS.153.8"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009872"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3622814"},{"key":"e_1_3_2_37_1","unstructured":"Dan Piponi. 2022. https:\/\/colab.sandbox.google.com\/drive\/1HGs59anVC2AOsmt7C4v8yD6v8gZSJGm6"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03741-2_1"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45315-6_1"},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00590-9_7"},{"key":"e_1_3_2_41_1","unstructured":"Gordon Plotkin and Ningning Xie. 2025. Handling the Selection Monad (Full Version). arXiv:2504.03890 [cs.PL] https:\/\/arxiv.org\/abs\/2504.03890"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2015.12.003"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-9(4:23)2013"},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564096_32"},{"key":"e_1_3_2_45_1","unstructured":"Sebastian Ruder. 2017. An overview of gradient descent optimization algorithms.arXiv:1609.04747 [cs.LG] https:\/\/arxiv.org\/abs\/1609.04747"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454039"},{"key":"e_1_3_2_47_1","volume-title":"Reinforcement learning: An introduction","author":"Sutton Richard S","year":"2018","unstructured":"Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction. MIT press."},{"key":"e_1_3_2_48_1","doi-asserted-by":"publisher","DOI":"10.2307\/2271658"},{"key":"e_1_3_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371119"},{"key":"e_1_3_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3473576"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:07:38Z","timestamp":1784196458000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":49,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729321"],"URL":"https:\/\/doi.org\/10.1145\/3729321","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}