1 Intro

This article serves as the background for a future article about effects and effect systems.

I can’t promise that I didn’t let some of this article influence me and anyway it’s a fun read.

{-# LANGUAGE PolyKinds, RankNTypes #-}

module Main where

import Data.Kind (Type)
import Control.Monad (forM)

2 Effects, effectively

I’ll start by posing a question.

The following function loads a state variable of type Int into a variable n, saves a new value (n + 1), and then finally halts and returns with no value (the () type):

state_example_intro :: CPSState Int ()
state_example_intro = do
  n <- cps_load
  cps_save (n + 1)

If I run this function 100 times, I will get back the value () every one of those 100 times. The question is: what will the state value be?

Take this second program:

try_example :: Int -> CPSExcept String Double
try_example n =
  if 0 == n
    then cps_throw "cannot divide by 0"
    else return ( 1.0 / (fromIntegral n) )

absurd_exception_demo :: IO Double
absurd_exception_demo = do
  ns <- forM [0, 1, 2] $ \n -> (try_example n) `catch` (\msg -> do
      putStrLn $ "error: " ++ msg
      return 0)
  return (sum ns)

The function try_example returns a Double-precision floating point number unless you give it an argument of 0. In that case it produces an error String which is printed to the console by catch. The computation recovers (in this case with an arbitrary result value) and continues.

How is this computation able to return a different type entirely in the event of an error, and how is the error routed to catch?

3 CPS

The concept of continuations is used extensively in programming language theory and semantics; they are abstract representations of the program’s current execution state as well as the future of the work to be done.

Most programming languages don’t expose continuations directly to the programmer (after all, does what I just describe sound like it would be terribly straightforward to even use?); rather, other control flow operators are defined in terms of continuations.

Haskell is “most” languages in this regard, but never fear, because we can use continuation passing style (CPS). In CPS, every function explicitly requires one final argument (its continuation) which it will use as its return keyword by passing to it the value being returned. Eg,

my_func arg1 arg2 = do
  x <- foo arg1
  y <- bar x arg2
  return y

is rewritten as

my_func arg1 arg2 ret = do
  x <- foo arg1
  y <- bar x arg2
  ret y

Now, programming like this explicitly would be annoying …

newtype CPS (result :: k) (m :: k -> Type) (answer :: Type) = CPS
  { (#) :: (answer -> m result) -> m result }

instance Functor (CPS r m) where
  fmap f (CPS c) = CPS (\k -> c (k . f))

instance Applicative (CPS r m) where
  pure v = CPS (\k -> k v)
  f <*> v = CPS (\k -> f # \g -> v # (k . g))
  m  *> k = m >>= \_ -> k

instance Monad (CPS r m) where
  return = pure
  m >>= k = _join (fmap k m) where
    _join :: CPS r m (CPS r m a) -> CPS r m a
    _join (CPS cc) = CPS (\k -> cc (\ (CPS c) -> c k))

sixteen :: CPS Int IO Int
sixteen = do
  s <- shift $ \k -> lift $ do
    putStrLn ("Calling (k 4) ...")
    eight <- k 4
    putStrLn ("Calling (k eight) ...")
    k eight -- *this* is the return value
  lift $ putStrLn ("k called with " ++ show s)
  return (s * 2) -- this is *not* the return value

seventeen :: IO ()
seventeen = do
  _16 <- reset sixteen
  putStrLn . show $ _16 + 1

-- some helpers which we will talk more about next article :)

lift :: Monad m => m a -> CPS r m a
lift v = CPS (v >>=)

reset :: Monad m => CPS r m r -> m r
reset (CPS cc) = cc return

shift :: Monad m => ((a -> m r) -> CPS r m r) -> CPS r m a
shift e = CPS (\k -> reset (e k))

4 Defining effects with CPS

FINALLY I can arrive at the point of all this. At the beginning of the article we showcased two effects: mutable local state and exception handling.

The examples are worth experimenting with as we will be examining them further in the next article. Nevertheless, we have everything we need right here to model effects with continuations.

type CPSState s a = forall r. CPS r ((->) s) a

cps_load :: CPSState s s
cps_load = CPS (\k s -> k s s)

cps_save :: s -> CPSState s ()
cps_save s = CPS (\k _ -> k () s)

run_cps_state :: CPSState s a -> s -> (s, a)
run_cps_state (CPS m) = m (flip (,))

*Main> run_cps_state state_example_intro 0
(1,())

type CPSExcept err a = forall r. CPS r (Either err) a

cps_throw :: err -> CPSExcept err a
cps_throw m = CPS (\ _ -> Left m)

run_cps_except :: CPSExcept err a -> Either err a
run_cps_except (CPS m) = m Right

-- this is a little friendlier and idiomatic.
catch :: Monad m => CPSExcept err a -> (err -> m a) -> m a
catch fn hndl = case run_cps_except fn of
  Left err -> hndl err
  Right val -> return val

*Main> absurd_exception_demo
error: cannot divide by 0
1.5

5 Recap; I already used the “to be continued” joke

The purpose of this post is not to be a comprehensive treatment of continuations or effects, as that would be impossible, but rather to get the gist of some powerful ideas across succinctly to inspire you, dear reader.

We covered what effects are, why we might want to account for them, and then constructed them in terms of continuations. In the next article we will build on these ideas to build an effect system.

By writing this article in literate Haskell I can ensure that the examples compile and behave appropriately and that nothing crucial is missing, so I hope you have fun experimenting with it.

main = do
  seventeen
  absurd_exception_demo >>= putStrLn . show
  putStrLn . show $ run_cps_state state_example_intro 0