“The Essence of Functional Programming” Part 1: The Identity Monad

This is the first of a new series of posts that will take papers that I read and will explain them and attempt to make them more concrete (and less theoretical) by showing real world examples using more industry-standard languages. These papers will be tagged with theory-in-practice. For more information on the “Theory in Practice” series, read the introductory post.

Today’s paper is “The essence of functional programming” by Philip Wadler. This paper is widely known as the paper which popularized monads, and introduces them in a relatively elementary context with a focus on practical programming use.

This is part 1 of a multi-part series. In order to allow the information to soak in and to not consume too much of your time, I’ve decided to split this into multiple parts which I will publish over the coming weeks. These will all be tagged with essence-of-functional-programming.

Part 1 will cover the inspiration for monads as well as introduce the trivial monad.

Prior knowledge required: Basic programming experience with basic experience in functional programming (in any language, whether it be Ruby, Python, C, etc.). The examples will be given in Haskell and Scala.

Inspiration: Purity vs. Impurity

The inspiration for monads comes from the desire to program in a purely functional environment, but to ease program modification in cases where it appears impure languages have the upper hand.

What is “purity?” What is “impurity?”

While a conceptual “pure vs. impure” discussion is out of the scope of this post and the definition of purity was not covered in the paper, I’ll quickly define the terms. A function is pure if it generates it’s result using nothing but the parameters given to it, whereas a function is impure if it uses or modifies some outside state. A quick example of a pure function:

def add(x: Int, y: Int) = x + y

And that same function becoming impure, since we’re modifying global state by outputting text to the world:

def add(x: Int, y: Int) = {
  println("Adding!")
  x + y
}

Additionally, the benefits of purity are:

• Increased modularity - A pure function can be used anywhere and it will be have the same way. Therefore pure functions are ideal for libraries among programs.
• Concurrency safe - Since a pure function modifies no outside state, it can be easily (theoretically) parallelized.
• Simplified testing - Once you test all input conditions and edge cases, you can be certain the function behaves correctly.

Of course, there are also benefits to impurity:

• State - Its very easy to maintain state in impure situations, since you just add a global variable to the mix, and every function can use it.
• Quick edits - You can just throw in a println wherever you see fit to assist in debugging.

A pure pain point

As an example for comparing purity vs impurity, let’s use a basic interpreter which takes as input a program, evaluates it, and returns the result. This is surely a simple venture in both pure and impure settings.

Now, what if we wanted to add error handling to this interpreter? With impurity, we could simply throw exceptions with the error message. But in a pure environment, we would have to modify the result type to also include errors at each recursive point, and each function would have to check for errors prior to running. Holy smokes batman, that’s annoying.

Okay, what about adding an execution count? With impurity, all that needs to be done is to add a global variable that is incremented with each operation. Again, though, for a pure language, we would have to modify the result type to include execution count everywhere.

Based on these examples, it looks like impurity wins completely! But, there is another option: Monads. Wadler argues that monads can be used to structure an interpreter so that the above changes can be made just as easily as with an impure language, while maintaining the purity of the computations.

The Monad

A monad consists of three parts. In Haskell, it is defined like so:

class Monad m where
  unitM :: a -> m a
  bindM :: m a -> (a -> m b) -> m b

The rough equivalent in Scala would be the following:

trait Monad[M[_]] {
  def unitM[A](a: A): M[A]
  def bindM[A, B](a: M[A], f: A => M[B]): M[B]
}

As you can see:

• M is a type constructor. That is, its not a complete type on its own, because it requires another type to complete it. An example, List in Scala is not a type, but List[Int] is. Therefore, List is a kind of type constructor.
• unitM is a function which takes a value and “lifts” it into the monad. So if you had a just an int, such as 7, and your monad was a list of ints, then unitM would make it a list [7]. In fact, although we won’t talk about it in this post, List is a monad!
• bindM is a function which allows computations to be done on the value held by the monad. Building on the list example, if you wanted to double each item in the list, you could do bindM([7], (x: Int => x + x)) and this would return [14]. Notice the computation was done on the items inside, but the result was still contained in the monad type, which was List for our short examples here.

So, unitM can be thought of as bringing a value into a monad and bindM can be thought of taking that value, doing some computation, and putting it back into a monad. The question remains: how do I get a value out of a monad? This operation is typically specific to each monad, so it is not generalized. You’ll see examples later.

Okay, I realize this was really abstract. The main takeaway from this section is that a Monad is nothing more than the three parts above. Don’t worry about understanding the “why?” of monads yet, concrete examples are on the way!

A basic interpreter

Our concrete example is going to be a basic interpreter. The interpreter was originally written in Haskell in Wadler’s paper. I’ve converted this to Scala. Both sources are available in this gist. Please read the interpreter over until you understand what it should do. You don’t need to understand the monadic parts, of course, but you should be able to get the gist of what it does. As an example, take the following input into the interpreter:

term = App(Lam("x", Add(Var("x"), Var("x"))), 
           Add(Con(10), Con(11)))

The above is roughly equivalent to the following Scala code:

term = ((x: Int) => x + x)(10 + 11)

With that input, running the interpreter should yield 42, since it adds 10 and 11, to make 21, and that is passed as the parameter into the lambda function, which doubles it to 42.

We will take the above interpreter, extend it in various ways using monads, and compare this approach to what would be necessary in an impure language.

Variation zero: Standard Interpreter with the Identity Monad

To begin, let’s create the trivial monad. This monad doesn’t actually do anything, it just wraps the value, but its a gentle introduction to monads and their operations:

case class Id[+A](val value: A)

object IdOps extends Monad[Id] {
  def unitM[A](a: A) = Id(a)
  def bindM[A,B](a: Id[A], f: A => Id[B]) = f(a.value)
  def showM[A](a: Id[A]) = a.value.toString
}

This monad is called the “identity monad.” It is called this because it doesn’t serve any real purpose except to wrap a value. While it may not be necessary, I will explain each operation for the purpose of being explicit about each monad operation:

• The type constructor M in this case is Id. As you can see, this matches the above definition of a monad by taking a single value of some type.
• unitM takes a value and wraps it in Id. This brings the value into the monad, just as was described earlier.
• bindM allows computations to be done on the value of the monad. In this case, the function is applied directly to the value. Since this is the identity monad, there is nothing sneaky going on here, just simple function application. If we had an Id(7) and did bindM(Id(7), (x: Int => unitM(x * 2))) then the result would be Id(14). Note the symmetry between this and the example given earlier when defining monads.

For the purpose of our interpreter, we’ve also introduced a showM function. This is not a standard monad function in general, but we’re requiring all monads implement this so that we have a way to get the value out of the monad as a string.

Despite its practical uselessness, the identity monad serves a practical purpose for this post since it demonstrates the simplest monad. The result of using this monad with our example is that it constructs a basic, working, interpreter.

Testing the Monad

In order to test the monads we’ll be using during this series, I’ve constructed the interpreter example in such a way that you simply have to subclass the Interpreter trait and point it to our latest monad to see the changes. Add the identity monad and create the interpreter:

class StandardInterp extends Interpreter {
  type M[A] = Id[A]
  override val monadOps = IdOps
}

Then create a basic test program and run it:

val current = new StandardInterp()
import current._

val term: Term = App(Lam("x", Add(Var("x"), Var("x"))),
                     Add(Con(10), Con(11)))

println(current.test(term))

The result should be “42.”

This is what we expected, since our monad does nothing in this case except introduces us to the basic operations and usage of it. It should be clear to see that in the future we’ll add considerably more logic to the monad, and the interpreter will quite simply be augmented with additional functionality without at all compromising the purity of it’s functions.

Look for part 2 in the coming days!