Templated Monads? Monadic Templates?

Posted on by Idorobots

So, I finally found some time for a Template Metaranting follow-up post. This time let's get down to business as this one contains a fair amount of code.

Sadly, I won't rant as much but instead I'll try to show how awesome D's templates really are. We'll write a piece of code, based on this Scheme implementation, that is, a simple monad) that we'll use to build a binary tree, with uniquely numbered nodes containing their height, without any global state (therefore purely) entirely at compile time.

Quick Reader, grab my code!

ADVENTURE!

Let's jump straight in, shall we?

import std.typecons;

template MakeNumberedValue(alias tag, alias val) {
  enum MakeNumberedValue = tuple(tag, val);
}

template NumberedValue(alias tv) {
  enum NumberedValue = tv[ 1];
}

template NumberedTag(alias tv) {
  enum NumberedTag = tv[ 0];
}

template Return(alias value) {
  template Return(alias counter) {
    alias MakeNumberedValue!(counter, value) Return;
  }
}

template Bind(alias M, alias F) {
  template Bind(alias counter) {
    enum t = NumberedTag!(M!counter);
    enum v = NumberedValue!(M!counter);
    alias F!v M1;

    alias M1!t Bind;
  }
}

So... That's all. That's the monad. We define several simple templates that manage our numbered pairs. A pair consists of a unique tag and a value it stores. Next we define two basic monad operations - that is - bind (>>=) and return (well... return). I'll leave checking the Monad Laws to the Reader as I'm too lazy to do it myself.

Let's now build the binary tree analogically to the original Scheme implementation:

template Increment(alias n) {
  enum Increment = MakeNumberedValue!(n+1, n);
}

template MakeNode(alias value, alias kids) {
  template __Lambda(alias counter) {
    alias Return!(tuple(MakeNumberedValue!(counter, value), kids))
          __Lambda;
  }

  alias Bind!(Increment, __Lambda) MakeNode;
}

template BuildBtree(alias depth) {
  static if(depth == 0) {
    alias MakeNode!(depth, "leaf") BuildBtree; // The leaf node.
  }
  else {
    template __Lambda1(alias left) {
      template __Lambda2(alias right) {
        alias MakeNode!(depth, tuple(left, right)) __Lambda2;
      }

      alias Bind!(BuildBtree!(depth-1), __Lambda2) __Lambda1;
    }

    alias Bind!(BuildBtree!(depth-1), __Lambda1) BuildBtree;
  }
}

This part is a little less readable as there are no anonymous templates in D (what would that even be?). I won't bother explaining this snippet as it's pretty involved, it contains nested templates, template aliases, static conditionals and a standard library defined tuple - several of D's numerous template goodies.

Just enjoy it. <3

Lastly, we need to "run" the monad and output it to the console:

template RunMonad(alias M, alias counter) {
  alias M!counter RunMonad;
}

void main() {
  enum numberedBinaryTree = RunMonad!(BuildBtree!3, 100);
  pragma(msg, numberedBinaryTree);
}

This code creates a numberedBinaryTree of depth 3, each node with a unique identifier starting with 100. I used pragma(msg, ...) to output the tree just to make it clear that it was, indeed, created at compile time. Here's the "pretty-formatted" output that shows our binary tree:

Tuple(115, Tuple(
  Tuple(114, 3),Tuple(Tuple(
    Tuple(106, 2), Tuple(Tuple(
      Tuple(102, 1), Tuple(Tuple(
        Tuple(100, 0), "leaf"), Tuple(
        Tuple(101, 0), "leaf"))), Tuple(
      Tuple(105, 1), Tuple(Tuple(
        Tuple(103, 0), "leaf"), Tuple(
        Tuple(104, 0), "leaf"))))), Tuple(
    Tuple(113, 2), Tuple(Tuple(
      Tuple(109, 1), Tuple(Tuple(
        Tuple(107, 0), "leaf"), Tuple(
        Tuple(108, 0), "leaf"))), Tuple(
      Tuple(112, 1), Tuple(Tuple(
        Tuple(110, 0), "leaf"), Tuple(
        Tuple(111, 0), "leaf"))))))))

It may not be as readable as the Scheme version, but that's a small price to pay. Now don't get me wrong, this fairly involved code just shows the capabilities of D's templates - you can implement such complex ideas as monads very easily. Additionally, it maps nearly directly to the Scheme code. That's a yet another reason I like D so much.

BTW, I might write a little more useful monad as a followup to this post, to show that this can be, in fact, useful. Stay tuned.

2016-02-16: Adjusted some links & tags.