15 May, 2010

monads: overloading semicolon, && and ||

Monads are sometimes described as 'overloading semicolon', aimed at eg. the C or Java programmer. This is some text about that idea.

But references there don't seem to refer to && and || - two other control operators that are regularly used (especially in C) and that I think are interesting to compare to ;

&& and || are defined primarily as 'boolean or' and 'boolean and'. But its very common to write expressions like this:
succeeded = (p != NULL && *p==5)
Evaluation of this uses more than the 'boolean and' functionality of &&. It also uses the property that && only evaluates its second parameter if its first parameter returned true - if the first parameter returned false, then the second parameter is never evaluated. That's a little bit of laziness sneaking into an otherwise strict language. In the example above, it stops the evaluation of *p when p is a null pointer.

So contrast ; and &&.

If you're a C programmer, they're totally different things - ; sequences statements, and && is an operator. Try to forget that difference for now.

You can write:
f() ; g()
which executes f, discards its result and then executes g.

Or you can write:
f() && g()
which executes f, then if f does not fail, it executes g - if either f or g fail then the expression as a whole fails, otherwise the expression succeeds. What do I mean by fail? I mean that f and g must return booleans indicated whether they succeeded or failed at doing whatever it was they were supposed to do.

So there are different ways to sequence operations (; and &&, and the operations (f and g) need to have different interfaces depending on the particular way of sequencing: when using ; there are no particular constraints. When using && we must indicate success or failure in every operation.

Both of these look like the Haskell operator >>: In Haskell, you can write:
f >> g
meaning "first do f, and then do g". But the novelty is that >> has different meanings in different contexts - and those contexts are called monads.

For example, the IO monad behaves quite like ;
print "hello" >> print "World"
which looks like:
printf("hello\n") ; printf("world\n");

and the Maybe monad behaves a bit like (but also a bit different from) &&
main() {
 test() && printf("world\n");

int test() {
  return (2==3); // fail...
prints nothing.

In Haskell, the Maybe monad looks more like this:
Nothing >> Just 5
Just 1 >> Just 5
Just 5
Just 1 >> Nothing

In the Haskell example, Nothing means failure, and Just something means success (more on that in a bit).

In the first Maybe expression, Nothing >> Just 5, our first statement fails, so we don't run the second.

In the second example, Just 1 >> Just 5, the first statement succeeds (it returns Just something - so then we run the second statement which also succeeds (because it returns Just something) and so the statement as a whole succeeds.

And in the third example, the first statement succeeds, but second one fails, so the whole expression fails.

To add confusion, there are two distinct syntaxes in Haskell for writing monadic expressions. They do the same thing, and there is no real advantage to one over the other so far, but in a bit, the differences will be exposed. The above has introduced one form, using >>. The other form looks like this, using the do keyword
  putStrLn "hello"
  putStrLn "world"
  Just 1
  Just 5
Those are the same as earlier example, but in a different syntax. When you write something using do notation it is automatically translated into >> notation by the compiler. For now, that is just joining the lines together and putting in >>, which is not much difference. But there will be bigger differences later.

The Maybe example looks quite contrived - and it is - because so far I haven't explained the other important part of monads, which is value binding. That's where the analogy with ; and && breaks down and you start getting into more functional programming territory.

Note that all the above examples are missing some things that are used all the time (in C, Java and Haskell): return values, and variable assignment. (in one of the examples, I used p but only to read, not to write). This is an area where Haskell can be quite different from languages like C and Java.

Now, remember how I said that depending on what you're using to sequence your statements, those statements must match a particular interface. For example, if you're using &&, then those statements must return a boolean success. Using && hides away that return value - you write f() && g() without actually mentioning or testing the return value. Instead you let && deal with it; and in the Maybe monad, you let >> deal with it, and if using do notation you just put statements in sequence on separate lines, and magically they'll stop running when one of them fails!

What happens when I want variables and return values though?

In the ; style of writing C, you can write:
x = f(); g(x)
Now we expect f to return a value, and later on in a subsequent statement, we want to be able to access that value. In this C example, we do that by assigning the return value of f() into a variable x and then when we want to pass a parameter to g, we can write x again to get that value back. People do that every day. Nothing fancy - just normal programming like you learned when you were 8 years old.

So now how does that work in C using && to sequence statements? We can't write:
( x = f() ) && g(x)
because we're already using the return value of f() to indicate success or
failure - we can't return some arbitrary value too. (and remember we're using && here to sequence our statements - you're not allowed to suddenly say "ok lets put a ; and then an if statement). Uh oh.

Well, actually sometimes in C, we do manage to return a value and indicate success/failure at the same time. For example, fopen returns a pointer to a FILE or returns a null pointer to indicate failure. So fopen is reporting two things: did it succeed? (null or not-null), and if it did succeed then we can extract some more information - the pointer to the FILE struct.

The Maybe monad in Haskell does something similar. Remember a statement in the Maybe monad above returns Nothing if the operation failed, or Just something if the operation succeeded. I coughed politely and ignored the something at the time. But now see that the something what the operation returns on success.

This is more general than the fopen NULL pointer case. The fopen style only works when your data-type has a "magic value" to indicate failure - when using pointers, NULL, or perhaps countDinosaurs() could return -1 if it failed. But this isn't always possible (for example, if I am using some xor() function then any output is possible and there is nowhere for me to indicate failure)... and it is awkward for every procedure to use its own convention.

So now consider our Maybe monad example from before (slightly rewritten):
f = Just 1
g = Nothing
f >> g
In this, f succeeds and returns 1, and g fails and so does not return a value.

Well, what can we do with that return value? Just like in other languages, we can use it in later computations.

Now, there are two ways of writing this: the do style and the >> style. The do style is most like C and Java, and the >> style looks totally different.

I'll try to explain both. Try to understand both - the do style should be pretty easy to understand because it looks (aside from which symbols are used) quite like Java. But the >> style is more "functional" and might steer your thinking into writing functional code functionally, rather than "writing C in Haskell" as the do notation leads to (or at least I find it tempts me to).

Lets look at the IO monad. This lets us have functions which do IO (something which is forbidden in plain Haskell code (for better or worse)).

I want to have a program which will read a line from stdin, and output it on stdout. In C, that might be (assuming we have a nice readline function):

So in Haskell: As building blocks, we have print, which is a command you can run in the IO monad that will output the string that you pass to it (this was used right up near the top of this article); and we have getLine which is a command you can run in the IO monad that reads in a line from stdin and returns it.

So we want to run getLine, and then we want to run putStrLn, passing in the value that we got from getLine.

First lets write it in do notation:
  x <- getLine
  putStrLn x
This style runs getLine and binds its return value to x. That means whenever you refer to x later on in the do block, you mean whatever value was returned by getLine. This style is very similar to C or Java - it looks like we do some computation, assign its value to a variable, and then later on use that variable. Now here's the more functional way:
getLine >>= print
This uses an operator >>=. This behaves a bit like >> in that it puts two operations in sequence. But it also wires up the return value of the first statement to be the parameter of the second statement. Now remember that >> is different for each monad. It represents that monad's particular way of sequencing operations. >>= is likewise different for each monad. In the IO monad, it sequences operations and passes their values around just like above. But what about in the Maybe monad? Here's an example. First we have an operation in the maybe monad that takes an integer and succesfully returns that integer incremented. We use Just something to indicate success, and that something is x+1 to increment our integer.
increment x = Just (x+1)
Lets use this: In do notation:
  v <- Just 5
  increment v
which gives us:
Just 6
or the same in >>= notation:
Just 5 >>= increment
In the do notation, you can write as many lines as you like, and similarly in the >> notation you can write as many statements as you like:
Just 5 >>= increment >>= increment >>= increment
Just 8
But the point of the Maybe monad is to handle failures nicely. So what happens if we have a failure? What do these two fragments do:
Nothing >>= increment
or equivalently:
  x <- Nothing
  increment x
Now >>= will behave like >> which in the Maybe monad is quite like how && behaves in C. Ignore the value passing bit of >>= and concentrate just on the >> bit of it: in the Maybe monad, >> behaves like && - if the left-hand side fails, then we don't evaluate the right hand side. And thats what happens here - the left hand side fails (by returning Nothing) and so we never even to try evaluate increment. So now look at the do notation version. First we try to bind x to some computation, but that computation fails, so we don't evaluate the rest of the line. Now look at this Java code fragment:
x = v();
 y = increment(x);
That sets x to the some value caused by running a function v, and then runs increment on that value. First we run v and then we always run increment. Right? Yes, if v looks something like:
static int v() { return 5; }
But what about this:
static int v() { throw new RuntimeException(); }
Now we evaluate v but it fails, and so we don't evaluate increment. Instead, the program as a whole fails. So now the Maybe monad looks like && but also looks like exception handling - && and exception handling are almost the same thing! (which is quite surprising sounding, but they're often used for very similar purposes). What's the difference then? Well, an Exception propagates upwards and makes the whole of your program fail, unless you explicitly catch that exception, and you use ; to separate statements. Failures with && don't propagate out of the expression using the && - instead the expression returns a boolean false to whatever program code is surrounding it, and continues running. Essentially, you are forced to catch the failure, because you get told explicitly "I succeeded" or "I failed" (by the expression as a whole evaluating to true or false). So, I've shown two notations for monads - do notation and >> notation - and a few examples of code written in both styles. Turns out you've already probably written code in both styles if you've programmed in C and programmed in Java, because you will have used && for error handling in some places, and Java exceptions in some other places. So there's nothing new here. Which style is better? Well, it depends... If you are passing a value from one operation to the next, with nothing else going on, then the >> style is very concise: getLine >> print - we don't waste space assigning the line to a variable only to use it immediately and then forget about it. But when there are lots of actions returning lots of values, it can be easier to use the variables of do notation to keep track of them all:
  print "what is your name?"
  name <- getLine
  print "what is your age?"
  age <- getLine
  print ( "Hello "++name++". You are "++age++" years old and you are cool!" )
Using >> notation is awkward here - somehow you need to combine 5 actions into a linear sequence of actions to perform: print >> getline >> print >> getline >> print but you need to wire the values from getline around in non-linear fashion. Its possible (indeed, when you write in do notation it is translated into >> form by the compiler, as I said above) but it looks ugly - its easier often to use do notation and let the compiler sort it out for you. The Maybe monad adds failure handling to sequenced operations. It turns out that you already probably used that functionality without explicitly realising that was happening. What other interesting stuff can we build by making a monad with its own >> behaviour? One that gives behaviour that you don't find natively in C or Java is backtracking and filtering computation using the list ([]) monad. In the IO monad, a monadic action always returns a value. In the Maybe monad, a monadic action either returns a value or fails. In the [] monad, a monadic action can return multiple values (or one or zero values). We can use the [] monad to try out all combinations of some sets of values. For example:
  x <- [1,2,3,4]
  y <- [100,1000, 1000000]
  [x * y]
gives the result:
This looks like a normal do block, but instead of Just and Nothing from the Maybe monad, we now specify values using []. And we can put many values inside the brackets. In this code, x will iterate over each the value of [1,2,3,4], and inside that, y will iterate over each value of [100,1000,1000000], and then we'll evaluate the value of [x*y], and then all the results for every iteration will be collected together into the output list. You can write list filters like this too:
  x <- [1,2,3,4,5]
  y <- if isEven x then x else []
(assuming we've defined: isEven x = x `rem` 2 == 0) This gives [2,4] as output. And we can write searches that combine both of the above iteration and filtering. For example, say we want to find all of the pairs of digits that add to 5 (for example, 3+2 = 5, so (3,2) is a solution, but 8+1=9 so (8,1) is not a solution) We can write it like this:
  l <- [0,1,2,3,4,5,6,7,8,9]
  r <- [0,1,2,3,4,5,6,7,8,9]
  if l+r==5 then [(l,r)] else []  
which gives us this answer: [(0,5), (1,4), (2,3), (3,2), (4,1), (5,0)] There's a more specific syntax for the list monad in Haskell, called list comprehensions. The above could be written as:
[(l,r) | l <- [0,1,2,3,4,5,6,7,8,9], r<-[0,1,2,3,4,5,6,7,8,9], l+r == 5]
To keep tying in with other langauges, Python has list comprehensions too with a very similar syntax:
>>> [(x,y) for x in [0,1,2,3,4,5,6,7,8,9] for y in [0,1,2,3,4,5,6,7,8,9] if x+y==5]
[(0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)]
This article is about overloading ; which the above seems to be drifting away from. So what does our overloaded semicolon operator (>> and >>=) look like in the list monad? Lets look at f >>= g. In general, this runs f then runs g feeding in the result of f - onto that behaviour we add our monad-specific behaviour. Lets look at how this behaves in a simple [] monad expression to increment the numbers in a list. First define increment:
increment x = [x+1]
which is used like this:
increment 10
Now use increment in a monadic expression:
[1,2,3] >>= increment
What did >>= do here? It seems to have run increment three times, to increment three different numbers. And indeed it did. In the [] monad, our sequencing operator will run its right hand side operation multiple times, once for each of the values returned by the left hand side, and then it will collect the results together into a list. How does that tie into the do notation? It means that when I say x<-[4,5,6], then the whole rest of the program will be run three times - once with x=4, once with x=5 and once with x=6, and then the final result of the program will be joined together in a list. Almost done with rambling for now, but I'll make one final comment: I used increment twice in the above text, once with the Maybe monad:
increment x = Just (x+1)
and once with the [] list monad:
increment x = [x+1]
These are almost the same - they both mean "return a value" in the language of the particular monad they live in. But just as >> and do syntax is independent of the particular monad being used, there is an independent way to "return a value", using return:
increment x = return (x+1)
When you use increment in the Maybe monad, then it will mean Just x+1, and when you use it in [] then it will mean [x+1], but even better, someone else can use that definition of increment in a monad that I have never even heard of - because return will do the 'right thing' whatever that happens to be.

ok definitely enough rambling for now.

No comments:

Post a Comment