Title: Metaprogramming is Your Friend

Whenever I create a new C++ file using Emacs a simple elisp script executes. This script:

In short, the script automates some routine housekeeping for me.

Nothing extraordinary is going on here. One program (the elisp script) helps me write another program (the C++ program which needs the new file).

By contrast, C++ template-metaprogramming is extraordinary. It inspires cutting-edge C++ software; it fuels articles, newsgroup postings and books [Abrahams_and_Gurotovy]; and it may even influence the future direction of the language.

Despite (or maybe because of) this, this article has little more to say about template-metaprogramming. Instead we shall investigate some ordinary metaprograms. For example, the elisp script - a program to write a program - is a metaprogram. There may be other metaprograms out there which, perhaps, we don't notice. And there may be other metaprogramming techniques which, perhaps, we should be aware of.

I like the definition found in the [Wikipedia]:

Actually, it's the first half of this definition I like (everything up to and including "data"). The second seems rather to weaken the concept by being too specific, and in my opinion its presence reflects the current interest in C++ template-metaprogramming - but a Wikipedia is bound to relect what's in fashion!

Having established what metaprogramming is, the obvious follow-up is "Why?" Writing programs to manipulate ordinary data is challenging enough for most of us, so writing programs to manipulate programs must surely be either crazy or too clever by half.

Rather than attempt to provide a theoretical answer to "Why?" at this point, let's push the question on the stack and discuss some practical applications of metaprogramming.

I've already spoken about programming Emacs to create C++ files in a standard format. We can compare this technique to a couple of common alternatives:

The first option is tough on the fingers and few of us would fail to introduce a typo or two. The second is better but all too often is executed without due care - maybe because a programmer prefers to concentrate on what she wants to add rather than on what she ought to remove - and all too often leads to a new file which is already slightly broken: perhaps a comment remains which only applies to the original file, perhaps there's an incorrect date stamp.

The elisp solution is an improvement. It addresses the concerns described above and can be tailored to fit our needs most exactly. All decent editors have a macro language, so the technique is portable.

Of course, there is a downside. You have to be comfortable customising your editor. (Or you have to know someone who can do it for you.)

By "batch editing" I mean the process of creating a program to edit a collection of source files without user intervention. This is closely related to editor metaprogramming - indeed, I often execute simple batch edits without leaving my editor (though the editor itself may shell-out instructions to tools such as find and sed).

Very early on in my career (we're talking early 80's) I worked with a programmer who preferred to edit source files in batch mode. His desk did not have a computer terminal on it. Instead, he would study printouts, perhaps marking them up in pencil, perhaps using a rubber to undo these edits, before finally writing - by hand - an editor batch file to apply his changes. He then visited a computer terminal to enter and execute this batch file.

Even then, this was an old-fashioned way of working, yet he was clear about its advantages:

These days, builds are quicker and batch editing is more immediate. With a few regular expressions and a script one can alter every file in the system in less time than it takes to check your email. As an example, in another article [Guest1] I describe the development of a simple Python script to relocate source files into a new directory structure, taking care to adjust internal references to #included files.

The benefits of using a script to perform this sort of operation are a superset of those listed above. In addition, a scripted solution beats hand hacking since it is:

Again, there is a downside. You have to invest time in writing the script, which may well require a larger investment in learning a new language. Many of us would regard proficiency in other languages as an upside but it may be difficult to make that initial investment under the usual project pressures.

So, once again, it may end up being a team-mate who ends writes the script for you. Indeed, many software organisations have a dedicated "Tools Group" which specialises in writing and customising tools for internal use during the development of core products. Perhaps this team could equally well be named a "Metaprogramming Group"?

The compiler is the canonical example of a metaprogram: it translates a program written in one language (such as C) into an equivalent program written in another language (object code).

Of course, when we invoke a compiler we are not metaprogramming, we are simply using a metaprogram, but it is important to be aware of what's going on. We may prefer to program in higher-level languages but we should remember the compiler's role as our translator.

We lean on compilers: we rely on them to faithfully convert our source code into an executable; we expect different compilers to produce "the same" results on different platforms; and we want them to do all this while tracking language changes.

In some environments these considerations are taken very seriously. For safety critical software, a compiler will be tested systematically to confirm the object code produced from various test cases is correct. In such places, you cannot simply apply the latest patch or tweak optimisation flags. You may even prefer to work in C rather than C++ since C is a smaller language which translates more directly to object code.

In other environments we train ourselves to get along with our compilers. We accept limitations, report defects, find workarounds, upgrade and apply patches. Optimisation settings are fine-tuned. We prefer tried-and-tested and, above all, supported brands. We monitor newsgroups and share our experiences.

One last point before leaving compilers alone: C and C++ provide a hook which allows you to embed assembler code in a source file - that's what the asm keyword is for. I guess this too is metaprogramming in a rather back-to-front form. The asm keyword instructs the compiler to suspend its normal operation and include your handwritten assembler code directly. Its exact operation is implementation dependent, and, fortunately, rarely needed.

The program which follows is a short but non-trivial Python script. It makes use of a couple of text codecs from the Python standard library to generate a C++ function. This C++ function converts a single character from ISO 8859-9 encoding into UTF-8 encoded Unicode.

def warnGenerated():
  '''Return a standard 'generated code' warning.'''
  import sys, time
  return (
    '// GENERATED CODE. DO NOT EDIT!\n'
    '// generated by %s, %s' %
    (' '.join(sys.argv),
     time.asctime(time.localtime()))
    )
def functionHeader(codec):
  '''Return the decode function header.'''
  return '''/**
* @brief Convert from %(codec)s into UTF-8
* encoded Unicode
* @param %(codec)s An %(codec)s encoded character
* @param it Reference to an output iterator
* @note If the input character is invalid, the
* Unicode replacement character U+FFFD will be
* returned.
*/
template <typename output_iterator>
void
%(codec)s_to_utf8(
  unsigned char %(codec)s,
  output_iterator & it)''' % { 'codec' : codec }

def convertCh(ch, codec):
  '''Return the 'case' statement converting
  the input character using the supplied codec'''

  from unicodedata import name

  ucs = chr(ch).decode(codec, 'replace')
  utf = ucs.encode('utf-8')
  ucname = name(ucs, 'Control code')
  action = '; '.join(['*it++ = 0x%02x' % ord(c)
                      for c in utf])

  return '''case 0x%02x: // %s
  %s;
  break;''' % (ch, ucname, action)

def codeBlock(prefix, body, indent = ' ' * 4):
  '''Return an indented code block.
  This code block will be formatted:
  prefix
  {
    body
  }'''
  import re
  indent_re = re.compile('^', re.MULTILINE)
  return '''%s
{
%s
}''' % (prefix, indent_re.sub(indent, body))

codec = 'iso8859_9'
print warnGenerated()

print codeBlock(
  functionHeader(codec),
  codeBlock(
    'switch(%s)' % codec,
    # iso8859-* encodings are 8-bit
    '\n'.join([convertCh(ch, codec)
               for ch in range(0x100)]),
    indent = '' # don't indent case: labels
    )
  )

By now, it should go without saying that this script is a metaprogram. Before discussing why I think it's a good use of metaprogramming, some notes:

I like this script since it makes use of the standard Python library to create code we can use in a C++ program. The hard work goes on in the calls to encode() and decode() and we don't even have to look at the implementations of these functions, let alone maintain them. Their speed does not affect the speed of our C++ function and I am willing to trust their correctness, meaning I don't have to locate or purchase the ISO 8859 standards.

The second big win is that all the boilerplate code is generated without effort. If, at some point in the future, we need a fuller range of ISO 8859 text converters, then we tweak the script so the final section reads, for example:

codecs = ['iso8859_%d' for n in range(1, 10)]

print warnGenerated()

for codec in codecs:
  print codeBlock(
    functionHeader(codec)
    ....
    )

and let it run. And should we decide on a different strategy for handling invalid input data, again, the metaprogram is our friend.

As mentioned in passing, C++ has a sophisticated templating facility which (amongst other things) makes metaprogramming possible without needing to step outside the language.

C++ also inherits the C preprocessor: a rather unsophisticated facility, but one which is equally ready for use by metaprogrammers. In fact, careful use of this preprocessor can allow you to create generic C algorithms and simulate lambda functions.

For example:

#define ALL_ITEMS_IN_LIST(T, first, item, ...) \
do {                                     \
   T * item = first;                     \
   while (item != NULL) {                \
     __VA_ARGS__;                        \
     item = item->next;                  \
   }                                     \
} while(0)

#define ALL_FISH_IN_SEA(first_fish, ...) \
        ALL_ITEMS_IN_LIST(Fish, first_fish, \
                          fish, __VA_ARGS__)

The first macro, ALL_ITEMS_IN_LIST, iterates through items in a linked list and optionally performs some action on each of them. It requires that list nodes are connected by a next pointer called next. The second macro, ALL_FISH_IN_SEA, specialises the first: the node type is set to Fish * and the list node iterator is called fish instead of item.

Here's an example of how we might use it:

/**
 * @brief Find Nemos
 * @param fishes Linked list of fish
 * @returns The number of fish in the list called
 * Nemo
 */ 
int findNemo(Fish * fishes) {
  int count;
         
  ALL_FISH_IN_SEA(fishes,
     if(!strcmp(fish->name, "Nemo")) {
       printf("Found one!\n");
       ++count;
     }
  );
  return count;
}

Note how simple it is to plug a code snippet into our generic looping construct. I have used one of C99's variadic macros to do this (these are not yet part of standard C++, but some compilers may support them).

I hesitate to recommend using the preprocessor in this way for all the usual reasons [Sutter]. That said:

One final point: the inline keyword (intentionally) does not require the compiler to inline code. The preprocessor can do nothing but!

Take a look at the following Python function which on my machine lives in <PYTHONROOT>/Lib/pickle.py

def encode_long(x):
  r"""Encode a long to a two's complement
  little-endian binary string.
  Note that 0L is a special case, returning
  an empty string, to save a byte in the
  LONG1 pickling context.
  >>> encode_long(0L)
  ''
  >>> encode_long(255L)
  '\xff\x00'
  >>> encode_long(32767L)
  '\xff\x7f'
  >>> encode_long(-256L)
  '\x00\xff'
  >>> encode_long(-32768L)
  '\x00\x80'
  >>> encode_long(-128L)
  '\x80'
  >>> encode_long(127L)
  '\x7f'
  >>>
  """
  ....

The triple quoted string which follows the function declaration is the function's docstring (and the r which prefixes the string makes this a raw string, ensuring that the backslashes which follow are not used as escape characters). This particular docstring provides a concise description of what the function does, fleshed out with some examples of the function in action. These examples exercise special cases and boundary cases, rather like a unit test might.

Python's doctest module [Doctest] enables a user to test that these examples work correctly. Here's how to doctest pickle in an interactive Python session:

>>> import pickle
>>> import doctest
>>> doctest.testmod(pickle)
(0, 14)

The test result, (0, 14), indicates 14 tests have run with 0 failures. For more details try doctest.testmod(pickle, verbose=True). In case anyone is confused, 7 of the tests apply to encode_long - and unsurprisingly the other 7 apply to decode_long.

Incidentally, if pickle.py is executed (rather than imported as a library) it runs these tests directly.

The doctest module is a metaprogram - an example of Python being used to both read and execute Python. To see how it works I suggest taking a look at its implementation. The code runs to about 1500 lines of which the majority are documentation and many of the rest are to do with providing flexibility for more advanced use.

In essence, note that docstrings are not comments, they are formal object attributes. Now, Python allows you to list and categorise objects at runtime, so we can collect up the docstrings for classes, class methods and for the module itself. Once we have all these docstrings we can search them to find anything which looks like the output of an interactive session using Python's text parsing capabilities. The remaining twist is Python's ability to dynamically compile and execute source code using the compile and exec commands. So, we can replay the documentation examples, capturing and checking the output.

The doctest module provides no more than an introduction to metaprogramming in Python. Given a Python object it is possible to get at the object's class, which is itself an object which can be dynamically queried and even modified at run-time. This isn't the sort of trick which is often required: I haven't tried it myself so I'd better keep quiet and refer you to the experts. See for example [vanRossum] or [Raymond].

Sometimes the best way to solve a particular family of problems is to create a domain specific language, which may be implemented as an extension to a standard language For example (and once again, quite early in my career), I worked for an organisation - I'll call it Vector Products - which specialised in solid geometry software. Vector Products developed and actively maintained a proprietary extension to C - I'll call it C-cubed - which provided native support for various domain-specific primitives: vectors (the sort you find in 3D mathmematics, not std::vector), ranges, axis-aligned boxes; and for domain specific operators to work with these primitives.

I should stress that this C extension pre-dated standard C++. C++ classes and operator overloading can now handle much of what C-cubed provided. Nonetheless, Vector Products' investment paid off: C-cubed allowed programmers to write vector mathematics in a clean and legible way, thereby freeing them to concentrate on the real solid geometry problems they needed to solve.

I believe that the earliest incarnations of C++ were essentially domain-specific extensions to C. For early C++, the domain would be "Object Oriented Programming". [Stroustrup]

This again is metaprogramming, though (particularly with respect to the supplied examples) it is closely related to compilation.

Most of this article puts a positive spin on metaprogramming. I'm happy enough to leave you with this impression, but I should also mention some problems.

context.decodeOut()
  << context.indent()
  << field_name << " "
  << bitwidth
  << " = 0x" << value << "\n";

cpp_file
  << indent()
  << "context.decodeOut() << context.indent() << "
  << quote(field_name
        + " "
        + bitwidth 
        + " = 0x")
  << " << context.readFieldValue("
  << quote(field_name) + ", "
  << value 
  << ") << \"\\n\";\n";

This article has touched on metaprogramming in a few of its more common guises. I hope I have persuaded you that metaprogramming is both ubiquitous and useful, and that it shouldn't be left to a select few.

At one time, the aim of computer science seemed to be to come up with a language whose concepts were pitched at such a high level that software development would be simple. Simple enough that people could program machines as easily as they could, say, send a text message^[1]. Compilers would be intelligent and forgiving enough to translate wishes to machine code.

This aim is far from being realised. We do have higher-level languages but their grammars remain decidedly mechanical. Programs written in low-level languages still perform the bulk of processing. Perhaps a more realistic aim is for a framework where languages and programs are compatible, able to communicate with humans and amongst themselves, on a single device or across a network.

In such a framework, metaprogramming is your friend.

Thanks to Dan Tallis for reviewing an earlier draft of this article.