CSC/ECE 517 Spring 2013/ch1 1h jc

Metaprogramming in statically typed languages

Common Uses

Pre-generate static data at compile time

One common use of metaprogramming in statically typed languages is to write programs that will pre-generate tables of data for use at runtime.

One simple but useful code generator is to build static lookup tables. Often, in order to build fast functions in C programming, we simply create a lookup table of all of the answers. This means that we 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 following example we 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, we can start from the end and work backward. Firstly we need 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:

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:

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.

Code generator for the table macro

1. !/usr/bin/perl

1. tablegen.pl

1. 1. 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;
  }

}

Mini-language for boiler-plate

If you have a large application where many of the functions include a lot of boilerplate code, 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.