Edinburgh Research Explorer

Effects for Efficiency: Asymptotic Speedup with First-Class Control

Research output: Contribution to journalArticlepeer-review

Related Edinburgh Organisations

Open Access permissions



  • Download as Adobe PDF

    Final published version, 449 KB, PDF document

    Licence: Creative Commons: Attribution (CC-BY)

Original languageEnglish
Article number100
Pages (from-to)1-29
Number of pages29
JournalProceedings of the ACM on Programming Languages (PACMPL)
Issue numberICFP
Publication statusPublished - 2 Aug 2020
Event25th ACM SIGPLAN International Conference on Functional Programming - Virtual Conference
Duration: 23 Aug 202026 Aug 2020


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.


25th ACM SIGPLAN International Conference on Functional Programming


Virtual Conference

Event: Conference

Download statistics

No data available

ID: 163468301