On Monads, Part I

Introduction

This is the first instalment in two (or maybe three) posts I shall write to explain how Monads work in stateless function-oriented programming languages. This is less intended as a resource for a third party than as a way to reinforce my own learning. All of the material is taken from the first eight chapters of a freakishly-amazing book: Design Concepts in Programming Languages, which every programmer should buy and worship. If you have time, skip this and go read that book instead.

The Problem With Stateless Programming

In stateless programming languages there are two things that are rather difficult to do: propagate errors (this one applies to programming in general) and maintain some sort of state as our program executes. The second thing is quite difficult in stateless programming languages due the to the lack of mutable variables (hence the name stateless) – in a regular imperative programming language this is trivial, we just use a mutable state variable to represent state, whose value we change from time to time.

If we think carefully, we will see the above two problems cam be solved by figuring out a way to do the following:

  • Introduce some idea of sequentiality in an otherwise timeless language.
  • Propagate a block of information transparently through a set of statements being executed sequentially.

Both these problems can be solved by monadic style of programming in stateless languages.

Sum Domains

The concept of a sum domain a critical to this discussion. A sum domain of two smaller domains (consider a domain to be a type, or a set of objects; so Integer can conceivably be the domain consisting of all integers) A and B is denoted by A + B. A + B consists of all the elements in A and B. It is not like an union of two sets in one important way – every element in A + B keeps track of where it came from. Specifically, we wrap every value in A + B in an invocation of an injection function, which includes the information about what the source domain is. The injection functions for the above case of A and B will look like A->(A + B) and B->(A + B), for elements from A and B respectively. Thus, an element a in A will be mapped to the element A->(A + B) a in A + B. In C, this can probably be related to a (C / C++ / Java) union of two elements in a struct which also has a tag mentioning the field in the union that has a valid value.

A unit domain is a domain consisting of finite discrete values. So the domain Color = { Red, Blue, Green } is a unit domain. This roughly corresponds to an enum in C.

Propagating Errors

The above two concepts provide a rather elegant way to represent errors in stateless programming languages. Let’s say we are writing a procedure perfect-division which takes two integers and returns their quotient if the second one divides the first one perfectly, and signals an error otherwise. To model errors, we first talk of two domains we will work with: the Integer domain, representing inputs to the function, and the Error unit domain, which consists of the values { IllegalDivision, DivisionByZero }. We create a new domain Answer = (Integer + Error), and write perfect-division such that it returns one value from the Answer as its result. In other words, we set the return type of perfect-division to be Answer. Once this is done, we rig perfect-division to return Integer->Answer(X) where X is the result of a division performed without errors, and to return Error->Answer(IllegalDivision) or Error->Answer(DivisionByZero) in case there is an error.

With the above things in mind, a perfect-division procedure will look like (in a hypothetical pseudo LISPish syntax):

  (define perfect-division (integer-a integer-b)
    (cond ((= 0 integer-b) (Error->Answer DivisionByZero))
          ((= 0 (% integer-a integer-b))
           (Integer->Answer (/ integer-a integer-b)))
          (t (Error->Answer IllegalDivision))))

However, we’d also like to be able to chain calls to perfect-division, like (perfect-division (perfect-division 30 5) (perfect-division 4 2)). For this to happen, we need perfect-division take inputs as elements of the domain Answer and not Integer. This also means that we will have to, in the general case, deal with, say, an Error->Answer IllegalDivision in perfect-division. To do this, we need a match operator – one which matches and unpacks elements from a sum domain to an element from one of the constituent domains. I’ve taken it to have similar semantics to LISP’s cond. With the match operator, we can write perfect-division-safe as:

  (define perfect-division-safe (integer-a integer-b)
    (match ((integer-a (Error->Answer x))
            (Error->Answer x))
          ((integer-b (Error->Answer x))
            (Error->Answer x))
          ((integer-a (Integer->Answer a))
            (match ((integer-b (Integer->Answer b))
                     (perfect-division a b)))
 ;; Default cases omitted

A better way to encapsulate this is to have a with-integer idiom, which takes of matching the errors for us:

  (define with-integer (value function)
    (match ((integer-a (Error->Answer x))
            (Error->Answer x))
           ((integer-a (Integer->Answer x))
            (function x)))

In English, this function takes a value and a function. If value is really an Error, it directly returns the Error, otherwise it applies the supplied function over the integer value of value. Now, we can write perfect-division-safe using with-integer:

  (define prefect-division-safe (integer-a integer-b)
    (with-integer (integer-a
      (lambda (a)
        (with-integer (integer-b
          (lambda (b)
            (+ a b))))))))

Not only is this approach much cleaner, we can actually have some (simple) syntactic sugar which allows us to make this even more streamlined.

Do realize that the choice of the Error and Integer domains are completely arbitrary, and we can, in general, use this method to conceal any hidden information through a computation (which, in this case, is whether the last computation resulted in an Error). Also note that the type of with-integer is Answer->(Integer->Answer)->Answer. While this is not directly relevant now, figuring out the types of functions often helps to clear things up.

In the next post, we will talk about how we can thread (i.e. impost a loose ordering on the execution) state through a computation.

Advertisements
This entry was posted in Computers and tagged , , , . 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