Monads, Part 2: A Data Structure for Computation

Posted on July 9, 2012.

Refresher

In the last post, we learned about monads and how to use them to implement exception handling, vector operations, and debug output. To refresh your memory, a monad is defined by:

  1. A type constructor that defines a monadic type (usually parameterized by some other type).
  2. A unit function that takes a value and returns a value in the corresponding monadic type.
  3. A bind operation that takes a monadic value and a function from the non-monadic type to the monadic type. It returns a value in the monadic type.

Today we’ll talk about how one can use monads to describe impure computations in a pure language.

A Simple Example

Let’s define a monad which represents a computation. A computation can be written as a string, such as “Add 2 and 3, multiply their sum by 4, and return the result.” As always, we’ll use Fython, a purely functional subset of Python. So our monadic type is str, and our two monadic operations are:

def unit(x):
  return 'return ' + str(x)

def bind(x, f):
  return 'return execute(' + f.__name__ + '(execute(' + x + ')))'

We’ll see in a moment how these functions work. Note that, for simplicity, our monadic type is not parameterized on some other type (unlike with normal monads).

A monad is only useful if we have some monadic functions that we can compose with bind. Let’s define the following:

input = 'ask the user for a line of text and return it'

def output(text):
  return 'print (' + text + ') to the screen and return None'

input is a string that could theoretically be executed by some kind of interpreter that understands English. Similarly, output returns a string that could also be executed. For example, here is a functional version of the Hello, World program:

main = output('Hello, World!')

Notice that main is not a function. It doesn’t have to be, since it doesn’t take the universe as an argument as it did in previous posts. It’s simply the string:

(print (Hello, World!) to the screen and return None)

...which can be interpreted as a computer program. So here’s the magic: using monads, we can construct computations that express side effects, and let the runtime execute these “impure” programs. So to “run” a program means to execute the computation stored in main. When executing the computation, we do so eagerly (this is necessary to ensure that every computation is executed, whether we use their return values or not), even if our language is lazy.

Let’s try a more complex example. Suppose we want to ask the user to input some text and then print it back to her. It would look like this:

main = bind(input, output)

If we inspect main, we see that it holds the following string:

return execute(output(execute(ask the user for a line of text and return it)))

Sweet! To execute this expression eagerly, one would go from the inside out. First, evaluating the inner computation requires that the user enters a line of text. Then, that string is passed to output, which itself returns a computation. Finally we perform the computation returned by output (which involves printing to the screen), and whatever that computation returns is the return value of our program. But we don’t care about the final return value—we execute this program solely for the side effects (this is why the computation must be executed eagerly, even if the underlying programming language is lazy).

A More Practical Implementation

Representing computations as strings isn’t very practical. Only a human knows how to interpret something like (print (Hello, World!) to the screen and return None), and computations are for computers after all. Let’s define a better representation (this will serve as the type constructor for our monad):

class ComputationType:
  UNIT   = 0
  BIND   = 1
  INPUT  = 2
  OUTPUT = 3

class Computation:
  def __init__(self, type, values):
    self.type = type
    self.values = values
  def __repr__(self):
    if self.type == ComputationType.UNIT:
      type_str = 'ComputationType.UNIT'
    elif self.type == ComputationType.BIND:
      type_str = 'ComputationType.BIND'
    elif self.type == ComputationType.INPUT:
      type_str = 'ComputationType.INPUT'
    elif self.type == ComputationType.OUTPUT:
      type_str = 'ComputationType.OUTPUT'
    return 'Computation(' + type_str + ', ' + self.values.__repr__() + ')'

Note that we’ve defined __repr__ so that we can print a computation and examine its structure. Now, let’s define unit and bind for this monad:

def unit(x):
  return Computation(ComputationType.UNIT, [x])

def bind(x, f):
  return Computation(ComputationType.BIND, [x, f])

Okay, that’s the whole monad! Now let’s rewrite input and output:

input = Computation(ComputationType.INPUT, [])

def output(text):
  return Computation(ComputationType.OUTPUT, [text])

We now have a way of describing computations! It’s almost like we have a programming language within a programming language. In order for this monad to be useful, though, we need a way of executing a computation. As you know by now, this is not possible in Fython (our functional subset of Python). Let’s break the rules and write just one function in imperative Python, and we’ll consider this to be part of the runtime:

def execute(computation):
  if computation.type == ComputationType.UNIT:
    return computation.values[0]
  elif computation.type == ComputationType.BIND:
    return execute(computation.values[1](execute(computation.values[0])))
  elif computation.type == ComputationType.INPUT:
    return raw_input()
  elif computation.type == ComputationType.OUTPUT:
    print computation.values[0]
    return None

Sweet, let’s try it out! We’ll start with Hello, World, which is exactly as it was in the previous example.

main = output('Hello, World!')

What is main? Let’s find out:

>>> main
Computation(ComputationType.OUTPUT, ['Hello, World!'])

It’s a computation of type ComputationType.OUTPUT, just as we would expect. Now let’s run this computation:

>>> execute(main)
Hello, World!

Sweet victory! You can now truly see how monads can be used to do I/O in a pure functional language. Let me emphasize that the execute procedure isn’t written in our pure language (Fython), and it’s not referentially transparent. Rather, it is implemented as part of the runtime—we don’t get to use it in Fython. The interpreter uses it to execute our program (when we call execute(main), we are basically playing the role of the runtime). When we write programs in Fython, it is essentially non-existent to us.

More Advanced Examples

Now that we understand the idea, let’s try to write some more useful programs than Hello, World. First, we can try out the program from the previous example which reads a line of text and prints it back:

main = bind(input, output)

This time, we get:

>>> main
Computation(ComputationType.BIND, [Computation(ComputationType.INPUT, []), <function output at 0x00000000027E1198>])

And running the program:

>>> execute(main)
This will get printed back!
This will get printed back!

Note that I entered the first This will get printed back!, and the second one was printed by the program as we would expect.

Now let’s write a program that responds to user input:

def respond(input):
  return output('You said YES!') if input == 'yes' else output('You said NO!')

main = bind(input, respond)

Let’s test it out:

>>> execute(main)
yes
You said YES!

>>> execute(main)
no
You said NO!

It works! Conditional logic appears to be more straightforward with monads than with uniqueness types. Let’s modify the example so that it keeps asking the user for input until she says yes:

def main_wrapper(dummy):
  return main

def respond(input):
  return output('You said YES!') if input == 'yes' else bind(output('Try saying \'yes\' once in a while.'), main_wrapper)

main = bind(input, respond)

Does it work?

>>> execute(main)
no
Try saying 'yes' once in a while.
no
Try saying 'yes' once in a while.
no
Try saying 'yes' once in a while.
yes
You said YES!

Sweet! Unbounded recursion doesn’t seem to be a problem either. Notice how we defined main_wrapper simply because bind expects a function of one argument. It turns out that this is a common monadic pattern, so let’s abstract it:

def chuck(u, v):
  return bind(u, lambda x: v)

I chose the word chuck for lack of a better name—it is not traditional monad parlance. chuck performs the computation u, ignores its return value, and then performs v and returns the result. Earlier I mentioned that execute must be eager when evaluating its argument—this is why: if execute was lazy, the first computation (u) might never get executed because the lambda expression doesn’t use it. Let’s rewrite our example using chuck:

def respond(input):
  return output('You said YES!') if input == 'yes' else chuck(output('Try saying \'yes\' once in a while.'), main)

main = bind(input, respond)

Does it still work?

>>> execute(main)
no
Try saying 'yes' once in a while.
no
Try saying 'yes' once in a while.
no
Try saying 'yes' once in a while.
yes
You said YES!

Excellent. To conclude, let’s write a program that asks the user for two lines of input, concatenates them, and prints the result:

def respond2(input1):
  return lambda input2: output('You said "' + input1 + '" and "' + input2 + '".')

def respond1(input1):
  return bind(input, respond2(input1))

main = bind(input, respond1)

And finally:

>>> execute(main)
hello
world
You said "hello" and "world".

It works! Hopefully by now you have an idea of how to compose impure computations with monads. Let me know in the comments if anything wasn’t clear!

Tags:  home theory

comments powered by Disqus