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][otherarticle]
influence me and anyway it's a fun read.
This is an executable essay
---
This post is written in literate Haskell, which means that (the source for)
this essay is a valid Haskell program you can run yourself:
- If you don't have Haskell installed, [easily do so with ghcup][ghcup]
- Download the [source for this essay][essaysrc] as `effects.lhs`
- Compile the program with `ghc -o effects effects.lhs`!
- Or open an interactive session with `ghci` and load `effects.lhs` into it.
It also means enduring this annoying boilerplate.
We enable a few GHC-specific language extensions and import a few packages from
the standard `base` library.
> {-# LANGUAGE PolyKinds, RankNTypes #-}
> {- cabal:
> build-depends: base
> -}
> module Main where
> import Data.Kind (Type)
> import Control.Monad (forM)
Okay now for the good stuff.
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`?
The cause: Effects
---
Effect
: An observable behavior or outcome of a program execution besides returning a
result value.
If that sounds extremely broad that's because it is.
The most obvious effect for Haskell programmers is `IO` ("input/output"), the
ability to send and receive data to and from "the outside world" - every single
Haskell program begins with a function `main :: IO ()`, because without effects
you cannot even interact with the program.
Both the `CPSState` and `CPSExcept` types represent computations with *side
effects* (or just *effects*), and not too far below the surface you'll find
that they have quite a lot in common.
Don't "monads" have something to do with this?
---
[Yes][moggi], and I encourage programmers to read Moggi's work on representing
side effects as monads, but we actually won't be doing another monad tutorial
today.
Effect systems basically have one monad whose internal workings you can ignore
if you are simply designing effect-laden software.
And now we will visit that particular monad type, `CPS`.
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 ...
The `CPS` monad
---
... but this is Haskell!
> newtype CPS (result :: k) (m :: k -> Type) (answer :: Type) = CPS
> { (#) :: (answer -> m result) -> m result }
This reads as: a term of type `CPS result m answer` is
- a function in possession of some `answer` value expecting a
- continuation which takes `answer` values to `m result` values, which then
- returns that very same `m result` by applying the continuation to the
`answer`.
Why do we care about CPS?
---
It so-happens that `CPS` is a `Monad` (and hence an `Applicative` and a
`Functor`) [^1] :
> 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))
Note that the continuation evaluates to the type `m result` - it must be some
kind of type constructor wrapped around the actual result value.
Part of the reason for this is that the mediating type `m` affects properties
and capabilities of `CPS`.
For example, when `m ~ IO`,
> 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))
The function `sixteen` uses the *delimited continuation* operators `shift` and
`reset` in order to manipulate the flow of control; they will play an important
role in the next article so I snuck them in here.
`lift` takes advantage of the way we split the `CPS` result type into `m` and
`result` in order to augment the type `m` (which or may not be a `Monad`) with
the ability to manipulate control flow.
Here, I chose `IO` so that the example would be compelling.
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.
State
---
Type definition
> type CPSState s a = forall r. CPS r ((->) s) a
The type `((->) s)` is the type of "functions with an argument `s`."
In the Haskell community this type is often referred to as `Reader s` or `Env
s` (for all types `s`, of course).
`Reader` is a monad providing read-access to a dynamic value, so `CPS r ((->)
s)` is `CPS` but with the "extra effect" of being able to access a hidden `s`.
The consequence of this choice, ultimately, is that continuations now have a
second argument, the state value in question.
Operators
> cps_load :: CPSState s s
> cps_load = CPS (\k s -> k s s)
The first operation we define is *loading* a local state value.
Note that our `CPS` continuation has a second parameter now.
We fulfill this loading operation by passing the state value to the
continuation itself as its first argument.
> cps_save :: s -> CPSState s ()
> cps_save s = CPS (\k _ -> k () s)
To *save* is the reverse of loading a value.
The operation does not return any meaningful value; internally, it ignores the
state value it will be overwriting, and will instead pass along a new value of
its own.
Running stateful functions
The final ingredient is the function to kick-start effect handling and also
define what happens when you "return" in a stateful function.
> run_cps_state :: CPSState s a -> s -> (s, a)
> run_cps_state (CPS m) = m (flip (,))
This pairs the state with the final `answer`. When we run this (excerpt from
GHCI):
```
*Main> run_cps_state state_example_intro 0
(1,())
```
Exceptions
---
Fundamentally the idea behind exceptions is that we can return `Either` an
`answer` *or* some `err`or value, to be handled by a different code path.
Type definition
> type CPSExcept err a = forall r. CPS r (Either err) a
Operations
> cps_throw :: err -> CPSExcept err a
> cps_throw m = CPS (\ _ -> Left m)
Running exceptions
> 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
And now, in GHCI, we can begin using our DIY exception system:
```
*Main> absurd_exception_demo
error: cannot divide by 0
1.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
[ghcup]: https://www.haskell.org/ghcup/
[moggi]: http://www.cs.cmu.edu/afs/cs/user/crary/www/819-f09/Moggi91.pdf
[^1]: And as we all know, Haskell rewards monads with readable syntax, so these
typeclass instances do serve a purpose.
[essaysrc]: https://niltag.net/code/effects.lhs
[otherarticle]: https://blog.poisson.chat/posts/2019-10-26-reasonable-continuations.html