Asymptotic speedup via effect handlers

Abstract

We study a fundamental efficiency benefit afforded by delimited control, showing that for certain higher-order functions, a language with advanced control features offers an asymptotic improvement in runtime over a language without them. Specifically, we consider the generic count problem in the context of a pure functional base language \({\lambda_{\textrm{b}}}\) and an extension \({\lambda_{\textrm{h}}}\) with general effect handlers. We prove that \({\lambda_{\textrm{h}}}\) admits an asymptotically more efficient implementation of generic count than any implementation in \({\lambda_{\textrm{b}}}\). We also show that this gap remains even when \({\lambda_{\textrm{b}}}\) is extended to a language \({{{{{{\lambda_{\textrm{a}}}}}}}}\) with affine effect handlers, which is strong enough to encode exceptions, local state, coroutines and single-shot continuations. This locates the efficiency difference in the gap between ‘single-shot’ and ‘multi-shot’ versions of delimited control.

To our knowledge, these results are the first of their kind for control operators.