Last article I talked about computing things at compile time with C++ templates. It hurts so incredibly bad, so, by popular demand, I give you:

constexpr (or Generalized Constant Expressions)

constexpr lets you write functions that execute at compile time that (mostly) don’t look as exotic as Haskell. For instance, our best friend, the factorial:

constexpr int factorial(int n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

To calculate it at compile time, we just do:

constexpr int factorial_6 = factorial(6);

If you don’t believe that it’s a compile-time constant:

static_assert(factorial_6 == 720, "your compiler is funky :(");

However, we have one big restriction: constexpr can only consist of a single return statement. That means you can’t declare variables, use for or while loops or even use the if statement. To get around this, we use recursion and the ?: operator. Additionally, you can only call other constexpr functions and reference other constexpr global variables.

We can, however, have structures and classes, and even use them with templates!

template<typename T>
struct Cons {
    const T head;

    // Yes, we can even use _pointers_!
    const Cons<T> *tail;
};

// We need a pointer to this list later for the tail of the list, so we
// allocate in the data segment of our program like this. There's nothing we
// can do about it.
constexpr Cons<int> l1 = {
    .head = 2,
    .tail = nullptr
};

// :(
constexpr Cons<int> l = {
    .head = 1,
    .tail = &l1
};

Not too pleasant, but at least the angle brackets here aren’t that scary. With a few static_asserts, we can make sure that it is, in fact, a compile-time list:

static_assert(l.head == 1, "yep");
static_assert(l.tail->head == 2, "still yep");

We can print out the list, too, with a simple recursive function:

#include <iostream>

template<typename T>
void print_list(const Cons<T> *xs) {
    if (!xs) return;
    std::cout << xs->head << std::endl;
    print_list(xs->tail);
}

With this function, we can pass any Cons<T> * into it:

print_list(&l);

We can also implement a constexpr version of our foldl function (see this if you’re not familiar with it):

// We can't use lambda functions with constexpr, so we have to write a functor
// for it.
template<typename X, typename Y>
struct add {
    constexpr X operator()(const X &x, const Y &y) {
        return x + y;
    }
};

// The functor is passed to foldl as a template parameter.
template<typename F, typename T, typename U>
constexpr T foldl(const U &z,
                  const Cons<T> *xs) {
    return xs == nullptr ? z : foldl<F, T, U>(F()(z, xs->head), xs->tail);
}

Now we can call foldl over our list with an absolutely ridiculous way of passing arguments:

constexpr int sum = foldl<add<int, int>, int, int>(0, &l);
static_assert(sum == 3, "it burns!");

CTFE (or Compile-Time Function Execution)

<rfw> Zor: could constexpr be better than CTFE
<Zor> no

Over in the D camp, there’s something similar to constexpr that’s been around for a while — CTFE. For instance, we can do this (factorial examples are too damn easy, I’m sorry):

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

A simple static assertion reveals that we can compute it at compile time:

static assert(factorial(6) == 720);

And we can make CTFE explicit by assigning to something of type enum:

enum factorial_6 = factorial(6);
static assert(factorial_6 == 720);

D functions also don’t have to be declared as CTFE — they are executed at compile time depending on the context they’re present in. They are also subject to certain restrictions which are significantly less restrictive than those of constexpr.

For instance, we can implement an iterative version of factorial that adheres to D CTFE but not C++ constexpr restrictions:

int factorial_iterative(int n) {
    int result = 1;
    while (n > 0) {
        result *= n--;
    }
    return result;
}

static assert(factorial_iterative(6) == 720);

However, I couldn’t figure out how to reconstruct the singly-linked list example with D’s CTFE, even with various combinations of immutable, new and enum. This is probably more painful than C++11’s constexpr structs. If I’m doing something horrifically wrong, feel free to drop me a line in the comments and I’ll rectify this section.

Conclusion

I’ve gotten J&J’s “no more tears” baby shampoo in my eyes. It hurts like BUGFUCK. It sets your damn eye on FIRE, just like any other soap.

ikkyu2