### Introduction

This is the first instalment in two (or maybe three) posts I shall write to explain how `Monad`

s 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.