Capturing the future by replaying the past (functional pearl)

James Koppel, Gabriel Scherer, 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 to be used in languages that don't natively support continuations, by replaying computations instead of directly capturing state.

What Problem Does This Paper Address?

Many powerful programming language features, like monads and continuations, are often confined to niche languages or require complex monadic syntax. While Filinski showed that delimited continuations can implement any monadic effect, delimited continuations themselves are rare. This paper tackles the challenge of bringing these advanced monadic effects to a wider audience by showing how to implement delimited continuations using more common language features: exceptions and mutable state. This opens the door to using sophisticated programming patterns in a broader range of languages.

Methods

The core innovation is "thermometer continuations," which avoid direct state capture by replaying the entire computation. When a "delimited" point is reached, instead of capturing the current state, the system records the computation's path. To re-enter that state, the entire computation is replayed from the beginning, guided by the recorded path. This replay mechanism is implemented using exceptions and mutable state. The paper also leverages Filinski's construction to show how these thermometer continuations can then be used to implement any monadic effect. A key aspect is the "replay-based nondeterminism" as a simpler warm-up, demonstrating the core replay idea.

Datasets

Not discussed in the paper. The paper focuses on implementation and theoretical aspects, with performance evaluation on existing benchmarks.

Key Insights and Ideas

  • Replay as a Continuation Primitive: The most striking insight is that direct state capture isn't always necessary. Replaying the entire computation, guided by a recorded history, can achieve the same effect as capturing a continuation. This is a clever way to sidestep the need for complex runtime support for continuations.
  • Exceptions and State as Building Blocks: The paper demonstrates that common features like exceptions and mutable state are surprisingly powerful, capable of implementing sophisticated control flow primitives like delimited continuations.
  • Monadic Effects in Mainstream Languages: By providing a path to delimited continuations, this work significantly lowers the barrier to entry for using advanced monadic programming patterns in languages that lack native support.
  • Nondeterminism as a Special Case: The paper shows how the general mechanism for thermometer continuations has an elegant and efficient specialization for nondeterminism, making it a practical tool for handling choice.

Key Results

The paper presents a working implementation of thermometer continuations in SML. Performance benchmarks show that while the generic implementation can be slower than direct approaches, optimized versions are competitive. For search-heavy programs like N-queens, replay-based approaches (including optimized thermometer continuations) offer practical performance, sometimes even outperforming other direct-style implementations. The authors also provide a formal correctness proof for a simplified case of replay-based nondeterminism.

Limitations and Future Work

The authors acknowledge that the basic replay approach can be inefficient, especially for computations with costly pure code and deep branching. They also note that the use of Unsafe.cast for universal types, while carefully designed to be type-safe in their context, is a point of concern. Future work could explore integrating safer type-level mechanisms for universal types and improving the efficiency of the replay machinery, particularly for stateful computations and nested continuations. The paper also suggests that this work could inspire new ways to implement advanced effects in languages like Java.

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 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 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 Gabriel Scherer and Armando Solar-Lezama},
  title = {{Capturing the future by replaying the past (functional pearl)}},
  journal = {Proc. ACM Program. Lang.},
  year = {2018},
  doi = {10.1145/3236771},
}
Figure