Saturday, October 28, 2006

Monads as Universe Helpers

To see if the grass is greener on the other side of the programming fence, I've been accumulating a scaffolding of knowledge about functional programming which recently culminated in my understanding of the really cool and deep concept of monads.

Monads chain computations in a special way. There are many types of monads, and each chains its computations in its own special way. One of them chains computations in good old procedural fashion, keeping results around inside good old assignable variables and running computations according to our good friends the flow constructs; if, while, for and collaborators. Another familiar face is the layer-based architecture, the bureaucratic tower in which each floor's computation feeds the layer immediately above it. Another monad lets any computation abort part of the remaining computational chain by throwing an exception, and yet another generalizes the idea to the also-quite-cool concept of continuations.

Now, given that I already knew these useful models, was it really worth it to bang my head against the wall until monads finally made sense? Well, walls as just as rigid you would imagine them to be, so I would not recommend doing so if you're only looking for a new tool to add in your ever-growing bag of programming tricks. I believe the concept is more of a philosophical tool, actually. Or perhaps a mathematician's cute pet.

Remember what happened last time philosophers played with the concept of computability? Their fellow physicists had experimented with the world and made very impressive predictions about the behaviour of thrown balls and sliding blocks and complicated pulley systems. What do you know, it seems the world might be computable after all; determinism enters the scene and turns us all into emotionless mechanical contraptions.

The mechanical contraptions cried and argued against their fate, ridiculed defenceless pulley systems so they would feel better about themselves, and actively looked for escape clauses in their contract with the universe. Then one triumphal morning, quantum mechanics defeated the crooked determinism beast by invalidating science's dream of perfectly accurate predictions. What a relief; we could now choose to be emotionless lottery contraptions if we so wished. But of course what we really wanted all along was free will, not unpredictability.

Enter monads. And markov chains. You are an anthropomorphic dot moving in a large graph representing the universe. At each time-step, you must choose one of your node's outgoing edges and follow it to a new node. Some universe implementations may be deterministic or random about this and you won't be left with much of a choice. Some implementations might be kind enough to give you free will. But the gods who subcontracted the construction of the universe to our firm aren't quite sure which it will be yet, so we better make our implementation modular in that respect.

We also better make sure that our implementation can scale well, because universes tend to grow astronomically large. For one thing, we definitely don't want to fill up drive after drive with nodes and edges, so we will need to use a trick. We will only keep track of your current node and compute your possible outgoing edges, on the fly, whenever we need them. The architecture of our universe is thus composed of three parts: a function mapping nodes to possible actions (Laws), a current node (Creature), and that thing which chains executions of the functions using either free will or not (Monad). Yes, a free will monad; I told you this stuff was deep.