/* Filename: rpn.cpp
Author: Adam Berger (adam@addaon.com)
Make: clang++ -std=c++11 rpn.cpp
Date: 13 June 2012 */
/*******************************************************************************
WHY THIS DOCUMENT EXISTS:
The purpose of this file is to demonstrate a handful of features new to C++11.
The main new feature that is explored is variadic templates. Along the way,
we'll take a look at decltype, template aliases, and deleted methods. Lambda
functions are discussed but are currently lacking compiler support.
The discussion assumes that the reader is familiar with C++03 templates, and in
particular non-type template parameters and template specialization. If you can
read the following (a standard template metaprogramming example), you're set:
template <int N>
struct Factorial { enum { value = N * Factorial<N - 1>::value }; };
template <>
struct Factorial<0> { enum { value = 1 }; };
This file will develop a miniature domain-specific language for expressing
compile-time constants. The author is NOT proposing that this is a good idea,
nor that this should be incorporated into your code; it is merely a strawman
upon which we can hang the use of a few new features.
C++11 is a new standard, and compiler support is limited. This code is tested
with clang++ 3.1. It does not work using g++ 4.2.1, and works with one caveat
(mentioned in the code) on g++ 4.8.0. Because it is tested on only a single
compiler, it is possible (perhaps likely) that there a non-standard-compliant
abuses of C++11 features here, that will not work on future, more compliant
compilers. If you recognize any such usage, please let me know.
THE PROJECT:
We would like to be able to express compile-time integer constants in reverse
polish notation (RPN), as used by Hewlett-Packard calculators, the Forth
programming language, and others. That is, instead of:
const int x = (3 + 2) * (5 + 7);
we would like to be able to write:
const int x = 3 2 + 5 7 + *;
We will choose not to focus on the minutiae of syntax. Rather than using tricks
with macros and operator overloading to approximate this syntax as closely as
possible, we will settle for a syntax that is a better fit to C++:
const int x = Rpn::Push<3>::Push<2>::Add::Push<5>::Push<7>::Add:Mult::value;
Hopefully the mapping from our chosen syntax to the ideal syntax is obvious.
How do we approach this problem? You will recall that RPN calculation is based
upon transformations of a stack of values. We will represent this stack as a
variadic non-type template. That is, the stack at any point in the calculation
is a C++ type which has, as template parameters, a list of integers. We will
keep the top of the stack as the leftmost (first) parameter.
Let's dive into code:
*******************************************************************************/
/* Hide away the implementation in a namespace, rather than pollute the
global namespace with implementation details. */
namespace rpn {
/* As discussed, we will represent the stack as a templated type. It is
templated by an arbitrary number of integers; so Stack<> represents the
empty stack, Stack<7> has only the number 7 on it, and Stack<3, 4, 5> has
a bunch of values, with 3 being on top. We're just forward-declaring the
template type here, implementation will follow. The ... in the template
parameter declares that parameter as variadic (that is, representing zero
or more such parameters). */
template <int... S>
struct Stack;
/* The operations that can be performed on a stack depend on the number of
values contained on the stack. Each operation requires a certain minimum
number of values. The template type Stack0<int...> defines those operations
that can be performed on a stack with AT LEAST zero elements (that is, any
stack). We will later ensure that all Stack<>s with at least zero elements
(that is, all of them) extend Stack0. */
template <int... S>
struct Stack0 {
/* Stacks are entirely compile-time entities, and can never be instantiated.
Here we use a deleted method to tell the compiler to not automatically
generate the default constructor for the Stack0 template type. Because
all other stack types will extend Stack0, this prevents any stack type
from being instantiated. Before deleted types, we would have declared
but not defined a private constructor to accomplish the same goal. */
Stack0() = delete;
/* Here's our first "operation". A stack with zero or more items on it can
have a new value pushed onto it. Because we are representing stacks as
types, the Push operation itself needs to define a type. Prior to C++11,
this would mean using a typedef; but Push needs to take a template
parameter, which typedefs do not support. Template aliases, which use
the new syntax seen here, are the answer. Generally,
typedef Type Name;
is equivalent to the new
using Name = Type;
with the exception that the latter can define templated types.
Notice that on the right side of the template alias, we're using ... in
a way we haven't seen before. S was defined in the template parameters
for Stack0 as a variadic parameter (that is, it represents a list of
parameters); this new type (sometimes called a "pack", in this case a
"pack" of ints) can not be used directly. The ... operator here acts
to "unpack" S. That is, the result of S... is each element of S, in
order, separated by argument-separating commas. So for Stack0<3, 4, 5>,
S... is equivalent to 3, 4, 5.
Make sure you understand why Stack0<3, 2>::Push<4> is the type
Stack<4, 3, 2>; we'll show that Stack<3, 2> is Stack0<3, 2> later. */
template <int N>
using Push = Stack<N, S...>;
/* It is reasonable to ask a stack of any size what its size is; we provide
a size operation here. We use the sizeof... operator; this is distinct
from the sizeof operator, and acts only on packs. (This is basically the
only case where an operator works on a pack directly, instead of
requiring an unpack; the C rule of thumb that "declaration reflects use"
applies here. The pack is declared with a ..., so uses of it will have a
single ..., whether that's the unpack operator itself or a part of the name
of the sizeof... operator.) */
static const int size = sizeof...(S);
/* We're going to define one more operation on a stack of any size. This
operation is the most complex that we'll discuss, though. I strongly
recommend skipping this discussion for now, and coming back to it after
reading the rest of this file. I'll remind you to come to it later.
Rather than just performing rpn operations on a stack and reading off
a value, we'd also like to allow the user to pass the arguments on the
stack to an existing function. The function to be called must take
arguments matching the entire stack; so if there are five values on the
stack, the function must take five integers. The top of stack will be
passed as the first argument to the function. The function to be called
can return any type.
How do we express this? We would like call to be a static member variable
that takes a function pointer as an argument. That allows us to write
Rpn::SomeOperations::call(function). (Consistent with the rest of this
file, we use Uppercase for operations that return a stack, and lowercase
for operations that terminate RPN mode and return a constant value.) What
is the type of the function pointer argument to call? The return type
must be a template type, which the compiler will deduce from the value
passed in. This allows the user to supply functions that return any type.
As a result, call() itself must be a template method. The argument types
of the function pointer are a bit trickier. If the stack is empty, we
want no arguments; if the stack is of size one, we want the function to
take a single int; if the stack is of size two, it must take two ints;
and so on. That is, we want sizeof...(S) ints as the argument.
To understand the chosen approach, we must dig a bit deeper into the
unpack operator. We mentioned that for S = <3, 4, 5>, S... unpacks to
the argument list 3, 4, 5. But ... can be applied to an arbitrary
expression containing a pack, not only to the pack itself. So if
S = <3, 4, 5>, f(S)... unpacks to f(3), f(4), f(5). This can be very
powerful. For our purposes, we'll combine it with the new C++11 decltype
operator. decltype(foo) is the type of foo, and can be used anywhere a
type can be used. So for S = <3, 4, 5>, decltype(S)... gives decltype<3>,
decltype<4>, decltype<5>; or equivalently, int, int int.
Now that we've managed to declare the argument to call(), actually
calling through that function pointer is straightforward. An unpack on
the stack does the trick directly.
Compatibility note: g++ 4.8.0 unpacks this differently than I would
expect. For Stack0<3, 4, 5>, f should have type T(*)(int, int, int);
but g++ 4.8.0 gives it type T(*)(int, ...). I believe, but am not sure,
that this is a g++ bug rather than a misunderstanding on my part. */
template <typename T>
static T call(T (*f) (decltype(S)...)) {
return f(S...);
}
};
/* Just like we defined a template type Stack0 to represent a stack with at
least zero elements, we'll define Stack1 to represent a stack with at least
one element. We'll name this element T, for top of stack; there's also a
variadic template argument representing the (zero or more) values beneath
the top of the stack. A stack with one or more argument is certainly a stack
with zero or more arguments, so Stack1 extends Stack0. Note the use of unpack
in specifying Stack0<T, S...>. */
template <int T, int... S>
struct Stack1 : Stack0<T, S...> {
/* The "Dup" operation duplicates the top item on the stack; that is,
Stack1<5, 0>::Dup is Stack<5, 5, 0>. (Again, the relationship between
Stack<5, 0> and Stack1<5, 0> is established later.) Because Dup does not
require templating, we can use a simple typedef. We could equally as well
have written
using Dup = Stack<T, T, S...>
in C++11 syntax. */
typedef Stack<T, T, S...> Dup;
/* Although we are representing stacks using types, at some point we need
to declare an actual integer value. We will thus provide a way to get
the top value of the stack as an integer. We could equally well write
enum { value = T };
to define value here, but I tend towards the explicitly typed method. */
static const int value = T;
};
/* By now you know the routine; a Stack2 has at least two arguments on it. It
extends Stack1, because a stack with at least two elements certainly has at
least one. (Stack1 already extends Stack0, so Stack2 doesn't need to do so
explicitly.) We'll name the top element of the stack T1 and the next element
down T2. */
template <int T1, int T2, int... S>
struct Stack2 : Stack1<T1, T2, S...> {
/* Two+ element stacks are where interesting operations start to happen.
For the sake of simplicity, we'll define just a handful. Swap just swaps
the top element of the stack and the next one down; so Stack2<3, 4>::Swap
is Stack<4, 3>. Swap preserves the number of values on the stack. */
typedef Stack<T2, T1, S...> Swap;
/* The other operations we'll define are the basic arithmetic operations,
which do what they say on the box. All act on the top two elements of
the stack, leaving one less element. Stack2<3, 4, 5>:Add is Stack<7, 5>.
Subtraction subtracts the second element from the top; division divides
the top element by the second. */
typedef Stack<T1 + T2, S...> Add;
typedef Stack<T1 - T2, S...> Sub;
typedef Stack<T1 * T2, S...> Mult;
typedef Stack<T1 / T2, S...> Div;
};
/* Now that we've defined variadic templated types for Stack0, Stack1, and
Stack2, we need to relate this back to the original Stack type. Operations
define types in terms of the original Stack type; but that Stack type must
itself extend the appropriate StackN type so that operations are visible.
That is, Stack<> must extend Stack0<>; Stack<3, 2> must extend Stack2<3, 2>
(and through that, extend Stack1<3, 2> and Stack0<3, 2>). Our tool for doing
this is template specialization. In the base case, a Stack is a Stack0,
regardless of arguments. */
template <int... S>
struct Stack : Stack0<S...> {};
/* We will specialize the definition of Stack. A Stack with at least one
template parameter will match the definition of Stack above; but it will
match this definition "more closely", so this definition will be preferred.
A stack which matches this definition extends Stack1, and operations on
one-element stacks are available. Note that the definition of Stack above
and this definition define completely separate template types; in our
particular case they're related by inheritance, but this is not required. */
template <int T, int... S>
struct Stack<T, S...> : Stack1<T, S...> {};
/* Finally, we will further specialize the definition of Stack to handle the
case of two or more values. Any Stack with two or more values will match
this definition "more closely" than either definition above, and therefore
will be a Stack2. */
template <int T1, int T2, int... S>
struct Stack<T1, T2, S...> : Stack2<T1, T2, S...> {};
} /* Close namespace rpn */
/* Our entire implementation was defined in the rpn namespace. We will define
a single symbol in the global namespace to allow us to gracefully access
or implementation. The symbol Rpn represents an empty stack, a clean slate
upon which operations can be performed. */
typedef rpn::Stack<> Rpn;
/************************ TEST CODE *******************************************/
/* I personally prefer printf to cout for testing purposes. */
#include <cstdio>
/* Shortcut to print an integer */
void print(int i) { printf("%i\n", i); }
/* We'll need a simple function for testing; printsum(3, 4) prints 7 */
void printsum(int a, int b) { print(a + b); }
/* One more simple one: square a number */
int square(int n) { return n * n; }
/* Here's our main function; just exercise Rpn a bit */
int main() {
/* Should print 6: 8 1 dup + swap - */
print(Rpn::Push<8>::Push<1>::Dup::Add::Swap::Sub::value);
/* Should print 7: demonstrate we can create big stacks, check size */
print(Rpn::Push<1>::Dup::Dup::Dup::Dup::Dup::Dup::size);
/* Should print 8: Rpn can be used anywhere a constant can be */
print(Rpn::Push< Rpn::Push<2>::Dup::Dup::Mult::Mult::value >::value);
/* The next couple tests use the call operation. If you skipped reading
about it earlier, go back and read it now. */
/* Should print 9: We can call a non-void function. */
print(Rpn::Push<3>::call(square));
/* Should print 10: We can call a void function */
Rpn::Push<10>::call(print);
/* Should print 11: We can call a two-arg function on a two-value stack */
Rpn::Push<3>::Push<4>::Dup::Add::call(printsum);
/* A C++11 lambda that captures no values can be implicitly cast to a
function pointer, so the following line should be valid and print 12.
Compiler support isn't quite there yet, however, and this line works
with g++ 4.8.0 but not clang++ 3.1. */
//Rpn::Push<12>::call([](int a) { print(a); });
return 0;
}
No comments:
Post a Comment