C++11: Simple Compile-time Calculator With Constexpr

Hi everyone! In this post we'll run through a classical computer science exercise: Building an arithmetic evaluator. This one will only manage +, -, * and /, no parenthesis, infix notation, no space (simple to add, but boring). That may look too simple… Let's add a constraint: computations must be done at compile time.

For the little story, I wanted to code it after one of my teacher told me a story about a project for students that consists in building an arithmetic evaluator (bistromathique) able to deal with very huge number (a lot bigger than 2³²). The computation to do was stored in a file given to the student before 'make' was run to build its project. A student simply created a rule in his Makefile that makes another program evaluates the input file and redirected the result into the expected binary that only printed it out. Nice cheat right? Unfortunately for him, he was caught, that's why we know the story, but the idea is exploitable. Why not making computation at compile time? A real problem is how to parse this expression.

In this post, I'll first show you how to think the problem to be able to represent it simply. Then, I'll present the available tools to make "beautiful" compile-time expressions with C++11, and finally I'll show and explain the whole code. Let's go!

1 How to evaluate an arithmetic expression?

1.1 Language Theory

There is a lot of different way to evaluate an arithmetic expression. Some people will make it with the Shunting Yard algorithm, or with some tools to generate parser (Bison for example), etc. I wanted a simple way to do it. Bison will not be helpful here, Shunting Yard is too heavy. Should we create a constant Abstract Syntax Tree? Or a constant Stack? It doesn't seem interesting for us to translate it, in term of time (at a development level). The proposed solution is based on Language Theory. The arithmetic language follows a simple grammar. First, you have to know how to read a grammar. A grammar is composed of several rules of this form:

<symbol> ::= expression

<symbol> is called nonterminal. expression is a sequence of symbols. Symbols are a nonterminal or a terminal (a terminal doesn't appear on the left side of a rule. In this post, they appear between double quotes). There could be several possibilities (one expression or another, it is represented as ~expression1 | expression2). More information on Wikipedia. The simple arithmetic grammar used is:

<expr> ::= <T>
<T> ::= <U> "+" <T> | <U> "-" <T> | <U>
<U> ::= <number> "*" <U> | <number> "/" <U> | <number>
<number> ::= <number> <digit> | <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Well! It seems a little cryptic when you don't know what it is, but you'll see that it's not :). Your expression must follow a path in these rules to be grammatically valid. Otherwise there is an error. Let's see what say these rules: a valid expression follows the rules <T>. <T> means that the expression is a <U> plus <T>, or a <U> minus <T>, or just a <U>. <U> is a <number> times <U>, or a <number> slash <U>, or just a <number>. A <number> is a nonempty list of <digit>. And here it is! You can write an addition, a subtraction, a division and a multiplication.

The rule are selected in function of your expression, it takes (roughly) what matches the more. Here is how it passes through the rules with several examples:

• 2: take the rule <T>, <U>, <number>, <digit>. Valid.
• 2+3: take the rule <T>, <U> "+" <T>:
  • expr is 2. <U> becomes <number>, <digit>;
  • expr is 3. <T> becomes <U>, <number>, <digit>. Sill valid.
• 2+*3: take the rule <T>, <U> "+" <T>:
  • expr is 2. <U> becomes <number>, <digit>;
  • expr is *3. <T> becomes <U>, <number> "*" <digit>:
    • expr is empty. <number> is an error.

  So it is invalid.

I hope these little examples help you to understand how it works if you didn't know. You can ask questions in comments if you want ;-). I'll be pleased to help you. If you spot a mistake, don't hesitate to signal it!

1.2 How to implement it?

You should be convinced (I hope) that these rules would help us to implement simply an arithmetic evaluator. Moreover, since the priority between operators is managed by the recursion (yes, multiplication will occur before addition for example), you can do all the computations on-the-fly. No need to build a Stack, or an Abstract Syntax Tree. I really love this method because it is simple to implement. For people that think that the lack of parenthesis causes its method to be so easy, you're wrong. I let you the job to find where to integrate them (hint: the latter the rule is called, the higher its precedence is. Example, the multiplication is called later than the addition, and so it has a higher precedence).

We just have to represent these rules with functions. It's not really so easy, because if you implement it as this:

evalT(char* expr) { return evalU(head(expr)) - evalT(tail(expr)); }

In this snippet head takes the expression and returns the part before the '-' and tail returns the part after. You'll have this behavior: eval(2-4+2) will return -4. Because it will evaluate 4+2 before applying the '-'. So you must compute one <U> at a time. This way, 2-4+2 will be processed this way: accu = 2 - 4; accu = accu + 2 and accu will be equal to 0 as expected.

So it is really easy to implement, one function for each rule, and you have to loop over each new nonterminal (for <T> it is <U>, for <U> it is <number>…) and apply the right operation. And it will work!

But you may wonder (and it's great!): How can I do an error management? Simply, you can make lexical error (invalid character) when you process the value of your number in the last rule. And you can make a parse error if your last rule received an empty content. That means there is two operators side by side. Finally, all the error management is done in the function that evaluates your number.

Finally, to have a fully featured arithmetic evaluator, you have to find how to put the parenthesis in these recursive functions (hint: error management is also very simple in this case). Once again, you can ask question if you want :)

For having implemented it some time ago, I can say that it may take 3 functions of less than 30 lines each. But now, let's add some fun! Let's see how we can transform this into a compile-time version.

2 Compile-time arithmetic evaluator

2.1 Compile-time tools with C++11

"Constexpr is a 4th sublanguage added to C++" - Andrei Alexandrescu.

In C++03, there was only templates to make computation at compile-time (explicitly I mean. Sometimes compiler can do this kind of optimization alone). But it was really painful. For example, to make something as simple as factorial you had to declare a template class parametrized by an integer, and specialized it when the integer is 0. Here is how it looks:

template <unsigned n>
struct fact
{
  static const int value = n * fact<n - 1>::value;
};

template <>
struct fact<0>
{
  static const int value = 1;
};

The first class fact declares the general case where value is equal to n times n - 1 (it is just written with template). We then had to specialize this class when the integer is 0. That way, when you call fact<5>::value, it will answer 120 as expected. But this approach has some drawbacks. The syntax may look ugly (sweet euphemism…), it is error prone, hard to debug, and so on. I think no one will try to parse and evaluate complex structures with template. If this person exists, I have a deep respect for its courage…

So C++11 comes with a new support for compile time programming: constexpr. It allows to make computation during the compilation ("Because compilation was already too fast" - Herb Sutter). I have already discussed a little about constexpr in a previous post. Let's go a little deeper, according to the standard, there are several constraints that a function must satisfy to be considered as constexpr:

• Call only constexpr function,
• Only one return statement,
• static_assert are fine,
• All its declaration must be declared constexpr.

I don't write all the conditions here (the standard is long… More on cppreference) but here are the main conditions you should be aware of. First question: how to make real functions with only one return? In fact you have to deal a lot with recursion, and with ternary operator (?:).

Here is the implementation of factorial using constexpr:

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

Personally, I found this version simpler to write and to read. For me this is a great thing to gain in readability. There is a second huge advantage to deal with constexpr instead of template: constexpr can be used in the compile-time and run-time world. It avoids having two (very different) codes to solve the same problem. Some (important) things to note:

• static_assert can't be used to check the value of your argument since it can be called at run time. If you want to do that, you must pass the argument as template parameter. For a little discussion about that, see this question on stackoverflow.
• You can't declare an argument of a function constexpr.
• Prefix and postfix incrementation/decrementation on a variable are forbidden.
• Constexpr function are implicitly inline.
• Constexpr non-static method is const (if it is not a constructor of course!).
• There is an implementation defined (I think) limit for recursion, to change its value, you can use the -fconstexpr-depth= option. I'm not sure if this flag is standard, at least it works with g++-4.6.1, 4.7.1, clang++-3.0 and clang++-3.1.

2.2 How to do error management with constexpr?

This is a tougher question than it seems. I first tried to use static_assert, because I wanted to have an error clear at compile time. But the first point of the list of notes above makes me unable to succeed. So I used exception. Some part are not evaluated. For example, in b ? 1 : 0, the 0 part is evaluated only if b is false. So you can put a throw expression on the false part in a constexpr function. This will cause the function to not respect the definition of a constexpr function and it will fail the compilation. In my opinion, compile-time programming should have compile-time error.

I chose to implement it that way:

constexpr
bool my_static_assert(bool b, const char*)
{
  return b ? true : throw std::exception();
}

If I want to use it only at compile-time (the code above represents that case), I implement it that way. I want to have an explicit error message, that's why there is a second argument. As you can see, I don't use it (reminder: if you don't give a name to an argument, the compiler understand that it will not be used). So, you may wonder why I put that here? To get an helpful error message: Here is an extract of the g++ error message I get if I do a parse error in my program:

$ g++ --std=c++11 -DEXPR="\"3*+9\"" static_eval_expr.cc
static_eval_expr.cc: In function 'int main()':
static_eval_expr.cc:102:32: \
 in constexpr expansion of 'parseT(((const char*)"3*+9"), 0, 1)'
static_eval_expr.cc:96:43:  \
 in constexpr expansion of 'parseT_private(s, s, 0, value, ((int)op))'
........
static_eval_expr.cc:48:60:   in constexpr expansion of \
'my_static_assert((len != 0), \
((const char*)"Parse error: No side by side operators!"))'
static_eval_expr.cc:28:42: erreur: expression \
 '<throw-expression>' is not a constant-expression

(The dot line represents some lines I dropped out to simplify the example, lines finishing by a '\' continue in the line below). I hope it is clear enough. I can't get the exact location, but it is better than just a non understandable compile error right?

Note that I chose to raise std::exception because the error message doesn't give this information clearly, and the main information is contained in the constant string. In all other situations, std::exception is, in my opinion, to avoid. Using clear type is helping the compiler and the programmer. So don't use that in the real world! :)

Now, let's see how works my compile-time version of our arithmetic evaluator!

2.3 How it works

The classical grammar-based algorithm uses recursion, loops, and makes a pointer run through the string. We only have recursion. There is no mutable variable. So we have to figure out how to transform our run-time version (I didn't present the code of the run-time version here because I don't want student of my school to use it for their own project) into a full constant version.

To loop through the string we use recursion. I first implement a compile-time atoi (ascii-to-int). I assume that we use ASCII standard (I want that because in that case: the value of the character '4' subtracted to the character '0' is equal to 4, and the same for every character representing a digit). So let's see how we can do that with some checking. I'll use my_static_assert declared above.

constexpr
bool is_number(const char c)
{
  return c >= '0' && c <= '9';
}

constexpr
int myatoi(const char* s, int len, int value = 0)
{
  return *s && len
    ? (my_static_assert(is_number(*s), "Invalid character!"),
       myatoi(s + 1, len - 1,
             (*s - '0') + value * 10))
    : value;
}

is_number is trivial, it returns true if the character given in argument is a digit and false otherwise. Let's see myatoi now. It takes as first argument the string (we use char* because we can't use std::string since its not constexpr. So we go down one level and we directly work on the pointer). The second argument is the number of characters we must read. Because in our use case, we just send it part of the string to read, and this part is defined by a beginning and a size. The third argument is the current value accumulated. I indent all ternary expression to make it as clear as possible.

If we translate the code above in English, we have: if the current character is not null and we have still some characters to read: check that the current character is a number, if not raise an error. If it is valid, call yourself on the next character, reduce the number of character to read by one, and update the value. If we have finished to read our string, return the accumulated value.

Let's see how we update the value: We read our string from left to right, so we add the first character to value. Then we just have to multiply by 10 the accumulated value each time we move on the right! :)

Now, we have to apply our recursive calls to manage priority between the operators. Remember that we have to find a way to advance your "pointer" to didn't read several time the same part of the string we're working on.

Since all is constant, the way I found is to create a substring defined by the beginning of the substring and its length. Then we call recursively ourselves, with the updated value. So here is how it works: the function that manages the operation '+' and '-' is split into two: there is a function that makes the interface and initialize some variables, and the other one that does the job. So it ends up with two functions per rules. Here is (finally!) the whole code:

#include <iostream>

constexpr int parseT(const char* s, int value = 0, bool op = true);
constexpr int parseU(const char* s, int limit, int value = 1,
                     bool op = true);

constexpr
bool is_number(const char c)
{
  return c >= '0' && c <= '9';
}

constexpr
bool is_valid(const char c)
{
  return is_number(c) || c == '+' || c == '-' || c == '*' || c == '/';
}

constexpr
bool my_static_assert(bool b, const char*)
{
  return b ? true : throw std::exception();
}

constexpr
int myatoi_private(const char* s, int len, int value = 0)
{
  return *s && len
    ? (my_static_assert(is_number(*s), "Invalid character!"),
       myatoi_private(s + 1, len - 1,
                      (*s - '0') + value * 10))
    : value;
}

constexpr
int myatoi(const char* s, int len)
{
  return my_static_assert(len, "No side by side operators!"),
         myatoi_private(s, len);
}

constexpr
int parseU_private(const char* s, int limit, const char* begin, int len,
                   int value, bool mul)
{
  return *s && limit
    ? (*s == '*' || *s == '/'
       ? (mul
          ? parseU(s + 1, limit - 1, value * myatoi(begin, len),
                   *s == '*')
          : parseU(s + 1, limit - 1, value / myatoi(begin, len),
                   *s == '*'))
       : parseU_private(s + 1, limit - 1, begin, len + 1, value, mul))
    : (mul
       ? value * myatoi(begin, len)
       : value / myatoi(begin, len));
}

constexpr
int parseU(const char* s, int limit, int value, bool op)
{
  return parseU_private(s, limit, s, 0, value, op);
}

constexpr
int parseT_private(const char* s, const char* begin, int len,
                   int value, bool add)
{
  return *s
    ? (*s == '+' || *s == '-'
       ? (add
          ? parseT(s + 1, value + parseU(begin, len),
                   *s == '+')
          : parseT(s + 1, value - parseU(begin, len),
                   *s == '+'))
       : parseT_private(s + 1, begin, len + 1, value, add))
    : (add
       ? value + parseU(begin, len)
       : value - parseU(begin, len));
}

constexpr
int parseT(const char* s, int value, bool op)
{
  return parseT_private(s, s, 0, value, op);
}

int main()
{
  constexpr auto e = EXPR;
  constexpr auto res = parseT(e);
  std::cout << res << std::endl;
}

If you want to test the code, copy/paste this in your favorite editor, and compile it like this:

g++(4.6.1): g++ --std=c++0x -DEXPR="\"1+1\"" file.cc
g++(4.7.1 or 4.8): g++ --std=c++11 -DEXPR="\"1+1\"" file.cc
clang++(3.1): clang++ --std=c++11 -DEXPR="\"1+1\"" file.cc

It won't compile with a clang version lower than 3.1. If you have tried another compiler, feel free to report your results in comments :) You can replace 1+1 by any arithmetic expression composed by number, '+', '-', '*', '/'. If your expression is not valid, it won't compile. Note that spaces are forbidden. As said in the beginning, it is not a feature hard to add, but it adds dumb code when I want code to be crystal clear.

Now let's explain a little the code above, starting by the main. EXPR is the variable given on the command line when compiling (with the -D option). parseT takes a const char* and returns an integer. Variables can be declared constexpr, so we declare e and res constexpr. Then we just print the result. Now, let's run through the interesting part of the code.

parseT_private takes as second argument the beginning of the current sub expression we will give to the second level (parseU). So we have to create a parseT function that set the beginning of the expression. This is the same thing for parseU that calls myatoi. The main idea of the recursion is that I read my expression until I get one of the operator of my level (for parseT it is '+' or '-', for parseU it is '*' or '/'). Once it is done, it gives the substring between the beginning and just before the operator to be evaluated by the next level. And this updates the current value. We then run the recursion on the right part of the operator. We have to remember what was the operation before this subexpression to apply it when updating the current value. So at the beginning, value is 0, and the first operation is a '+' (this explains the op = true in parseT).

Let's see some steps of the program to understand how it thinks:

• 2+2: parseT("2+2") calls parseT_private("2+2", "2+2", 0, 0, true). We read 2, and we arrive to a '+'. So we call parseU on "2", which returns 2 since there is no '*' nor '/' in this expression. We add 2 to the variable value, we remember that we have seen a '+', and we call parseT on the right part of the '+'. We arrive to end of string, so we just call parseU on "2", and we get two. The previous operator was a '+', so we add. 2+2 = 4, as expected!
• 2*2+2: parseT_private("2*2+2", "2*2+2", 0, 0, true), we still stop at the '+', so parseU receives "2*2" and the variable limit is equal to 3 (to know where stop reading). In parseU_private we are looking for a '*' or a '/'. We get a '*', so we send the left part to myatoi, and we continue our recursion on the right part of the string. We remember that the previous operation was a '*'. We arrive on the limit of our expression (limit is now equal to 0), so we stop, and send 2 to myatoi and we multiply the current value to the return value of it, so we get 4. We are back to parseT_private, and the current value is 4. The rest of the recursion simply add 2 to it. And (finally) we get 6, as expected.

Now, let's develop a little one of the main function of the program, parseT_private. First of all, why this dumb name? It is a toy program, and I just wanted to differentiate it from parseT. So the first idea that came to my mind was just fine. In parseT_private, there are four different cases. The first one is:

• We are on a '+' or a '-', let's apply the previous operation which was a '+' on the left part of the operator and run the recursion of the right part.
• We are on a '+' or a '-', let's apply the previous operation which was a '-' on the left part of the operator and run the recursion of the right part.
• We are not in an operator, we continue to read the string. We increase the size of the current substring.
• We are arrived to the end. Let's do the last computation.

The code of parseT_private and parseU_private are very similar. They just don't play at the same level (remember the BNF grammar? These levels ;-) ). I found the code above quite elegant, since it solves a problem not so simple, moreover at compile-time, and it does it in less than 100 line of code. These functions just represent the algorithm I have described in the first part of the article with the constexpr constraints. Don't hesitate to ask question in comments if you want more information about a precise part of the code.

You may wonder "how to be sure that the result is computed at compile time?". Two solutions: you can add a static_assert in the main, to check if the result is the one you wanted, or you can use gdb. Let's see how to use our debugger:

$ g++ --std=c++0x -DEXPR="\"3+9-6+5-1+2-12+3*7+3\"" static_eval_expr.cc
$ ./a.out
24
$ gdb -q a.out
Reading symbols from a.out...(no debugging symbols found)...done.
(gdb) disassemble main
Dump of assembler code for function main:
   0x080485f4 <+0>:     push   %ebp
   0x080485f5 <+1>:     mov    %esp,%ebp
   0x080485f7 <+3>:     and    $0xfffffff0,%esp
   0x080485fa <+6>:     sub    $0x20,%esp
   0x080485fd <+9>:     movl   $0x8048772,0x18(%esp)
   0x08048605 <+17>:    movl   $0x18,0x1c(%esp)
   0x0804860d <+25>:    movl   $0x18,0x4(%esp)
   0x08048615 <+33>:    movl   $0x804a040,(%esp)
   0x0804861c <+40>:    call   0x80484c0 <_ZNSolsEi@plt>
   0x08048621 <+45>:    movl   $0x8048530,0x4(%esp)
   0x08048629 <+53>:    mov    %eax,(%esp)
   0x0804862c <+56>:    call   0x8048520 <_ZNSolsEPFRSoS_E@plt>
   0x08048631 <+61>:    mov    $0x0,%eax
   0x08048636 <+66>:    leave
   0x08048637 <+67>:    ret
End of assembler dump.
(gdb) q
$ echo $((0x18))
24

Disassemble shows the assembler code for a function. If we analyze it, we realize that there is no call to parseT. The two calls are due to std::cout and std::endl. If we look at 0x18 (<+17> or <+25>), it corresponds to 24, our result. So all has been computed a compile time, and there is no run time cost. Great isn't?

3 Conclusion

I hope this example of how to use constexpr for making compile-time programs. I don't say that you should make some programs like the one I show in this post, but it can help the compiler to optimize your programs by evaluating code at compile time instead of run time. It also solves certain problem like std::numeric_limits::max() which is a function representing a constant value. How to solve this problem? Putting a constexpr qualifier on this function does the job.

The main aim of this post is to present constexpr to people that didn't know it, to encourage people that have heard of it to take a closer look at this new feature, and finally (at least for me) to see how far I can go with constexpr.

I invite you to share your thoughts about constexpr or this post, your questions or even your own experimentation in the comments!