The Art of Metaprogramming (2005)

The art of metaprogramming, Part 1

Introduction to metaprogramming

Write programs to generate other programs

Code-generating programs are sometimes called metaprograms ; writing such programs is called metaprogramming . Writing programs that write code has numerous applications.

This article explains why you might consider metaprogramming and looks at some of the components of this art -- we'll dive into textual macro languages, survey specialized code generators and discuss how to build them, and dissect language-sensitive macro programming with Scheme.

Many different uses for metaprogramming

First, you can write programs that will pre-generate tables of data for use at runtime. For example, if you are writing a game and want a quick lookup table for the sine of all 8-bit integers, you can either calculate each sine yourself and hand-code it, have your program build the table at startup at runtime, or write a program to build the custom code for the table before compile-time. While it may make sense to build the table at runtime for such a small set of numbers, other such tasks may cause program startup to be prohibitively slow. In such cases, writing a program to build static data tables is usually your best answer.

Second, if you have a large application where many of the functions include a lot of boilerplate code, you can create a mini-language that will do the boilerplate code for you and allow you to code only the important parts. Now, if you can, it's best to abstract out the boilerplate portions into a function. But often the boilerplate code isn't so pretty. Maybe there's a list of variables to be declared in every instance, maybe you need to register error handlers, or maybe there are several pieces of the boilerplate that have to have code inserted in certain circumstances. All of these make a simple function call impossible. In such cases, it is often a good idea to create a mini-language that allows you to work with your boilerplate code in an easier fashion. This mini-language will then be converted into your regular source code language before compiling.

Finally, a lot of programming languages make you write really verbose statements to do really simple things. Code-generating programs allow you to abbreviate such statements and save a lot of typing, which also prevents a lot of mistakes because there is less chance of mistyping.

As languages acquire more features, code-generating programs get less appealing. What is available as a standard feature of one language may be available only through a code-generating program in another language. However, inadequate language design is not the only reason for needing code-generating programs. Easier maintenance is also a reason.

Basic textual macro languages

Code-generating programs allow you to develop and use small, domain-specific languages that are easier to write and maintain than writing them in the target language.

The tools used to create these domain-specific languages are usually referred to as macro languages . This article reviews several kinds of macro languages and shows how you can use them to improve your code.

The C preprocessor (CPP)

First let's look at metaprogramming that involves textual macro languages. Textual macros are macros that directly affect the text of the programming language without knowing about or dealing with the meaning of the language. The two most widely used textual macro systems are the C preprocessor and the M4 macro processor.

If you've done C programming, you have probably dealt with the #define macro of C. Textual macro expansion, while not ideal, is an easy way to do basic metaprogramming in many languages that don't have better code-generation capabilities. Listing 1 is an example of a #define macro:

Listing 1. Simple macro to swap two values

#define SWAP(a, b, type) { type __tmp_c; c = b; b = a; a = c; }

This macro allows you to swap the two values of the given type. This is best written as a macro for several reasons:

• A function call would take way too much overhead for a simple operation.
• You would have to pass the variables' addresses to the function rather than the variables' values. (This isn't too bad, but passing addresses makes the function call messier and prevents the compiler from being able to keep the values in registers.)
• You would have to code a different function for each type of item you wanted to swap.

Listing 2 is an example of the macro being used:

Listing 2. Using the SWAP macro

#define SWAP(a, b, type) { type __tmp_c; c = b; b = a; a = c; }

int main()

{

    int a = 3;

    int b = 5;

    printf("a is %d and b is %d\n", a, b);

    SWAP(a, b, int);

    printf("a is now %d and b is now %d\n", a, b);



    return 0;

}

When the C preprocessor is run, it literally changes the text from SWAP(a, b, int) to { int __tmp_c; __tmp_c = b; b = a; a = __tmp_c; } .

Textual substitution is a useful, but fairly limited feature. This feature has these problems:

__tmp_c

The problem of combining macros with expressions makes macro writing fairly difficult. For example, let's say you had the following macro called MIN that returns the smaller of two values:

Listing 3. Macro to return the minimum of two values

#define MIN(x, y) ((x) > (y) ? (y) : (x))

First of all, you may be wondering why so many parentheses were used. The reason is operator precedence. For example, if you did MIN(27, b=32) , without those parentheses it would expand into 27 > b = 32 ? b = 32 : 27 , which will get a compiler error because 27 > b will bind closer together because of operator precedence. If you put the parentheses back in, it will work as expected.

Unfortunately, there's still a second problem. Any function called as a parameter will be called for every time it is listed on the right-hand side. Remember, the preprocessor knows nothing about the C language and is just doing text substitutions. Therefore, if you do MIN(do_long_calc(), do_long_calc2()) , it will expand into ( (do_long_calc()) > (do_long_calc2()) ? (do_long_calc2()) : (do_long_calc())) . This will take a long time because at least one of the calculations will be performed twice.

It's even worse if one of those calculations has side effects (like printing, modifying a global variable, etc.) because these side effects will be processed twice. This "multiple call" problem can even cause the macro to return the wrong value if one of the functions returns a different value each call.

More information about C preprocessor macro programming is available in the CPP manual (see thesection for a link).

The M4 macro processor

The M4 macro processor is one of the most advanced textual macro-processing systems. Its main claim to fame is as a helper tool for the popular sendmail mailer configuration file.

The sendmail configuration is neither fun nor pretty. Sendmail's configuration file has an entire book devoted to it. However, the makers of sendmail wrote a set of M4 macros to make the process easier. In the macros you simply specify certain parameters, and the M4 processor applies a boilerplate that is specific to both your local installation and sendmail in general. And it comes up with a configuration file for you.

For example, Listing 4 is the M4 macro version of a typical sendmail configuration file:

Listing 4. Sample sendmail configuration with M4 macros

divert(-1)

include(`/usr/share/sendmail-cf/m4/cf.m4')

VERSIONID(`linux setup for my Linux dist')dnl

OSTYPE(`linux')

define(`confDEF_USER_ID',``8:12'')dnl

undefine(`UUCP_RELAY')dnl

undefine(`BITNET_RELAY')dnl

define(`PROCMAIL_MAILER_PATH',`/usr/bin/procmail')dnl

define(`ALIAS_FILE', `/etc/aliases')dnl

define(`UUCP_MAILER_MAX', `2000000')dnl

define(`confUSERDB_SPEC', `/etc/mail/userdb.db')dnl

define(`confPRIVACY_FLAGS', `authwarnings,novrfy,noexpn,restrictqrun')dnl

define(`confAUTH_OPTIONS', `A')dnl

define(`confTO_IDENT', `0')dnl

FEATURE(`no_default_msa',`dnl')dnl

FEATURE(`smrsh',`/usr/sbin/smrsh')dnl

FEATURE(`mailertable',`hash -o /etc/mail/mailertable.db')dnl

FEATURE(`virtusertable',`hash -o /etc/mail/virtusertable.db')dnl

FEATURE(redirect)dnl

FEATURE(always_add_domain)dnl

FEATURE(use_cw_file)dnl

FEATURE(use_ct_file)dnl

FEATURE(local_procmail,`',`procmail -t -Y -a $h -d $u')dnl

FEATURE(`access_db',`hash -T<TMPF> -o /etc/mail/access.db')dnl

FEATURE(`blacklist_recipients')dnl

EXPOSED_USER(`root')dnl

DAEMON_OPTIONS(`Port=smtp,Addr=127.0.0.1, Name=MTA')

FEATURE(`accept_unresolvable_domains')dnl

MAILER(smtp)dnl

MAILER(procmail)dnl

Cwlocalhost.localdomain

You don't need to understand it, but just know that this small file, after being run through the M4 macro processor, generates over 1,000 lines of configuration.

Similarly, autoconf uses M4 to produce shell scripts based on simple macros. If you've ever installed a program where the first thing you did was type in ./configure , you probably used a program generated using autoconf macros. Listing 5 is a simple autoconf program that generates a configure program over 3,000 lines long:

Listing 5. Sample autoconf script using M4 macros

AC_INIT(hello.c)

AM_CONFIG_HEADER(config.h)

AM_INIT_AUTOMAKE(hello,0.1)

AC_PROG_CC

AC_PROG_INSTALL

AC_OUTPUT(Makefile)

When run through the macro processor, this will create a shell script that will do the standard configuration checks, look for the standard paths and compiler commands, and build a config.h and a Makefile for you from templates.

The details of the M4 macro processor are too complex to discuss here, but links to more information about the M4 macro processor and its use in sendmail and autoconf are in thesection.

Programs that write programs

Now let's turn our attention from generic textual-substitution programs to highly specialized code generators. We'll review the various programs available, look at sample usage, and build a code generator.

A survey of code generators

GNU/Linux systems come with several program-writing programs. The most popular are probably:

• Flex, a lexical analyzer generator
• Bison, a parser generator
• Gperf, a perfect hash-function generator

These tools all generate output for the C language. You may wonder why these are implemented as code generators instead of as functions. There are several reasons:

• The inputs to these functions are very complicated and not easily expressible in a form that is valid C code.
• These programs compute and generate many static lookup tables for operation, and therefore it is better to generate these tables once during pre-compile time than during every invocation of the program.
• Many aspects of the functioning of these systems are customizable with arbitrary code placed in specific positions. This code can then use variables and functions that are part of the generated structure built by the code generator without having to define and derive all of the variables manually.

Each of these tools is focused on building a particular type of program. Bison is used to generate parsers; Flex is used to generate lexical analyzers. Other tools are more focused on automating specific aspects of programming.

For example, integrating database-access methods into imperative languages is often a chore. For making this both easier and more standardized, Embedded SQL is a metaprogramming system used to easily combine database access with C.

While there are many libraries available that allow you to access databases in C, using a code generator such as Embedded SQL makes combining C and database access much easier by merging SQL entities into C as an extended part of the language. Many Embedded SQL implementations, however, are basically just specialized macro processors that generate regular C programs as output. Using the Embedded SQL though, makes the database access much more natural, intuitive, and error-free for the programmer than through the direct use of libraries. With Embedded SQL, the intricacies of database programming are masked by a sort of macro sub-language.

How a code generator is used

To see how a code generator works, let's look at a short Embedded SQL program. In order to do this, you need an Embedded SQL processor. PostgreSQL comes with an Embedded SQL compiler, ecpg . To run this program, you need to create a database in PostgreSQL called "test". Then issue the following commands in that database:

Listing 6. Database creation script for example program

create table people (id serial primary key, name varchar(50));

insert into people (name) values ('Tony');

insert into people (name) values ('Bob');

insert into people (name) values ('Mary');

Listing 7 is a simple program to read and print out the contents of the database, sorted by the name field:

Listing 7. Example Embedded SQL program

#include <stdio.h>

int main()

{

   /* Setup database connection -- replace postgres/password w/ the

      username/password on your system*/

   EXEC SQL CONNECT TO unix:postgresql://localhost/test USER postgres/password;



   /* These variables are going to be used for temporary storage w/ the database */

   EXEC SQL BEGIN DECLARE SECTION;

   int my_id;

   VARCHAR my_name[200];

   EXEC SQL END DECLARE SECTION;



   /* This is the statement we are going to execute */

   EXEC SQL DECLARE test_cursor CURSOR FOR

      SELECT id, name FROM people ORDER BY name;



   /* Run the statement */

   EXEC SQL OPEN test_cursor;



   EXEC SQL WHENEVER NOT FOUND GOTO close_test_cursor;

   while(1) /* our previous statement will handle exitting the loop */

   {

      /* Fetch the next value */

      EXEC SQL FETCH test_cursor INTO :my_id, :my_name;

      printf("Fetched ID is %d and fetched name is %s\n", my_id, my_name.arr);

   }



   /* Cleanup */

   close_test_cursor:

   EXEC SQL CLOSE test_cursor;

   EXEC SQL DISCONNECT;



   return 0;

}

If you've done database programming in C before with a regular database library, you can tell that this is a much more natural way to code. Normal C coding does not allow returning multiple return values of arbitrary type, but our EXEC SQL FETCH line does precisely that.

To compile and run the program, just put it into a file called test.pgc and run the following commands:

Listing 8. Building an Embedded SQL program

ecpg test.pgc

gcc test.c -lecpg -o test

./test

Building a code generator

Now that you've seen several types of code generators and the types of things that they can do, it is now time to write a small code generator. Probably the simplest useful code generator you could write would be one to build static lookup tables. Often, in order to build fast functions in C programming, you simply create a lookup table of all of the answers. This means that you either need to pre-compute them by hand (which is wasteful of your time) or build them at runtime (which is wasteful of the user's time).

In this example you will build a generator that will take a function or set of functions on an integer and build lookup tables for the answer.

To think of how to make such a program, let's start from the end and work backward. Let's say you want a lookup table that will return square roots of numbers between 5 and 20. A simple program can be written to generate such a table like this:

Listing 9. Generate and use a lookup table of square roots

/* our lookup table */

double square_roots[21];



/* function to load the table at runtime */

void init_square_roots()

{

   int i;

   for(i = 5; i < 21; i++)

   {

      square_roots[i] = sqrt((double)i);

   }

}



/* program that uses the table */

int main ()

{

   init_square_roots();

   printf("The square root of 5 is %f\n", square_roots[5]);

   return 0;

}

Now, to convert this to a statically initialized array, you would remove the first part of the program and replace it with something like this, calculated by hand:

Listing 10. Square root program with a static lookup table

double square_roots[] = {

   /* these are the ones we skipped */ 0.0, 0.0, 0.0, 0.0, 0.0

   2.236068, /* Square root of 5 */

   2.449490, /* Square root of 6 */

   2.645751, /* Square root of 7 */

   2.828427, /* Square root of 8 */

   3.0, /* Square root of 9 */

   ...

   4.472136 /* Square root of 20 */

};

What is needed is a program that will produce these values and print them out in a table like the previous one so they are loaded in at compile-time.

Let's analyze the different pieces we have working here:

• An array name
• An array type
• A start index
• An end index
• A default value for the skipped entries
• An expression to compute the final value

These are all very simple, well-defined pieces -- they can simply be spelled out as a simple list. So we will probably want our macro call to combine these elements in a colon-separated list and look something like this:

Listing 11. Our ideal method for generating a compile-time table of square roots

/* sqrt.in */

/* Our macro invocation to build us the table.  The format is: */

/* TABLE:array name:type:start index:end index:default:expression */

/* VAL is used as the placeholder for the current index in the expression */

TABLE:square_roots:double:5:20:0.0:sqrt(VAL)



int main()

{

   printf("The square root of 5 is %f\n", square_roots[5]);

   return 0;

}

Now we just need a program to convert our macro into standard C. For this simple example, Perl is used because it can evaluate user code in a string, and its syntax is largely C-like. This allows it to load and process user code dynamically.

Our code generator should process the macro declarations, but pass through all non-macro portions unchanged. Therefore, the basic organization of the macro processor should look like this:

1. Read in a line.
2. Should the line be processed?
3. If so, process the line and generate output.
4. If not, simply copy the line directly to the output unchanged.

Listing 12 is the Perl code to create our table generator:

Listing 12. Code generator for the table macro

#!/usr/bin/perl

#

#tablegen.pl

#



##Puts each program line into $line

while(my $line = <>)

{

   #Is this a macro invocation?

   if($line =~ m/TABLE:/)

   {

      #If so, split it apart into its component pieces

      my ($dummy, $table_name, $type, $start_idx, $end_idx, $default,

         $procedure) = split(m/:/, $line, 7);



      #The main difference between C and Perl for mathematical expressions is that

      #Perl prefixes its variables with a dollar sign, so we will add that here

      $procedure =~ s/VAL/\$VAL/g;



      #Print out the array declaration

      print "${type} ${table_name} [] = {\n";



      #Go through each array element

      foreach my $VAL (0 .. $end_idx)

      {

         #Only process an answer if we have reached our starting index

         if($VAL >= $start_idx)

         {

            #evaluate the procedure specified (this sets $@ if there are any errors)

            $result = eval $procedure;

            die("Error processing: $@") if $@;

         }

         else

         {

            #if we haven't reached the starting index, just use the default

            $result = $default;

         }



         #Print out the value

         print "\t${result}";



         #If there are more to be processed, add a comma after the value

         if($VAL != $end_idx)

         {

            print ",";

         }



         print "\n"

      }



      #Finish the declaration

      print "};\n";

   }

   else

   {

      #If this is not a macro invocation, just copy the line directly to the output

      print $line;

   }

}

To run this program, do this:

Listing 13. Running the code generator

./tablegen.pl < sqrt.in > sqrt.c

gcc sqrt.c -o sqrt

./a.out

So in just a few lines of code you created a simple code generator that can dramatically ease your programming tasks. With that single macro, you can take away a lot of work for any program that has to generate mathematical tables indexed by integer. A little extra work would also allow tables containing full struct definitions; a little more would ensure that space isn't wasted at the front of the array with useless empty entries.

Language-sensitive macro programming with Scheme

While code generators understand a little bit about the target language, they are usually not full parsers and cannot take the target language into account without rewriting a complete compiler.

However, this might be simplified if there was a language already represented with a simple data structure. In the Scheme programming language, the language itself is represented as a linked list and the Scheme programming language is built for list processing! This makes Scheme the ideal language (almost) for creating programs that are transformed -- no massive parsing is needed to parse the program, and Scheme itself is a list-processing language.

In fact, Scheme's abilities to do transformation go beyond that. The Scheme standard defines a macro language specifically built to make it easier to make additions to the language. And most Scheme implementations provide additional features to aid in building code-generating programs.

Let's re-examine the problems of our C macros. With the SWAP macro you first had to explicitly say what types of values you were swapping, and second, you had to use a name for the temporary variable that you were sure wasn't in use elsewhere. Let's examine what the equivalent looks like in Scheme and how Scheme solves these issues:

Listing 14. Value-swapping macro in Scheme

;;Define SWAP to be a macro

(define-syntax SWAP

   ;;We are using the syntax-rules method of macro-building

   (syntax-rules ()

      ;;Rule Group

      (

         ;;This is the pattern we are matching

         (SWAP a b)

         ;;This is what we want it to transform into

         (let (

               (c b))

            (set! b a)

            (set! a c)))))



(define first 2)

(define second 9)

(SWAP first second)

(display "first is: ")

(display first)

(newline)

(display "second is: ")

(display second)

(newline)

This is a syntax-rules macro. There are several macro systems for Scheme, but syntax-rules is the standard.

In a syntax-rules macro, define-syntax is the keyword used to define a macro transformation. After the define-syntax keyword comes the name of the macro being defined; after that comes the transformation.

syntax-rules is the type of transformation being applied. Within the parentheses are any other macro-specific symbols being used other than the macro name itself (there are none in this case).

After that comes a sequence of transforming rules. The syntax transformer will go through each rule and try to find a matching pattern. After it finds one, it runs the given transformation. In this case there is only one pattern: (SWAP a b) . a and b are pattern variables that are matched to units of code in the macro invocation and used to rearrange the parts during transformation.

From the first look, this may appear to have some of the same pitfalls of the C version; however, there are several differences. First, since this is the Scheme language, the types are bound to the values themselves, not the variable names, so there is no worry at all about the variable type problems that occurred in the C version. But doesn't this have the same problem of variable naming that the original one had? That is, if one of the variables were named c , wouldn't that cause a conflict?

Actually it wouldn't. Macros in Scheme using syntax-rules are hygienic . This means that all temporary variables used by a macro are automatically renamed before the substitution occurs in order to prevent them from having conflicting names. Therefore in this macro, c will be renamed to something else before substitutions if one of the substitution variables is named c . In fact, it will likely be renamed anyway. Listing 15 is a possible result of the macro transformation on the program:

Listing 15. Possible transformation of the value-swapping macro

(define first 2)

(define second 9)

(let

   (

      (__generated_symbol_1 second))

   (set! second first)

   (set! first __generated_symbol_1))

(display "first is: ")

(display first)

(newline)

(display "second is: ")

(display second)

(newline)

As you can see, Scheme's hygienic macros can bring you the benefits of other macro systems without many of their pitfalls.

Sometimes however, you want macros not to be hygienic. For example, you may want to introduce bindings in your macro that are accessible to the code you are transforming. Simply declaring a variable will not do because the syntax-rules system will simply rename the variable. Therefore, most schemes also include a non-hygienic macro system called syntax-case .

syntax-case macros are harder to write, but they are much more powerful because you have pretty much the entire Scheme runtime available to you for transformation. syntax-case macros are not really standard, but they are implemented on many Scheme systems. Those that do not have syntax-case usually have other, similar systems available.

Let's look at the basic form of a syntax-case macro. Let's define a macro called at-compile-time that will execute a given form during compilation.

Listing 16. Macro to generate a value or set of values at compile time

;;Define our macro

(define-syntax at-compile-time

   ;;x is the syntax object to be transformed

   (lambda (x)

      (syntax-case x ()

         (

            ;;Pattern just like a syntax-rules pattern

            (at-compile-time expression)



            ;;with-syntax allows us to build syntax objects

            ;;dynamically

            (with-syntax

               (

                  ;this is the syntax object we are building

                  (expression-value

                     ;after computing expression, transform it into a syntax object

                     (datum->syntax-object

                        ;syntax domain

                        (syntax at-compile-time)

                        ;quote the value so that its a literal value

                        (list 'quote

                        ;compute the value to transform

                           (eval

                              ;;convert the expression from the syntax representation

                              ;;to a list representation

                              (syntax-object->datum (syntax expression))

                              ;;environment to evaluate in

                              (interaction-environment)

                              )))))

               ;;Just return the generated value as the result

               (syntax expression-value))))))



(define a

   ;;converts to 5 at compile-time

   (at-compile-time (+ 2 3)))

This will perform the given operation at compile time. More specifically, it will perform the given operation at macro-expansion time, which is not always the same as compile time in Scheme systems. Any expression allowed at compile-time on your Scheme system will be available for use in this expression. Now let's see how it works.

With syntax-case , you actually are defining a transforming function, which is where the lambda comes in. The x is the expression being transformed. with-syntax defines additional syntax elements that can be used in the transforming expression. syntax takes the syntax elements and combines them back together, following the same rules as the transformer in syntax-rules . Let's look at what's happening one step at a time:

1. The at-compile-time expression is matched.
2. In the innermost part of the transformation, expression is converted to a list representation and is evaluated as normal scheme code.
3. The result is then combined with the symbol quote into a list so that Scheme will treat it as a literal value when it becomes code.
4. This data is converted into a syntax object.
5. This syntax object is given the name expression-value for expressing it in the output.
6. The transformer (syntax expression-value) says that expression-value is the entirety of the output from this macro.

With this ability to perform computations at compile time, an even better version of the TABLE macro can be made than we defined for the C language. Listing 17 shows how you would do it in Scheme with our at-compile-time macro:

Listing 17. Building the square root table in Scheme

(define sqrt-table

   (at-compile-time

      (list->vector

         (let build

            (

               (val 0))

            (if (> val 20)

               '()

               (cons (sqrt val) (build (+ val 1))))))))



(display (vector-ref sqrt-table 5))

(newline)

This can be made even easier to use by making a further macro for table-building that will be remarkably similar to our C language macro:

Listing 18. Macro to build lookup tables at compile time

(define-syntax build-compiled-table

   (syntax-rules ()

      (

         (build-compiled-table name start end default func)

         (define name

            (at-compile-time

               (list->vector

                  (let build

                     (

                        (val 0))

                     (if (> val end)

                        '()

                        (if (< val start)

                           (cons default (build (+ val 1)))

                           (cons (func val) (build (+ val 1))))))))))))



(build-compiled-table sqrt-table 5 20 0.0 sqrt)

(display (vector-ref sqrt-table 5))

(newline)

Now you have a function that allows you to easily build whatever kind of tables you wish.

Summary

Whew! We've covered a large amount of territory, so let's take a moment to review. First we discussed which problems were best solved with a code-generating program. These include the following:

• Programs that need to pre-generate data tables
• Programs that have a lot of boilerplate code that cannot be abstracted into functions
• Programs using techniques that are overly verbose in the language you are writing them in

We then looked at several metaprogramming systems and examples of their use. This included generic textual-substitution systems, as well as domain-specific program and function generators. We then examined a specific instance of table-building and went through the motions of writing a code-generating program to build static tables in C.

Finally, we looked at Scheme and saw how it is able to tackle the issues we faced in the C language using constructs that were part of the Scheme language itself. Scheme is built to be both a language and a code-generating language for itself. Because these techniques are built into the language itself, it is simpler to program and doesn't suffer from many of the same problems inherent in other techniques discussed. This allows you to simply and easily add domain-specific extensions to the Scheme language in the place that code generators have traditionally held.

Part 2 of this series examines in more detail how to program Scheme macros and how they can make your large-scale programming tasks significantly easier.

Downloadable resources

• PDF of this content