{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T17:25:12Z","timestamp":1787592312610,"version":"build-2736575974"},"reference-count":33,"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\/legalcode"}],"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                    Monads provide a simple and concise interface to user-defined computational effects in functional programming languages. This enables equational reasoning about effects, abstraction over monadic interfaces and the development of monad transformer stacks to allow for multiple effects. Compiler implementors and assembly code programmers similarly virtualize effects, and would benefit from similar abstractions if possible. However, the implementation details of effects seem disconnected from the high-level monad interface: at this lower level much of the design is in the layout of the runtime\n                    <jats:italic toggle=\"yes\">stack<\/jats:italic>\n                    , which is not accessible in a high-level programming language.\n                  <\/jats:p>\n                  <jats:p>\n                    We demonstrate that the monadic interface can be faithfully adapted from high-level functional programming to a lower level setting with explicit stack manipulation. We use a polymorphic call-by-push-value (CBPV) calculus as a setting that captures the essence of stack-manipulation, with a type system that allows programs to define domain-specific stack structures. Within this setting, we show that the existing category-theoretic notion of a\n                    <jats:italic toggle=\"yes\">relative monad<\/jats:italic>\n                    can be used to model the stack-based implementation of computational effects. To demonstrate generality, we adapt a variety of standard monads to relative monads. Additionally, we show that stack-manipulating programs can benefit from a generalization of do-notation we call \u201cmonadic blocks\u201d that allow all CBPV code to be reinterpreted to work with an arbitrary relative monad. As an application, we show that all relative monads extend automatically to relative monad transformers, a process which is not automatic for monads in pure languages.\n                  <\/jats:p>","DOI":"10.1145\/3720434","type":"journal-article","created":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T13:48:26Z","timestamp":1744206506000},"page":"563-589","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Notions of Stack-Manipulating Computation and Relative Monads"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1274-1450","authenticated-orcid":false,"given":"Yuchen","family":"Jiang","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1274-0922","authenticated-orcid":false,"given":"Runze","family":"Xue","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"},{"name":"University of Cambridge, Cambridge, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8141-195X","authenticated-orcid":false,"given":"Max S.","family":"New","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,4,9]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","unstructured":"Andreas Abel Brigitte Pientka David Thibodeau and Anton Setzer. 2013. Copatterns: programming infinite structures by observations. In ACM Symposium on Principles of Programming Languages (POPL) Rome Italy. doi:10.1145\/2480359.2429075","DOI":"10.1145\/2480359.2429075"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","unstructured":"Thorsten Altenkirch James Chapman and Tarmo Uustalu. 2010. Monads Need Not Be Endofunctors. In International Conference on Foundations of Software Science and Computation Structures (FoSSaCS) Paphos Cyprus. 297\u2013311. doi:10.1007\/978-3-642-12032-9_21","DOI":"10.1007\/978-3-642-12032-9_21"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2024.107676"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","unstructured":"Pierre-Louis Curien Marcelo P. Fiore and Guillaume Munch-Maccagnoni. 2016. A theory of effects and resources: adjunction models and polarised calculi. In ACM Symposium on Principles of Programming Languages (POPL) St. Petersburg Florida. doi:10.1145\/2837614.2837652","DOI":"10.1145\/2837614.2837652"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3674654"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2018.21"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","unstructured":"Paul Downen Luke Maurer Zena M. Ariola and Simon Peyton Jones. 2016. Sequent calculus as a compiler intermediate language. In International Conference on Functional Programming (ICFP) Nara Japan. 10.1145\/2951913.2951931","DOI":"10.1145\/2951913.2951931"},{"key":"e_1_3_2_9_1","unstructured":"Dmitri Garbuzov William Mansky Christine Rizkallah and Steve Zdancewic. 2018. Structural Operational Semantics for Control Flow Graph Machines. (2018). arXiv:1805.05400"},{"key":"e_1_3_2_10_1","volume-title":"Interpr\u00e9tation fonctionnelle et \u00e9limination des coupures de l\u2019arithm\u00e9tique d\u2019ordre sup\u00e9rieur","author":"Girard Jean-Yves","year":"1972","unstructured":"Jean-Yves Girard. 1972. Interpr\u00e9tation fonctionnelle et \u00e9limination des coupures de l\u2019arithm\u00e9tique d\u2019ordre sup\u00e9rieur. Ph. D. Dissertation. Universit\u00e9 Paris Diderot."},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","unstructured":"Ralf Hinze. 2000. Deriving backtracking monad transformers. In International Conference on Functional Programming (ICFP) Montreal Canada. doi:10.1145\/357766.351258","DOI":"10.1145\/357766.351258"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","unstructured":"Mauro Jaskelioff. 2009. Modular Monad Transformers. In European Symposium on Programming (ESOP) York UK (Lecture Notes in Computer Science Vol. 5502). 64\u201379. doi:10.1007\/978-3-642-00590-9_6","DOI":"10.1007\/978-3-642-00590-9_6"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","unstructured":"Yuchen Jiang Max S. New Tingting Ding Runze Xue Yuxuan Xia and Nathan Varner. 2025a. Zydeco Implementation. doi:10.5281\/zenodo.14948044","DOI":"10.5281\/zenodo.14948044"},{"key":"e_1_3_2_14_1","doi-asserted-by":"crossref","unstructured":"Yuchen Jiang Runze Xue and Max S. New. 2025b. Notions of Stack-manipulating Computation and Relative Monads (Extended Version). arXiv:2411.12822","DOI":"10.1145\/3720434"},{"key":"e_1_3_2_15_1","volume-title":"Call-by-Push-Value","author":"Levy Paul Blain","year":"2001","unstructured":"Paul Blain Levy. 2001. Call-by-Push-Value. Ph. D. Dissertation. Queen Mary, University of London, London, UK."},{"issue":"5","key":"e_1_3_2_16_1","first-page":"75","article-title":"Adjunction Models for Call-by-Push-Value with Stacks","volume":"14","author":"Levy Paul Blain","year":"2005","unstructured":"Paul Blain Levy. 2005. Adjunction Models for Call-by-Push-Value with Stacks. Theory Appl. Categ. 14, 5 (2005), 75\u201375. http:\/\/www.tac.mta.ca\/tac\/volumes\/14\/5\/14-05abs.html","journal-title":"Theory Appl. Categ."},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","unstructured":"Paul Blain Levy. 2017. Contextual isomorphisms. In ACM Symposium on Principles of Programming Languages (POPL) Paris France. 400\u2013414. doi:10.1145\/3009837.3009898","DOI":"10.1145\/3009837.3009898"},{"key":"e_1_3_2_18_1","unstructured":"Paul Blain Levy. 2019. What is a Monoid? (2019). https:\/\/conferences.inf.ed.ac.uk\/ct2019\/slides\/83.pdf Presentation at Category Theory 2019."},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","unstructured":"Sheng Liang Paul Hudak and Mark Jones. 1995. Monad transformers and modular interpreters. In ACM Symposium on Principles of Programming Languages (POPL) San Francisco California. 333\u2013343. doi:10.1145\/199448.199528","DOI":"10.1145\/199448.199528"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","unstructured":"Sam Lindley Conor McBride and Craig McLaughlin. 2017. Do be do be do. In ACM Symposium on Principles of Programming Languages (POPL) Paris France. 500\u2013514. doi:10.1145\/3009837.3009897","DOI":"10.1145\/3009837.3009897"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129505004962"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90052-4"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796802004446"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","unstructured":"Guillaume Munch-Maccagnoni. 2014. Models of a Non-associative Composition. In International Conference on Foundations of Software Science and Computation Structures (FoSSaCS) Grenoble France. 396\u2013410. doi:10.1007\/978-3-642-54830-7_26","DOI":"10.1007\/978-3-642-54830-7_26"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","unstructured":"Rasmus E. M\u00f8gelberg and Alex K. Simpson. 2007. Relational Parametricity for Computational Effects. In IEEE Symposium on Logic in Computer Science (LICS) Wroclaw Poland. 346\u2013355. doi:10.1109\/LICS.2007.40","DOI":"10.1109\/LICS.2007.40"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","unstructured":"Pierre-Marie P\u00e9drot and Nicolas Tabareau. 2017. An EffectfulWay to Eliminate Addiction to Dependence. In IEEE Symposium on Logic in Computer Science (LICS) Reykjavik Iceland. doi:10.1109\/LICS.2017.8005113","DOI":"10.1109\/LICS.2017.8005113"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371126"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","unstructured":"Simon L. Peyton Jones and Philip Wadler. 1993. Imperative Functional Programming. In ACM Symposium on Principles of Programming Languages (POPL) Charleston South Carolina. 71\u201384. doi:10.1145\/158511.158524","DOI":"10.1145\/158511.158524"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","unstructured":"Gordon D. Plotkin and John Power. 2001. Semantics for Algebraic Operations. In Conference on the Mathematical Foundations of Programming Aarhus Denmark. doi:10.1016\/S1571-0661(04)80970-8","DOI":"10.1016\/S1571-0661(04)80970-8"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/800194.805852"},{"key":"e_1_3_2_31_1","first-page":"513","volume-title":"Information Processing 83, Proceedings of the IFIP 9th World Computer Congress, Paris, France","author":"Reynolds John C.","year":"1983","unstructured":"John C. Reynolds. 1983. Types, Abstraction and Parametric Polymorphism. In Information Processing 83, Proceedings of the IFIP 9th World Computer Congress, Paris, France, R. E. A. Mason (Ed.). 513\u2013523."},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","unstructured":"Hayo Thielecke. 2001. Comparing Control Constructs by Double-barrelled CPS Transforms. (2001). doi:10.1016\/S1571-0661(04)80974-5","DOI":"10.1016\/S1571-0661(04)80974-5"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","unstructured":"Philip Wadler. 1990. Comprehending Monads. In Proceedings of the 1990 ACM Conference on LISP and Functional Programming (Nice France) (LFP \u201990). 61\u201378. doi:10.1145\/91556.91592","DOI":"10.1145\/91556.91592"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/322169.322183"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3720434","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3720434","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T16:31:23Z","timestamp":1787589083000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3720434"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,9]]},"references-count":33,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2025,4,9]]}},"alternative-id":["10.1145\/3720434"],"URL":"https:\/\/doi.org\/10.1145\/3720434","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,9]]},"assertion":[{"value":"2024-10-16","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"}}]}}