|« Alchemy: PackedBits (BitLists Mk3)||C++: auto »|
I was amazed after I had converted only the first few portions of the
TypeList from the C++98 implementation to Modern C++. I have decided to convert my Alchemy API to use Modern C++ in order to truly learn the nuances by application of acquired knowledge. The code of these meta-programs are very elegant and completely readable. This really does feel like a new language, and an entirely new version of meta-programming.
The elegance enabled by the new constructs will allow me to present a complete
TypeList implementation for Modern C++ in this entry.
I have corrected errors and uploaded a new implementation file.
Compare and Contrast
My primary goal is to compare the differences between template meta-programming with with C++98 and Modern C++ (C++11 and beyond). While the concepts remain similar, the newer language has been expanded in a way that makes this a more natural way to compose functional programming logic with C++.
To be clear, I want to explicitly state that meta-programming has its places, and generally it will not be in core-application logic. Libraries and utilities that will be developed and tested, but are less likely to require maintenance work are good candidates for these types of solutions. Application programmers can take advantage of these complex machinations, yet the caller may never even realize what magic exists behind the curtain. A great example would the the C++ Standard Library itself.
Frame of reference
Andrei Alexandrescu made the concept of meta-programming accessible to the masses in his book Modern C++ Design, published in 2001. He demonstrates and develops many useful components for meta-programming that he created as part of his library, Loki.
This is the style of meta-programming that I first learned, and the type of structure that, Alchemy, is built around. I have altered the implementation and interfaces for my meta-constructs to suit my needs, compared to what is presented in the book. The next few sections demonstrate how the same tasks are accomplished in both versions of the language.
The most important of these constructs is the
TypeList is a work-horse construct that can be in a variety of unique ways, yet does not contain any internal data or run-time code.
structs become the natural type to act as a functional container, which performs all of its compile-time, or static, operations on types, and stores values in
static const values or
To simplify expressions, I made liberal use of typedefs. This helped me avoid the repitition of verbose template expressions and at the same time give a label to the purpose of that template. Sometimes there are no ways to simplify expressions other than turning to the pre-processor. I prefer to avoid the pre-processor at all costs in my application logic. However, I have grown accustomed to leaning on the pre-processor to generate code for me for repetitive definitions that appear in a class or at the global scope.
Here is an example of how Alchemy's TypeList is constructed. Internally, a
TypeNode provides the declarations for the head and tail types.
Now the definition of the
TypeList to show the organization of the structure:
Composing a structure should be much simpler than this nested definition. Therefore, I decided to wrap the inner declaration with a simpler outer definition. Unfortunately, there are only a few facilities available to customize
template declarations. The best option in my particular situation was template specialization.
I wanted to provide a natural interaction with my TypeList object, and still allow support for a variable number of parameters. Thirty-two was my initial number of parameters that I would support. I can live with writing thirty-two specializations once. However, I had many operations that I would also implement, and each of those would require specialized implementations as well. So I resorted to the preprocessor to generate the code for me.
Here is the definition of the MACRO, and how it was used. It generates the code in the block from above:
Yes, I definitely left out many of the gory details for the definitions of the MACROs. But why would you want them? We're moving forward into the future; but you can still access them from Alchemy on GitHub.
The direct usage of the
TypeList was then much more accessible to the user. Also, there was no need for them to use any MACROs to define a new
There are two primary additions to Modern C++ that make
template programming in general a pleasure to use, and that is to not even mention meta-programming itself:
- Variadic templates:
- Template aliases:
Similar to variadic function parameters, this feature allows a variable number of arguments to be used in a template definition.
This allows the
using keyword to be used in situations similar to
typedef. However, unlike
using can be defined as a template. Therefore, it is compatible with partially-specialized templates.
Here are the definitions that I required when I ported my code to Modern C++ (don't worry, I will explain the syntax afterwards):
And an implementation for these types:
No, really! That's it! We get the exact same usage as the code from above, and I'm not even sure that I need to explain this last chunk of code.
I admit, I had a few false-starts trying to get a grasp on the parameter pack. No, not to reach this point, neither of the code samples above are good for anything except defining a list of types. My first challenge appeared when I tried to create a meta-function to give me the type of parameter at a specific index in the list.
Let me introduce the new constructs, then I will demonstrate some of the elegant solutions that barely scratch the surface of their capabilities.
The parameter pack...
The variable defined within a variadic template is called the parameter pack.
The parameter pack is essentially a list of types delimited by commas. To define one as a parameterized type in a template definition, use the ellipsis between the
class declaration and the name that you assign your type. There can be whitespace before and after the ellipsis if you desire...or not. However, the general style that you are likely to see places the ellipsis attached to the type-declaration and a space before the type-name.
You may have noticed in my
type_list implementation and the declaration of the template function that I placed the ellipsis after the declared name. This is how you invoke the parameter pack in your logic.
Invoke the parameter pack
What does it mean to invoke the parameter pack?
Nothing really. You're setting it where you want to apply it, and the compiler goes to work ripping apart the parameter pack and generating your code. However, the compiler does need a little bit of help. You will need two things if you are generating code from the parameter pack:
- Recursive definition:
- Terminating condition:
This is a definition that will be implicitly called by the compiler as many times as necessary until it reaches your terminating case. If you refer to the definition of the
type_list, you will see that the parameter pack is applied in a context where another type is placed before it, separated with a common. This essentially peels one or more types away from the parameter pack at a time. In this sense, the template parameter pack is similar to the variadic MACRO usage.[/codespan]
A condition that will handle the case of an empty list, or at least terminate the recursion before the compiler attempts to go beyond the end of the parameter pack. It is not necessary for this to be an entirely different definition.
Size of a parameter pack
sizeof... operator has been provided to match the syntax of the parameter pack. This version of the operator is not related in anyway to the classic
The parameter pack cannot be a variable
The parameter pack must be decomposed completely at compile-time. It cannot be the sole definition of a
typedef or a
However, that does not mean that we are helpless. There is an idiom that exists with template programming that allows us to extract the type from a template parameter. I am not sure if it has a name.
Let me demonstrate it for you. This is the definition you are most likely to find on the Internet for a
The previous code is completely legal because the parameter pack expansion is defined and terminated with this definition. With another template that is given the right specialization, we can extract the parameter pack from the original type definition.
To demonstrate this, let's create a
length meta-function that will report the number of elements in the type_list that I defined above. We need to declare a default version of the
length meta-function. This function does not necessarily need to be implemented.
We can use the parameter pack from the
type_list because we specialized this template solely for the this type. The compiler does a best fit comparison when attempting to resolve types, and finds this version.
Up until this point, we have had the
typedef, which has served us well. However, it does have its shortcomings. I believe the most notable is that partial template specialization is not supported by a
template alias does provide this support.
Here's a more complex example:
Improves readability of templates
There is one other feature of template aliases that I did not fully appreciate until I started to use them. Most code examples do not get complex enough to allow you to fully appreciate the second feature. Let me demonstrate, then I will get into the gory details.
This is an example of an additional declaration that was added to C++14, but is possible in C++11. I am not sure if this technique wasn't discovered until after C++11, or they left it out to keep it from becoming C++12.
These definitions appear in C++14, but you can use this technique in C++11.
typedefs are a common way to reduce clutter in code. Primarily with templates because the use of
template type declarations require you to qualify the type with
typename if you are using a dependent-type.
What is a dependent-type?
That is a very good question. To help with the explanation dependent type is a shortened version of the name template parameter dependent type. I'm surprised the C++ community hasn't just adopted TPDT, but I digress. A dependent type is a sub-type declared within a
typename is required when referencing sub-items in a
template. I say sub-items because other things can be defined within a struct, that are accessed in the same manner as a dependent type, like a
typename is a clue to the compiler that you want it to be interpreted as a type.
The capabilities of the template alias allow us to clearly specify beforehand that we mean a type. Therefore both the
typename qualifier and sub-type required to access the dependent name are managed by the alias. This greatly simplifies code when there are many template types to deal with. Template meta-programming is a prime example.
One Last Tip
In the fall of 2014, N4115 Parameter Pack Searching[^] was proposed with some additions to the utility library. This would add a common form of the idiom that I described above to gain access to a parameter pack. The name proposed for the type is
I was trying to modify an existing parameter pack, and I just couldn't put the pieces together. So that is when I searched and found N4115 when I found N4144 Searching and Manipulation of Parameter Packs[^], by Bill Seymour and Stephan T. Lavavej. This is an amended version of the first document and it adds manipulation utilities. One in particular is
I already demonstrated the concepts of
packer, however, in my code I refer to it as
param_pack. Here is how
add_to is implemented. Multiple specializations are declared to handle the possibility of adding a parameter pack to a parameter pack.
You will see a demonstration of the usage in the next section.
A Modern C++ TypeList
I searched the Internet, albeit briefly, and I did not find any Modern C++ implementations of a TypeList that did not expand beyond this definition:
I found the fundamentals to convert the code that I already have into modern form. I want to convert and get it integrated first. If there are better practices, I can adjust the implementation in a working test harness.
I have already shown the definition of the basic
type_list structure that I use as well as a demonstration of the
param_pack, and the implementation for
add_to. In the code below, I have omitted the forward declarations and template aliases that I define in the type list header file.
I am going to blast through the different operations that I have built so I do not take up too much more of your time. If something is not clear, please drop a comment and I can further explain or even add more detail to the description.
I have posted a link to the single header file that contains all of these definitions at the bottom.
I wanted to be able to make a
type_list from an existing set of internal
type_nodes, and then later, a
Query the type of element at a specified index in the
type_list. This item required a helper template that I called
Now for the actual implementation of
I added the declaration of
nodes to simplify the declaration for
type. This wasn't strictly necessary. I added
rest for convenience in other solutions.
rest returns a
type_list of the elements remaining after the specified index.
For example, if there were 10 elements in a type list and index 6 was specified. A type list with elements [7,8,9] would be returned.
Stop me if I go too fast for the rest of these.
New functionality updated since the original post
Move a specified number of elements from the front of the second list, to the end of the first list. This function is used to implement
split, which is then used to implement
Splits the list into two separate lists at the specified pivot index.
Again, I am pleased at how much simpler my code has become with these new additions. It's still C++. It's like C++ with the Hemi. Statements can be expressed more tersely, which actually increases the readability of the code as opposed to the lose meaning. Repetitive typing and redundant code can also be reduced.
If you frequently program with templates, or are even a big fan of the C++ Standard Library, you owe it to yourself to become familiar with these two features.
As promised, here is a link to the full type list implementation:
- Download type_list.h - 19.8 KB
- Update June 6, 2015 at 8:49 PM MST