Capturing the Future by Replaying the Past.

James Koppel, Armando Solar-Lezama

TL;DR

This paper introduces "thermometer continuations," a novel way to implement delimited continuations using only exceptions and mutable state. This allows powerful monadic effects, previously confined to niche languages, to be implemented in mainstream languages like Scala, bringing advanced functional programming paradigms to a wider audience.

What Problem Does This Paper Address?

Many powerful programming concepts, like continuations and nondeterminism, are often relegated to specialized languages or require complex monadic encodings. While delimited continuations offer a way to implement arbitrary monadic effects in a direct style, they are rarely built into programming languages. Traditional implementations of delimited continuations require capturing an intermediate state of computation, which can be complex and require specific runtime support. The authors aim to bridge this gap by showing how to implement delimited continuations using only exceptions and mutable state, features common in most programming languages. This would democratize access to advanced functional programming techniques.

Methods

The core innovation is "thermometer continuations," which implement delimited continuations by replaying the entire computation from the start. Instead of directly capturing an intermediate state, the computation is guided by a recording of past choices. This replay mechanism is built upon two key ideas:

  • Replay-based nondeterminism: A simplified version is presented first, demonstrating how to achieve nondeterministic choice by replaying the computation and using state to track which choice to make at each step. This is extended to handle multiple choices and nested nondeterministic blocks.
  • Thermometer continuations: This generalizes the replay idea to delimited continuations. It uses exceptions and state to manage the replay process, effectively capturing and replaying continuations without direct runtime support for continuation capture. The name "thermometer" comes from a visualization of the process.

The paper also discusses Filinski's construction, which shows how delimited continuations can implement any monadic effect, and how thermometer continuations can be combined with this to achieve direct-style monadic programming. Optimizations are proposed to mitigate the performance overhead of replaying.

Datasets

Not discussed in the paper. The paper focuses on implementing a programming construct and evaluating its performance on existing benchmarks.

Key Insights and Ideas

  • Replay as a Continuation Capture Mechanism: The most striking insight is that replaying an entire computation can serve as a mechanism to capture and reuse continuations, bypassing the need for explicit runtime support for continuation capture.
  • Exceptions and State are Sufficient: The paper demonstrates that powerful control flow primitives like delimited continuations can be built using only exceptions and mutable state, which are widely available.
  • Monadic Reflection via Delimited Control: Filinski's insight that delimited control can implement monadic reflection is crucial. This allows for a unified way to express various monadic effects.
  • Performance is Surprisingly Practical: Despite the seemingly inefficient approach of replaying computations, the benchmarks show that thermometer continuations can achieve competitive performance, especially with optimizations.

Key Results

  • Implementation of Delimited Continuations: The paper successfully implements delimited continuations using only exceptions and mutable state, a significant contribution for language design.
  • Direct-Style Monadic Effects: By combining thermometer continuations with Filinski's construction, the paper shows how to implement arbitrary monadic effects in direct style, making them accessible in a wider range of languages.
  • Performance Benchmarks: The N-queens benchmark and parsing benchmarks demonstrate that replay-based approaches, while having overhead, are surprisingly practical. Optimized thermometer continuations perform comparably to other direct-style implementations and are often faster than generic delimited control implementations. For example, in the N-queens benchmark, optimized thermometers are competitive with other direct-style implementations. In parsing benchmarks, unoptimized thermometer continuations even outperform other methods in certain scenarios.

Limitations and Future Work

  • Unsafe Casts: The implementation of thermometer continuations uses Unsafe.cast for universal types to handle heterogeneous types in continuations. While designed to be type-safe in practice, the authors acknowledge this as a limitation and point to Filinski's work on type-safe implementations.
  • Garbage Collection and Closures: Implementing thermometer continuations in languages like C would require manual management of closures and environments, posing challenges for memory management.
  • Optimization for State Monad: The authors mention that their optimizations for fusing thermometer continuations with monadic reflection do not yet work with the state monad, which is an area for future work.
  • Integration with Runtime Systems: The paper suggests that integrating the generation of universal embeddings within replay machinery could lead to safer implementations.
  • Practicality in Mainstream Languages: While the paper shows practical performance, further work is needed to integrate these ideas seamlessly into mainstream language runtimes for optimal efficiency.

Summary updated

Abstract

Delimited continuations are the mother of all monads! So goes the slogan inspired by Filinski's 1994 paper, which showed that delimited continuations can implement any monadic effect, letting the programmer use an effect as easily as if it was built into the language. It's a shame that not many languages have delimited continuations. Luckily, exceptions and state are also the mother of all monads! In this Pearl, we show how to implement delimited continuations in terms of exceptions and state, a construction we call $\textit{thermometer continuations}$. While traditional implementations of delimited continuations require some way of "capturing" an intermediate state of the computation, the insight of thermometer continuations is to reach this intermediate state by replaying the entire computation from the start, guiding it using a recording it so that the same thing happens until the captured point. Along the way, we explain delimited continuations and monadic reflection, show how the Filinski construction lets thermometer continuations express any monadic effect, share an elegant special-case for nondeterminism, and discuss why our construction is not prevented by theoretical results that exceptions and state cannot macro-express continuations.
BibTeX
@article{koppel2018capturing,
  author = {James Koppel and Armando Solar-Lezama},
  title = {{Capturing the Future by Replaying the Past.}},
  journal = {Proc. ACM Program. Lang.},
  year = {2018},
  doi = {10.1145/3236771},
}

Loading related content...

Figure