Asymptotic Speedup via Effect Handlers

Daniel Hillerström, Sam Lindley, John Longley

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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 numbere5
Pages (from-to)1-54
Number of pages54
JournalJournal of Functional Programming
Volume34
DOIs
Publication statusPublished - 5 Apr 2024

Fingerprint

Dive into the research topics of 'Asymptotic Speedup via Effect Handlers'. Together they form a unique fingerprint.

Cite this