To give an idea of why CPS transform can sometimes be more efficient, consider the following two approaches to a "safe divide" function, which check if the denominator is 0: divMay :: Double -> Double -> Maybe Double divMay x y | y == 0 = Nothing | otherwise = Just (x / y) divCPS :: Double -> Double -> a -> (Double -> a) -> a divCPS x y onFail onSuccess | y == 0 = onFail | otherwise = onSuccess (x / y) Presumably, divMay will always force the allocation of a new object when y is not 0, through its usage of Just. divCPS, on the other hand, does not need to perform any allocation. I say presumably, because often times the compiler will be able to optimize this. To see evidence of that, I've put together a small benchmark[1], If I compile with optimizations turned of (-O0), I get results showing that CPS is faster. And looking at the core[2], we can see that divMay really does result in an extra allocation: $ ghc-core --no-cast -- -O0 foo.hs divMay'_r454 :: Double -> Double divMay'_r454 = \ (y_a4hf :: Double) -> Data.Maybe.fromMaybe @ Double (D# 0.0) (case == @ Double $fEqDouble y_a4hf (D# 0.0) of _ [Occ=Dead] { False -> Data.Maybe.Just @ Double (/ @ Double $fFractionalDouble (D# 10.0) y_a4hf); True -> Data.Maybe.Nothing @ Double }) divCPS'_r455 :: Double -> Double divCPS'_r455 = \ (y_a4hg :: Double) -> case == @ Double $fEqDouble y_a4hg (D# 0.0) of _ [Occ=Dead] { False -> id @ Double (/ @ Double $fFractionalDouble (D# 10.0) y_a4hg); True -> D# 0.0 } Yes, core has a lot of stuff going on due to the explicit type signatures, the "magic hash" unboxed types showing up, etc. But as you can see, there's a call to Data.Maybe.Just in divMay' that is not present in divCPS'. Now let's explain that "presumably" comment. GHC is really smart, and if you let it, it will often times optimize away these kinds of things, especially in small examples like this. In this case, the benchmark results show up as almost identical between the two versions, which is hardly surprising when you look at the core: $ ghc-core --no-cast -- -O2 foo.hs divMay'_r4ci :: Double -> Double divMay'_r4ci = \ (y_a4oE :: Double) -> case y_a4oE of _ [Occ=Dead] { D# x_a4Ml -> case x_a4Ml of wild1_X10 { __DEFAULT -> case /## 10.0 wild1_X10 of wild2_a4Rj { __DEFAULT -> D# wild2_a4Rj }; 0.0 -> main9 } } divCPS'_r4cj :: Double -> Double divCPS'_r4cj = \ (y_a4oF :: Double) -> case y_a4oF of _ [Occ=Dead] { D# x_a4Ml -> case x_a4Ml of wild1_X15 { __DEFAULT -> case /## 10.0 wild1_X15 of wild2_a4Rj { __DEFAULT -> D# wild2_a4Rj }; 0.0 -> main9 } } If you look past the different variable names, you'll see that the two functions are in fact identical. So to sum up this (longer than expected) email: * CPS allows you to avoid extra allocations, * but often times GHC can perform that optimization for you itself. You can look at the attoparsec codebase to see its usage of CPS, which is a more complicated usage of this same concept. Continuation passing web frameworks are a totally different story though, and have been covered pretty well elsewhere (probably best by Alberto[3], though others may have different links). [1] https://www.fpcomplete.com/user/snoyberg/random-code-snippets/cps-performanc... [2] Core is a lower-level form that GHC compiles code to before generating machine code. It gives a very good idea of what optimizations have been applied. I used the ghc-core tool for this. Gabriel Gonzalez wrote a nice blog post about this a few years back: http://www.haskellforall.com/2012/10/hello-core.html [3] https://www.fpcomplete.com/user/agocorona On Thu Jan 01 2015 at 6:00:12 AM Cary Cherng wrote:

I read (http://en.wikibooks.org/wiki/Haskell/Continuation_passing_style) that in some circumstances, CPS can be used to improve performance by eliminating certain construction-pattern matching sequences (i.e. a function returns a complex structure which the caller will at some point deconstruct). And that attoparsec is an example of this.

I don't see exactly how CPS gives rise to concrete examples of performance gains. Moreover how does this arise in parsing for example with attoparsec as mentioned.

I also encountered various web frameworks such as mflow that are based on continuations. How a typical http restful system is made into something based around continuations is not something that is obvious to me. And what is gained from that? _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

On Thu, Jan 1, 2015 at 11:00 AM, Cary Cherng wrote:

I don't see exactly how CPS gives rise to concrete examples of performance gains.

If you look at the "Reflection without Remorse" paper, you'll see performance gains painstakingly described for DLists / difference lists of type [a] -> [a]. The authors see such gains as an application of CPS, the moral being that CPS has a broad range of meanings. -- Kim-Ee