A question recently asked why a ‘constexpr’ function in C++ may comprise only a return statement. It’s a good question. On quick glance the restriction seems somewhat arbitrary, and indeed quite limiting. I think the answer comes not from the desires of the users (us programmers) but from the implications on compiler vendors. In particular, how does it simplify the job of a compiler?
The original question is here.
What is constexpr
Just a quick background: ‘constexpr’ is a new keyword in the C++11 standard. It allows simple expressions to be used as part of constant expressions, where previously only a simple literal constant could be used (ex: hard-coded integer or string literal). One of these key locations is static member variable initialization. Allowing expressions can both improve code readability, and allow more variables to be ‘const’. In practice a ‘constexpr’ will be evaluated at compile time possibly resulting in more efficient code.
Compilers are not abstract machines
It may not be obvious that a compiler is not an abstract machine. While a compiler may be able to produce executable code, there is no general need for it to know how to execute code on its own. The role of the compiler is to translate your code into a lower form which can then be executed by an abstract machine. The high-level transformations can be quite oblivious to what your code is actually doing.
If we look at the optimizer however we see something similar to what we want. In order to produce efficient runtime code it is often necessary to evaluate the code. Some common optimizations are const-folding and inlining. An optimizer will trace through expressions involving constants and replace them with the resulting value. Beyond just saving some calculation time, it allows the optimizer to do things like remove constant branches, perform loop unrolling, and further inline code.
Since the optimizer can do constant exression evaluation, ‘constexpr’ must be easy to implement, right? Unfortunately the answer isn’t yes. Likely a compiler vendor cannot use any of their optimization code to do the ‘constexpr’ evaluation. The problem is that optimizations tend to be done at a much lower level. Usually a compiler has a front-end which processes the high-level language like C++ into a lower level form, often called IR (intermediate representation). Optimizations are often performed on this form (both clang and gcc work this way).
A ‘constexpr’ however needs to be evaluated at a higher level, directly in the C++ front-end. All constants, including things like default parameters, are already resolved prior to the generation of IR. ‘constexpr’ is essentially asking the compiler to implement an abstract machine at a very high level.
But not a full machine
That is the source of the restrictions on ‘constexpr’. It would be a lot of work to need an abstract machine at the highest level of the compiler. Not even the low-level optimizer does the full work required of an abstract machine. Sure, some languages actually run in virtual machines, but even there that machine is still quite separated from the source language itself (for example with Java).
Allowing any type of evaluation to be done in a ‘constexpr’ would likely have been resisted and not added to the standard. Even if it were added it would likely be years before it could be implemented. To simplify the implementation, and likely remove resistance, the ‘constexpr’ requirements are extremely strict. The key limitation is that a function can only return a value, and more obviously only call other ‘constexpr’ functions with constant parameters.
This makes evaluation rather easy. If you’ve ever done the calculator example with a parser you’ve done this type of work. Evaluating the expression is primarily a matter of reducing a parse tree. Let’s consider the following code.
[sourcecode]
constexpr int neg( int a ) {
return -a;
}
constexpr int sub( int a, int b ) {
return a + neg(b);
}
struct holder {
static const int value = sub(2*sizeof(int),5);
};
[/sourcecode]
The static member ‘value’ needs to be evaluated at compile-time. If all the parameters are replaced with their input values the following full tree of the evaluation results.
You should notice the leaves are all simple constant values. This allows us to collapse any branch since the value will be known at compile time. Indeed, since a constant branch also evaluates to a constant this entire tree reduces to the value ’11’. As long as an expression can be represented by such a tree it can be evaluated with a simple recursive algorithm.
An implementation
Be aware however that a compiler will not likely produce that expanded tree. The parameters to a function are generally evaluated prior to the evaluation of the function call (as opposed to substituted as I have done). The order of operations the compiler may roughly be:
- p1 = eval( 2*sizeof(int) )
- p2 = eval( 5 )
- return call( sub, p1, p2 )
- — p3 = call( neg, p2 )
- — — return eval( -p2 )
- — return eval( p1 + p3 )
The functions ‘eval’ and ‘call’ could be real functions in the compiler. As an example, I might write the functions with the below signatures. Here ‘const_value’ is an object which holds a constant value and ‘syntax_tree’ holds the parsed source code.
[sourcecode]
const_value eval( syntax_tree expr, map<const_value> variables );
const_value call( string func, map<const_value> params );
[/sourcecode]
I should note that ‘call’ would likely be a fairly limited function. It would lookup the ‘syntax_tree’ for the provided function name then pass this on to the ‘eval’ function.
This brings us back to the limitations on ‘constexpr’. A compiler must already have types like ‘const_value’ and ‘syntax_tree’, otherwise it wouldn’t have been able to compile previous C++ code. With that already covered the ‘eval’ function is a rather modest addition rather than a fundamental change.
Curiously the ‘eval’ function might also exist. Prior to C++11, template parameters were already allowed to be integral expressions, and they had to resolved at compile-time. This new ‘eval’ function for ‘constexpr’ may just be an extension of that mechanism to allow more types. Given the close relationship between these features it’s surprising that the restrictions on templates weren’t lifted.
Conclusion
Does this answer our question of “Why a ‘constexpr’ is just a return statement?” It might, assuming the reason was primarily to reduce the effort required of compiler vendors. It does so by avoiding the need for a full abstract machine and instead builds upon concepts a compiler must already handle.
