Effects for Efficiency: Asymptotic Speedup with First-Class Control
summary
Claim: first-class control gives a real asymptotic advantage. The authors implement a generic count with effect handlers that visits each edge of an N-depth computation tree once, yielding O(2^N) runtime, and prove any implementation in a pure PCF-like core (even with mutable state and exceptions) needs Ω(N·2^N), so there is a strict asymptotic speedup. The paper extends to search and reports empirical measurements validating the gap.
AI-written summary · about
chapters (9)
- 0:00Intro
- 0:28Motivation: space exploration
- 2:45Methodology
- 3:25A predicate and its model
- 5:06Temporary restriction to n-standard predicates
- 5:43Efficient generic count with effect handlers
- 8:50Generic count without effect handlers
- 10:35PCF extensions
- 11:28Summary and future work
related talks
28mFirst-class Names for Effect Handlers
15mEfficient Compilation of Algebraic Effect Handlers
12mTowards Dependently-Typed Control Effects (Extended Abstract)
32mHigh-Level Effect Handlers in C++
17mAn Effectively Ω(c) Language and Runtime
17mThe Bounded Pathwidth of Control-Flow Graphs
01h 05mControl Flow Obfuscation for Featherweight Java + Efficient Fair Conjunction
22mA Type- And Control- Flow Analysis for System FC (Extended Abstract)