Effects for Efficiency: Asymptotic Speedup with First-Class Control

Daniel Hillerström, Sam Lindley, John Longley

Research output: Contribution to journalArticlepeer-review


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 generic count problem using a pure PCF-like base language λb and its extension with effect handlers λh. We show that λh admits an asymptotically more efficient implementation of generic count than any λb implementation. We also show that this efficiency gap remains when λb is extended with mutable state. To our knowledge this result is the first of its kind for control operators.
Original languageEnglish
Article number100
Pages (from-to)1-29
Number of pages29
JournalProceedings of the ACM on Programming Languages
Issue numberICFP
Publication statusPublished - 2 Aug 2020
Event25th ACM SIGPLAN International Conference on Functional Programming - Virtual Conference
Duration: 23 Aug 202026 Aug 2020

Cite this