Are C++ Templates Just MACros in Disguise

Simulation of templates in C (for a queue data type)

You can use subtle and ugly tricks in order to create that kind of templates. Here's what I would do:

Creation of a templated list

Macro to define the list

I would first create a macro - let's call it say define_list(type) - that would create all the functions for a list of a given type. I would then create a global structure containing function pointers to all the list's functions and then have a pointer to that global structure in each instance of the list (note how similar it is to a virtual method table). This kind of thing:

#define define_list(type) \
\
    struct _list_##type; \
    \
    typedef struct \
    { \
        int (*is_empty)(const struct _list_##type*); \
        size_t (*size)(const struct _list_##type*); \
        const type (*front)(const struct _list_##type*); \
        void (*push_front)(struct _list_##type*, type); \
    } _list_functions_##type; \
    \
    typedef struct _list_elem_##type \
    { \
        type _data; \
        struct _list_elem_##type* _next; \
    } list_elem_##type; \
    \
    typedef struct _list_##type \
    { \
        size_t _size; \
        list_elem_##type* _first; \
        list_elem_##type* _last; \
        _list_functions_##type* _functions; \
    } List_##type; \
    \
    List_##type* new_list_##type(); \
    bool list_is_empty_##type(const List_##type* list); \
    size_t list_size_##type(const List_##type* list); \
    const type list_front_##type(const List_##type* list); \
    void list_push_front_##type(List_##type* list, type elem); \
    \
    bool list_is_empty_##type(const List_##type* list) \
    { \
        return list->_size == 0; \
    } \
    \
    size_t list_size_##type(const List_##type* list) \
    { \
        return list->_size; \
    } \
    \
    const type list_front_##type(const List_##type* list) \
    { \
        return list->_first->_data; \
    } \
    \
    void list_push_front_##type(List_##type* list, type elem) \
    { \
        ... \
    } \
    \
    _list_functions_##type _list_funcs_##type = { \
        &list_is_empty_##type, \
        &list_size_##type, \
        &list_front_##type, \
        &list_push_front_##type, \
    }; \
    \
    List_##type* new_list_##type() \
    { \
        List_##type* res = (List_##type*) malloc(sizeof(List_##type)); \
        res->_size = 0; \
        res->_first = NULL; \
        res->_functions = &_list_funcs_##type; \
        return res; \
    }

#define List(type) \
    List_##type

#define new_list(type) \
    new_list_##type()

Generic interface

Here are some macros that simply call the list's functions via the stored function pointers:

#define is_empty(collection) \
    collection->_functions->is_empty(collection)

#define size(collection) \
    collection->_functions->size(collection)

#define front(collection) \
    collection->_functions->front(collection)

#define push_front(collection, elem) \
    collection->_functions->push_front(collection, elem)

Note that if you use the same structure to design other collections than lists, you'll be able to use the last functions for any collections that stores the good pointers.

Example of use

And to conclude, a small example of how to use our new list template:

/* Define the data structures you need */
define_list(int)
define_list(float)

int main()
{
    List(int)* a = new_list(int);
    List(float)* b = new_list(float);

    push_front(a, 5);
    push_front(b, 5.2);
}

You can use that amount of tricks if you really want to have some kind of templates in C, but that's rather ugly (just use C++, it'll be simpler). The only overhead will be one more pointer per instance of data structure, and thus one more indirection whenever you call a function (no cast is done, you don't have to store void* pointers, yeah \o/). Hope you won't ever use that :p

Limitations

There are of course some limitations since we are using mere text replacement macros, and not real templates.

Define once

You can only define each type once per compile unit, otherwise, your program will fail to compile. This can be a major drawback for example if you write a library and some of your headers contain some define_ instructions.

Multi-word types

If you want to create a List whose template type is made of several words (signed char, unsigned long, const bar, struct foo...) or whose template type is a pointer (char*, void*...), you will have to typedef that type first.

define_list(int) /* OK */
define_list(char*) /* Error: pointer */
define_list(unsigned long) /* Error: several words */

typedef char* char_ptr;
typedef unsigned long ulong;
define_list(char_ptr) /* OK */
define_list(ulong) /* OK */

You will have to resort to the same trick if you want to create nested lists.

Similarities and differences between Scala macros and C++ templates

One important difference between them is that Scala macros are written in Scala, whereas C++ templates are their own programming language, which is completely unlike C++. C++ is an imperative object-oriented strict impure language, C++ templates are a declarative hybrid logic/functional non-strict pure language, which was never intended to be used as a full-fledged programming language, and thus lacks many of the features necessary for programming in the large.

Over reliance on macros

Yes, here's one. When you need to add tracing code to your program in such a way that one configuration contains it and the other completely omits you have to use macros.

Something like:

#ifdef WITH_LOGGING
    #define LOG( x ) DoLog( x )
#else
    #define LOG( x )
#endif

now you use it this way:

LOG( L"Calling blahblahblah with " + getSomeStringHardToCompute() );

and in the configuration with WITH_LOGGING you have that code and otherwise it is completely omitted - not even present in the binary, and therefore

it doesn't help others analyze your program
you get a smaller binary
the program doesn't waste time fo logging at all
the compiler can produce better optimized code.

Using C++ templates or macros for compile time function generation

The inline function will be parsed once, at the point in the translation unit where it is declared, and the state of the macros at that point will be used. Calling the function multiple times with the macros defined differently will not change the definition of the function.

You can do this with a template though --- if you pass the "current state" as a template parameter then you can use a different instantiation at each call point:

template<unsigned state>
inline my_t read_memory(uint32 addr) {
  if(state & OPTIMIZE_BITMAP)
    return readOptimized(addr);
  else
    return MEMORY[addr];
}

int main(){
    read_memory<STATE_A>(some_addr);
    read_memory<STATE_B>(some_addr);
    ....
}

The compiler will realise that state & OPTIMIZE_BITMAP is a constant and optimize out one or other branch of the if for each template instantiation.

typed vs untyped vs expr vs stmt in templates and macros

The goal of these different parameter types is to give you several increasing levels of precision in specifying what the compiler should accept as a parameter to the macro.

Let's imagine a hypothetical macro that can solve mathematical equations. It will be used like this:

solve(x + 10 = 25) # figures out that the correct value for x is 15

Here, the macro just cares about the structure of the supplied AST tree. It doesn't require that the same tree is a valid expression in the current scope (i.e. that x is defined and so on). The macro just takes advantage of the Nim parser that already can decode most of the mathematical equations to turn them into easier to handle AST trees. That's what untyped parameters are for. They don't get semantically checked and you get the raw AST.

On the next step in the precision ladder are the typed parameters. They allow us to write a generic kind of macro that will accept any expression, as long as it has a proper meaning in the current scope (i.e. its type can be determined). Besides catching errors earlier, this also has the advantage that we can now work with the type of the expression within the macro body (using the macros.getType proc).

We can get even more precise by requiring an expression of a specific type (either a concrete type or a type class/concept). The macro will now be able to participate in overload resolution like a regular proc. It's important to understand that the macro will still receive an AST tree, as it will accept both expressions that can be evaluated at compile-time and expressions that can only be evaluated at run-time.

Finally, we can require that the macro receives a value of specific type that is supplied at compile-time. The macro can work with this value to parametrise the code generation. This is realm of the static parameters. Within the body of the macro, they are no longer AST trees, but rather ordinary well typed values.

So far, we've only talked about expressions, but Nim's macros also accept and produce blocks and this is the second axis, which we can control. expr generally means a single expression, while stmt denotes a list of expressions (historically, its name comes from StatementList, which existed as a separate concept before expressions and statements were unified in Nim).

The distinction is most easily illustrated with the return types of templates. Consider the newException template from the system module:

template newException*(exceptn: typedesc, message: string): expr =
  ## creates an exception object of type ``exceptn`` and sets its ``msg`` field
  ## to `message`. Returns the new exception object.
  var
    e: ref exceptn
  new(e)
  e.msg = message
  e

Even thought it takes several steps to construct an exception, by specifying expr as the return type of the template, we tell the compiler that only that last expression will be considered as the return value of the template. The rest of the statements will be inlined, but cleverly hidden from the calling code.

As another example, let's define a special assignment operator that can emulate the semantics of C/C++, allowing assignments within if statements:

template `:=` (a: untyped, b: typed): bool =
  var a = b
  a != nil

if f := open("foo"):
  ...

Specifying a concrete type has the same semantics as using expr. If we had used the default stmt return type instead, the compiler wouldn't have allowed us to pass a "list of expressions", because the if statement obviously expects a single expression.

.immediate. is a legacy from a long-gone past, when templates and macros didn't participate in overload resolution. When we first made them aware of the type system, plenty of code needed the current untyped parameters, but it was too hard to refactor the compiler to introduce them from the start and instead we added the .immediate. pragma as a way to force the backward-compatible behaviour for the whole macro/template.

With typed/untyped, you have a more granular control over the individual parameters of the macro and the .immediate. pragma will be gradually phased out and deprecated.

power(C++ - {templates}) = power(C++)?

Theoretically, C++ without templates is still Turing-complete, so you can write a program for every function in that language that can also be written in C++ with templates. To my knowledge, the macro preprocessor in C++ is not Turing-complete, but templates are. So there must exist functions which can be implemented purely as templates, but not with macros.

Practically, I don't think it is possible to re-implement everything with the same semantics. Without templates, you probably will have to sacrifice type-safety and stick to using macros, void* or inheritance-based approaches like the early Java classes did even for simple container libraries.

For more advanced meta-programming libraries, e.g. expression templates, dimensional analysis frameworks, Boost.Spirit Boost.Proto, I doubt that they can be implemented without another form of meta-programming. Macros may work, but this will be more like a code-generator and defer type-checking to the compiler and error messages will be even worse than what we have right now with templates. In addition, the semantics are different w.r.t parameter passing.