Compiling with Continuations

The last decade has seen a proliferation of advanced control structures, such as async/await, generators, coroutines, fibers, or algebraic effect handlers. These new control structures promise improved program structure (such as the avoidance of “callback hell”) and generally a higher level of abstraction. They are essential to structure large-scale, distributed, and asyncronous applications.

However, composing applications from multiple layers of domain-specific abstractions can come with a significant performance penalty. Ideally, programmers should not be forced to trade-off using the right abstraction (like exception handling, async/await, or effect handlers) with writing high-performance applications.

In this research area, we develop novel strategies to efficient implement advanced control-flow structuring mechanisms. There are two aspects to performance: enabling compile-time optimizations and having efficient run-time constructs.

Compile-time Optimizations

It is our goal to implement optimizations that fully remove the performance overhead, associated with control-flow abstractions, such as exceptions or effect handlers. We aim to optimize control flow across library boundaries in order to obtain performance comparable to hand-written, monolithic code.

In past research, we

  • revisited research on iterated continuation passing style (CPS), a generalization of CPS to support multiple layers of control effects;
  • demonstrated, that iterated CPS is a promising compilation target for effect handlers (research paper), obtaining speed-ups of up to 400x on selected benchmarks;
  • and we developed techniques to integrate resource management into a CPS translation (technical report).

Efficient Runtime Constructs

While we aim to fully remove the overhead of control effects at compile time, sometimes this is not immediately possible. This is for instance the case, when whole program optimizations are not possible (for instance when separate compilation is required). In these cases, an efficient runtime support for control effects becomes important.

In a second line of work, we are implementing optimized runtimes for control effects, such as effect handlers.

Just-in-time Compilation of Control Effects

Finally, combining the two above lines of work, we plan to develop a just-in-time (JIT) compiler, specialized to optimize control effects.

DFG Project: Efficient Compilation of Control Effects (ECCE)

Our research on efficient compilation strategies for control effects is supported by the German Research Foundation (DFG) under project number DFG-448316946.

Abstract

The history of programming language design and implementation is to a significant degree the history of control structures. The last decade has seen a new proliferation of advanced control structures, such as async/await, generators, coroutines, or fibers. These new control structures promise improved program structure (such as the avoidance of "callback hell") and generally a higher level of abstraction.

However, the way such control structures are implemented today is highly unsatisfactory. They are often hard-coded into a language, (i.e., they are not user-definable), they are not composable (i.e., programs using different abstractions cannot be combined in one project), or implementations for one control abstraction cannot be reused to implement similar other control abstractions.

To resolve the aforementioned limitations, we embrace effect handlers as a high-level control abstraction. Backed by a strong theoretical background and a static type- and effect system, effect handlers encourage a modular definition of control abstractions as user-defineable libraries and naturally allow users to compose these libraries in one program. As of today, the abstraction of effect handlers comes with a cost in performance.The goal of the ECCE project (Efficient Compilation of Control Effects) is to remove these costs and provide "control-flow abstraction without regret".

Specifically, we aim to establish a research programme to achieve novel compile-time and just-in-time optimizations for effect handlers, accompanied by both a theoretical framework to reason about correctness and costs as well as implementations for realistic languages. Efficient effect handlers will enable programmers to develop many general purpose, as well as domain specific control-flow constructs without sacrificing performance.

Funding Information

Collaborators

Jonathan Brachthäuser (University of Tübingen)

Philipp Schuster (University of Tübingen)

Marius Müller (University of Tübingen)

Klaus Ostermann (University of Tübingen)

Publications

Region-based Resource Management and Lexical Exception Handlers in Continuation-Passing Style

by Philipp Schuster, Jonathan Immanuel Brachthäuser, and Klaus Ostermann

In European Symposium on Programming (ESOP 2022), 2022.

Learn More

A Typed Continuation-Passing Translation for Lexical Effect Handlers

by Philipp Schuster, Jonathan Immanuel Brachthäuser, Marius Müller, and Klaus Ostermann

In Accepted for publication in Proceedings of the International Conference on Programming Language Design and Implementation (PLDI), 2022.

Learn More

All About That Stack: A Unified Treatment of Regions and Control Effects

by Philipp Schuster, Jonathan Immanuel Brachthäuser, and Klaus Ostermann

Technical report. University of Tübingen, Germany, 2021.

Learn More

Compiling Effect Handlers in Capability-Passing Style

by Philipp Schuster, Jonathan Immanuel Brachthäuser, and Klaus Ostermann

In Proceedings of the International Conference on Functional Programming (ICFP). ACM Press, 2020.

Learn More

Zero-cost Effect Handlers by Staging (Technical Report)

by Philipp Schuster, Jonathan Immanuel Brachthäuser, and Klaus Ostermann

Technical report. University of Tübingen, Germany, 2019.

Learn More

Typing, Representing, and Abstracting Control: Functional Pearl

by Philipp Schuster and Jonathan Brachthäuser

In Proceedings of the International Workshop on Type-Driven Development. ACM Press, 2018.

Learn More