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);
            }
       }

With that single macro, we 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.

       /* 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

          #!/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:

Running the code generator

          ./tablegen.pl < sqrt.in > sqrt.c
          gcc sqrt.c -o sqrt
          ./a.out

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.