Compiler? I Hardly Know Her!

This week I've been working on a programming language I designed. Specifically, I've been working on a compiler. A friend told me about the LLVM Compiler Infrastructure, and after reading up on it for a while I decided to use it. Here are some reasons why I made this decision:

• LLVM supports multiple platforms.
• LLVM optimizes your code, and allows you to create further optimizations.
• Existing tools that work with LLVM will be able to work with my language.
• LLVM is tested and maintained, which means less testing and maintenance on my part.

Basically, you write some high-level assembly code, and LLVM does the rest of the work for you.

I've spent a long time planning out this language. However, actually writing the compiler has been pretty challenging so far. It's one thing to know you could look at an arbitrary program and compile it by hand. It's quite another to write something that does all that for you.

Since I've only made a little headway on the compiler, I'll talk a little about the language itself. My working name for the language is Virtual. Here are a few of its features:

• Virtual is designed to be performant (comparable to C++ and D).
• Virtual allows for flexible metaprogramming, including templates, and reflection.
• Plus, procedural generation of classes and functions.
• All compile-time expressions must be simplified before code is ever generated.
• This essentially allows you to do functional programming at compile-time.
• Lambda functions
• Shorthand loop syntax can replace most loops.
• C++: for (int i = 0; i < foo.size(); i++) foo[i] = i;
• Virtual: [foo.* = *],
• Tuples are first class citizens.
• and can be used as the return type of a function.
• Inline expansion can be forced, both for an entire function and for individual calls.
• Perfect forwarding is a natural consequence.

It may seem a little kitchen-sinky, but care was taken not to include conflicting features. Bringing all together will be a challenge, to say the least, but I'm looking forward to using it someday.

Break for Christmas

Forgot to post this yesterday, but no post this week on account of Christmas C: Happy holidays everyone! Also, read this if you need some cheering up!

The Space Jelly

Hey guys! So this week I don't have much to talk about, so I decided I'd write a little prose instead. It's a response to the concept art writing prompt on this io9 post.

"Our self is quite long."

So spake the space jelly. The creature arrived unceremoniously ten years ago. At first, it was taken to be a hoax. One can hardly blame people for being skeptical with headlines like, "Giant Jellyfish Found in Low Earth Orbit".

A Short Introduction to Template Metaprogramming

Template metaprogramming is a technique that allows you to do a lot of work at compile-time rather than run-time. It's a good way to generate code that is both flexible and fast. In this post, I'm going to walk through a simple example.

Edit: The examples in this post are written in C++.

So lets say that you're implementing a vector class. It might look something like this:

template <typename T, unsigned int n>
class Vector
{
    public:
        Vector<T, n> operator+ (const Vector<T, n>& v) const;

        T data[n];
};

You want to implement vector addition. You first thought would probably be to do something like this:

template <typename T, unsigned int n>
Vector<T, n> Vector<T, n>::operator+ (const Vector<T, n>& v) const
{
    Vector<T, n> temp;

    for (int i = 0; i < n; i++)
        temp.data[i] = data[i] + v.data[i];

    return temp;
}

This gets the job done, but it isn't optimal. We have to check the variable i every iteration to make sure it's still less than n. In an ideal world, we'd do this:

template <typename T, unsigned int n>
Vector<T, n> Vector<T, n>::operator+ (const Vector<T, n>& v) const
{
    Vector<T, n> temp;

    temp.data[0] = data[0] + v.data[0];
    temp.data[1] = data[1] + v.data[1];
    temp.data[2] = data[2] + v.data[2];
    ...
    temp.data[n - 1] = data[n - 1] + v.data[n - 1];

    return temp;
}

Unfortunately, C++ is not cool enough to have a straight forward way of doing that, so we have to get creative. That's where templates come in! We can make the variable i a template parameter and rewrite this function as a recursive function.

template <typename T, unsigned int n, unsigned int i>
void AddVectors(Vector<T, n>& result, const Vector<T, n>& l, const Vector<T, n>& r)
{
    AddVectors<T, n, i - 1>(result, l, r);
    result.data[i] = l.data[i] + r.data[i];
}

template <typename T, unsigned int n>
void AddVectors<T, n, 0>(Vector<T, n>& result, const Vector<T, n>& l, const Vector<T, n>& r)
{
    result.data[0] = l.data[0] + r.data[0];
}

template <typename T, unsigned int n>
Vector<T, n> Vector<T, n>::operator+ (const Vector<T, n>& v) const
{
    Vector<T, n> temp;
    AddVectors<T, n, n - 1>(temp, *this, v);
    return temp;
}

There are still a couple of problems with this though. First, we're still not gaining performance; we've just traded condition checking for function calling. Second, C++ doesn't let you partially specialize functions. To solve the first problem, we use the inline keyword. This gets rid of the function calls and puts the code direction into the calling function. To get around the second, we can put the function in a template class like this:

template <typename T, unsigned int n, unsigned int i>
struct AddVectors
{
    static inline void Func(Vector<T, n>& result, const Vector<T, n>& l, const Vector<T, n>& r)
    {
        AddVectors<T, n, i - 1>::Func(result, l, r);
        result.data[i] = l.data[i] + r.data[i];
    }
};

template <typename T, unsigned int n>
struct AddVectors<T, n, 0>
{
    static inline void Func(Vector<T, n>& result, const Vector<T, n>& l, const Vector<T, n>& r)
    {
        result.data[0] = l.data[0] + r.data[0];
    }
};

template <typename T, unsigned int n>
Vector<T, n> Vector<T, n>::operator+ (const Vector<T, n>& v) const
{
    Vector<T, n> temp;
    AddVectors<T, n, n - 1>::Func(temp, *this, v);
    return temp;

}

There! Now you have a function that adds two vectors without a loop and without extra function calls! This is just a simple example, but the same technique can be used on larger, more complicated problems. However, I should mention a few caveats before you start going crazy using it everywhere.

First of all, compilers are pretty good at optimizing. In the simple example above, the compiler would probably get rid of the loop anyway. Metaprogramming is best saved for recurring problems that come up frequently in your program (vector math, for example). Second, the inline keyword isn't guaranteed to work. The C++ standard leaves it up to the compiler to decide what should or should not be inlined. The inline keyword is really just a request from the programmer. There are usually compiler-specific keywords to force the compiler to inline a function, but using them requires extra maintenance if you ever want to support a different compiler. Lastly, if it wasn't already apparent, code like this is much longer and much harder to follow than normal code. It can also significantly increase compile times. If you're working with other people, the performance gains might not be worth the confusion.

All that said, there are definitely real and useful packages out there that use template metaprogramming. Both boost and Eigen rely on it heavily. I have a lot more to say on the topic, but I'll save it for later posts.

Of Groups and Other Things

My goal is to make a grid-based cube world, not unlike Minecraft. However, I don't want it to appear outright as boxy as that, so I'm going to include other shapes, not just cubes. Here's how I can to decide on which shapes to use.

The first shape that came to mind, other than a cube, was a slope. Naturally this led to corner slopes as well, both inner and outer. I then decided I wanted slabs, blocks that are only a portion of the height of a full block. This led to the idea of scaled slopes as well. I decided to divide the shapes into four possible heights. Not content to favor the vertical direction, I decided to include all rotations and reflections of these shapes.

At this point, the number of shapes had already climbed into the thousands. It became evident that if I wouldn't be able to handle each shape by hand on a case by case basis. I needed to to use math!

So I started thinking of mathematical ways to organize the different shapes. The easiest thing to do was to categorize each block by which slices you'd have to make to carve it out of a cube. For the slopes, that meant cutting diagonally. For the slabs, cutting flat across the middle.

Because I wanted four levels to my shapes, I just had to figure out all the slices that only cut across fourths on each edge. That way, there would be no awkward shapes that wouldn't match up with any other shape.

This actually turned out to be quite challenging. In 2D, the idea is pretty simple. You just pick any two points on the outside and draw a line through them. It's doesn't work out so nicely in 3D. There are lots of ways you can pick three points that don't result in a valid cut.

I spent a long time on that, but it seemed that no matter which way I organized the shapes, there'd be a couple of gaps full of invalid cuts. After many hours of trying to make that work out, I went with a somewhat simpler approach. I start with a tetrahedron made by slicing through three of the cube's corners. Then, I take that and scale it on each axis. Then I take those shapes and extrude them along each axis. Then, I also include the inversions of all those shapes.

When all is said and done, I end up with 54,000 different combinations. This way of doing it also has some nice properties. I can arrange the whole thing in a 30x30x30x2 grid, which allows me to look things up easily. I can encode the position of a shape within this grid using 5 bits for each axis and a bit for inversion (encoding each axis separately allows me to discern qualities of a shape easily). This is exactly 16 bits, which allows me to use 2 bytes per block rather than more, and doesn't waste them. I can also tell whether two shapes cover the same cross section along an axis by checking if they're in the same line in that grid.

To sum up a long story, here is a picture taken from within that grid of possibilities.