Effects for efficiency: Asymptotic speedup with first-class control

Daniel Hillerström, Sam Lindley, John Longley

Research output: Contribution to journalConference article

Abstract

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
JournalProceedings of the ACM on Programming Languages
Volume4
Issue numberICFP
DOIs
Publication statusPublished - 2 Aug 2020
Event25th ACM SIGPLAN International Conference on Functional Programming 2020 -
Duration: 23 Aug 202028 Aug 2020

Keywords

  • asymptotic complexity analysis
  • effect handlers
  • generic search

ASJC Scopus subject areas

  • Software
  • Safety, Risk, Reliability and Quality

Fingerprint Dive into the research topics of 'Effects for efficiency: Asymptotic speedup with first-class control'. Together they form a unique fingerprint.

  • Cite this