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