Effects for efficiency: Asymptotic speedup with first-class control

Daniel Hillerström; Sam Lindley; John Longley

doi:10.1145/3408982

Effects for efficiency: Asymptotic speedup with first-class control

Daniel Hillerström, Sam Lindley, John Longley

Research output: Contribution to journal › Conference article › peer-review

2 Citations (Scopus)

34 Downloads (Pure)

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 language	English
Article number	100
Journal	Proceedings of the ACM on Programming Languages
Volume	4
Issue number	ICFP
DOIs	https://doi.org/10.1145/3408982
Publication status	Published - 2 Aug 2020
Event	25th ACM SIGPLAN International Conference on Functional Programming 2020 - Duration: 23 Aug 2020 → 28 Aug 2020

Keywords

asymptotic complexity analysis
effect handlers
generic search

ASJC Scopus subject areas

Software
Safety, Risk, Reliability and Quality

Access to Document

10.1145/3408982Licence: CC BY

Download pdf
Copyright © 2020 Owner/Author
Final published version, 449 KBLicence: CC BY

Cite this

@article{a6fbb1a4e70b4204afadbab84672bb80,

title = "Effects for efficiency: Asymptotic speedup with first-class control",

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.",

keywords = "asymptotic complexity analysis, effect handlers, generic search",

author = "Daniel Hillerstr{\"o}m and Sam Lindley and John Longley",

year = "2020",

month = aug,

day = "2",

doi = "10.1145/3408982",

language = "English",

volume = "4",

journal = "Proceedings of the ACM on Programming Languages",

issn = "2475-1421",

publisher = "Association for Computing Machinery",

number = "ICFP",

note = "25th ACM SIGPLAN International Conference on Functional Programming 2020, ICFP 2020 ; Conference date: 23-08-2020 Through 28-08-2020",

}

TY - JOUR

T1 - Effects for efficiency

T2 - 25th ACM SIGPLAN International Conference on Functional Programming 2020

AU - Hillerström, Daniel

AU - Lindley, Sam

AU - Longley, John

PY - 2020/8/2

Y1 - 2020/8/2

N2 - 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.

AB - 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.

KW - asymptotic complexity analysis

KW - effect handlers

KW - generic search

UR - http://www.scopus.com/inward/record.url?scp=85090278171&partnerID=8YFLogxK

U2 - 10.1145/3408982

DO - 10.1145/3408982

M3 - Conference article

SN - 2475-1421

VL - 4

JO - Proceedings of the ACM on Programming Languages

JF - Proceedings of the ACM on Programming Languages

IS - ICFP

M1 - 100

Y2 - 23 August 2020 through 28 August 2020

ER -

Effects for efficiency: Asymptotic speedup with first-class control

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this