Tales from the Evil Empire

Bertrand Le Roy's blog

News


Bertrand Le Roy

BoudinFatal's Gamercard

Tales from the Evil Empire - Blogged

Blogs I read

My other stuff

Archives

June 2010 - Posts

How I understood monads, part 2/2: have we met before?

(c) Bertrand Le Roy The first post in this series can be found here:
http://weblogs.asp.net/bleroy/archive/2010/06/16/how-i-understood-monads-part-1-2-sleepless-and-self-loathing-in-seattle.aspx

Last time, I tried to explain how beer and Lou helped me finally understand monads. I gave a couple of trivial examples. Hopefully now that you have this new functional hammer, everything will start looking like a nail.

So let’s have a look at a few screws this time.

Like last time, I’ll be pretty liberal with the definition of a monad as long as the spirit of monads seems to be preserved. Feel free to nitpick in the comments ;)

Oh yeah, jQuery is a monad

In jQuery, you first create a wrapped set of HTML elements and then execute operations on it, the result of which is a new wrapped set:

$(".foo")
    .filter(":odd")
    .map(function () {
        return this.id;
    });

Seems familiar? That because it is: the wrapped set is a monad. Pretty much.

The unit function of the monad, which is responsible for boxing an object into the monadic type is the $ function: $(elt) is building the wrapped set for the elt element.

The binding operation is more implicit than it’s been in previous C# examples and consists in just executing one of the built-in set operations or one of the plug-ins: the operation is specified by simply calling it. So for the monad to really take arbitrary operations there is a registration phase here (the registration of the plug-in) but what the operations themselves are doing is in the spirit of monads: they act on the underlying DOM or JavaScript types and return a new wrapped set.

Unboxing the wrapped elements is done by calling the get function.

Oh yeah, FluentPath is a couple of monads

Ah, here’s one I wrote before I even understood what a monad is (assuming that I do now). FluentPath is wrapping System.IO’s string paths and arrays of string paths into Path and PathCollection boxes. Once this is done, you can execute one of the built-in operations, the result of which is also a wrapped path or path collection. You can also execute custom operations:

var dirs = Path.Get("video")
    .GetFiles("*.avi", true)
    .Copy(p => p.Parent.Combine("backup").Combine(p.FileName))
    .ChangeExtension(p => p.Extension + ".bak")
    .Map(p => p.Up(2));

This is pretty close to jQuery (for a reason, FluentPath was inspired by jQuery).

Path.Get is wrapping the path, the operations are method calls, with or without Lambda parameters.

An example of an arbitrary or custom operation on the set can be seen in the example above: the Map call is taking each element of the path collection and going two levels up on it. The result is a new wrapped set of paths.

Unboxing is done by calling ToString on a path.

Oh yeah, Linq providers are monads

Just look at this:

var l = new[] {"foo", "bar", "baz"}
    .Select(s => "... " + s)
    .Select(s => s + " bleroy was here.");

Looks familiar? Again, it should be. We could just as well write this same example this way:

var l = from s in
            from s in new[] {"foo", "bar", "baz"}
            select "... " + s
        select s + " bleroy was here.";

See? The IEnumerable<T> interface is the box and the selects are binding the operations.

What’s interesting here is that we have a way to specify operations on an enumeration of things that is independent from the kind of thing we’re working on: an array like above, or a SQL Server table, an XML document or whatever has a Linq provider.

It’s also independent of how the operations get executed: a Linq provider abstracts away how the expression of the operation gets translated into actual operations that the underlying type can understand.

This second abstraction is where the real magic in Linq resides: when you write a where clause in Linq, the actual implementation of that clause may be SQL or a C# operation or who knows what, but how you write the expression itself doesn’t change.

And while we’re talking about expressions…

Oh yeah, Expression<T> is a monad

An expression in .NET is a representation of a function:

Expression<Func<string, string>> expr = 
    s => s + " appended some stuff.";

In this example, we are taking a Lambda and wrapping it into an expression object. The beauty of it is that this object can then be manipulated at runtime to build new expressions, which can then be unwrapped into functions and executed.

By now you should have seen where I’m going with this: boxing a Lambda is done by wrapping it into an Expression and unboxing is done by calling Compile() on the expression.

The Bind operation is less obvious and would not fit in this post but it can be done by implementing an expression tree visitor.

Oh yeah, Parallel.ForEach is a monad

The new parallel extensions in .NET 4 are quite interesting as they offer parallel computation under a familiar model.

For example, you can do this:

Parallel.ForEach(
    Directory.GetFiles("*.jpg"),
    path => {
        var bitmap = new Bitmap(path);
        bitmap.RotateFlip(RotateFlipType.RotateNoneFlipXY);
        bitmap.Save(path + ".flipped");
    });

This code will execute a rotation operation on each JPEG image in the current directory, in parallel as much as possible, which is ideal for long-running and independent operations such as image manipulation.

What really happens is that the enumeration of files returned by Directory.GetFiles is getting wrapped into a ParallelEnumerable, and then the operation is getting executed on each of the elements of the enumeration in parallel.

The boxing operation is thus represented here by the AsParallel method (which is implicitly called by Parallel.ForEach). The binding operation of the monad is Parallel.ForEach.

What we are seeing here is a monad whose only goal is to provide a different execution model for an existing operation. The value of the monad pattern is quite clear in this example: a familiar programming model is being quite naturally extended.

Oh yeah, C#4’s dynamic is a monad

Thanks to the new dynamic keyword in C#4, it is now possible to ask the C# compiler to relax compile-time type checking and instead resolve the members of some objects at runtime.

Here’s a somewhat trivial example:

dynamic foo = new {
    bar = "baz"
};
Console.WriteLine(foo.bar);

This example is rather pointless but what’s important is that what can be wrapped into a dynamic object comes in many shapes: .NET objects can be accessed this way (through reflection), but you can also wrap COM objects or pretty much anything provided that somebody wrote the code to resolve the underlying type system at runtime.

Boxing is done by assigning the object from the underlying type system to a dynamic variable like above. You can then perform any C# operations on the wrapped object and access the members of the underlying type system exactly as if it were a native .NET object.

The monad binding is implicit here. What really happens is that the operations are being delegated at runtime to the underlying type system by the dynamic object provider.

Monads everywhere

With functional programming becoming more mainstream and insidiously getting into more “classical” languages such as C# or JavaScript, it’s probably not such a big surprise that its patterns would find their way into our everyday APIs. Once you know the monad pattern, all sorts of things that you weren’t noticing before suddenly seem to jump into focus, like one of those optical illusions that at first you don’t see, and that once you see cannot be unseen.

Did you spot monads in familiar places? Let me know in comments.

Next time, I’ll look at expressing monads with CallStream, and after that I’ll make a post to answer some of the comments I got on this post and the previous one, such as “why should I care?”

How I understood monads, part 1/2: sleepless and self-loathing in Seattle

(c) Bertrand Le Roy For some time now, I had been noticing some interest for monads, mostly in the form of unintelligible (to me) blog posts and comments saying “oh, yeah, that’s a monad” about random stuff as if it were absolutely obvious and if I didn’t know what they were talking about, I was probably an uneducated idiot, ignorant about the simplest and most fundamental concepts of functional programming. Fair enough, I am pretty much exactly that.

Being the kind of guy who can spend eight years in college just to understand a few interesting concepts about the universe, I had to check it out and try to understand monads so that I too can say “oh, yeah, that’s a monad”.

Man, was I hit hard in the face with the limitations of my own abstract thinking abilities. All the articles I could find about the subject seemed to be vaguely understandable at first but very quickly overloaded the very few concept slots I have available in my brain. They also seemed to be consistently using arcane notation that I was entirely unfamiliar with.

It finally all clicked together one Friday afternoon during the team’s beer symposium when Louis was patient enough to break it down for me in a language I could understand (C#). I don’t know if being intoxicated helped. Feel free to read this with or without a drink in hand.

So here it is in a nutshell: a monad allows you to manipulate stuff in interesting ways. Oh, OK, you might say. Yeah. Exactly.

Let’s start with a trivial case:

public static class Trivial {
    public static TResult Execute<T, TResult>(
this T argument,
Func<T, TResult> operation) {
return operation(argument); } }

This is not a monad. I removed most concepts here to start with something very simple. There is only one concept here: the idea of executing an operation on an object. This is of course trivial and it would actually be simpler to just apply that operation directly on the object. But please bear with me, this is our first baby step. Here’s how you use that thing:

"some string"
  .Execute(s => s + " processed by trivial proto-monad.")
  .Execute(s => s + " And it's chainable!");

What we’re doing here is analogous to having an assembly chain in a factory: you can feed it raw material (the string here) and a number of machines that each implement a step in the manufacturing process and you can start building stuff. The Trivial class here represents the empty assembly chain, the conveyor belt if you will, but it doesn’t care what kind of raw material gets in, what gets out or what each machine is doing. It is pure process.

A real monad will need a couple of additional concepts. Let’s say the conveyor belt needs the material to be processed to be contained in standardized boxes, just so that it can safely and efficiently be transported from machine to machine or so that tracking information can be attached to it.

Each machine knows how to treat raw material or partly processed material, but it doesn’t know how to treat the boxes so the conveyor belt will have to extract the material from the box before feeding it into each machine, and it will have to box it back afterwards.

This conveyor belt with boxes is essentially what a monad is. It has one method to box stuff, one to extract stuff from its box and one to feed stuff into a machine.

So let’s reformulate the previous example but this time with the boxes, which will do nothing for the moment except containing stuff.

public class Identity<T> {
    public Identity(T value) {
        Value = value;
    }

    public T Value { get; private set;}
    
    public static Identity<T> Unit(T value) {
        return new Identity<T>(value);
    }

    public static Identity<U> Bind<U>(
Identity<T> argument,
Func<T, Identity<U>> operation) {
return operation(argument.Value); } }

Now this is a true to the definition Monad, including the weird naming of the methods. It is the simplest monad, called the identity monad and of course it does nothing useful. Here’s how you use it:

Identity<string>.Bind(
    Identity<string>.Unit("some string"),
    s => Identity<string>.Unit(
s + " was processed by identity monad.")).Value

That of course is seriously ugly. Note that the operation is responsible for re-boxing its result. That is a part of strict monads that I don’t quite get and I’ll take the liberty to lift that strange constraint in the next examples.

To make this more readable and easier to use, let’s build a few extension methods:

public static class IdentityExtensions {
    public static Identity<T> ToIdentity<T>(this T value) {
        return new Identity<T>(value);
    }

    public static Identity<U> Bind<T, U>(
this Identity<T> argument,
Func<T, U> operation) {
return operation(argument.Value).ToIdentity(); } }

With those, we can rewrite our code as follows:

"some string".ToIdentity()
    .Bind(s => s + " was processed by monad extensions.")
    .Bind(s => s + " And it's chainable...")
    .Value;

This is considerably simpler but still retains the qualities of a monad. But it is still pointless.

Let’s look at a more useful example, the state monad, which is basically a monad where the boxes have a label. It’s useful to perform operations on arbitrary objects that have been enriched with an attached state object.

public class Stateful<TValue, TState> {
    public Stateful(TValue value, TState state) {
        Value = value;
        State = state;
    }

    public TValue Value { get; private set; }

    public TState State { get; set; }
}

public static class StateExtensions {
    public static Stateful<TValue, TState>
ToStateful<TValue, TState>(
this TValue value,
TState state) {
return new Stateful<TValue, TState>(value, state); } public static Stateful<TResult, TState>
Execute<TValue, TState, TResult>(
this Stateful<TValue, TState> argument,
Func<TValue, TResult> operation) {
return operation(argument.Value)
.ToStateful(argument.State); } }

You can get a stateful version of any object by calling the ToStateful extension method, passing the state object in. You can then execute ordinary operations on the values while retaining the state:

var statefulInt = 3.ToStateful("This is the state");
var processedStatefulInt = statefulInt
    .Execute(i => ++i)
    .Execute(i => i * 10)
    .Execute(i => i + 2);
Console.WriteLine("Value: {0}; state: {1}",
processedStatefulInt.Value, processedStatefulInt.State);

This monad differs from the identity by enriching the boxes. There is another way to give value to the monad, which is to enrich the processing. An example of that is the writer monad, which can be typically used to log the operations that are being performed by the monad. Of course, the richest monads enrich both the boxes and the processing.

That’s all for today. I hope with this you won’t have to go through the same process that I did to understand monads and that you haven’t gone into concept overload like I did.

Next time, we’ll examine some examples that you already know but we will shine the monadic light, hopefully illuminating them in a whole new way. Realizing that this pattern is actually in many places but mostly unnoticed is what will enable the truly casual “oh, yes, that’s a monad” comments.
Part 2/2 of this series can be found here:
http://weblogs.asp.net/bleroy/archive/2010/06/29/how-i-understood-monads-part-2-2-have-we-met-before.aspx

Here’s the code for this article:
http://weblogs.asp.net/blogs/bleroy/Samples/Monads.zip

The Wikipedia article on monads:
http://en.wikipedia.org/wiki/Monads_in_functional_programming

This article was invaluable for me in understanding how to express the canonical monads in C# (interesting Linq stuff in there):
http://blogs.msdn.com/b/wesdyer/archive/2008/01/11/the-marvels-of-monads.aspx

How Orchard works

(c) Bertrand Le Roy I just finished writing a long documentation topic on the Orchard project wiki that aims at being a good starting point for developers who want to understand the architecture, structure and general philosophy behind the Orchard CMS.

It is not required reading for anyone who only wants to write Orchard modules and themes but hopefully it will help people who want to evaluate the platform and start writing patches.

Read it here:
http://orchardproject.net/docs/How-Orchard-works.ashx

When failure is a feature

(c) Bertrand Le Roy 2004 Warning: this post is going to be slightly off-topic and non-technical. Well, not computer science technical at least.

I was reading an article in SciAm this morning about the possibility of a robot uprising. Don’t laugh yet, this is a very real, if still quite remote possibility.

The main idea that was described was that AI could rise one day to self-awareness and to an ability to improve itself through self-replication beyond human abilities to control it.

Sure, that’s one possibility, and some people are actually arguing that if that’s the case, maybe it’s just the march of evolution and humankind is just destined to one day become obsolete and be replaced by something fitter, whether from good old evolution or by artificially creating its own replacement.

I would tend to agree but I do have an objection. There is a distinction in this kind of speculation that is not often pointed out: self-replication and evolution are not the same thing.

We don’t know exactly how a self-replicating pre-biotic device emerged out of inanimate matter a few billion years ago, but that it did and that it managed to evolve to the variety of life that we observe today was only possible because of one crucial little feature of the whole system: failure.

Because they arose naturally, the first pre-biotic replicators probably were clunky little things that were only working within specific conditions and that were failing often. In particular, such an imperfect replication mechanism could fail in lots of different ways under the influence of a varying environment.

And this is precisely what enabled them to mutate into something a lot more interesting. That ability to create imperfect copies of themselves is what made it possible for early organisms to adapt to an environment that is sure to change (from external causes as well as under the influence of the organisms themselves on their own environment).

Guess what? This “strategy” has been so successful that it is still a feature of all living organisms today. You’d think that organisms could have evolved to remove the imperfections and to ensure perfectly faithful self-replication. But that in the long run would be a losing strategy because the next time the environment changes in a way that is no longer compatible with your perfection, you die and leave no successor.

In fact, modern organisms did evolve such perfecting mechanisms that suppress mutations from expressing themselves, but the amazing thing is that this suppression can fail under stress, which might be part of what you observe at times of mass extinctions, which are also fertile events in that they trigger the appearance of a large number of new species that are fit to the new conditions in a geologically short amount of time.

Sex on the other hand is another evolved way of introducing variation into the genes of a population. In other words, sex is the greatest invention of all times after failure.

What I’m getting at is that we may be able in the not so remote future to create self-replicating machines and when we do, we might make the mistake of making the replication perfect. It may actually be a lot simpler to do so: the easiest to build self-replicating structure probably is a lot simpler than the messy stuff nature came up with through random processes and selection.

And if the replication is perfect, this leaves no room for anything new, ever. What it could allow on the other hand is a reproduction mechanism that is much more efficient than anything life has been able to invent yet, the sort of manufactured efficiency that could take over the planet.

Self-awareness is clearly not necessary for self-replication and might even impair it so why they are packed together so often is kind of a mystery to me.

So why am I talking about this today? To make the larger point that failure can be an essential creative force and that without it the world would be a cold and sterile place where creativity has no role to play.

I often tell my 6-year-old that if she never fails, she will never learn. Failed ideas for example are at the heart of the concept of brainstorming: failure is the path to success.

More Posts