Wasabi: Metaprogramming

February 24th, 2008 by Stefan Rusek

It has been a while since I last wrote about Wasabi. I had intended to write much more frequently, but then a little thing called FogBugz 6.1 happened. It contains a number of fixes for our Windows customers, and it also has PHP support.

Right now the Wasabi team is doing a lot of work. We’ve written a couple of experimental code targets, and have a very large portion of the language supported when compiling to .NET/Mono. There are still some major hurdles, but we are very excited about what is coming down the pipe! Once the work is finished we hope to be able to release Windows and Linux versions of FogBugz at the same time instead of in sequence. .NET and Mono both significantly outperform ASP and PHP, so we are excited at the prospect of FogBugz running faster.

Metaprogramming is writing code that generates or modifies code (typically within the same application). Often metaprogramming takes the form of adding a member to or modifying an existing member of a class. Memoization is an example of something that is often implemented using metaprogramming (when it is available). Memoization is a functional programming technique that is used when a function will always give the same result if you give it the same input. Generating Fibonacci numbers is a great example of where memoization is useful. Here is an example in JavaScript

function fib(x) {
    return x < 1 ? 1 : fib(x-1) + fib(x-2);
}

function memoize(f) {
   var dict = {};
   return function() {
      var result = dict[arguments[0]];
      if (typeof(result) == "undefined")
         dict[arguments[0]] = result = f(arguments[0]);
      return result;
   }
}

x = fib(5); // fib gets called 177 times
fib = memoize(fib);
x = fib(10); // fib gets called 19 times

Without memoization, fib is very inefficient, because each time you call it, it must call itself two more times. When memoization is added then the second time that fib calls itself, the answer has already been calculated. The result is that with careful use of a memoize metafunction, the programmer can dramatically improve execution time. Memoization is a simple example of metaprogramming, but it has many more applications.

Since the Wasabi compiler is written in C#, I spend a lot of my time in C# Land lately. This isn’t all bad, since I like the language and the CLR. However, I do find myself missing a number of features that Wasabi has that C# lacks. In particular, metaprogramming is absent in C#, and I keep getting annoyed every time I switch from Wasabi to C# because of it.

When I am programming in C# I have often found myself wrapping a set of methods on another class. For example, earlier this week for a personal project, I was writing a class that wrapped a System.IO.TextReader object and did some extra clean-up when the class was disposed. If I had metaprogramming in C# I could have written a function that added all the simple wrapper functions for me. In the TextReader case, it was only about 5 methods, but I often find myself needing to wrap a set of methods on another class with a little bit of code to do something extra. The result is that you end up having to write tons of duplicated code when it could be written more concisely with metaprogramming.

Like a few of Wasabi’s other cool features, metaprogramming depends on picture functions. (I find myself amazed at just how useful a concept picture functions has turned out to be. They just keep popping up over and over.) To do metaprogramming you simply make a picture function that generates code.

A really simple example is to add a member that prints message:

<ExecuteAtCompiler, Picture> Sub GenMessage()
<%
    Sub Message()
        Response.Write "Dzien dobry!"
    End Sub

%>
End Sub

<CodeGenerator("GenMessage")> Class A
End Class

So at compile time, the compiler sees that there is a codegenerator attached to A, so it asks the built-in Wasabi interpreter to take a picture of that function and parses the newly generated code. So after the codegenerator runs, the class is the same as if it were originally:

Class A
    Sub Message()
        Response.Write "Dzien dobry!"
    End Sub
End Class

So far it doesn’t look much more useful that C’s #define statement, so lets do something more interesting. A codegenerator can take up to two parameters. If the first one is given then it will be the AST node for type being modified. This allows the codegenerator to inspect the type and its members so that it can change what it does based on type it is modifying.

<ExecuteAtCompiler, Picture> Sub GenTypeName(oType)
    If Not oType.FindMember("TypeName") Is Nothing Then Exit Sub
<%
   Function TypeName()
        TypeName = "
<%=oType.RawName%>"
    End Function

%>
End Sub

<CodeGenerator("GenTypeName")> Class A
End Class

<CodeGenerator("GenTypeName")> Class B
    Function TypeName()
        TypeName = "BEE"
    End Function
End Class

This time our example does a little more. The codegenerator does nothing to class B. Class B already has a method called TypeName, and the first line of the codegenerator checks to see if the method it is going to generate already exists. Class A doesn’t contain the TypeName method so the codegenerator will add a method that returns the name of the class. The codegenerator has access to all of the AST so it can inspect anything about the program it wants.

As I said before, codegenerators can have two parameters. The second parameter is a string that can be passed in on a per class basis. This parameter allows for additional information to be passed that can do other cool things. The first thing that we wrote for FogBugz was a codegenerator called ActiveRecord. In FogBugz, we have a class called CSchema (along with CTable, CColumn, and CIndex). CSchema creates an array of CTable objects and fills them with schema information. This class is used by FogBugz to create and update the database during setup. ActiveRecord creates an instance of the CSchema object (the same exact one that FogBugz uses), and adds a bunch of database-related method and fields:

<ExecuteAtCompiler, Picture> Sub ActiveRecord(oType, sTable)
    Dim oSchema = New CSchema
    oSchema.LoadTables

   Dim oTable = oSchema.FindTable(sTable)

   If oType.FindMember("Load") Is Nothing Then
<%
    Function Load(ix)
        Load = False
        Dim cmd = GetCmd("SELECT * FROM
<%=sTable%> WHERE <%=oTable.PrimaryKey.Name%> = ?", "I")
        cmd.SetParam 1, ix
        Dim rs = cmd.Execute
        Load = InternalLoad(rs)
    End Function
%>
   End If
End Sub

<CodeGenerator("ActiveRecord", "Bug")> Class CBug
End Class

This little toy version of ActiveRecord should probably also generate a method called InternalLoad, but the general idea is above. If the class doesn’t have a Load method ActiveRecord will generate one that acts like the way you might expect Load to behave. ActiveRecord greatly simplified the amount of work we did on new entity classes for FogBugz 6. It also had the wonderful feature that bugs in ActiveRecord were much more likely to show themselves. When we did find a bug in ActiveRecord, we fixed it once and it fixed all the classes that used it!

Since codegenerators look like code inside code, they can be tricky to read at times, but this is easily overcome by syntax highlighting, which we’ve gotten working decently with both Vim and Visual Studio.

One more important note about Wasabi codegenerators: they run a compile time, while some other metaprogramming systems run at runtime. Runtime metaprogramming is nice because it can inspect the environment and change the way the program works, but most of the time it doesn’t need to, so you needlessly take a performance hit, and the metaprogram runs on every execution. In Wasabi since it runs at compile time, it gets executed only once. This means that if you were writing a library that generated prime numbers, you could have it pre-generate the first 10,000 primes for debug builds, and for release builds it could pre-generate the first 100,000,000 primes. So at build time we take a big hit in terms of compile time, but when consumers go to use the library, they get blazing fast prime numbers.

Codegenerators are by far my favorite feature of Wasabi, and I find that I miss them whenever I find myself using a language that lacks codegenerators.