## Monday, September 10, 2012

### 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 232). 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,
{
return *s
? (*s == '+' || *s == '-'
? 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))
? 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!

## Monday, September 3, 2012

### Customizing Zsh (Part 1): Hooks and RPrompt

This post follows my post on the zsh macros, and explain how to use the zsh hooks "preexec", and how to customize your (right) prompt to give information about something that changes (current branch of git, date, …).

## 1 Preexec hook

To enable the hooks, the user first has to load the add-zsh-hook function. To achieve that goal, paste the following line:

```autoload -U add-zsh-hook
```

Once it is done, we are able to add and remove a function from a hook. For our case, we suppose we want to add the `hook_function` to the `preexec` hook. The following snippet shows how to do that.

```hook_function()
{
echo \$1
echo \$2
echo \$3
}

# add-zsh-hook -d preexec hook_function # Remove it for this hook.
```

Adding and removing a function from a hook is done the same way for every hooks.

The preexec hook is ran each time a command is read by the shell and is about to be executed.

Each function run by the preexec hook receives three arguments. The first one is the line as it was written. The second line is the line with alias expanded and truncated with a certain size limit. The third line is the full line with alias expanded. This thread shows an example. For the macros module, I decided to use the third expression because I want to be able to use my aliases in my macros. But that depends of the application you want to write.

## 2 Interactive prompt

You know that, there is plenty of ways to customize your prompts in Zsh. I'll just present one of them today, some post about the same topic might follow.

What I present today is how to use your `RPROMPT` to print some information about what you want, and is actualized every time you enter a new command. It is easy to do, here is the first step:

```setopt prompt_subst
```

Maybe you have recognized the beginning of what you have to add to your configuration file to make the zsh macros module working? Well done! Otherwise, it doesn't matter. So what does this little line? According to the man (man zshoptions): "If set, parameter expansion, command substitution and arithmetic expansion are performed in prompts".

Let's see what happens if we don't set this option:

```\$ msg="Hello"
\$ RPROMPT="(\$msg)"
\$                                       (Hello)
\$ msg="Goodbye"                         (Hello)
\$                                       (Hello)
\$ echo \$RPROMPT                         (Hello)
(Hello)
\$                                       (Hello)
```

Pretty annoying right? In fact, the shell expands `\$msg` before it is received by `RPROMPT`, so what happens is simple, it prints the value of what he receives: "Hello" literally. So, let's see what happens if we re-execute the same sequence of commands with the `prompt_subst` option set?

```\$ setopt prompt_subst
\$ msg="Hello"
\$ RPROMPT="(\$msg)"
\$                                       (Hello)
\$ msg="Goodbye"                         (Hello)
\$                                       (Hello)
\$ echo \$RPROMPT                         (Hello)
(Hello)
\$                                       (Hello)
```

Here is the most common error (I think) that leads your prompt not to expand your variables. The `RPROMPT` command doesn't know there is a variable to expand, and you have to prevent your shell to expand it by single-quoting your assignation. This way:

```\$ RPROMPT='(\$msg)'
\$ echo \$RPROMPT                         (Hello)
(\$msg)
\$ msg="Goodbye"                         (Hello)
\$                                       (Goodbye)
```

There is two things to be careful with when you want to have your prompt expanding some content: the option `prompt_subst` must be set, and the content of the variable `RPROMPT` contains the thing you want to be expanded each time (Think about single quoting it!).

Now let's see what we can do with it! If you are a module writer, you can use a variable as flag (as I did), or give a function that allows to get information about something (as it's done by zsh to allow user to get vcs information).

For getting your branch in your `RPROMPT`, I recommend you to read the answer of ko-dos which is very complete. If you just paste the code, it will work. But you know why it uses single quotes, and why there must be the prompt_subst option set. For the zstyle part, I didn't try to understand it. One day, I'll try :)

Let's see how get the time in your right prompt. First, how to get the time only when calling the `date` command? I read this post to find the right format. It is just `date +%T`. Now let's apply what we have learn:

```\$ RPROMPT='\$(date +%T)'
\$                                       (23:42:00)
```

Now you are just limited by your needs and by your imagination :) If you make your own custom prompt, please share it in comments. I hope you like it!