{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T22:18:25Z","timestamp":1770243505272,"version":"3.49.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"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":[[2024,10,8]]},"abstract":"<jats:p>\n                    Lexically scoping effect handlers is a language-design idea that equips algebraic effects with a modular semantics: it enables local-reasoning principles without giving up on the control-flow expressiveness that makes effect handlers powerful. However, we observe that existing implementations risk incurring costs akin to the run-time search for dynamically scoped handlers. This paper presents a compilation strategy for lexical effect handlers, adhering to the lexical scoping principle and targeting a language with low-level control over stack layout. Key aspects of this approach are formalized and proven correct. We embody the ideas in a language called L\n                    <jats:sc>exa<\/jats:sc>\n                    : the L\n                    <jats:sc>exa<\/jats:sc>\n                    compiler translates high-level effect handling to low-level stack switching. We evaluate the L\n                    <jats:sc>exa<\/jats:sc>\n                    compiler on a set of benchmarks; the results suggest that it generates efficient code, reducing running-time complexity from quadratic to linear in some cases.\n                  <\/jats:p>","DOI":"10.1145\/3689770","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T03:23:04Z","timestamp":1728357784000},"page":"1670-1698","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Lexical Effect Handlers, Directly"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-0842-4697","authenticated-orcid":false,"given":"Cong","family":"Ma","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-0100-0201","authenticated-orcid":false,"given":"Zhaoyi","family":"Ge","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7057-0912","authenticated-orcid":false,"given":"Edward","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8206-4694","authenticated-orcid":false,"given":"Yizhou","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,10,8]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"[n.d.]. Effect handlers benchmarks suite. https:\/\/github.com\/effect-handlers\/effect-handlers-bench Accessed: 2024-04-01."},{"key":"e_1_3_1_3_2","unstructured":"[n.d.]. MLton. http:\/\/mlton.org"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158096"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371116"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380180902"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3527320"},{"key":"e_1_3_1_8_2","article-title":"Effects as capabilities: Effect handlers and lightweight effect polymorphism","volume":"4","author":"Brachth\u00e4user Jonathan Immanuel","year":"2020","unstructured":"Jonathan Immanuel Brachth\u00e4user, Philipp Schuster, and Klaus Ostermann. 2020. Effects as capabilities: Effect handlers and lightweight effect polymorphism. Proc. of the ACM on Programming Languages (PACMPL) 4, OOPSLA (Nov. 2020). https:\/\/doi.org\/10.1145\/3428194 10.1145\/3428194","journal-title":"Proc. of the ACM on Programming Languages (PACMPL)"},{"key":"e_1_3_1_9_2","article-title":"Effekt: Capability-passing style for type- and effect-safe, extensible effect handlers in Scala","volume":"30","author":"Brachth\u00e4user Jonathan Immanuel","year":"2020","unstructured":"Jonathan Immanuel Brachth\u00e4user, Philipp Schuster, and Klaus Ostermann. 2020. Effekt: Capability-passing style for type- and effect-safe, extensible effect handlers in Scala. Journal of Functional Programming (JFP) 30 (March 2020). https:\/\/doi.org\/10.1017\/S0956796820000027 10.1017\/S0956796820000027","journal-title":"Journal of Functional Programming (JFP)"},{"key":"e_1_3_1_10_2","first-page":"6","article-title":"A monadic framework for delimited continuations","volume":"17","author":"Kent Dyvbig R.","year":"2007","unstructured":"R. Kent Dyvbig, Simon Peyton Jones, and Amr Sabry. 2007. A monadic framework for delimited continuations. Journal of Functional Programming (JFP) 17, 6 (2007). https:\/\/doi.org\/10.1017\/S0956796807006259 10.1017\/S0956796807006259","journal-title":"Journal of Functional Programming (JFP)"},{"key":"e_1_3_1_11_2","article-title":"From folklore to fact: comparing implementations of stacks and continuations","author":"Farvardin Kavon","year":"2020","unstructured":"Kavon Farvardin and John Reppy. 2020. From folklore to fact: comparing implementations of stacks and continuations. In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI). https:\/\/doi.org\/10.1145\/3385412.3385994 10.1145\/3385412.3385994","journal-title":"In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI)"},{"key":"e_1_3_1_12_2","article-title":"The essence ofcompiling withcontinuations","author":"Flanagan Cormac","year":"1993","unstructured":"Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. 1993. The essence ofcompiling withcontinuations. In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI). https:\/\/doi.org\/10.1145\/155090.155113 10.1145\/155090.155113","journal-title":"In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI)"},{"key":"e_1_3_1_13_2","volume-title":"The Java Language Specification","author":"Gosling James","year":"2024","unstructured":"James Gosling, Bill Joy, Guy Steele, Gilad Bracha, Alex Buckley, Daniel Smith, and Gavin Bierman. 2024. The Java Language Specification (SE 22 ed.). Oracle America, Inc. https:\/\/docs.oracle.com\/javase\/specs\/jls\/se22\/jls22.pdf","edition":"22"},{"key":"e_1_3_1_14_2","article-title":"A generalization of exceptions and control in ML-like languages","author":"Gunter Carl A.","year":"1995","unstructured":"Carl A. Gunter, Didier R\u00e9my, and Jon G. Riecke. 1995. A generalization of exceptions and control in ML-like languages. In Int\u2019l Conf. on Functional Programming Languages and Computer Architecture (FPCA).","journal-title":"In Int\u2019l Conf. on Functional Programming Languages and Computer Architecture (FPCA)"},{"key":"e_1_3_1_15_2","unstructured":"Daniel Hillerstr\u00f6m. [n.d.]. multicont. https:\/\/opam.ocaml.org\/packages\/multicont Accessed: 2024-07-01."},{"key":"e_1_3_1_16_2","article-title":"Handlers in action","author":"Kammar Ohad","year":"2013","unstructured":"Ohad Kammar, Sam Lindley, and Nicolas Oury. 2013. Handlers in action. In ACM SIGPLAN Conf. on Functional Programming (ICFP). https:\/\/doi.org\/10.1145\/2500365.2500590 10.1145\/2500365.2500590","journal-title":"In ACM SIGPLAN Conf. on Functional Programming (ICFP)"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009872"},{"key":"e_1_3_1_18_2","unstructured":"Daan Leijen and KC Sivamarakrishnan. 2021. libmprompt. https:\/\/github.com\/koka-lang\/libmprompt"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-009-9155-4"},{"key":"e_1_3_1_20_2","article-title":"Interruptible iterators","author":"Liu Jed","year":"2006","unstructured":"Jed Liu, Aaron Kimball, and Andrew C. Myers. 2006. Interruptible iterators. In ACM SIGPLAN Symp. on Principles of Programming Languages (POPL). https:\/\/doi.org\/10.1145\/1111037.1111063 10.1145\/1111037.1111063","journal-title":"ACM SIGPLAN Symp. on Principles of Programming Languages (POPL)"},{"key":"e_1_3_1_21_2","unstructured":"Cong Ma Zhaoyi Ge Edward Lee and Yizhou Zhang. 2024. Lexical Effect Handlers Directly (artifact). https:\/\/doi.org\/10.5281\/zenodo.13770453 10.5281\/zenodo.13770453"},{"key":"e_1_3_1_22_2","volume-title":"Lexical Effect Handlers, Directly (Extended Version)","author":"Ma Cong","year":"2024","unstructured":"Cong Ma, Zhaoyi Ge, Edward Lee, and Yizhou Zhang. 2024. Lexical Effect Handlers, Directly (Extended Version). Technical Report CS-2024-04. School of Computer Science, University of Waterloo."},{"key":"e_1_3_1_23_2","article-title":"From capabilities to regions: Enabling efficient compilation of lexical effect handlers","volume":"7","author":"M\u00fcller Marius","year":"2023","unstructured":"Marius M\u00fcller, Philipp Schuster, Jonathan Lindegaard Starup, Klaus Ostermann, and Jonathan Immanuel Brachth\u00e4user. 2023. From capabilities to regions: Enabling efficient compilation of lexical effect handlers. Proc. of the ACM on Programming Languages (PACMPL) 7, OOPSLA2 (Oct. 2023). https:\/\/doi.org\/10.1145\/3622831 10.1145\/3622831","journal-title":"Proc. of the ACM on Programming Languages (PACMPL)"},{"key":"e_1_3_1_24_2","article-title":"Continuing Web Assembly with effect handlers","volume":"7","author":"Phipps-Costin Luna","year":"2023","unstructured":"Luna Phipps-Costin, Andreas Rossberg, Arjun Guha, Daan Leijen, Daniel Hillerstr\u00f6m, KC Sivaramakrishnan, Matija Pretnar, and Sam Lindley. 2023. Continuing Web Assembly with effect handlers. Proc. of the ACM on Programming Languages (PACMPL) 7, OOPSLA2 (Oct. 2023). https:\/\/doi.org\/10.1145\/3622814 10.1145\/3622814","journal-title":"Proc. of the ACM on Programming Languages (PACMPL)"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023064908962"},{"key":"e_1_3_1_26_2","first-page":"4","article-title":"Handling algebraic effects","volume":"9","author":"Plotkin Gordon","year":"2013","unstructured":"Gordon Plotkin and Matija Pretnar. 2013. Handling algebraic effects. Logical Methods in Computer Science 9, 4 (Dec. 2013).","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/141471.141563"},{"key":"e_1_3_1_28_2","article-title":"A typed continuationpassing translation for lexical effect handlers","author":"Schuster Philipp","year":"2022","unstructured":"Philipp Schuster, Jonathan Immanuel Brachth\u00e4user, Marius M\u00fcller, and Klaus Ostermann. 2022. A typed continuationpassing translation for lexical effect handlers. In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI). https:\/\/doi.org\/10.1145\/3519939.3523710 10.1145\/3519939.3523710","journal-title":"In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI)"},{"key":"e_1_3_1_29_2","article-title":"Retrofitting effect handlers onto OCaml","author":"Sivaramakrishnan KC","year":"2021","unstructured":"KC Sivaramakrishnan, Stephen Dolan, Leo White, Tom Kelly, Sadiq Jaffer, and Anil Madhavapeddy. 2021. Retrofitting effect handlers onto OCaml. In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI). https:\/\/doi.org\/10.1145\/3453483.3454039 10.1145\/3453483.3454039","journal-title":"In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI)"},{"key":"e_1_3_1_30_2","article-title":"Theorems for free!","author":"Wadler Philip","year":"1989","unstructured":"Philip Wadler . 1989. Theorems for free!. In Int\u2019l Conf. on Functional Programming Languages and Computer Architecture (FPCA). https:\/\/doi.org\/10.1145\/99370.99404 10.1145\/99370.99404","journal-title":"In Int\u2019l Conf. on Functional Programming Languages and Computer Architecture (FPCA)"},{"key":"e_1_3_1_31_2","article-title":"Effect handlers, evidently","volume":"4","author":"Xie Ningning","year":"2020","unstructured":"Ningning Xie, Jonathan Immanuel Brachth\u00e4user, Daniel Hillerstr\u00f6m, Philipp Schuster, and Daan Leijen. 2020. Effect handlers, evidently. Proc. of the ACM on Programming Languages (PACMPL) 4, ICFP (2020). https:\/\/doi.org\/10.1145\/3408981 10.1145\/3408981","journal-title":"Proc. of the ACM on Programming Languages (PACMPL)"},{"key":"e_1_3_1_32_2","article-title":"First-class names for effect handlers","volume":"6","author":"Xie Ningning","year":"2022","unstructured":"Ningning Xie, Youyou Cong, Kazuki Ikemori, and Daan Leijen. 2022. First-class names for effect handlers. Proc. of the ACM on Programming Languages (PACMPL) 6, OOPSLA2 (Oct. 2022). https:\/\/doi.org\/10.1145\/3563289","journal-title":"Proc. of the ACM on Programming Languages (PACMPL)"},{"key":"e_1_3_1_33_2","article-title":"Generalized evidence passing for effect handlers: Efficient compilation of effect handlers to c","volume":"5","author":"Xie Ningning","year":"2021","unstructured":"Ningning Xie and Daan Leijen. 2021. Generalized evidence passing for effect handlers: Efficient compilation of effect handlers to c. Proc. of the ACM on Programming Languages (PACMPL) 5, ICFP (2021). https:\/\/doi.org\/10.1145\/3473576 10.1145\/3473576","journal-title":"Proc. of the ACM on Programming Languages (PACMPL)"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738008"},{"key":"e_1_3_1_35_2","article-title":"Abstraction-safe effect handlers via tunneling","volume":"3","author":"Zhang Yizhou","year":"2019","unstructured":"Yizhou Zhang and Andrew C. Myers. 2019. Abstraction-safe effect handlers via tunneling. Proc. of the ACM on Programming Languages (PACMPL) 3, POPL (Jan. 2019). https:\/\/doi.org\/10.1145\/3290318 10.1145\/3290318","journal-title":"Proc. of the ACM on Programming Languages (PACMPL)"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908086"},{"key":"e_1_3_1_37_2","article-title":"Handling bidirectional control flow","volume":"4","author":"Zhang Yizhou","year":"2020","unstructured":"Yizhou Zhang, Guido Salvaneschi, and Andrew C. Myers. 2020. Handling bidirectional control flow. Proc. of the ACM on Programming Languages (PACMPL) 4, OOPSLA (Nov. 2020). https:\/\/doi.org\/10.1145\/3428207 10.1145\/3428207","journal-title":"Proc. of the ACM on Programming Languages (PACMPL)"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689770","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689770","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T09:05:31Z","timestamp":1770195931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689770"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,8]]},"references-count":36,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2024,10,8]]}},"alternative-id":["10.1145\/3689770"],"URL":"https:\/\/doi.org\/10.1145\/3689770","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,8]]},"assertion":[{"value":"2024-04-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}