What are the requirements to prefer CPS over algebraic data types?

Question

I have little experience with algebraic data types, because I work in a language without native support. Usually one can use continuation passing style to get a remotely similar experience, but the handling of CPS encoded types is less comfortable.

Considering this why would a library like Parsec use CPS?

newtype ParsecT s u m a
    = ParsecT {unParser :: forall b .
                 State s u
              -> (a -> State s u -> ParseError -> m b) -- consumed ok
              -> (ParseError -> m b)                   -- consumed err
              -> (a -> State s u -> ParseError -> m b) -- empty ok
              -> (ParseError -> m b)                   -- empty err
              -> m b
             }

One clue would be the try parser, which rules out the consumed error case by passing the empty error continuation in both cases:

try :: ParsecT s u m a -> ParsecT s u m a
try p =
    ParsecT $ \s cok _ eok eerr ->
    unParser p s cok eerr eok eerr
--                   ^^^^     ^^^^

This is possible, because both continuations cerr and eerr have the same type and only differ in their position, which reminds me of structural typing. While I think you cannot do this with ADTs, there is probably a way to implement the same behavior with them. Apart from this, a single combinator wouldn't justify the far-reachuing decision to rely on CPS. So why was this decision made?

Buckthorn

I think there's a performance benefit here - less intermediate structures. In terms of expressivity, I think they're "equal". – Estellestella

I believe this is an old design decision, originally made because of performance reasons, but on modern GHC non-CPS parsers are much faster than CPS ones. For resumable parsers though CPS provides a simple implementation. – Diarmuid

@AndrásKovács Do you have some links handy with benchmark comparisons of the two? I'm interested in reading more. – Estellestella

@AndrásKovács, my recollection is that the very modern serialise package uses CPS, but takes other steps to avoid relying too much on the optimizer (maybe eschewing specialization?). Then again, parsing is not the same as deserialization. – Pendulum

@Pendulum Unfortunately I don't have a comparison of CPS and non-CPS parsers with otherwise exactly the same functionality and semantics. I do notice though that none of the fastest libraries are CPS. CPS also prevents e.g. unboxed sums which didn't exist in old times but which is a major boost now. – Diarmuid

For serialization the non-CPS persist is one of the several non-CPS fastest choices. For parsing, bytesmith and the unreleased parsnip and flatparse libraries are AFAIK the fastest. All of them use unboxed sums and no CPS. They're rather fringe but I'm confident in the assessment. – Diarmuid

Answer 1

This change was made March 2, 2009 in commit a98a3ccb by Antoine Latter. The commit comment was just:

commit a98a3ccbca9835fe749b8cd2d475a0494a84a460
Author: Antoine Latter <[email protected]>
Date:   Mon Mar 2 00:20:00 2009 +0000

    move core data type over to CPS

and it replaced the original ADT for ParsecT:

data ParsecT s u m a
    = ParsecT { runParsecT :: State s u -> m (Consumed (m (Reply s u a))) }

with the new version in your question, adding a runParsecT adapter to convert everything back:

runParsecT :: Monad m => ParsecT s u m a -> State s u -> m (Consumed (m (Reply s u a)))
runParsecT p s = unParser p s cok cerr eok eerr
    where cok a s' err = return . Consumed . return $ Ok a s' err
          cerr err = return . Consumed . return $ Error err
          eok a s' err = return . Empty . return $ Ok a s' err
          eerr err = return . Empty . return $ Error err

I see that he made a blog post in February 2009 where he wrote about finally understanding CPS style and wrote about a CPS version of MaybeT. He didn't talk about any performance advantages, but merely noted that the CPS style had the advantage that Monad and MonadPlus instances for MaybeT could be written without calling >>= or return on the underlying monad or doing explicit case analysis of Maybe values.

In a later December 2009 blog post, he writes about his "obsession with functionalizing monad transformers", gives an example of ErrorT and explicitly notes:

I haven't benchmarked whether or not this is faster for anything, but I find the whole thing a lot of fun.

However, he then goes on in the same blog post to talk about how adding functionality to Parsec 3 to make it a monad transformer instead of a plain old monad and parametrizing it over the input type led to poor performance (about 1.8x slower on some benchmarks). He discovered that converting over to CPS style made Parsec 3 as fast as Parsec 2, at least when those new abstractions (transformers) weren't being used.

Speculating about the timing, I think that Antoine thought CPS was "cool" and had stylistic advantages that appealed to him, so he had it top of mind when working on Parsec 3. When new abstractions in Parsec 3 led to a performance problem, he fortuitously discovered that converting it to CPS appeared to fix them, though he didn't do a detailed study of why (just some speculation in the blog post). However, it's a little unclear to me if he actually converted to CPS first, before discovering the performance advantage, or tried CPS with the expectation that it might help performance. The blog post reads like the conversion was done intentionally to address performance, but that might have just been for sake of simpler exposition in the blog post.

Shute

Answer 2

One big issue is that ParsecT is a monad transformer, and monad transformers defined using ADTs block optimizations more than monad transformers using CPS.

The expression pure x >>= k :: ExceptT e m a gives a minimal illustrative example.

1. With ExceptT e m a defined as m (Either e a), that expressions doesn't simplify well, because it involves (>>=) of the underlying monad m which is abstract.

2. With ExceptT e m a defined as forall r. (Either e a -> m r) -> m r, pure x >>= k basically beta-reduces to k x, without making any assumption about m.

You need to specialize m to optimize a term of type m (Either e a) at all, whereas the continuation-based variant can go a long way without specialization.

However, CPS is also not the ideal representation in Haskell, because the continuations are functions which get allocated on the heap. Functions are cheap but not zero cost.

At the end of the day the abstractness of m in monad transformers really gets in the way, to optimize, you have to specialize, i.e., break modularity. Thus a more promising approach is to use some special primitive monad (IO) with dedicated support from the run-time system, as the basis of an effect system.

---

See also the talk Effects for Less, by Alexis King, and the related library eff.

Lindesnes