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, in C++14 we will have runtime-sized arrays, and compilers like Clang or GCC already implement them. So for instance, even the following code is 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.

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

16 Responses to Compile-time computations

  1. Instead of the “throw exception()” in some of these examples could you not use a static_assert(false, “appropriate error message”) instead?

  2. Hi Matt.
    static_assert would not work. If I say:

    int positive( int i ) {
      if (i <= 0) {
        static_assert(false, "");
      }
      return i;
    }
    

    (no constexpr), the function will fail to compile and no-one would be even checking the value of i. This is because the value of i is a runtime property of the program, and the assertion is evaluated at compile-time.

    Now, if I add a constexpr and rewrite:

    constexpr int positive( int i ) {
      return (i <= 0) ? static_assert(false, "") : i;
    }
    

    The situation is practically the same: function positive, although it can be used in compile-time computations, is also a normal function that can be called at runtime, and the same reasoning applies: the value of i is a runtime property of the program, and the assertion is evaluated at compile-time.

    It would also fail for another reason: static_assert is a declaration rather than expression and cannot be ‘called’ inside expression — the above function has a syntax error. I could re-wirite it to:

    constexpr int positive( int i ) {
      static_assert(i > 0, "");
      return i;
    }
    

    But it is still illegal. For a similar reason: the value of i is (or at least could be) a runtime property of the program, and the assertion is evaluated at compile-time.

    The following, though, is correct:

    constexpr int forward( int i ) {
      return i;
    }
    
    static_assert( forward(1) > 0, "positive");
    

    Regards,
    &rzej

  3. What about


    constexpr
    template
    int positive() {
    static_assert(i > 0, "");
    return i;
    }

    Usage:
    int arr[positive()];

  4. Hi Oleksandr,
    Wordpress has eaten some portions of your code example. I guess, the original looked like this:

    template <int i>
    constexpr int positive() {
      static_assert(i > 0, "");
      return i;
    }
    
    int arr[ positive<10>() ];
    

    Is this correct?
    If so, the answer is ‘yes’. This will work; and in fact works on GCC 4.7.2. The only problem I would have with that is the expression positive<10>(). Now it does no longer look like a natural function call, but some template ‘trick’. It is likely to putt off people. Note that similar tricks are already available in C++03:

    template <int i>
    struct positive
    {
      static_assert(i > 0, "");
      enum {value = i};
    };
    
    int arr[ positive<10>::value ];
    

    Regards,
    &rzej

  5. Rick Wildes says:

    I guess what the previous comments are trying to say is they don’t mind using the throw to generate a compile time error but if the function is invoked at runtime they want to do something else. It would be nice if you could at least optionally have 2 versions of a function (some kind of overloading) where one is used strictly for constexpr only and the other is used for runtime evaluation only.

    • Hi Rick. Constexpr-based overloading might not be a good idea for other reasons, but the effect you expect — if I understood your description correctly — can be achieved today:

      int handle_at_runtime(int i)  // note: no constexpr
      {
        // invalid argument handling
      }
      
      constexpr int positive(int i) 
      {
        return i > 0 ? i : handle_at_runtime(i);
      }
      

      Because handle_at_runtime is non-constexpr, it works the same way as a throw.

      • Rick Wildes says:

        But will that generate a compile error if I passed a literal -1 to positive?

        • No: constexpr functions are not guaranteed to be evaluated at compile-time.
          The guaranty they do offer is that when you need to compute a compile-time constant, they can be used.

          void fun()
          {
            int i = positive(-1); // possibly evaluated at run-time
          }
          
        • Rick Wildes says:

          Right. So this means I can not create a constexpr function that does both of the following:
          1) issues a compiler error when evaluated at compile time if invalid literals are used.
          2) does not throw an error when evaluated at run time if invalid dynamic parameters are used.

          It would be nice if constexpr could be used on the parameters to indicate that the parameter must use a constant expression then allow overloading for liked named function that isn’t a constexpr.

  6. @Rick:

    Right. So this means I can not create a constexpr function that does both of the following:
    1) issues a compiler error when evaluated at compile time if invalid literals are used.
    2) does not throw an error when evaluated at run time if invalid dynamic parameters are used.

    It looks constexpr functions cannot even guarantee your bullet 1:

    constexpr int forward(int i)
    {
      return i;
    }
    
    void fun()
    {
      int i = forward(1); // possibly evaluated at run-time
    }
    

    But I wonder why “does not throw exception” is so important for you.

    • Rick Wildes says:

      The overuse of exceptions can make a library unusable. I’m not saying this is the case in any of your examples but there are times when using an exception is over kill.

      The other thing I would like to do with constexpr functions is to force the function to only be used with constant expressions (i.e. disallow at compiler to use runtime evaluation). Would this work?

      template <int int_expr>
      struct must_be_int_constexpr
      {
      };
      
      // can only use this with constant expressions!
      constexpr int ensure_positive(int i)
      {
        typedef must_be_int_constexpr<i> ensure_positive_only_works_with_constexprs;
        return (i <= 0) ? throw std::exception() : i;
      }
      
      int main( )
      {
          int user_number = get_number_from_user();
          
          ensure_positive(5);           // works
          ensure_positive(user_number); // compiler error
      
      
      	return 0;
      }
      
      • If you want to handle precondition violations by other means than exceptions in constexpr functions, you can do that. You can use the technique I described above, with non-constexpr subexpression. At compile-time, it has the same effect as throwing an exception.

        Your expectation that the same function should do something different in run-time and something different at compile-time is somewhat against the idea of constexpr functions. Their goal was to be able to perform the same computation in either case.

        Your example above will not work. Parameter i can either be a compile-time constant or a run-time variable. The body of the function must be prepared to handle either; no matter how the function will be used or if it will be used at all.

        If you need compile-time-only functions, I guess the only option is to resort to C++03 metafunctions:

        template <int i>
        struct ensure_positive
        {
          static_assert(i > 0, "not positive");
          static constexpr int value = i;
        };
        
        int array[ ensure_positive<10>::value ];
        

        If this syntax is inacceptable, you can wrap it into a macro:

        #define ENSURE_POSITIVE(NUM) (ensure_positive<(NUM)>::value)
        
        int array[ ENSURE_POSITIVE(10) ];
        
  7. legends2k says:
    #include <stdexcept>
    using namespace std;
    
    constexpr int factorial( int i )
    {
        return (i > 1) ? i * factorial(i – 1) : 1;
    }
    
    constexpr int safe_factorial( int i )
    {
        return (i < 0) ? // error condition
        throw exception() : // error reporting
        factorial(i); // real computation
    }
    
    int main()
    {
        int x[safe_factorial(-3)];
    }
    

    Compiling this in g++ 4.8 gives no compile-time error (all I get is an unused variable warning). Am I doing something wrong here?

    • No: it looks like GCC implemented “variable-length arrays” or something similar. The following also compiles fine.

      int main()
      {
        int i = 2;
        int x[i];
      }
      

      It looks like some of the examples from my post will not work now. I recommend using the following code for testing:

      #include <stdexcept>
      
      using namespace std;
      
      constexpr int factorial( int i)
      {
        return i > 1 ? i * factorial(i - 1) : 1;
      };
      
      constexpr int safe_factorial( int i )
      {
        return (i < 0) ? // error condition
        throw exception() : // error reporting
        factorial(i); // real computation
      }
      
      template <int N> struct test{};
      int main()
      {
        test<safe_factorial(3)> t;
      }
      
  8. talagmon says:

    “…Compiler will impose some restrictions on your function: it *must* be a single return statement.”
    In some compilers that support c++1y extension may allow you to use more then one return statement.

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