Exactly when are templates expanded?

C++ templates are only expanded as necessary. The following is error-free even though does_not_exist() does indeed not exist. The method never_called() is never called and thus never expanded, and so does_not_exist() is never needed.

  template< typename X >
  struct
use_non_existant_stuff
  {
    int never_called( )  { does_not_exist( ); }
  };

// no errors or warnings here
use_non_existant_stuff< int > inst_that_does_not_use_methods;

But what about when a template method is expanded. When are the identifiers resolved? Consider the class uses_hidden_fn<..>.

  template< typename X >
  struct
uses_hidden_fn
  {
    X x;
    int call_hidden_fn( )  { return hidden_fn( x); }
  };

namespace hiding_ns {
int hidden_fn( double);
}

// This is OK.
uses_hidden_fn< double > inst_double;

// This fails because hidden_fn( double) is not visible.
int a = inst_double.call_hidden_fn( );

Invoking the method call_hidden_fn() fails because although hidden_fn(double) is defined, it is hidden in the hiding_ns namespace.

You can solve this problem with a simple using hiding_ns::hidden_fn; declaration. And hidden_fn(double) doesn’t have to be exposed before it is needed, only before the end of the compilation unit. The following compiles without error or warning.

  template< typename X >
  struct
uses_hidden_fn
  {
    X x;
    int call_hidden_fn( )  { return hidden_fn( x); }
  };

// This is OK.
uses_hidden_fn< double > inst_double;

// This is OK because hidden_fn( double) is declared below.
int a = inst_double.call_hidden_fn( );

// Declare hidden_fn(double) after we needed it above.
namespace hiding_ns {
int hidden_fn( double);
}
using hiding_ns::hidden_fn;

I’m testing this on the Microsoft (ms9) compiler, but I think it’s standard that templates are not expanded and identifiers are not bound until the end of the compilation unit.

This also compiles without complaint.

  template< typename X >
  struct
uses_hidden_fn
  {
    X x;
    int call_hidden_fn( )  { return hidden_fn( x); }
    int call_hidden_fn2( ) { return hidden_fn2( ); }
  };

namespace hiding_ns {
struct hidden_type { };
}

uses_hidden_fn< hiding_ns::hidden_type > inst;
int a = inst.call_hidden_fn( );
int b = inst.call_hidden_fn2( );

// Declare hidden_fn(..) after we needed it above.
namespace hiding_ns {
int hidden_fn( hidden_type &);
int hidden_fn2( );
}
using hiding_ns::hidden_fn2; // needed
//using hiding_ns::hidden_fn; // not needed!

I was surprised. I thought that we’d still need the using hiding_ns::hidden_fn; declaration at the bottom to make this work, but the (MS) compiler doesn’t complain. Apparently calling hidden_fn(..) with an argument whose type is in the hiding_ns namespace is enough of a hint for the compiler to dig hiding_ns::hidden_fn(hidden_type&) out of that namespace.

If you declare another hidden_fn(hiding_ns::hidden_type&) at top namespace scope the compiler complains that there are two hidden_fn(..)s to choose from. So it does not prefer the exposed declaration over the hidden one.

Although this sort of behavior is interesting, I would recommend strongly against relying on it. Even if it is standard (is it?), it feels like something on the edge. It is clearer to declare hiding_ns::hidden_fn(..) near the top of the file, followed by a using statement. That way hidden_fn(..) is exposed before uses_hidden_fn<..> is expanded.

Erlang as C++ code generator

In my last post I talked about how templates could be extended to manipulate and transform bits of the C++ syntax tree. Parsed C++ syntax objects, like block statements and parameter lists, are just the kind of thing you need when generating code.

But there are other ways to approach the problem. You can generate code as text, spitting out source code files to be compiled. Or you can generate code with the preprocessor.

With the preprocessor you don’t deal with syntax trees of course, since the preprocessor doesn’t know how to parse C++. It only knows how to tokenize the text stream, and so it deals with tokens. Tokens are syntax primitive, and aren’t as abstract as statements or expressions, but you can do a lot with just tokens. Sometimes you want to work on that level anyway, like when you want to generate a piece of code with unmatched curly brackets, maybe to open a namespace.

Of course the preprocessor is weak without recursion, looping, or data structures. But you can imagine a sophisticated language, embedded in C++ source like the preprocessor, that inserted generated C++ token streams. You’d want a language with recursion, data structures, and data types that could be manipulated and transformed.

The Erlang language gives us a hint of what this might look like. (We could also look to Prolog as a model, although it may be overkill, at least for what I have in mind.)

Erlang appears well suited to code generation. It’s declarative and functional like the C++ template language. Functional means a function’s return value depends only on its arguments and will always be the same if you pass in the same parameters. In other words, my_struct<43,char*> will evaluate to the same type as long as the arguments 43 and char* don’t change.

Erlang’s pattern matching and native list structure are good for simple parsing and list processing, which are also useful for code generation. Erlang-style pattern matching and guards are particularly useful if you’re working without strong typing.

Here’s what an Erlang-like preprocessing language might look like embedded in C++. Here we define a simple function, chop_off_head/1, which returns a list sans the first element. (The /1 part of the name means it take one argument.)

// Warning - this is all fantasy/speculative C++
// It will NOT compile.

// How would we embed a language like Erlang in
// C++ source code?

// 1. Surround the meta code in a special wrapper,
// like you do with asm { ... }
erlang {
  -module( cpp).
  -export( [chop_off_head_a/1]).
  chop_off_head_a( [] ) -> [];
  chop_off_head_a( [A | Rest] ) -> Rest.
}

// 2. Make it clear that we're defining parts of a module
// in the special wrapper, and we're not in "shell" mode.
erlang:module( cpp ) {
  -export( [chop_off_head_b/1]).
  chop_off_head_b( [] ) -> [];
  chop_off_head_b( [A | Rest] ) -> Rest.
}

// 3. Keep the Erlang code in a separate file. This way
// we can also load/test the Erlang code in a native
// environment. Allow a "-module(cpp)." line in the
// included file.
erlang:module( cpp ) {
# include "cpp.erl"
}

We have to distinguish module definitions from commands. Modules only define Erlang functions and do not generate any C++ code until the functions are called.

How do we feed C++ tokens to the Erlang functions, and how are the return tokens injected back into the compiled program? I’m thinking the code might look something like this.

// Warning - this is all fantasy/speculative C++
// It will NOT compile.

// What would a call to an embedded Erlang function
// look like?

  template< typename ... TYPEs >
  struct
mystruct_a
  {
    // We could set an erlang variable to build a list
    // and then pass that to the function. The last function
    // returns a list of cpp tokens to be taken up by the
    // compiler.
    erlang {
      X =
      -cpp_tokens_start
        TYPEs ...
      -cpp_tokens_end.
      cpp:generate_member_vars_a( X ).
    }
  };

  template< typename ... TYPEs >
  struct
mystruct_b
  {
    // Or we could unpack TYPEs into a comma-separated list.
    erlang:cpp:generate_member_vars_b( [ TYPEs ... ] ).
  };

In these examples I assume TYPEs… expands to a comma-separated list of types which will have to have some standard representation for the embedded Erlang, maybe as atoms or Erlang tuples.

In the mystruct_a example, X is set to a list of all the tokens of the expanded TYPEs… including the comma separators. Since a type can consist of many tokens (think int const * const &) the Erlang function will need the comma tokens. Unless we get the compiler to parse the tokens for us and set X to an Erlang list of type object.

I use -cpp_tokens_start and -cpp_tokens_end (which is NOT standard Erlang) to escape out of Erlang and tell the compiler to tokenize everything between as C++, and to bundle all those tokens up into a list and assign them to X. If we use delimiters like { and } (curly brackets) we’ll have a harder time specifying unmatched } in our escaped C++ token stream.

Maybe the C++ parser could compose the C++ tokens between -cpp_tokens_start and -cpp_tokens_end into more abstract objects, like s.

The last function in the wrapper, cpp:generate_member_vars_a(X), presumably returns a list of C++ tokens that the compiler takes and and treats as C++ code.

In mystruct_b I was thinking [TYPEs…] would expand into something like [int,float,char] which is an Erlang list. In this case the commas would not be tokenized since they are part of the Erlang syntax.

Finally, here’s what the Erlang code used above might look like.

-module( cpp).

% File contains functions to parse, manipulate,
% and generate C++ token streams.


% == exports ==========================

-export( [make_type/1]).
-export( [make_variable/2]).
-export( [make_numbered_name/2]).
-export( [parse_tokens_type_list/1]).
-export( [transform_types_to_variables/3]).
-export( [generate_tokens_for_variable_decl/1]).
-export( [generate_tokens_for_variable_decls/1]).
-export( [generate_member_vars/1]).


% == record declarations ====================

-record( type, {name}).
-record( variable, {name, type}).


% == make_type/1 =======================

make_type( Name ) ->
  #type{ name=Name }.


% == make_variable/2 =======================

make_variable( Name, Type = #type{} ) ->
  #variable{ name=Name, type=Type }.


% == make_numbered_name/2 =======================
%
% Generates a string from a prefix and a number:
%   make_numbered_name( "my_name_prefix_", 3245) ->
%   "my_name_prefix_3245"

make_numbered_name( Prefix, Counter ) ->
  list_to_atom(
    string:concat(
      Prefix,
      integer_to_list( Counter ))).


% == parse_tokens_type_list/1 =======================
%
% This only parses simple type lists, where each type is
% a single token. Works with type lists like this:
%   type1 , type2 , type3
% Does not work for a type consisting of more than one
% token, like this:
%   type1 * , type2 const & , int ( * ) ( int , char )

parse_tokens_type_list( [] ) ->
  [];
parse_tokens_type_list( [Arg | Rest] ) ->
  [ make_type( Arg)
  | lists:reverse(
      parse_tokens_type_list_tail( Rest, [] ))].

parse_tokens_type_list_tail( [], Collect ) ->
  Collect;
parse_tokens_type_list_tail( [',', Arg | Rest], Collect ) ->
  parse_tokens_type_list_tail(
    Rest,
    [ make_type( Arg) | Collect ]).


% == transform_types_to_variables/1 ======================
%
% From a list of types, generates variable declarations
% separated by semicolons. The variables will have generated
% names. The following:
%   transform_types_to_variables( [int, char], "var_", 34)
% yields a list of 6 tokens like this:
%   int var_34 ; char var_35 ;
%
% Can be used to generate class-member variables.

transform_types_to_variables( Types, Prefix, Counter ) ->
  lists:reverse(
    transform_types_to_variables_tail(
      Types, Prefix, Counter, [] )).

transform_types_to_variables_tail( [], _, _, Collect ) ->
  Collect;
transform_types_to_variables_tail(
    [Type = #type{} | Rest], Prefix, Counter, Collect ) ->
  transform_types_to_variables_tail(
    Rest,
    Prefix,
    Counter + 1,
    [ make_variable(
	    make_numbered_name( Prefix, Counter ),
        Type)
    | Collect
    ]).


% == generate_tokens_for_variable/1 ======================

generate_tokens_for_variable_decl( Var = #variable{} ) ->
  [ (Var#variable.type)#type.name,
    Var#variable.name,
    ';'
  ].


% == generate_tokens_for_variable_decls/1 ======================

generate_tokens_for_variable_decls( Vars ) ->
  lists:append(
    lists:reverse(
      generate_tokens_for_variable_decls_tail( Vars, [] ))).

generate_tokens_for_variable_decls_tail( [], Collect ) ->
  Collect ;
generate_tokens_for_variable_decls_tail(
    [Var = #variable{} | Rest], Collect ) ->
  generate_tokens_for_variable_decls_tail(
    Rest,
    [generate_tokens_for_variable_decl( Var ) | Collect]).


% == generate_member_vars/1 ======================
%
% Given a stream of tokens from a type list, generates
% a bunch of variable declarations.
%
% The following:
%   generate_member_vars( ['my_type_x', ',', 'my_type_y'])
% will generate the following C++ tokens:
%   my_type_x member_var_0 ;
%   my_type_y member_var_1 ;
%
% Another name for this could be:
%   transform_tokens_type_list_to_variable_decls

generate_member_vars( Tokens ) ->
  generate_tokens_for_variable_decls(
    transform_types_to_variables(
      parse_tokens_type_list( Tokens), "member_var_", 0)).

As you can see, expressing ideas in Erlang is a lot easier than expressing them as C++ template meta-functions, which is the reason I started thinking about using it for code generation. Erlang is a clean and easy-to-understand language that could work well at the token level or higher. But you can also see how the Erlang and C++ syntax clash, particularly when feeding C++ tokens to Erlang functions, although my proposal above could probably be improved.

I firmly believe that code-generating languages and development environments will become much more important in the future, and the C++ language is clearly moving in that direction. One tool that could help is a re-vamped C++ preprocessor, maybe based on a language like Erlang or Prolog. Or maybe it could even look like Javascript, which is imparative, and would be good at treating the code as a character stream. Or maybe C++ templates really are the best solution, especially if they could be extended to work with smaller fragments of parse tree.

It’s something to think about.

Templates and the C++ syntax tree

In my last few posts I’ve been writing about C++0x templates. Specifically I’ve been talking about how to make template classes easier to read by allowing more-imperative/less-declarative and more-iterative/less-recursive class definitions. I’ve talked about extending the packing operator and adding code-generating scripting to the compiler.

The C++ compiler already has “scripting” of sorts, in the form of the preprocessor. But this is very limited, a declarative language without recursion (or iteration), at least not without very clever hackery (see the Boost Preprocessor BOOST_PP_.. macros and my earlier post about using BOOST_PP_.. macros).

The usual way of generating C++ code is with templates, which are declarative and allow full recursion. Templates should be all you need, but they are surprisingly difficult to use. This is partly due to syntax, but mainly due to the fact that templates only deal with large syntactic sub-trees (class and function definitions). You cannot use a template if you just want to generate an expression or an argument list. Also templates only have integers and classes (structs) available as data structures (although MPL helps here a little), and that template selection (pattern matching) is primitive (you cannot easily match patterns buried inside structures or lists).

In a previous post I talk about how convenient it would be if we could use the packing operator to generate member variables for the tuple class.

/* fantasy code -- will not work */

  template< typename ... TYPEs >
  class
tuple
  {
      // Member variables - not a legal use of ...
      private:
      TYPEs ...
    values;

    /* .. etc .. */
  };

It’d be nice if you could write a meta-function using templates to generate the sequence of member-declarations necessary (the BNF non-terminal for the sequence is called member-specification).

/* fantasy code -- will not work */

  template< typename ... TYPEs >
  struct
generate_member_variables
  {
      // Generate member declarations like this:
      //   TYPE0 member_0 ;
      //   TYPE1 member_1 ;
      //   TYPE2 member_2 ;
      //    .. etc ..
      typedef
      std::grammar::
      generate_member_specification_from_types
       <  0
        , "member_"
        , std::grammar::list< TYPEs ... >
       >::eval
    eval;
  };

  template< typename ... TYPEs >
  class
tuple
  {
      private:
      // The compiler will change the following struct
      // into a sequence of member variables.
    generate_member_variables< TYPEs ... >::eval;

    /* .. etc .. */
  };

To make this work you’d need a library of meta-functions (templated structs) and classes to represent parts of the C++ syntax tree. The compiler would also have to recognize these snippets of syntax tree and compile them into the program like they were a normal part of the token stream. (You’d also need to be able to manipulate lists, tokens, literals, identifiers, and strings at compile-time.)

In the above example we assume a meta-function library that lives in namespace std::grammar and can build a struct that the compiler will recognize as a sequence of member variable declarations.

With these changes you could specify member variables something like this.

/* fantasy code -- will not work */

using std::grammar::member_specification;
using std::grammar::member_declarator;
using std::grammar::type_name;
using std::grammar::identifier;
using std::grammar::list;

  struct
my_struct
  {
    // example 1
    // generates these member vars:
    //   int m_id;
    //   double m_price;
    //   char* p_name;
    codegen typename
    member_specification
     <  list< int, double, char* >
      , list< "m_id", "m_price", "p_name" >
     >::eval;

    // example 2
    // generates these member vars:
    //   my_class1 member_var1;
    //   my_class2 member_var2;
    codegen typename
    member_specification
     < list
        <  member_declarator
            <  type_name< "my_class1" >
             , identifier< "member_var1" >
            >
         , member_declarator
            <  type_name< "my_class2" >
             , identifier< "member_var2" >
            >
        >
     >::eval;

    /* .. etc .. */
  };

This example introduces the keyword codegen which tells the compiler to expect a special type. A little like typedef, ‘cept not really. When the compiler sees codegen it knows treat the type as a C++ syntax tree and expand it into inline code.

The C++ compiler could be much more code-generation friendly. Defining meta-classes and meta-functions to represent and manipulate parsed C++ code is a good first step, along with adding a way to inline these syntax-tree objects into the code. Boost MPL provides a good of example of how those meta-objects can be defined.

This would let you build small parts of the syntax tree, like parameter lists, expressions, and initialization lists that you could reuse. These in turn would make it easier to generate larger class and function templates.

Next Page →