Delimited Continuations

Delimited Continuations

A limiting factor for effect system performance is the need to implement delimited continuations outside of the runtime. Accordingly, this proposal presents a design for native delimited continuation primitive operations that can be used to efficiently capture the RTS (runtime system) stack. A guiding principle of the design is to be minimal. Rather than burden GHC with the full complexity of designing and implementing algebraic effects, this proposal provides a path for users to experiment with designs as ordinary Haskell libraries without sacrificing performance.

Effect systems provide the ability to capture portions of the current continuation. Without native support for first-class continuations from the runtime, this must be implemented by writing the program in CPS. In Haskell, this is naturally expressed using a monad, Cont.

There already exist various monadic implementations of delimited control (unlike regular continuations, delimited continuations return a value, and thus may be reused and composed).

• The CC-delcont library - a monadic treatment of delimited continuations. This implements the delimited continuation monad CC and transformer CCT, which may be respectively used to execute computations with delimited control and layer delimited control effects over an arbitrary monad.

• The Freer monad, which has been used in several libraries to implement delimited continuations specifically for the purpose of effect systems.

• The effects library, which uses nested continuation transformers to achieve delimited control.

These approaches have various performance trade-offs, but they all suffer from the same fatal flaw: programs must pay for the cost of continuation capture, even if they never actually capture the continuation. (To capture a continuation means to expose a slice of a continuation frame, i think). This is a real problem for effect systems as many programs that use effects have no need to capture the continuation. For example, the Reader, State, and Writer effects need no continuation manipulation, and the Error effect only needs to abort the continuation early, not capture it.

The scope of the proposed change is limited to the RTS: no other part of the compiler needs to be touched. The user-facing interface consists of one new primitive type and three new primitive operations.