{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T07:50:19Z","timestamp":1790927419019,"version":"4.1.0"},"reference-count":69,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T00:00:00Z","timestamp":1712275200000},"content-version":"unspecified","delay-in-days":95,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2024]]},"abstract":"Abstract<\/jats:title>\n \n We study a fundamental efficiency benefit afforded by delimited control, showing that for certain higher-order functions, a language with advanced control features offers an asymptotic improvement in runtime over a language without them. Specifically, we consider the\n generic count<\/jats:italic>\n problem in the context of a pure functional base language\n \n \n \n ${\\lambda_{\\textrm{b}}}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and an extension\n \n \n \n ${\\lambda_{\\textrm{h}}}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n with general\n effect handlers<\/jats:italic>\n . We prove that\n \n \n \n ${\\lambda_{\\textrm{h}}}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n admits an asymptotically more efficient implementation of generic count than any implementation in\n \n \n \n ${\\lambda_{\\textrm{b}}}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We also show that this gap remains even when\n \n \n \n ${\\lambda_{\\textrm{b}}}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is extended to a language\n \n \n \n ${{{{{{\\lambda_{\\textrm{a}}}}}}}}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n with\n affine effect handlers<\/jats:italic>\n , which is strong enough to encode exceptions, local state, coroutines and single-shot continuations. This locates the efficiency difference in the gap between \u2018single-shot\u2019 and \u2018multi-shot\u2019 versions of delimited control.\n <\/jats:p>\n To our knowledge, these results are the first of their kind for control operators.<\/jats:p>","DOI":"10.1017\/s0956796824000030","type":"journal-article","created":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T09:06:42Z","timestamp":1712308002000},"update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":4,"title":["Asymptotic speedup via effect handlers"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4730-9315","authenticated-orcid":false,"given":"DANIEL","family":"HILLERSTR\u00d6M","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1360-4714","authenticated-orcid":false,"given":"SAM","family":"LINDLEY","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"JOHN","family":"LONGLEY","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2024,4,5]]},"reference":[{"key":"S0956796824000030_ref46","doi-asserted-by":"publisher","DOI":"10.1145\/178243.178246"},{"key":"S0956796824000030_ref47","first-page":"486","volume-title":"In POPL","author":"Leijen","year":"2017"},{"key":"S0956796824000030_ref11","first-page":"48:1","article-title":"Binders by day, labels by night: Effect instances via lexically scoped handlers","volume":"4","author":"Biernacki","year":"2020","journal-title":"PACMPL"},{"key":"S0956796824000030_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796820000027"},{"key":"S0956796824000030_ref56","unstructured":"MLton. (2020) MLton website."},{"key":"S0956796824000030_ref66","first-page":"456","volume-title":"In MFCS","author":"Simpson","year":"1998"},{"key":"S0956796824000030_ref3","unstructured":"Bauer, A. (2018) What is algebraic about algebraic effects and handlers? CoRR. abs\/1807.05923."},{"key":"S0956796824000030_ref4","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-10(4:9)2014"},{"key":"S0956796824000030_ref62","first-page":"1","volume-title":"FoSSaCS","author":"Plotkin","year":"2001"},{"key":"S0956796824000030_ref65","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2015.12.003"},{"key":"S0956796824000030_ref32","unstructured":"Hillerstr\u00f6m, D. (2021) Foundations for Programming and Implementing Effect Handlers. Ph.D. thesis. UK: The University of Edinburgh."},{"key":"S0956796824000030_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2014.02.001"},{"key":"S0956796824000030_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(91)90036-W"},{"key":"S0956796824000030_ref24","unstructured":"Felleisen, M. (1987) The Calculi of Lambda-nu-cs Conversion: A Syntactic Theory of Control and State in Imperative Higher-order Programming Languages. Ph.D. thesis. Indianapolis, IN, USA: Department of Computer Science. AAI8727494."},{"key":"S0956796824000030_ref52","doi-asserted-by":"publisher","DOI":"10.3233\/COM-180200"},{"key":"S0956796824000030_ref21","unstructured":"Dolan, S. , White, L. , Sivaramakrishnan, K. , Yallop, J. & Madhavapeddy, A. (2015) Effective concurrency through algebraic effects. In OCaml Workshop."},{"key":"S0956796824000030_ref50","first-page":"1","volume-title":"When is a functional program not a functional program? In ICFP","author":"Longley","year":"1999"},{"key":"S0956796824000030_ref30","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796819000121"},{"key":"S0956796824000030_ref35","unstructured":"Hillerstr\u00f6m, D. , Lindley, S. , Atkey, R. & Sivaramakrishnan, K. C. (2017) Continuation passing style for effect handlers. In FSCD. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 18:1\u201318:19."},{"key":"S0956796824000030_ref20","first-page":"151","volume-title":"LISP and Functional Programming","author":"Danvy","year":"1990"},{"key":"S0956796824000030_ref43","doi-asserted-by":"publisher","DOI":"10.1145\/1086365.1086390"},{"key":"S0956796824000030_ref18","volume-title":"Introduction to Algorithms","author":"Cormen","year":"2009"},{"key":"S0956796824000030_ref19","unstructured":"Daniels, R. (2016) Efficient Generic Searches and Programming Language Expressivity. Master\u2019s thesis. UK: School of Informatics, the University of Edinburgh."},{"key":"S0956796824000030_ref28","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155113"},{"key":"S0956796824000030_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796897002827"},{"key":"S0956796824000030_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796806006058"},{"key":"S0956796824000030_ref22","first-page":"443","volume-title":"In LICS","author":"Escard\u00f3","year":"2007"},{"key":"S0956796824000030_ref29","first-page":"45","volume-title":"In PLDI","author":"Flatt","year":"2020"},{"key":"S0956796824000030_ref37","doi-asserted-by":"publisher","DOI":"10.1145\/3408982"},{"key":"S0956796824000030_ref38","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90059-1"},{"key":"S0956796824000030_ref53","volume-title":"Theory and Applications of Computability","author":"Longley","year":"2015"},{"key":"S0956796824000030_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73576"},{"key":"S0956796824000030_ref60","unstructured":"Pir\u00f3g, M. , Polesiuk, P. & Sieczkowski, F. (2019) Typed equivalence of effect handlers and delimited control. In FSCD. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 30:1\u201330:16."},{"key":"S0956796824000030_ref61","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90044-5"},{"key":"S0956796824000030_ref2","unstructured":"Barendregt, H. P. (1984) The Lambda Calculus: Its Syntax and Semantics, revised ed. North-Holland."},{"key":"S0956796824000030_ref45","first-page":"121","article-title":"\u00dcber eine Schlussweise aus dem Endlichen ins Unendliche","volume":"3","author":"K\u00f6nig","year":"1927","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"S0956796824000030_ref54","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-13346-1_15"},{"key":"S0956796824000030_ref10","first-page":"6:1","article-title":"Abstracting algebraic effects","volume":"3","author":"Biernacki","year":"2019","journal-title":"PACMPL"},{"key":"S0956796824000030_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796820000039"},{"key":"S0956796824000030_ref63","first-page":"80","volume-title":"In ESOP","author":"Plotkin","year":"2009"},{"key":"S0956796824000030_ref27","unstructured":"Felleisen, M. & Friedman, D. P. (1987) Control operators, the SECD-machine, and the \u03bb-calculus. In The Proceedings of the Conference on Formal Description of Programming Concepts III, Ebberup, Denmark. Elsevier, pp. 193\u2013217."},{"key":"S0956796824000030_ref58","volume-title":"Purely Functional Data Structures","author":"Okasaki","year":"1999"},{"key":"S0956796824000030_ref36","doi-asserted-by":"publisher","DOI":"10.1145\/3408982"},{"key":"S0956796824000030_ref39","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800003889"},{"key":"S0956796824000030_ref44","volume-title":"The Art of Computer Programming, Volume 1: Fundamental Algorithms","author":"Knuth","year":"1997"},{"key":"S0956796824000030_ref59","first-page":"104","volume-title":"In POPL","author":"Pippenger","year":"1996"},{"key":"S0956796824000030_ref57","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90052-4"},{"key":"S0956796824000030_ref68","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796809990074"},{"key":"S0956796824000030_ref41","first-page":"159","volume-title":"In TFP","author":"Kawahara","year":"2020"},{"key":"S0956796824000030_ref49","first-page":"500","volume-title":"In POPL","author":"Lindley","year":"2017"},{"key":"S0956796824000030_ref42","first-page":"59","volume-title":"Haskell","author":"Kiselyov","year":"2013"},{"key":"S0956796824000030_ref34","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796820000040"},{"key":"S0956796824000030_ref69","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90011-0"},{"key":"S0956796824000030_ref51","first-page":"1","article-title":"The recursion hierarchy for PCF is strict","volume":"14","author":"Longley","year":"2018","journal-title":"Logical Methods Comput. Sci."},{"key":"S0956796824000030_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90045-4"},{"key":"S0956796824000030_ref64","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-9(4:23)2013"},{"key":"S0956796824000030_ref16","first-page":"328","author":"Cartwright","year":"1992"},{"key":"S0956796824000030_ref67","first-page":"206","volume-title":"In PLDI","author":"Sivaramakrishnan","year":"2021"},{"key":"S0956796824000030_ref33","doi-asserted-by":"publisher","DOI":"10.1145\/2976022.2976033"},{"key":"S0956796824000030_ref48","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00088-9"},{"key":"S0956796824000030_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796801004099"},{"key":"S0956796824000030_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/3428194"},{"key":"S0956796824000030_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.043"},{"key":"S0956796824000030_ref9","unstructured":"Berger, U. (1990) Totale Objekte und Mengen in der Bereichstheorie. Ph.D. thesis. Munich: Ludwig Maximillians-Universtit\u00e4t."},{"key":"S0956796824000030_ref23","first-page":"75","volume-title":"In PLDI","author":"Farvardin","year":"2020"},{"key":"S0956796824000030_ref40","first-page":"145","volume-title":"In ICFP","author":"Kammar","year":"2013"},{"key":"S0956796824000030_ref8","doi-asserted-by":"crossref","unstructured":"Benton, P. (1994) A mixed linear and non-linear logic: Proofs, terms and models. In CSL. Springer, pp. 121\u2013135.","DOI":"10.1007\/BFb0022251"},{"key":"S0956796824000030_ref1","unstructured":"Barber, A. (1996) Dual Intuitionistic Linear Logic. Technical report ECS-LFCS-96-347, University of Edinburgh."},{"key":"S0956796824000030_ref55","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90053-6"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796824000030","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T22:37:02Z","timestamp":1779835022000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796824000030\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"references-count":69,"alternative-id":["S0956796824000030"],"URL":"https:\/\/doi.org\/10.1017\/s0956796824000030","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}],"article-number":"e5"}}