Archive for the ‘Wasabi’ Category

Wasabi: Fragment Caching and Memoization

March 5th, 2008 by Ben Kamens

Stefan recently discussed some of the benefits of picture
functions and metaprogramming in Wasabi. One of the first (and arguably one of
the most useful) internal tools that these features spawned during FogBugz 6
development was the ability to easily memoize and cache function results.

Performance was one of our primary concerns when working
on FogBugz 6, so the ability to reuse previously calculated results within any single
request (memoization) or to store longer-lasting results in the database for
use in future requests (fragment caching) was badly needed. Those who are
familiar with other popular web frameworks are probably used to having these
caching tools readily available, although their implementations are sometimes
quite clunky. We were a little bit jealous, so we decided to chase after our
own implementation.  Unfortunately, in
classic ASP/VBScript there is no way to easily achieve this behavior without
massive code duplication and, as a result, an increasingly high likelihood of
cache-related errors.

Wasabi metaprogramming lets us solve the problem
gracefully. What we need is a way to tag a function as <Cacheable>, in which case every call to the function
will check the database for previously stored results and short-circuit if such
a result is found, avoiding the possibly expensive function execution (for the
rest of this article I will only discuss caching, which uses the FogBugz
database as its storage, although memoization is an almost equivalent piece of
functionality which uses per-request in-memory storage).

However, there are a number of complicating factors:

1. Different function inputs produce different outputs.
2. Cached results, or fragments, are usually
user-specific. I should never see the cached result of a function called by
Stefan or Joel.
3. Changes in the database state over time may invalidate
pieces of the fragment cache. 

Let's modify Stefan's flower picture function and make a
little utility function that generates the picture of a flower stem with a leaf
either on the left or the right. It also places the flower in a pot depending
on the state of the database: 

Picture> _

Sub MyStem( fLeft )
    If fLeft Then
         __ |
         \ \|
          \ |
            | __
            |/ /
            | /
    End If

    If HasFlowerPot()
        \       /
         \     /
    End If
End Sub 

Notice that we've added a <Cacheable> attribute to this function. This means that
anytime, say, Joel's user logs in
to FogBugz and generates a call to
MyStem requesting a leaf on the left, we check the database to see if the
result of this function with matching parameter values has already been stored
for Joel. If so, we give him back the stored value in presumably much shorter
time than letting the entire function run (you'll have to pretend for this
example that execution actually takes a significant amount of time), Joel
doesn't wait as long for the page to load, FogBugz is faster, and everyone's

What did we need to accomplish this?  We need to intercept calls to MyStem,
normalize all parameters, and check the database for any matching cached
results.  If we don't find any, we need
to run the original MyStem function, take a picture of its result, store the
result in our cache, and return the result. These pieces are easy with Wasabi,
and Stefan has already covered most of the necessary tools. I won't go into the
specifics here, but the intermediate code generated by Wasabi would look
something like:

Sub MyStem( fLeft )

    Dim sArgs =

sArgs) Then
Response.Write FragmentCache.Retrieve(“MyStem”, sArgs) 
        Dim sResult
= PictureOf OriginalMyStem(fLeft)
sArgs, sResult)
Response.Write sResult
End If

End Sub

A slightly more interesting piece of the fragment cache
is its database-oriented cache maintenance. The original <Cacheable> attribute sent an
additional argum
ent along to its code generator, “FlowerPots”. This string matches the name of a database table which
MyStem now depends on, and anytime the contents of table FlowerPots changes,
the cached results of MyStem are invalidated.

How does this work? Since Wasabi knows about all
Cacheable functions at compile time, we can build up a dictionary which
associates database table names with their dependent cached functions. Since
all SQL queries go through our own SQL command wrapper, any time a SQL command
is run from within FogBugz we can simply detect which tables are being changed
and invalidate all associated function results. 
This means that whenever I “DELETE
* FROM FlowerPots”, the cached results of MyStem are also deleted so no stale
potted flowers are incor
rectly drawn. Although it may seem that
detecting any and all updates to FlowerPots is too aggressive of a
cache-invalidation tactic, we do have all types of more specific tools which
let programmers choose whether or not to invalidate the cache during specific

As mentioned by Stefan, one of the nicest things about
letting Wasabi generate code at compile-time is that the user doesn't have to
wait for these associations to be created and for cache maintenance to be

Being able to simply add <Cacheable(“TableName”)> to any expensive
function and gain safe, database-dependent fragment caching has been an
enormous advantage, particularly when generating large chunks of HTML. There is
no way FogBugz 6 would perform anywhere near its current
speed if we weren't
able to make use of easy tricks like <Cacheable> and <Memoizable>.

In the future, when we have nice
serialization/deserialization worked out for all of our objects, we'll also be
able to cache objects (which we can already memoize since in this case they're
simply stored in memory).

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 = "
    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

   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.

Wasabi: Client-side Code

November 13th, 2007 by Stefan Rusek

Because the first versions of Wasabi had to be mostly compatible with ASP, Wasabi retains some (though thankfully not all) of the problems that exist in PHP or ASP. Yet one of the beauties of having our own in-house compiler is that we can fix those problems, piece-by-piece, or, at any point, write a one-shot compiler back-end for the language of our choosing. (Another really cool option is to have Wasabi v2 generate Wasabi v3 syntax, so we could dramatically alter the syntax, if we wanted.)

For the moment, rather than using Wasabi as a one-shot way to move away from VBScript, we’ve instead opted to improve the compiler by adding features to make writing code more pleasant. We can’t make every change we’d like to make, since certain constructs cannot be translated easily into ASP or PHP, but we can still make some surprisingly large modifications. We added a type inferencer, which has greatly reduced the amount of wasted development time. But one of the features that has given us the most extra power has been adding client-side code generation.

Last week I talked about how we came up with picture functions so that we could solve an HTML generation problem. Picture functions were created to serve another purpose as well: they are a core part of what makes the ability to generate client-side code useful.

In FogBugz 5, the case view page took a long than we would have liked to render and send to the client, even though it didn’t really look as if it should. The reason was that we sent down a table with sections for viewing, editing, resolving, and assigning cases. If the case was an email it had replying and forwarding sections. This meant that we sent down a lot of data that we didn’t actually use most of the time, but if you clicked the edit button, the UI changed instantly without having to go back to the server. For FogBugz 6, we wanted to keep the quick response time for the case editing page, but cut down on the data that we had to send down.

One solution would be to write the UI on the server (for users who don’t have JS) and rewrite the UI in JS (for quick response times). But then we would have had two implementations of the same UI, and we would have had to fix bugs in two places and maintenance would be awful. Needless to say, that is not a path I encourage anyone to go down.

Back-ends for Wasabi are pretty easy to write, and you can add a new target language in a relatively short period of time, though it would admittedly take a bit longer for the needed runtime to be implemented in the target language. (In fact, I wrote an experimental Python generator in about five hours not long ago.)

Since we had Wasabi, we chose to add a JS back-end and the ability for the compiler to distinguish between code intended for the server, code intended for the client, and code intended for both. Once that was in place, the compiler just needed the Wasabi runtime library implemented in JS.

If a function or class is marked ExecuteAnywhere, then it will be generated in both the server language (ASP or PHP) and in the client language (JS). ExecuteOnClient means that the function or class should be generated on the client. The default is to generate only in the server language. Since client and server code use separate namespaces, two functions could have the same name and signature, but one be generated for the server and the other for the client. Here is an example:

<Picture, ExecuteAnywhere> Sub GenerateTable
    Dim rs = GetTableData
    Do Until rs.EOF
End Sub

Function GetTableData
    Dim cmd = GetCmd("SELECT * FROM Person WHERE fDeleted = 0")
    GetTableData = cmd.Execute
End Function

<ExecuteOnClient> Function GetTableData
    GetTableData = New RecordSet(DB.Person.Select( _
        Lambda(p) Not p.fDeleted))
End Function

So in the code above, the GenerateTable() function gets generated for both the server and the client, and when we need to actually get data, we have a server-side version that grabs the data directly from the database and a client-side version that grabs it from a local cache. We don’t completely avoid having two pieces of code that do the same thing, but we greatly reduce duplication, and the two versions of the same code can be right next to each other so that a change to one doesn’t involve hunting down the other version (that you may not even know exists).

To generate the table, we can call GenerateTable() directly, the table gets sent to the HTTP response, and the client can simply take a picture of it. Here is what might be generated for the client:

var gHtml = "";
function pictureOf(fxn) {
   var oldHtml = gHtml;
   gHtml = "";
   var result = gHtml;
   gHtml = oldHtml;
   return result;

function GenerateTable() {
   gHtml += "<table>";
   var rs = GetTableData();
   while (!rs.EOF) {
     gHtml += "<tr><td>" + rs["sName"] + "</td></tr>";
   gHtml += "</table>";

function GetTableData() {
   return new RecordSet(DB.Person.Select(
     function(p) { return !p.fDeleted; }));

Then to put the generated HTML to use we have another ExecuteOnClient function and an onclick event:

<a href="default.asp?generateTableOnServer"
     onclick="ShowTable(); return false;">Show Table</a>

<ExecuteOnClient> Sub ShowTable
   Dim oPlaceHolder = document.getElementById("idTablePlaceholder")
   oPlaceHolder.innerHTML = PictureOf GenerateTable
End Sub

Given the above code, the table appears almost instantly for users with JS enabled and still offers a reasonable fallback for non-JS browsers (such as most mobile phones).

So in FogBugz 6, if you click on a case, you get the HTML to view the case and a small JS object that can be used to generate all the other case editing pages. Client-side code generation is extremely easy to use and greatly reduces the amount of extra code that has to be written for web development.

Wasabi: How Do I Picture Functions

November 6th, 2007 by Stefan Rusek

Coming up with a clean way to generate HTML was one of the first features that we needed to spec out. Any sufficiently large web application has a complicated database query whose information needs to be printed out in different, possibly disconnected parts of the page. For example, say you wanted to print summary information for a complex, database-backed table before the table itself. You could add a COUNT(*) (or some aggregate functions) to get the summary information, then reissue the query to get the data, but then you have to execute your complex query twice. So what you want to do is generate the table and gather the data you need first, then generate the summary information.

(I should add a little information about ASP. ASP is a stream-centric architecture. This is in contrast to ASP.NET, where you construct a tree of HtmlControls that represent the HTML and then serialize the tree into html. The stream-centric model uses fewer resources, but it is less flexible regarding the order that actions can be performed.)

I was considering using one of two models to solve this problem. The first was an ASP.NET-like model where we would have a bunch of objects representing HTML nodes. Once they were ready, we would convert them to actual HTML text. The other model was more like a lot of JS frameworks, and used a lot of functions along with arrays and dictionaries to generate HTML. Each of these had the advantage of solving the data generation ordering problem, but neither of these really felt satisfactory. So I got some of the developers to together to discuss the issue. Joel asked why we didn't just use picture functions. None of us knew what he was talking about, so he explained them to us. It turns out that a picture function is just a function that uses ASP's built-in content generation mechanism to generate a "picture" of the content, but does nothing else. So the following is a picture function:

Sub MyFlower
     _   _
    / \ / \
   |\_ | _/|
  (  _'#`_  )
   |/  |  \|
       | __
       |/ /
       | /
End Sub

This didn't immediately solve the problem, but it did give us something to think about. The biggest problem with this method is that we didn't have any way to normalize the data, so HTML validation would be close to impossible. The advantage was that we already had a bunch of code in FogBugz that fit this pattern.

Another nagging concern was that I didn't really have much respect for the ASP method of embedding HTML in code. As I thought about it some more, I began to realize that not all uses of embedding HTML were bad. The above function is probably the cleanest way to generate a PRE tag with a flower in it that I can think of. The problem with ASP's method of generating HTML is not that technique itself, but that it has been so misused in the past. Like many programming features over the past half century, it has been abused to create a horrible mess, but, done properly, it makes extremely clean code possible. (In fact the latest version of VB.NET has ASP-like mechanisms built-in for XML data generation, and Lisp has always been able to mix data and code together.)

Next we needed a way to use picture functions to solve the problem I already mentioned. The first feature that Wasabi got that VBS doesn't have is the ability to attach metadata to Classes and Functions. So we added a Picture metadata attribute, and a new language keyword PictureOf. So the problem is solved by the following code:

<Picture> Sub TableBody( rs, ByRef count, ByRef total)
End Sub

Dim rs = GetData()
Dim count, total
Dim sTable = PictureOf TableBody(rs, count, total)
%><div>The average is <%=total/count%></div><%
Response.Write sTable

Under the covers, we have a global object called OurResponse that wraps the Response object and has a stack of StringBuilder objects. To take a picture of a function the compiler generates a call to OurResponse.Push(), which creates a new StringBuilder on the stack. To retrieve the picture, the compiler calls OurResponse.Pop(), which converts the StringBuilder to a string and removes it from the stack. This allows a picture function to take the picture of another function if it needs to. So the PictureOf line above gets generated as:

Dim sTable
TableBody rs, count, total
sTable = OurResponse.Pop()

And all calls to Response.Write are replaced with OurResponse.Write. In ASP we only do the replacement for lambdas, picture functions, and functions called by picture functions. (You must do this for lambdas because you never know if they will be called in a picture context.)

The ability to take pictures of functions has turned out to be a very valuable feature that makes a lot of code easier and cleaner to write. The really cool thing about picture functions is that, after they were spec'ed out, they started turning up in other specs and have become instrumental in a number of Wasabi features: client-side code generation, meta programming, memoization, caching, and of course contributing to making Wasabi just that much more awesome.

The Origin of Wasabi

October 31st, 2007 by Stefan Rusek

As the primary developer and maintainer of Wasabi, I've wanted to write a series of articles on Wasabi for awhile, and last week, I decided to talk to Joel about it. Today, I will start off with a short history of the language, and later, I will talk about some of its cooler features and where we want to take it in the future.

Several years ago Joel and Michael decided that they wanted to have a Unix version of FogBugz. At the time, FogBugz was your typical ASP application. Since throwing away a large code base and starting from scratch is typically a bad idea, the final decision was to have an intern write a compiler to translate a subset of ASP into PHP. Thus, Thistle was born. Thistle had a tokenizer, a simple parser, and a finite state machine based PHP generator. Along with Thistle some work was done to normalize certain parts of the code base to fit the subset of ASP that was allowed. This meant, among other things, replacing all the calls to CreateObject() with Server.CreateObject(), so that those calls could be intercepted and the PHP versions of corresponding objects could be created.

For concepts that just could not be normalized, there was special syntax to embed PHP code directly in the ASP. Thistle has four special comment markers:

  • '#A – This told Thistle that it was entering an ASP only block
  • '#P – This told Thistle that it was entering a PHP only block
  • '#E – This told Thistle that it was exiting an ASP or PHP block
  • '~! – This told thistle that the rest of the line was PHP code

So the following lines would write which language was being used the HTTP response:

Response.Write "This is written in "
Response.Write "ASP"
'~! print("PHP);

It isn't pretty, but the code works properly in ASP unmodified and generates the following PHP:

print("This is written in ");

So with much less effort than rewriting FogBugz, we had both Windows and Unix versions of FogBugz, and Thistle continued to get small updates over the next couple years.

I started at Fog Creek in December of 2005, and my first project was an in-house testing suite. One of the goals of the testing tool was that it be able to give code coverage reports for each test. For this I added the ability to generate ASP to Thistle. The idea of compiling ASP to ASP seems silly, but it was very easy to insert code coverage logging information into the generated code. Once I had code coverage information, I was able to quickly find the areas of FogBugz that were not being tested.

Everyday at Fog Creek we gather around the lunch table and have a great time together. Certain topics and themes come around pretty often. (Such as having a Zoolander themed Halloween party.) One topic in particular kept coming up throughout my first four or five months. No single programming language exists that does all the things that typically require four. You need a server language (In FB5 this was ASP and PHP), a client language (probably JS), a content language (HTML), and a formatting language (CSS).

These conversations and other conversations about features of modern dynamic languages like Python led to the idea of using Thistle to make a new language that overcame many of the issues with writing ASP. There are a lot of problems with ASP, and since Microsoft is no longer making new versions of ASP and doesn't even install it by default anymore, those problems are not going away.

We wanted to make it so that as many programmer errors as possible were found at compile time instead of runtime. This is because it is much easier to be told that a variable doesn't exist immediately instead of having to go through an entire repro-case just to find out that instead of fixing your bug, you have to fix a typo and repeat the test.

So I started writing up specs for proposed features and extensions to the language. After a certain amount of discussion and revision of the initial set of specs I started working on updating Thistle. Thus FogBasic was born, and the compiler was renamed fbc. At first I needed to update the compiler so that it could handle the extra work, so the tokenizer was updated to more fully match the available tokens in the language. I added a parser and generated a full abstract syntax tree. The type checker was the bulk of the work since it needed to be able to infer most of the type information from the code.

Before the type checker was added, I needed to test that the parser and new PHP generator worked properly. So after each compile I would compare the generated code that fbc generated with Thistle's generated code, and once I had them both generating the same code, I was able to start adding type inferencing features.

During the summer of 2006, we realized that I was a complete dork for naming it FogBasic, so we had a naming contest. Everyone submitted their name suggestions, and we did instant run-off voting to decide the name we would actually use. The final two were Bone Crusher 3000 and Wasabi. As much as I wanted to be typing bc3k into the command line, Wasabi won out. Since then Wasabi has continued to get improvements and almost all of the new code in FogBugz 6 uses one or more Wasabi features.

As of today, Wasabi can generate ASP, PHP, and JS. In the future I will talk about how we use these different languages, how we have reduced the amount of code that we need to write, how Wasabi allows us to do meta programming, and how we see Wasabi evolving in the future.

Looking for more?

Visit the Archives or subscribe via RSS.