Continuation-passing style (CPS) in Haskell

Wikipedia: The key to CPS is to remember that:

  1. every function takes an extra argument, its continuation
  2. every argument in a function call must be either a variable or a lambda expression (not a more complex expression)

Wikipedia: This has the effect of turning expressions "inside-out" because the innermost parts of the expression must be evaluated first, so CPS explicates the order of evaluation as well as the control flow

So, the example in the wikipedia example will be as follows.

module Main (main) where

-- Continuation-passing style example
-- <https://en.wikipedia.org/wiki/Continuation-passing_style>

-- Pythagoras in direct style
pyth :: Float -> Float -> Float
pyth a b = sqrt $ a*a + b*b

-- Multiplication in cps style
mult_cps :: Float -> Float -> ((Float -> r) -> r)
mult_cps a b = \k -> k $ a * b

-- Addition in cps style
add_cps :: Float -> Float -> ((Float -> r) -> r)
add_cps a b = \k -> k $ a + b

-- Square root in cps style
sqrt_cps :: Float -> ((Float -> r) -> r)
sqrt_cps a = \k -> k $ sqrt a

-- Pythagoras in cps style
pyth_cps :: Float -> Float -> ((Float -> r) -> r)
pyth_cps a b = \k -> mult_cps a a (\a2 -> mult_cps b b (\b2 -> add_cps a2 b2 (\a2b2 -> sqrt_cps a2b2 k)))

-- Identity in cps style
id_cps :: Float -> (Float -> Float) -> Float
id_cps a k = k $ a

main :: IO ()
main = putStrLn $ (pyth_cps 3 4 show) ++ " = " ++ (show $ pyth 3 4)

Note that cps functions has an extra argument which is the continuation function.

mult_cps :: Float -> Float -> (Float -> r) -> r
mult_cps a b k = k $ a * b

Is evaluation order more clear? Maybe?

pyth_cps 3 4 show
mult_cps 3 3 (\a2 -> mult_cps 4 4 (\b2 -> add_cps a2 b2 (\a2b2 -> sqrt_cps a2b2 show)))
mult_cps 4 4 (\b2 -> add_cps 9 b2 (\a2b2 -> sqrt_cps a2b2 show))
add_cps 9 16 (\a2b2 -> sqrt_cps a2b2 show)
sqrt_cps 25 show
show 5
5

References