Some of my previous articles have already showcased advantages of using constexpr to shift runtime computations to compile time. In
we were able to precompute Fibonacci numbers, in
it was used to embed hash codes and in
we’ve learnt how to combine runtime and compile-time checks for optimal performance of most common use-cases.
All above techniques are useful in certain scenarios and are very easy to implement. So it’s not a surprise that they don’t use much of the constexpr’s power.
This article is going to take the next step and implement a tiny reverse polish notation calculator. But we’ll do this at compile-time, of course!
To simplify the code so that it fits well into the scope of the article, it will support only single digit numbers, plus and -. So the goal is, given a string "1 2 + 3 + 1 -", evaluate function should return 5.
Since language grammar is fairly trivial, our Token struct can look something like
We can also write a trivial fixed-capacity Stack implementation for convenience. Note, that in C++17 we are very limited in terms of the data structures that can be used in constexpr context. In practice, that means that we can use pretty much just std::string_view and std::array, so having our own constexpr-friendly Stack is handy.
Note, for the purpose of the article, this implementation intentionally violates some C++ rules and conventions to reduce the amount of code.
Ok, now we have everything in place to implement lexing logic
And the last piece of the puzzle is the evaluator that uses textbook stack-based solution for evaluation
The above code was written using TDD, which is super convenient using static_assert
Note, that Clang has difficulties with above code, but GCC is pretty happy with it and you can play with it in compiler explorer.
The above example is not meant to be used in production, but should hopefully give you some ideas for using DSLs to describe complex or performance-sensitive use-cases using declarative style. Imagine, sed(“s/foo/bar/”, input) function that builds a specialized automaton at compile-time to perform complex regex replacements in the most efficient way or validating emails, IP addresses and other common formats at compile-time.