Stack-based template metaprogramming in C++ (11)

Many months ago right after G++ 4.7 was released I discovered a nifty syntax for writing metaprograms using a stack language similiar to Forth and Factor. I started writing a small library around it, but got sidetracked and never finished it. The following is an explanation and code.

Preliminary reading

http://factorcode.org/ is a great place to learn stack language programming and can be used as a reference when implementing words.

Rationale

Here’s a short, contrived example of a traditional metafunction (such as from Boost MPL) that computes the number of elements in a container that satisfy a predicate, squares the result, and then adds 5:

template<typename Predicate, typename List>
struct foo
: add<
      square<
          typename length<
              typename filter<
                  Predicate, List
              >::type
           >::type
      >::type,
      int_<5>
  >
{};

Yeah, that sucks.

Now compare it to a stack-based approach which was working code in my library:

struct foo : word<filter, length, square, int_<5>, add> {};
// alternate syntax:
using foo = word<filter, length, square, int_<5>, add>;

The difference is light and day! And if you make a mistake the errors are nicer too! I recall getting it down to a static assert message that contained the type of error and current stack which was infinitely more readable than the 10000 page garbage standard TMP spits out.

So how is this implemented?

The Stack

First off, let’s start out with implementing a stack using TMP. Stack languages use the stack for storing data.

The simplest way is to use variadic templates. A stack with ‘foo’ on top and ‘qux’ on the bottom can be represented as the following using variadic templates:

stack<foo, bar, qux>

In addition, we need to be able to push, pull, and get the top of the stack in order to use it.

Here is the full implementation:

template<typename...>
struct stack;
template<typename X, typename... Xs>
struct stack<X, Xs...> {
  using type = stack;
  using top = X;
  
  template<typename T>
  using push = stack<T, X, Xs...>;

  using pop = stack<Xs...>;
};
template<>
struct stack<> {
  using type = stack;

  template<typename T>
  using push = stack<T>;
};

(Note that templates aliases are used for the push/pop/top functions. This is because I find it to be more convenient than templated structs with a type member.)

Unfortunately, this stack has a minor problem notation-wise; languages like Factor position the top of the stack on the right while our notation positions it on the left. While this has no effect on the semantics of the program, it can be confusing to use. Luckily, the evaluator can use any type of TMP stack that supports push, pop, and top and so it is possible to write TMP stacks that notate the top of the stack on the right, although that is beyond the scope of this article.

Let’s also write a few helper functions that operate on our stacks as they’ll be needed later:

// pops N times from Stack
template<typename Stack, int N>
struct stack_drop {
  using type = typename stack_drop<typename Stack::pop, N - 1>::type;
};
template<typename Stack>
struct stack_drop<Stack, 0> {
  using type = Stack;
};

// returns top after popping N times from Stack
template<typename Stack, int N>
struct stack_index {
  using type = typename stack_index<typename Stack::pop, N - 1>::type;
};
template<typename Stack>
struct stack_index<Stack, 0> {
  using type = typename Stack::top;
};

Evaluation Groundwork

Implementing evaluation is where things get tricky. First off, let’s talk about words.

A ‘word’ in stack languages is essentially the functions that make up the program, and thus the input words compose the program code. In fact, the way words are implemented is just as metafunctions – they input a stack and output stack.

Words will be represented abstractly – a type that contains an apply metafunction can be used as a word. Here’s the pattern you’ll see:

struct {
  template<typename Stack>
  struct apply { // apply the stack to this word
    // ??
  };
};

One way of constructing words is through word composition. Given a list of words, composing them involves piping the output stack of the previous word as the input to the next, thus creating a new word which sends its input to the first word of the composition, and returns the result of the final word.

Here’s the skeleton of the implementation:

// word composition
template<typename... Words>
struct word {
  template<typename Stack>
  struct apply {
    // ??
  };
};

Word composition is crucial to creating stack programs. In fact, a stack program is just a composition of words!

Because of this, our eval function will have a word and a stack as parameters, with another stack being returned. Here’s the skeleton:

template<typename Word, typename Stack = stack<>>
struct eval {
  using stack = // ??
};

The stack defaults to an empty stack for convenience.

Here’s how it’s used:

eval<foo_word, stack<>>::stack

Complete Evaluator

Our groundwork is done, now onto the actual implementation.

Let’s first talk about implementing word composition.

A simple method of composing a list (which I did not use) involves realizing that words and composition form a monoid. The binary operator simply composes two words, and the identity word is just a word that returns its stack unchanged. Because of this, we can compose a list of words by folding the binary composition over the list.

Accidentally, however, I took a different path of implementation which I now realize is more powerful. The basis requires redefining word application to include another parameter – the list of words that come after the word being evaluated. For instance, if you’re evaluating this list:

[foo, bar, qux]

Then the list [bar, qux] would be applied to foo, which then applies [qux] to bar, and then [] to qux.

Those familiar with continuation passing style will see the similarity!

Here’s the new skeleton:

template<typename... Words>
struct {
  template<typename Stack>
  struct apply {
    template<typename... Remaining>
    struct continuation {
      // ...
    };
  };
};

I’m using the term continuation and remaining as those are the closest terms I can think of. Keep in mind that it’s referring to the remaining words of the composed list, not of the entire program. Thus, it forms what I’ll call (probably mistakenly) a scoped continuation.

Let’s start out implementing the simplest word we can think of: the identity word. As said early, the identity word returns its stack unchanged. While this may seem useless, we can actually use it as a starting point to create other words.

Here’s the code:

struct id {
  template<typename Stack>
  struct apply {
    // This only catches the empty list - specialization will catch others
    template<typename...>
    struct continuation {
      using stack = Stack;
    };

    template<typename Word, typename... Remaining>
    struct continuation<Word, Remaining...> {
      using stack =
        typename Word::template apply<Stack>
        ::template continuation<Remaining...>::stack;
    };
  };
};

This has two behaviors:
- The resulting stack with an empty continuation/remaining list is simply the stack passed as an argument
- The resulting stack with a non-empty continuation/remaining list is the result of applying the stack to the first word of the continuation list and passing the tail of the list along.

Notice that id is actually doing word composition – it’s composing itself with the head of the continuation/remaining list.

With that done, here’s the implementation of the word composition struct:

template<typename... Words>
struct word {
  template<typename Stack>
  struct apply {
    template<typename... Remaining>
    struct continuation {
      using stack = typename id::apply<
        typename id::apply<Stack>::template continuation<Words...>::stack
      >::template continuation<Remaining...>::stack;
    };
  };
};

So what’s going on here? Well, id is used to set a starting stack value and then pass it through a list of words. The inner use of id is constructing a single word out of an inner list, and the outer use is composing it with the remaining outer list. It’s quite hard to describe in English!

Finally, here’s the eval metafunction:

template<typename Word, typename Stack = stack<>>
struct eval {
  using stack = typename id::apply<Stack>::template continuation<Word>::stack;
};

Again, id is used to set a starting stack value and then pass it through a word.

Primitives

With the evaluator done, let’s create a few primitive words so it can be tested out.

Here’s a primitive which pushes a type value onto the stack:

template<typename T>
struct push {
  template<typename Stack>
  struct apply {
    template<typename... Remaining>
    struct continuation {
      using stack = typename id::apply<
        typename Stack
        ::template push<T>
      >::template continuation<Remaining...>::stack;
    };
  };
};

Here are some integer primitives:

template<int I>
struct int_wrapper {
  static int const value = I;
};

struct add {
  template<typename Stack>
  struct apply {
    template<typename... Remaining>
    struct continuation {
      using stack = typename id::apply<
        typename stack_drop<Stack, 2>::stack
        ::template push<intc<
          stack_index<Stack, 0>::stack::value
          +
          stack_index<Stack, 1>::stack::value
        >>
      >::template continuation<Remaining...>::stack;
    };
  };
};

template<int N>
struct int_ : push<int_wrapper<N>> {};

And finally a primitive which swaps the top two values of the stack:

struct swap {
  template<typename Stack>
  struct apply {
    template<typename... Remaining>
    struct continuation {
      using stack = typename id::apply<
        typename stack_drop<Stack, 2>::stack
        ::template push<typename Stack::top>
        ::template push<typename stack_index<Stack, 1>::stack>
      >::template continuation<Remaining...>::stack;
    };
  };
};

Let’s test it out!

#include <iostream>

struct ten_and_five : word<int_<5>, int_<10>> {};
struct foo : word<ten_and_five, swap, int_<20>, add> {};

int main() {
  std::cout << eval<foo>::stack::top::value;
  foo x;
}

Improved Primitive Definitions

Once you have a sufficient number of primitives you can simply define other words using them instead of writing complex code involving apply and continuation. However, to get to that point involves lots of boilerplate.

To improve things, you can define metafunctions to automate this process. For example:

struct add  : func2_to_word<boost::mpl::add> {};
struct minus :func2_to_word<boost::mpl::minus> {};

I also recall using X-macros for more complicated words.

These will be left as excessive to the reader.

Interesting Things #1 – Word order

An interesting thing about stack languages is that you can easily factor out words without changing the program.

Here’s a modified version of the test program:

struct five : int_<5> {};
struct ten_and_five : word<five, int_<10>> {};
struct foo : word<ten_and_five, word<swap, word<int_<20>>>, word<word<add>>> {};

While the words are named differently their order is the same and thus the output is the same. This property will not hold if you do things with the “scoped continuation” as explaining below.

Interesting Things #2 – Quotations

Quotations are essentially a list of words which exist on the stack. They are analogous to first-class functions in traditional programming.

Two primitives which you will want for dealing with quotations are call and if_then_else, which you can learn about in the Factor manual.

Here’s how you could use them:

template<typename... Words>
struct quot : push<word<Words...>> {}

struct foo : word< quot<a, b>, call > {};

struct bar : word< quot<a>, quot<b>, bool_<true>, if_then_else > {};

Interesting Things #3 – Continuations/Remaining

Recall earlier I mentioned that implementing words using continuation/remaining lists is more powerful than the alternative. Well, part of the reason is because you can make use of that list when defining words. Program manipulation and introspection become possible!

For instance, our push word could use the head of the list as it’s argument:

struct foo : word<push2, bar> {};
// would be same as:
struct foo : word<push<bar>> {};

Or we could add (basic) if/then/else syntax:

struct foo : word<if, pred, then, quot<bar>, else, quot<qux>> {};
// else is optional
struct foo : word<if, pred, then, quot<bar>> {};
// pred is optional
struct foo : word<if, then, quot<bar>> {};

Or we could push that list onto the stack as a quotation which could be used to model exceptions or goto:

struct foo : word<word<push_rem, foo, bar>, call> {};

These are just a few examples – there are tons of different things you can do!

Full code

My original library code is a mess but here’s the code used in this post:
http://pastebin.com/vhDjGvFB

About these ads
This entry was posted in Programming and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s