{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T02:37:35Z","timestamp":1773283055674,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2020,8,2]],"date-time":"2020-08-02T00:00:00Z","timestamp":1596326400000},"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":[[2020,8,2]]},"abstract":"<jats:p>We study the fundamental efficiency of delimited control. Specifically, we show that effect handlers enable an asymptotic improvement in runtime complexity for a certain class of functions. We consider the<jats:italic>generic count<\/jats:italic>problem using a pure PCF-like base language \u03bb<jats:sub><jats:italic>b<\/jats:italic><\/jats:sub>and its extension with effect handlers \u03bb<jats:sub><jats:italic>h<\/jats:italic><\/jats:sub>.<\/jats:p><jats:p>We show that \u03bb<jats:sub><jats:italic>h<\/jats:italic><\/jats:sub>admits an asymptotically more efficient implementation of generic count than any \u03bb<jats:sub><jats:italic>b<\/jats:italic><\/jats:sub>implementation.<\/jats:p><jats:p>We also show that this efficiency gap remains when \u03bb<jats:sub><jats:italic>b<\/jats:italic><\/jats:sub>is extended with mutable state.<\/jats:p><jats:p>To our knowledge this result is the first of its kind for control operators.<\/jats:p>","DOI":"10.1145\/3408982","type":"journal-article","created":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T13:48:02Z","timestamp":1596462482000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Effects for efficiency: asymptotic speedup with first-class control"],"prefix":"10.1145","volume":"4","author":[{"given":"Daniel","family":"Hillerstr\u00f6m","sequence":"first","affiliation":[{"name":"University of Edinburgh, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sam","family":"Lindley","sequence":"additional","affiliation":[{"name":"University of Edinburgh, UK \/ Imperial College London, UK \/ Heriot-Watt University, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Longley","sequence":"additional","affiliation":[{"name":"University of Edinburgh, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,8,3]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"What is algebraic about algebraic efects and handlers? CoRR abs\/","author":"Bauer Andrej","year":"1807"},{"key":"e_1_2_2_2_1","article-title":"Programming with algebraic efects and handlers","volume":"84","author":"Bauer Andrej","year":"2015","journal-title":"J. Log. Algebr. Meth. Program."},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Jordan Bell and Brett Stevens. 2009. A survey of known results and research areas for n-queens. Discret. Math. 309 1 ( 2009 ) 1-31. Jordan Bell and Brett Stevens. 2009. A survey of known results and research areas for n-queens. Discret. Math. 309 1 ( 2009 ) 1-31.","DOI":"10.1016\/j.disc.2007.12.043"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796801004099"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Dariusz Biernacki Maciej Pir\u00f3g Piotr Polesiuk and Filip Sieczkowski. 2019. Abstracting algebraic efects. PACMPL 3 POPL ( 2019 ) 6 : 1-6 : 28. Dariusz Biernacki Maciej Pir\u00f3g Piotr Polesiuk and Filip Sieczkowski. 2019. Abstracting algebraic efects. PACMPL 3 POPL ( 2019 ) 6 : 1-6 : 28.","DOI":"10.1145\/3290319"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Dariusz Biernacki Maciej Pir\u00f3g Piotr Polesiuk and Filip Sieczkowski. 2020. Binders by day labels by night: efect instances via lexically scoped handlers. PACMPL 4 POPL ( 2020 ) 48 : 1-48 : 29. Dariusz Biernacki Maciej Pir\u00f3g Piotr Polesiuk and Filip Sieczkowski. 2020. Binders by day labels by night: efect instances via lexically scoped handlers. PACMPL 4 POPL ( 2020 ) 48 : 1-48 : 29.","DOI":"10.1145\/3371116"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796897002827"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796806006058"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","volume-title":"Observable Sequentiality and Full Abstraction","author":"Cartwright Robert","DOI":"10.1145\/143165.143232"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Lukas Convent Sam Lindley Conor McBride and Craig McLaughlin. 2020. Doo bee doo bee doo. J. Funct. Program. 30 ( 2020 ). To appear. Lukas Convent Sam Lindley Conor McBride and Craig McLaughlin. 2020. Doo bee doo bee doo. J. Funct. Program. 30 ( 2020 ). To appear.","DOI":"10.1017\/S0956796820000039"},{"key":"e_1_2_2_12_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","edition":"3"},{"key":"e_1_2_2_13_1","unstructured":"Robbie Daniels. 2016. Eficient Generic Searches and Programming Language Expressivity. Master's thesis. School of Informatics the University of Edinburgh Scotland. http:\/\/homepages.inf.ed.ac.uk\/jrl\/Research\/Robbie_Daniels_MSc_dissertation.pdf Robbie Daniels. 2016. Eficient Generic Searches and Programming Language Expressivity. Master's thesis. School of Informatics the University of Edinburgh Scotland. http:\/\/homepages.inf.ed.ac.uk\/jrl\/Research\/Robbie_Daniels_MSc_dissertation.pdf"},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1145\/91556.91622","article-title":"Abstracting Control","author":"Danvy Olivier","year":"1990","journal-title":"LISP and Functional Programming. ACM"},{"key":"e_1_2_2_15_1","volume-title":"OCaml Workshop.","author":"Dolan Stephen","year":"2015"},{"key":"e_1_2_2_16_1","first-page":"443","article-title":"Infinite sets that admit fast exhaustive search","author":"Escard\u00f3 Mart\u00edn H\u00f6tzel","year":"2007","journal-title":"LICS. IEEE Computer Society"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385994"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","volume-title":"The Theory and Practice of First-Class Prompts","author":"Felleisen Matthias","DOI":"10.1145\/73560.73576"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(91)90036-W"},{"key":"e_1_2_2_21_1","first-page":"193","volume-title":"The Proceedings of the Conference on Formal Description of Programming Concepts III","author":"Felleisen Matthias"},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1145\/155090.155113","article-title":"The Essence of Compiling with Continuations","author":"Flanagan Cormac","year":"1993","journal-title":"PLDI. ACM"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385981"},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Yannick Forster Ohad Kammar Sam Lindley and Matija Pretnar. 2019. On the expressive power of user-defined efects: Efect handlers monadic reflection delimited control. J. Funct. Program. 29 ( 2019 ) e15. Yannick Forster Ohad Kammar Sam Lindley and Matija Pretnar. 2019. On the expressive power of user-defined efects: Efect handlers monadic reflection delimited control. J. Funct. Program. 29 ( 2019 ) e15.","DOI":"10.1017\/S0956796819000121"},{"key":"e_1_2_2_25_1","first-page":"15","article-title":"Liberating efects with rows and handlers. In TyDe@ICFP","author":"Hillerstr\u00f6m Daniel","year":"2016","journal-title":"ACM"},{"key":"e_1_2_2_26_1","volume-title":"APLAS (Lecture Notes in Computer Science","author":"Hillerstr\u00f6m Daniel"},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","unstructured":"Daniel Hillerstr\u00f6m Sam Lindley and Robert Atkey. 2020a. Efect handlers via generalised continuations. J. Funct. Program. 30 ( 2020 ) e5. Daniel Hillerstr\u00f6m Sam Lindley and Robert Atkey. 2020a. Efect handlers via generalised continuations. J. Funct. Program. 30 ( 2020 ) e5.","DOI":"10.1017\/S0956796820000040"},{"key":"e_1_2_2_28_1","volume-title":"Continuation Passing Style for Efect Handlers. In FSCD (LIPIcs","volume":"84","author":"Hillerstr\u00f6m Daniel"},{"key":"e_1_2_2_29_1","unstructured":"Daniel Hillerstr\u00f6m Sam Lindley and John Longley. 2020b. Efects for Eficiency: Asymptotic Speedup with First-Class Control (extended version). arXiv:2007. 00605 [cs.PL] Daniel Hillerstr\u00f6m Sam Lindley and John Longley. 2020b. Efects for Eficiency: Asymptotic Speedup with First-Class Control (extended version). arXiv:2007. 00605 [cs.PL]"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90059-1"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Neil Jones. 2001. The expressive power of higher-order types or life without CONS. J. Funct. Program. 11 ( 2001 ) 5-94. Neil Jones. 2001. The expressive power of higher-order types or life without CONS. J. Funct. Program. 11 ( 2001 ) 5-94.","DOI":"10.1017\/S0956796800003889"},{"key":"e_1_2_2_32_1","first-page":"145","article-title":"Handlers in action","author":"Kammar Ohad","year":"2013","journal-title":"ICFP. ACM"},{"key":"e_1_2_2_33_1","first-page":"59","article-title":"Extensible efects: an alternative to monad transformers","author":"Kiselyov Oleg","year":"2013","journal-title":"Haskell. ACM"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Oleg Kiselyov Chung-chieh Shan Daniel P. Friedman and Amr Sabry. 2005. Backtracking Interleaving and Terminating Monad Transformers: (Functional Pearl). ( 2005 ) 192-203. Oleg Kiselyov Chung-chieh Shan Daniel P. Friedman and Amr Sabry. 2005. Backtracking Interleaving and Terminating Monad Transformers: (Functional Pearl). ( 2005 ) 192-203.","DOI":"10.1145\/1090189.1086390"},{"key":"e_1_2_2_35_1","volume-title":"The Art of Computer Programming","author":"Knuth Donald"},{"key":"e_1_2_2_36_1","first-page":"486","article-title":"Type directed compilation of row-typed algebraic efects","author":"Leijen Daan","year":"2017","journal-title":"POPL. ACM"},{"key":"e_1_2_2_37_1","volume-title":"John Power, and Hayo Thielecke","author":"Levy Paul Blain","year":"2003"},{"key":"e_1_2_2_38_1","first-page":"500","article-title":"Do be do be do","author":"Lindley Sam","year":"2017","journal-title":"POPL. ACM"},{"key":"e_1_2_2_39_1","first-page":"1","article-title":"When is a functional program not a functional program?","author":"Longley John","year":"1999","journal-title":"ICFP. ACM"},{"key":"e_1_2_2_40_1","unstructured":"John Longley. 2018. The recursion hierarchy for PCF is strict. Logical Methods in Comput. Sci. 14 3 : 8 ( 2018 ) 1-51. John Longley. 2018. The recursion hierarchy for PCF is strict. Logical Methods in Comput. Sci. 14 3 : 8 ( 2018 ) 1-51."},{"key":"e_1_2_2_41_1","doi-asserted-by":"crossref","unstructured":"John Longley. 2019. Bar recursion is not computable via iteration. Computability 8 2 ( 2019 ) 119-153. John Longley. 2019. Bar recursion is not computable via iteration. Computability 8 2 ( 2019 ) 119-153.","DOI":"10.3233\/COM-180200"},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"John Longley and Dag Normann. 2015. Higher-Order Computability. Springer. John Longley and Dag Normann. 2015. Higher-Order Computability. Springer.","DOI":"10.1007\/978-3-662-47992-6"},{"key":"e_1_2_2_43_1","doi-asserted-by":"crossref","unstructured":"Robin Milner. 1977. Fully Abstract Models of Typed \u03bb-Calculi. Theor. Comput. Sci. 4 1 ( 1977 ) 1-22. Robin Milner. 1977. Fully Abstract Models of Typed \u03bb-Calculi. Theor. Comput. Sci. 4 1 ( 1977 ) 1-22.","DOI":"10.1016\/0304-3975(77)90053-6"},{"key":"e_1_2_2_44_1","unstructured":"MLton. 2020. MLton website. http:\/\/www.mlton.org MLton. 2020. MLton website. http:\/\/www.mlton.org"},{"key":"e_1_2_2_45_1","doi-asserted-by":"crossref","unstructured":"Eugenio Moggi. 1991. Notions of Computation and Monads. Inf. Comput. 93 1 ( 1991 ) 55-92. Eugenio Moggi. 1991. Notions of Computation and Monads. Inf. Comput. 93 1 ( 1991 ) 55-92.","DOI":"10.1016\/0890-5401(91)90052-4"},{"key":"e_1_2_2_46_1","doi-asserted-by":"crossref","volume-title":"Purely functional data structures","author":"Okasaki Chris","DOI":"10.1017\/CBO9780511530104"},{"key":"e_1_2_2_47_1","first-page":"104","article-title":"Pure versus impure Lisp","author":"Pippenger Nicholas","year":"1996","journal-title":"POPL. ACM"},{"key":"e_1_2_2_48_1","volume-title":"FSCD (LIPIcs","volume":"131","author":"Pir\u00f3g Maciej","year":"2019"},{"key":"e_1_2_2_49_1","doi-asserted-by":"crossref","unstructured":"Gordon Plotkin. 1977. LCF considered as a programming language. Theor. Comput. Sci. 5 3 ( 1977 ) 223-255. Gordon Plotkin. 1977. LCF considered as a programming language. Theor. Comput. Sci. 5 3 ( 1977 ) 223-255.","DOI":"10.1016\/0304-3975(77)90044-5"},{"key":"e_1_2_2_50_1","volume-title":"Plotkin and John Power","author":"Gordon","year":"2001"},{"key":"e_1_2_2_51_1","volume-title":"Plotkin and Matija Pretnar","author":"Gordon","year":"2013"},{"key":"e_1_2_2_52_1","doi-asserted-by":"crossref","unstructured":"Matija Pretnar. 2015. An Introduction to Algebraic Efects and Handlers. Electr. Notes Theor. Comput. Sci. 319 ( 2015 ) 19-35. Invited tutorial paper. Matija Pretnar. 2015. An Introduction to Algebraic Efects and Handlers. Electr. Notes Theor. Comput. Sci. 319 ( 2015 ) 19-35. Invited tutorial paper.","DOI":"10.1016\/j.entcs.2015.12.003"},{"key":"e_1_2_2_53_1","volume-title":"Proceedings of the Symposium on Computers and Automata 21 ( 1971 ).","author":"Scott Dana","year":"1971"},{"key":"e_1_2_2_54_1","volume-title":"MFCS (Lecture Notes in Computer Science","author":"Simpson Alex K."},{"key":"e_1_2_2_55_1","unstructured":"SML \/NJ. 2020. SML\/NJ website. http:\/\/www.smlnj.org SML \/NJ. 2020. SML\/NJ website. http:\/\/www.smlnj.org"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796809990074"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3408982","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3408982","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:58Z","timestamp":1750193278000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3408982"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,2]]},"references-count":54,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2020,8,2]]}},"alternative-id":["10.1145\/3408982"],"URL":"https:\/\/doi.org\/10.1145\/3408982","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,2]]},"assertion":[{"value":"2020-08-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}