Monads are often considered to be a stumbling block for learning Haskell. Somehow they are thought of as scary and hard to understand. They are however nothing more than a design pattern, and a rather simple one at that. Monads give us a standardized way to glue a particular kind of computations together, passing the result of each computation to the next. As such they are useful well beyond functional programming.
JavaScript
My favourite example is the well-known “callback hell” in JavaScript. JavaScript functions often take a callback as argument, a function that they invoke on completion. Functions that take a callback argument are called asynchronous functions. The problem arises when we want to call another asynchronous function inside the callback; we end up with deeply nested callbacks.
Let’s consider an example. Suppose we want to collect configuration files for our application in the current directory, in the user’s home directory, and in the system-wide configuration directory. We might do something like
function getConfigFiles(callback) {
function extractConfigFiles(filess) { ... }
fs.readdir(".", function(hereErr, here) {
fs.readdir(process.env.HOME, function(homeErr, home) {
fs.readdir("/etc", function(etcErr, etc) {
callback(extractConfigFiles([here, home, etc]));
})
})
});
}Since readdir is an asynchronous function, and we need to call it three times, we end up with this deeply nested structure. You can see how this might get out of hand. By contrast, in Haskell we would recognize that these kinds of asynchronous functions form a monad (the continuation monad, to be precise); after all, this fits the pattern: we want to glue asynchronous functions together, passing the result of each function to the next. In Haskell we would write the above code as
getConfigFiles = do
here <- readdir "."
home <- readdir homedir
etc <- readdir "/etc"
return $ extractConfigFiles [here, home, etc]
where
extractConfigFiles = ...This looks and feels like simple sequential code, but it isn’t; this code is precisely equivalent to the JavaScript example above it. Note that there are tons of attempts to address callback hell in JavaScript; many of which are in fact inspired by monads.
Ziria
Let’s now move from the mainstream and high level to the more esoteric and low level. Ziria is a domain specific language designed at Microsoft Research specifically for the development of Software-defined radios. Well-Typed have been working with Microsoft Research over the last few months to improve the Ziria compiler (itself written in Haskell), primarily the front end (internal code representation, parser, scope resolution and type checking) and the optimizer.
Ziria is a two-level language. The expression language is a fairly standard imperative language. For example, we can write a function that computes factorial as
fun fac(n : int) {
var result : int := 1;
while(n > 0) {
result := result * n;
n := n - 1;
}
return result
}The expression language contains all the usual suspects (mutable variables, arrays, structs, control flow constructs, etc.) as well as good support for bit manipulation and complex numbers.
The more interesting part of the language however is the computation language. Ziria programs define stream computations: programs that transform an incoming stream of bits into an outgoing stream of bits. In particular, Ziria is designed so that we can write such stream computations in a high level way and yet end up with highly performant code; Ziria’s flagship example is an implementation of the WiFi 802.11a/g protocol that is able to operate in realtime.
The simplest way to turn our simple factorial computation into a stream transformer is to map our fac function:
let comp streamFac = map facBut there are also other ways to build up stream computations. There are two fundamental primitive stream computations: take reads an element from the input stream, and emit writes an element to the output stream. Of course now we need a way to glue stream computations together; you guessed it, they form a monad. For example, here is a stream processor which creates an output stream such that each element of the output stream is the sum of all preceding elements of the input stream, starting with some initial value init:
fun comp sum(init : int) {
var total : int := init;
repeat {
x <- take;
do { total := total + x }
emit total;
}
}As a second example, consider this function which copies the first n elements from the input stream to the output stream and then terminates, returning the last element it wrote to the output stream:
fun comp prefix(n : int) {
var last : int;
times n {
x <- take;
do { last := x }
emit x;
}
return last
}This kind of monadic composition where the result of one stream computation is passed to another is known as “control path composition” in the Ziria literature. We also have “data path composition”, where the output stream of one processor becomes the input stream of another. For example, consider
let comp compositionExample = {
var total : int := 0;
repeat {
newTotal <- sum(total) >>> prefix(5);
do { total := newTotal - 1 }
}
}We use data path composition (>>>) to make the output stream of the sum stream transformer the input stream of the prefix stream computer. We then use control path composition to update a local variable with the last value that was written minus one, and we repeat. The effect is that we sum the input stream, but decrement the running total by one every 5 elements. So, given an input stream
1,2,3,4,5,6,7,8,9,10we output
1,3,6,10,15,20,27,35,44,54Ziria also offers a variant operator (|>>>|) which makes sure that the computations performed by the two stream processors happen in parallel.
A Haskell perspective. Stream computers can be compared to Haskell pipes, where a stream computer is something of typePipe a b IO, with an input stream of typeaand an output stream of typeb;dois the equivalent ofliftIO. Control path composition corresponds to monadic or “horizontal” composition, while data path composition corresponds to vertical composition.
Optimization
Monads come with laws: properties that most hold true for all monadic code. The Ziria compiler takes advantage of these laws in the optimizer. For example, suppose you write
x <- take
y <- return (x + 1)
emit yAt this point the so-called “left identity” law kicks in, and the compiler rewrites this to
x <- take
let y = x + 1
emit ywhich will then subsequently be cleaned up by the inliner. Other optimizations applied by the Ziria compiler include loop unrolling, partial evaluation, etc. It also uses a simple SMT solver to remove unnecessary conditionals, following the approach we described in a previous blogpost.
One optimization deserves special mention, although it’s not related to monads per se. The vectorization optimization turns a stream computer that takes single elements from the input stream and outputs single elements to the output stream into a stream computer which takes arrays of elements from the input stream and outputs arrays of elements to the output stream, so that the resulting code can be further optimized to operate on multiple elements simultaneously and to reduce the overhead involved from reading and writing to stream buffers.
For example, consider the following Ziria program:
fun sumArray(xs : arr int) {
var total : int := 0;
for i in [0, length(xs)] {
total := total + xs[i];
}
return total;
}
let comp sum4 = {
repeat {
xs <- takes 4;
emit sumArray(xs);
}
}
let comp stutter = {
repeat {
x <- take;
emit x;
emit x;
}
}
let comp stutterSum = sum4 >>> stutterComputation sum4 takes 4 elements from the input stream, sums them up, and emits the result; we say that the cardinality of sum4 is 4:1. Computation stutter writes every element in the input stream twice to the output stream; we say that its cardinality is 1:2; the cardinality of the composition stutterSum is therefore 2:1. The optimizer turns this program into this (cleaned up for readability only):
fun sum4_vect(xs : arr[288] int) {
var ys : arr[72] int
for i in [0, 72] {
let xs : arr[4] int = xs[i*4:+4]
var total : int
total := xs[0];
total := total+xs[1];
total := total+xs[2];
total := total+xs[3];
ys[i] := total
};
return ys
}
fun stutter_vect(xs : arr[72] int) {
var ys : arr[144] int
for i in [0, 72] {
ys[i*2] := xs[i];
ys[i*2+1] := xs[i]
};
return ys
}
let comp stutterSum = map sum4_vect >>> map stutter_vectThe optimizer has done an excellent job here. Both sum4 and stutter have become expressions, rather than computations, that are passed as arguments to map, which can be optimized better in the code generator; sum4 now takes an array of 288 elements and returns arrays of 72 elements (4:1), while stutter_vect takes arrays of 72 elements and returns arrays of 144 elements (2:1) and the inner loop in stutter has been unrolled.
This ability of the Ziria compiler to optimize the code for different kinds of pipeline widths is one of the reasons that it is possible to write software-defined radios in Ziria in a high level manner; with other approaches such as Sora this kind of optimization had to be done by hand. The Ziria compiler also does a number of other optimizations; for a more detailed discussion, see Ziria: A DSL for wireless systems programming.
Conclusion
Monads aren’t an obscure concept that has been invented just to work around peculiarities of Haskell. They are a very general and universal design principle with applications everywhere. The concept of monads has been found useful in JavaScript, C++, Java, Scala, C#, Ruby, Rust, Go, and many other languages. Recognizing the monad pattern when it arises in your code can lead to nicer, more readable and easier to maintain designs, and recognizing the monad pattern in language design helps programmers do this. In Ziria monads turn out to be precisely the right abstraction that makes it possible to have a language in which we can write software-defined radios at a very high level of abstraction and which can yet be compiled down to highly efficient code.