On types, functional programming and monads.

There is a lot of confusion about types and monads, especially among people who’ve never used them to their full extent. In this post I wish to explore the motivations for having type systems and monads in a programming language, along with the trade-offs languages make on those matters. I will start with types, since that is the more familiar of the two concepts. I when talking about monads, I will draw a lot of parallels to types.

Haskell primer

To make sure that this tutorial is readable for everyone, I will quickly explain a bit of the syntax of Haskell. If you are already familiar with Haskell, skip past this section.

In Haskell, one doesn’t use parentheses when applying functions:

    print "Hello"

But one may use it to make the prefix notation work when applying nested functions:

    print (addOne 1)

I will sometimes be using whitespace to avoid parentheses:

    print
      addOne 1

One defines functions simply by writing the name, followed by the arguments, followed by an equals sign, followed by the result:

    addOne x = x + 1

One usually adds type annotations, but it is very, very rarely needed, as Haskell has global type inference:

    addTwo :: Int -> Int
    addTwo x = x + 2

Parameterized types have a similar syntax. For instance, a map from strings to ints is called

    Map String Int

In Haskell, we can use binary functions as infix functions:

    plus :: Int -> Int -> Int
    plus x y = x + y

    example x = x `plus` x

Haskell also has the let-in concept:

    let x = 2 in x*x

This is a nice way of having temporary variables. We can define lambdas using this syntax:

    \parameter -> body

Read the backslash as a lambda. I will be changing small parts of Haskell (mainly the libraries) to make it more beginner-friendly.

Types

Suppose we are designing a language. Let's suppose that we choose not to have a type system. In this case, we may end up confusing the types of variables in subtle ways. The damage of this can be reduced with rigorous unit testing and excellent variable naming, but one can still lose lots of time on bugs from this. Another problem is that it makes refactoring harder, since the validation that you did it right is weaker.

Another choice is to fix a set of types from the beginning. Few languages do this, as it isn't much better than not having a type system. In fact, not having a type system is equivalent to having exactly one type.

A nicer choice would be to let the programmer define data types from building blocks. Older languages (and Go) do not let the programmer parameterize types with types, so we will look at this example first. This lets the programmer create their own data types, but usually not general-purpose ones, such as lists. There are ways to acheive polymorphism without parameterized types (such as inheritance), but I will not write about that now.

The type systems of Haskell and many functional languages, along with some modern less-than-functional languages allow the programmer to define data types parameterized with other data types in a way that looks like this:

    data Option a = None | Just a

This translates quite directly to English:

The data type Option of a is either None or Just of a.

One can define a wide variety of data types this way, and using pattern matching, one can use them in safe ways:

    logIn userData = do
      maybeUser <- lookupUser userData
        case maybeUser of
          None -> -- display error
          Just user -> -- log user in

Effect systems

You thought I was going to talk about monads now? Well, I'm not. First, I will introduce the concept of an effect system. Just like there can be a lot of bugs when not expecting what stuff is, there can be a lot of bugs when not expecting what stuff does. Just like a type system restricts what stuff can be, an effect system restricts what stuff can do. Some effect systems can also restrict what stuff can't do, such as not committing/rollbacking database transactions.

Drawing parallels to types, the simplest effect system is not having an effect system. This does not help catching bugs, but it is quite popular. Not every mainstream language lacks an effect system. For instance, Java has a badly designed effect system called "checked exceptions".

Another way to make an effect system is by fixing a set of effects. Such a set could be IO (in the Haskell-jargon for anything sense), state, exceptions and nontermination. This limits the programmer a lot; we are not, for instance, able to ensure that database transactions are handled appropriately. Borrowing examples from a Koka (which implements this kind of effect system) tutorial:

    function sqrTotal(x: Int): total int {
      return x * x
    }
    function sqrIO(x: Int): io int {
      print("effect")
      return x * x
    }
    function sqrDiv(x: Int): div int {
      if (x < 5) {
        while {true} {}
      }
      return x*x
    }
    function sqrExn(x: Int): exn int {
      if (x < 5) {
        error("oops")
      }
      return x*x
    }

A third way is to let the programmer define an effect system in a way a bit like the data type example. An example syntax for this could be:

    effect StreamReader = read :: Option Char | hasMore :: Bool

One could then imagine "handlers" that convert one kind of effect (such as StreamReader) to some "greater" kind (such as IO), to be able to use the effect for things (such as reading files).

We can also imagine parameterized versions of effects defined in the same way as above:

    effect StreamReader el = read :: Option el | hasMore :: Bool
    effect State st = set :: st -> Unit | get :: st
    effect Exn ex = throw :: ex -> Void

To make the language simpler, one may want to unify the effect system and the type system. In that case, one can define combinators that make effects a lot nicer to work with. One way to combine effects and types is by making effects a kind of "type constructors", which take the parameters of the effect along with the result of the computation. That is, a piece of code that can read from a character stream and returns an int would be of type StreamReader Char Int.

    catchAndReturn :: Exn ex a -> a -> a
    catchAndReturn code default =
      case code of
        throw _ -> default
        return x -> x

We may ask ourselves the question: do we really need to have a separate syntax for defining effects, now that effects are just certain kinds of types? The answer is no, and it turns out that by not having a special syntax for effects, we get some much more powerful effects. In fact, they become so powerful that I would dare to say that functional languages (at least tomorrows functional languages) will be much better at imperative programming than imperative languages.

First, let us define a simple effect as if it were a type, just to have an example. We will choose state, because that is a simple effect. First, observe that state is basically the same as carefully threading a value to every function:

    while :: a -> (a -> Bool) -> (a -> a) -> a
    while state cond action  =
      if cond
        then
          while (action state) cond
            action
        else state

    test :: Int -> (Int, String)
    test state =
      while state (\st -> st > 10) -- while (state > 10)
        (\st -> st - 1)            --   state = state - 1

This is not very readable, but it tells us something about state: a stateful calculation with a state of type st returning something of type a is a normal calculation of the type st -> (st, a). We can try encoding that in types:

    data State st a = Stateful (st -> (st, a))
    runState :: State st a -> st -> (st, a) -- utility function
    runState state = -- this can be done in a better way,
      case state of -- but for simplicity, it is done this way
        Stateful f -> f

We can then try to write while using this:

    while :: (st -> Bool) -> State st Unit -> State st Unit
    while cond action = Stateful (\state ->
      if cond state
        then
          runState
            while cond
              action
            first (runState action state))
        else (state, Unit)

This doesn't seem much cleaner. That turns out to be a result of missing combinators. For instance, we have no combinator for combining stateful effects in a sequence. A good combinator for that is this:

    andThen :: State st a -> (a -> State st b) -> State st b
    andThen stA stB = State (\st0 ->
      let (st1, a) = runState st st0 in
        runState (f a))

It turns out that some combinators for interacting with the state are also nice. These combinators may be easier to understand after reading the next implementation of while.

    get :: State st st
    get = State (\st -> (st, st))

    result :: a -> State st a
    result a = State (\st -> (st, a))

The implementation of while is...

    while :: (st -> Bool) -> State st Unit -> State st Unit
    while cond action =
      get `andThen` (\x ->
      if cond x
        then action `andThen` (\Unit ->
             while cond
               action)
        else result Unit)

This implementation does not look nearly as bad as the original implementation. It can be improved, but I will get to that later. In a sense, result takes a value and makes some stateful code that has no effect, but has the result that the function result was given as a parameter.

You may be thinking "Congratulations! You've just implemented an ugly version of something I use every day!". I will admit that this thought is not completely unjustified, but hang in there. It turns out that andThen and result are combinators that make sense for every kind of effect. You may ask "What can these combinators even be used for?". Again, this is not completely unjustified. It turns out that with only these combinators, one can implement a slightly different version of while, but before we do that, I need to introduce you to typeclasses.

Typeclasses

One way to make code more reusable is to use typeclasses. A good example of a typeclass is monoid, which basically lets you concatenate things, regardless of what they are:

    double :: Monoid a => a -> a
    double x = x <> x

This function lets us double arbitrary things. For instance, the result of double "Haskell is awesome!" is "Haskell is awesome!Haskell is awesome!"

The type of double should be read "If a is a monoid, given an a, we can give you an a.". We can also define other utility functions for monoids, such as concatenating every element in a list, but that is not important right now. The important thing is that we can turn a type that isn't a monoid into a monoid, simply by writing an implementation of a few things. This way, we get all of the utility functions for monoids for free.

The way we do this is by creating a typeclass instance. For instance, suppose we want to make Int a monoid such that <> adds numbers. One would do it like this:

    instance Monoid Int where
      x <> y = x + y
      empty = 0

Many typeclasses have rules associated with them. For instance, one rule of monoids is that no matter what x is, x <> empty must be x.

After implementing monoid for ints, we can use our previously defined utility function:

    double 2

As one would expect, the result of evaluating the above code is 4.

Another thing we can do is declare typeclasses that can be implemented by others. For instance, suppose we decide that andThen and result are sufficient for effects. In that case, we can define a typeclass for effects like this:

    class Effect ef where
      andThen :: ef a -> (a -> ef b) -> ef b
      result :: a -> ef a

We should also decide on some laws. First, let's formalize our intuition that result does not have any effect, and instead is used to have the right type in combination with andThen. First, if we have some effectful code called effectful, and we take that code andThen give its result to result, we would expect it to be the same as the original code:

    effectful `andThen` (\res -> result res) = effectful

Next, if we have some effectful function called effectfulFunc, we would expect that if we take a value, give that value to result andThen execute effectfulFunc, it is the same as executing effectfulFunc with the original value:

    result x `andThen` effectfulFunc = effectfulFunc x

Another laws that we would expect is hard to formulate in English, but here the algebraic formulation is:

    (effectful `andThen` firstEffectfulFunc) `andThen` secondEffectfulFunc
     =
    effectful `andThen` (\x -> firstEffectfulFunc x `andThen` secondEffectfulFunc)

You may not understand the equation above yet, but hopefully you've learned why Haskellers often use single-character-names. To understand the example above, we may need to change it to a language more familiar to you. It basically says that these two pseudo-code snippets are the same:

    secondEffectfulFunc(firstEffectfulFunc(effectful()))

    x = effectful()
    secondEffectfulFunc(firstEffectfulFunc(x))

In other words, it lets you extract the result of a computation to a local variable.

Examples

We can implement multiple examples of the effect typeclass above. Obviously, we can use the functions I already defined for State to make State an Effect:

    instance Effect (State st) where
      andThen stA stB = State (\st0 ->
        let (st1, a) = runState st st0 in
          runState (f a))
      result a = State (\st -> (st, a))

Another effect we can imagine is dynamic scoping:

    data DynScope env a = DynScoped (env -> a)
    runDynScope :: DynScope env a -> env -> a
    runDynScope dynScope env =
      case dynScope of
        DynScoped f -> f env

    instance Effect (DynScope env) where
      andThen dynSA dynSB = DynScope (\env ->
        runDynScope
          dynSB
            runDynScope dynSA env
          env)
      result x = DynScope (\env -> x)

Another one is IO, but we cannot really implement that, since what makes IO special is that it is native code. We can make Prolog-style nondeterminism an effect by using lists, but that'll have to wait for another blog post.

Exceptions, software transactional memory, context-sensitive parsing and continuation passing are also examples of effects that fit the Effect typeclass.

Utility functions

There is not a big advantage to having defined all of this if we don't have any utility functions. Luckily, we can define lots of utility functions.

A common pattern is that we have a list of things to execute, and we want to execute them sequentially, and collect all the results in a list. This can be done like this:

    sequence :: Effect ef => [ef a] -> ef [a] -- [something] is a list of somethings
    sequence list =
      case list of
        first : rest ->
          first `andThen` (\x ->
            sequence rest `andThen` (\xs ->
              result (x : xs)))
        Empty ->
          result Empty

I also talked about a generalized while. This does not make sense for every kind of effect, only those in which the result of an action can change depending on preceding actions. That does not matter for the implementation, but there's no point in using it with effects like DynScope.

    while :: Effect ef => ef Bool -> ef Unit -> ef Unit
    while cond action =
      cond `andThen` (\bool ->
        if bool
          then action `andThen` (\Unit ->
                 while cond action)
          else result Unit)

Monads

So where do monads come into all this? Depending on your knowledge, you may already know this, but the Effect typeclass... is the exact same as the Monad typeclass. Now, there are arguably some monads that don't fit the effect intuition, but I think this intuition is what makes monads so important for programming.

In the future, I want people to at least separate effect systems, monads and Haskell when they write rants, but that is unlikely to happen.

It may seem impractical to write a type for each mishmash of effects you use, and luckily, there is a good solution for that, called monad transformers, but that will have to wait for another post.

Remember that the entire point originally was to catch bugs, but I would like to see you implement Prolog-style nondeterminism in a language that does not have monads or something equivalent in power (continuations), or something more powerful (macros).

You may still think that the above examples looks ugly, and I agree, so let me introduce... do notation. Basically, do notation replaces

    do x <- m
       stuff using x

with

    m `andThen` (\x ->
      do stuff using x)

and it replaces

    do expression

with

    expression

It may not seem like such a simple a transformation is able to make the code prettier, but I'll let you decide:

    sequence list =
      case list of
        first : rest ->
          do x <- first
             xs <- sequence rest
             result (x : xs)
        Empty ->
          result Empty

    while cond action =
      do bool <- cond
         if cond
           then do
             Unit <- action
             while cond action
           else result Unit
About these ads
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s