Computer, Programming, Review

Strawman functions in C++ Templates & Meta Programming.

I got a very unique opportunity to hear to Dr. Vijayan here in Bangalore. He was training us on Advanced C++ and the 1st session exceeded all my expectation. We discussed Templates for the whole day today. After listening to him for 8 hours straight, I can tell you that he was not done with Templates. I won’t be shocked if he picks up this topic again tomorrow.

To summarize briefly what I learnt today, we started the discussion with need for Templates in C++, Java and such statically typed languages in comparison with dynamic languages such as Python. Some of the points worth noting for me were,

( I will try to elaborate on these points later)

  1. sizeof is a compile time operation in C++. Hence, sizeof() ends up making C++ Templates very powerful.
  2. Specialization is preferred over generalization in templates. In particular, compiler preference goes with the extent of specialization.
  3. Objects, which are synonymous with variabled are runtime entities and types are compile time entities. Types include User defined types (Classes, C++ Structures), Plain Object Types such as C structures, Built-in types such as int, char etc.
  4. Unless a variable appears in the argument of a template function, it will not be “deduced” by default by the compiler.
  5. Default parameters are allowed only for Class Templates and not allowed for Function templates as of C++98.
  6. Only restriction for Template Member is that it cannot be a virtual Function. This is because there is no way that the compiler can deduce the number of translation units for a particular Template< T >. Number of translations of template T will be decided on runtime based on the types defined.
  7. Templates runs through the code only to the extent to which it is required.

While discussing a compile time implementation of one of the runtime operation, we discussed Meta Programming. In this, we needed to make a decision such as,

if ( 1 )

// do something

else

//do something else for value 0

during compile time. We cannot use if – else statements as they are runtime operations. In such a scenario, where we need to make a decision between two alternatives during compile time, we can use strawman functions with sizeof operator such that these strawman functions return different “return type” for different alternatives (May be, char for 0 and int for 1) and then, based on these “return types” we can use templates to run the code.

I know I am confusing you so stay with me. Consider a piece of code.

Code 1:

int i = 99;

sizeof(++i);   //sizeof will report the size to be 2 bytes or 4 bytes based on the implementation but what would the value of i be, after the execution of this line?

It will remain to be 99 as ++i will not be computed. Since, sizeof is a compile time operation and ++i is a runtime operation, ++i will not be evaluated except that “++i”s data type will be found out, which is ‘int’ in this case.

This means, we can write any function with any code in it and all sizeof cares about is the return type. You can officially write that poem you wanted to write in your C++ code without any ‘;‘ (semi-colon) or declaring it as a string. This function, when declared in sizeof( //here// ), will not be executed as the execution of a function will be a runtime operation.

Such a function whose code will not be executed but whose return type is used to determine the type (data type) during compile time is called a Strawman function.

Code 2:

Consider two overloaded functions,

  • template <> strawmanFunction <char>  ()  { returns char corresponding to 0 }
  • template <> strawmannFunction <int> ()  { returns int corresponding to 1}

We can now safely use, sizeof ( strawmannFunction ) to determine the values between 0 and 1, based on the specialization of int and char.

If this is still confusing apologies for poor narration. Lastly, Try implementing factorial code calculation suring compile time. Usual runtime code would be something like,

Code 3:

int factorial (n ) {

if (n == 1 ) return 1;

return n * factorial (n – 1) ;

}

When you implement the same logic with templates, you can have the factorial of the number during compile-time itself. It’s like having a constant which is pre-compiled before even you run your code!

Code 4:

template < typename T > T factorial ( T n ) { return n * factorial ( n – 1 ); }

Now, this code will instantiate translations for n – 1 for n. But this will not end with 1 and hence, it will result in Infinite Loop. So how do we implement if statement in Templates such that it runs in compile-time? (Remember, if-else is a runtime thing!) Look at the point number 2 above. Specialization is preferred over Generalization. Hence, if we can implement a Specialized case for 1 in the above Template definition, we are through. So, here it is.

Code 5:

template < typename T > T factorial<1> ( T n ) { return 1; } // This will be preferred over Code 4. The instantiation of different translations of Template T will end with this code.

Templates were fun. Although, I did realise today that the word easy is very relative. Whenever Mr.Vijayan said easy it took me 10 minutes to understand what’s going on.

Advertisements
Standard

3 thoughts on “Strawman functions in C++ Templates & Meta Programming.

  1. Yannick says:

    The metaprogram for factorial should rather looks something like this:

    template struct factorial
    {
    enum {value = N * factorial::value;}
    };

    template int struct factorial
    {
    enum {value = 1};
    };

    The example you give is a template version of factorial that will be instantiated at compile time but will produce result at run time. It can be instantiated for any type that implements the right operators. In practice it would return the expected result only for numeric types.
    You can’t use return values from functions since they are based on a runtime operation. You should rather use classes data members and enums (since they are r-values so no memory allocation is needed which garantees a pure “compilation time” process).

  2. Yannick says:

    Template square brackets got removed in my previous post…
    Not sure how to get them displayed right… I leave it to the webmaster to make the correction.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s