Compile-time computations

Constant expressions are those that can be evaluated, and their result used, during the program compilation. For example,

const char array[ 8 * 8 + 1 ];

We can see that the compiler not only compiles the code, but also evaluates some expressions and uses the results.

This is fairly straightforward. But now, consider the following example:

const int i = 2;
const char array[ i == 2 ? 64 : throw exception() ];

Update. Initially, in order to prove that computations are performed at compile-time we used the declaration of a built in C++ array, as above. This was ok for C++11. However, for C++14 something like runtime-sized arrays was considered, and compilers like Clang or GCC provided implementation of something similar: Variable-Length Arrays. So for instance, even the following code would be valid in C++14:

void fun(int i)
{
  int array[i];
  // ...
}

Therefore we will now use class template std::array for similar proofs.

Throwing an exception (which is an expression) cannot be evaluated at compile-time, but since i == 2 is true, the third argument of conditional operator should not be evaluated; at least at run-time. So is the above a valid code? Not in C++03. It is valid however in C++11. Does this sound incredible? We are already used to the following idiom:

return ptr && ptr->getAns();

Dereferencing a null pointer is illegal, but because we use operator && we are guaranteed that the second sub-expression will not be evaluated if the first one evaluates to false. This guarantee is called short circuiting. The similar situation occurs in the above example with throwing an exception. Since the compiler knows that the condition in the conditional operator will evaluate to true, it knows that it will not need to evaluate the third expression. In fact, the compiler must not evaluate the third expression, so the fact that the third expression would be throwing an exception is irrelevant.

C++11 goes even further in terms of compile-time computations and allows using functions in constant expressions, provided that those functions also are defined in terms of constant expressions. Here is an example of such function:

constexpr int factorial( int i )
{
    return (i > 1) ? i * factorial(i - 1) : 1;
}

std::array<const char, factorial(5) + 1> arr;

The new keyword constexpr indicates that you may want to use your function as part of constant expressions (of course, you can still use it as a normal function). Compiler will impose some restrictions on your function: it must be a single return statement. The expression in return statement must be a constant expression itself (this allows calling other constexpr functions). To be more precise, apart from a single return statement, you can put using declarations, typedef declarations and static_asserts in constexpr functions.

You can think of a constexpr function as a potentially constant expression with a name. You could also think of it as a function that can be evaluated at compile-time. What are constexpr functions good for? You can find some use cases here (along with more detailed description of constant expressions feature). In this post we will only see one, but very useful application of generalized constant expressions.

Reporting errors in constexpr functions

An expression is a piece of code that, as any typical function, can be given input values that it is not designed for. For normal functions we can check for invalid input values and throw an exception to avoid incorrect computations. But how can we check for invalid input in an expression? By writing a more complex expression. For normal run-time expressions it is easy when we use conditional operator. Conditional operator is sort of if-statement for expressions. Have a look:

const int j = (i % 2 == 1) ? throw exception() : i / 2;

The real computation in this expression is division by two in the 3rd sub-expression in conditional operator. The rest is checking for ‘invalid expression input’: 1st sub-expression checks the precondition, 2nd sub-expression aborts the evaluation of expression. Normally, noöne checks preconditions like this: it is more clear to put the check in a separate instruction before the real computation; this way the program is easier to read. However, for constexpr functions we have no other choice because we are constrained to having only one expression. Therefore you will see more conditional expressions in constexpr functions.

You may wonder if the above conditional expression is correct. Aren’t the second and the third sub-expression supposed to be of the same type? Well, no. The rules for conditional operator are quite sophisticated and one of them says that if one of the sub-expressions is a throw expression, the type of the entire conditional operator is that of the other sub-expression. It makes sense: if you get to evaluate the 2nd sub-expression, noöne will be interested in the value returned by the conditional operator.

So this was about validating input in ‘run-time’ expressions; how do we do it in compile-time expressions? Exactly the same way. Have a look at this improved factorial function that will reject negative input values:

constexpr int safe_factorial( int i )
{
    return (i < 0) ?        // error condition
        throw exception() : // error reporting
        factorial(i);       // real computation
}

If this is evaluated at compile-time and i is positive or zero, we will return another constant expression: factorial(i). If i is negative we will need to evaluate the throw, and since it cannot be evaluated at compile-time, we will get a compilation error:

array< int, safe_factorial(3) >  arr1; // 6-element array
array< int, safe_factorial(-3) > arr2; // compilation error

The compilation error message will not say about invalid input to function safe_factorial, it will be saying something about incorrectly using constant expressions; but still: compilation error is better than run-time error. You can make the error message prettier by moving error-checking code into a separate function:

constexpr int requires_nonnegative( int i ) 
{
    return (i < 0) ? throw exception() : i;
}

constexpr int safe_factorial( int i )
{
    return requires_nonnegative(i),
           factorial(i);
}

Now, the error message will complain about requires_nonnegative being a non-constant expression, which may make finding the error easier. The above usage of comma operator is worth your attention. The operator it is hardly ever used, and if it is, it is for side effects that its first operand may produce. In constant expressions, though, we cannot have side effects. Yet, this abortion of compilation, that requires_nonnegative may trigger, can be considered a special case of a side effect allowed in static contexts. Note that if necessary, you can put multiple preconditions, by using more commas.

Parsing literals

So, all this looks like a nice toy, but is it really useful? Typical programs wait for user’s input and process it, or convert input streams to output streams, or wait for requests; all of these require data that is available only at run-time. But there are some computations that can still be conducted during compilation. One of those is the initialization of static constants where we can check constant initialization for errors. We will explain this in detail. Suppose we have a program that deals with dates. We have a class Date for dates which has the following constructor.

Date::Date( unsigned d, Month m, unsigned y ); 

Month is an enumeration consisting of values Jan = 1, Feb = 2, and so on. Of course, not every three values (d, m, y) make a valid date. Now, we want to have a special date in our program that indicates a threshold. This will be a constant particular to our application. In C++03 we can declare it as:

const Date dateX( 29, Feb, 1900 ); 

Does February have 29 days in 1900? If it does not, when program is run, an exception will be thrown (most probably), and since it is a global object’s initialization, and there is no place where a try-catch block could be placed, the program will terminate. Due to this problem of throwing globals’ constructors it is recommended that types with complicated initialization should not be globals. Only ‘literal’ types, like integers, had better be globals. In C++11 we can make our class Date such literal type. We will define the class as follows:

class Date
{
    unsigned d;
    Month m;
    unsigned y;

    public:
    constexpr Date( unsigned d, Month m, unsigned y );
    // other stuff ...
};

This is another usage of keyword constexpr. We define a constructor that can be called at compile-time, and hence, we define a type that can be initialized at compile time. (We use word ‘can’, because this class can still be used as normal class). Now we define the constexpr constructor. It is also constrained. It cannot have a body. We can only use expressions in initializer-list. Of course, only potentially constant expressions (to be more precise, in the constructor body we can put some declarations like typedef declarations, using declarations and static_assert). Here is the definition:

constexpr Date::Date( unsigned d, Month m, unsigned y )
: d( requires_goodDay(d, m, y) )
, m(m)
, y( requires_positive(y) ) 
{} // empty body

You can already guess how function requires_positive will look like. Function requires_goodDay could look like this.

constexpr
unsigned requires_goodDay(unsigned d, Month m, unsigned y)
{
    return (d == 0 || d > 31) ?      
               throw BadDayName(d) :
           (is30day(m) && d == 31) ? 
               throw BadDayOfMonth(d, m) :
           (m == Feb && d >= 30) ?   
               throw BadDayOfMonth(d, m)  :
           (!isLeap(y) && m == Feb && d == 29) ? 
               throw Bad29Feb(y) :
           d; // real return value
}

Does it look like mess? In order to check multiple error conditions we had to nest multiple conditional expressions. The above expression is equivalent to the following block:

{
    if( d == 0 || d > 31 )
        throw BadDayName(d);
    else if( is30day(m) && d == 31 )
        throw BadDayOfMonth(d, m);
    else if( m == Feb && d >= 30 )
        throw BadDayOfMonth(d, m);
    else if( !isLeap(y) && m == Feb && d == 29 )
        throw Bad29Feb(y);
    else
        return d;
}

Nested conditional expressions will occur often when extensively using constexpr functions for compile-time computations. Generic compile-time computations were not the primary motivation for generalizing constant expressions in C++11, and in this (and the following) article we are taking the feature to its extreme. This is why we need to bare with a bit inconvenient syntax. There may be nicer ways to write this function, but this is just to prove that it can be written. Now, for the last step of our problem. We have to force our program constant to be initialized at compile-time:

constexpr Date dateX( 29, Feb, 1900 ); 

This is a third usage of the keyword constexpr. It forces the compiler to initialize the constant at compile-time; or to fail the compilation.

And this is it. Note that as of writing this post, C++11 is not an official standard, and the only compiler I am aware of that implements generalized constant expressions is GCC 4.6. Next time we will see how to parse strings at compile-time.