C++0x: The Lambda Expression Debate

he next C++ standard (C++0x) will have lambda expressions as part of the standard. N2550 introduces them. It's a short document, and it's not too painful to read. Go ahead and click it.

Like many new C++ standards, it's not clear yet how the new feature is going to be used. Michael Feathers has already decided not to use them. At least one other person seems to mostly agree. I, on the other hand, am with Herb Sutter who seems excited enough about the feature to imply that MSVC10 will have support for it. This is going to be a great feature. Incidentally, Sutter has mentioned an addition to C++/CLI in the past that would add less sophisticated lambda support for concurrency. I suspect he's serious about adding the support soon.

There have been many times when I've desperately wanted to avoid defining a one-off functor or function in my code. In fact, there have been times when I've been desperate enough to actually use Boost.Lambda! This standard is a clear win over Boost's attempts to deal with the limitations of C++03.

It's worth showing you what's possible. I'm going to steal code from other people's blogs since I don't have a compiler to test code. Here is Sutter's example:

find_if( w.begin(), w.end(),
[]( Widget& w ) { return w.Weight() > 100; } );

This has more punctuation than those earlier bloggers wanted to see. However, I'd call it extremely clean. It's the normal STL find_if algorithm with a lambda expression to create a functor. The initial [] declares the capture set for the lambda in case you wanted a closure. I'll talk about that later.

If you haven't been following the decltype/auto proposals in C++0x, you may be surprised to see that you don't have to declare the return type of the functor. As a side note, you will be able to use the auto keyword to allow the compiler to automatically determine the return type of a function. Expression template libraries are going to change a lot now that this becomes possible:

using namespace boost::xpressive;
auto crazyRegexToMatchDollars = '$' >> +_d >> '.' >> _d >> _d;

Suddenly, you can avoid placing your complicated types in container types that erase most of the type information.

That's another subject, though. The short version is that the compiler figures out the return type of your lambda expression based on the type of the expression that gets returned.

The capture list in the original lambda example is worth talking about. There are several options here. My favorite is the one Herb Sutter used: an empty list. This means that there are no captured variables in the closure, and this seems like a great default. In this case, the lambda expression cannot access any variables stored on the stack outside of the lambda declaration.

If the empty square brackets were replaced with a [&] or a [=], then any references to stack variables in the lambda expression will get something copied into the functor that the lambda expression creates. This level of automation may make some sense for extremely small lambda expressions.

It's great that the fully automatic behavior is optional. If the original [] is used, then you'll get a compiler error if you accidentally access a variable that may go out of scope before your functor is destroyed. The empty closure list appears to be a great safety mechanism. [=] is a good second choice, however. This makes all captures be copy constructed into the functor. Because everything gets copied, it should be safe from lifetime issues. [&] will copy non-const references into the functor and should probably be used with caution.

If you really need to write to a capture, you can list the variables that you want to use explicitly with a & in front of the variables. This means that, when reading the code, you'll realize that the variables listed in the capture list have to outlast the functor created by the lambda expression. Ironically, I'd go with the opposite of some of those earlier blogs and guess that [&] should be avoided as much as possible. (They seemed to think that storing references to unspecified captures should be done by everyone, all the time. C# does this, but it also has garbage collection to help out.)

So far, this extension looks great! I can imagine a lot of different ways to use different capture sets. It looks like a succinct way to make a variety of commonly needed functors, and I'm a fan of the safety that it allows. It should get people to make a lot more functors.

I'm really looking forward to n2550 going into compilers. I'll be watching GCC closely to see when they add reliable support for it, and I may stop using MSVC at home as soon as they do.

This originally appeared on PC-Doctor's blog.

The Next JavaScript...

ECMAScript 4.0 (ES4) is on its way. This will be the next standard for JavaScript. It's not going to be usable on web pages for a while, though. In fact, I suspect I won't be using it on my web page for at least 5 years. The problem is simple: as long as people still use older browsers, you won't be able to assume that people have it.

However, the features in it are an interesting look at what the standards committee thinks is wrong with the current JavaScript. This is not a minor patch release. This is a dramatically overhaul of the current JavaScript (ES3). Oh, they've included a lot of minor things that are simply broken in ES3. These changes are certainly interesting, but today I'm going to talk about their major focus. They want to make it easier to develop large applications in JavaScript. Clearly, they understand that people are starting to develop large applications for web browsers, and they feel that there are problems with the currently available technologies for this.

I don't have any experience with developing what I'd call a large JavaScript application, but we are starting to develop an extension of PC-Doctor for Windows that uses JavaScript in numerous places to control its behavior. In my dreams, I imagine that it will eventually become a large application made up of plugins that run on JavaScript.

Let's go through the major features that the committee thinks I'll need as our technology gets bigger...

Classes and conventional OOP. I thought this was interesting. They're adding conventional classes as an alternative to the prototype based inheritance that ES3 supports. This comes with a bunch of normal OOP things like virtual functions, getter and setter functions for "virtual properties", interfaces, inheritance, etc.

I can certainly understand why they wanted this. Type safety is greatly enhanced if you can know exactly what type something has. ES4 makes it possible to create a "conventional" class who's members look a lot like Java's and C#'s. You can't write or delete arbitrary properties of one of these classes. With ES4 and a properly written program, the language will be able to determine that you're doing something unintended to some objects and fail at runtime.

Type safety. The new class system allows values to actually have a strict type. Most user created types in ES3 are simply Objects with certain properties and a specific value of the prototype member. That's close to a type, but it's only an approximation since it's possible to change it with some member assignments. The new classes will have a strict type that cannot be changed.

This is bigger than it sounds. This means that code can require certain types in certain variables. It means that a member function will remain a member function for the lifetime of that object. The runtime engine can enforce this, too. The standard doesn't hide the fact that inserting some extra asserts in the code will slow things down, however. They bring this up clearly, and they don't apologize for it.

This is called type safety, and it's something that I've been advocating for a while. The committee wanted it badly enough to be willing to slow programs down for it. They go beyond even that, though.

They've introduced another mode of execution called "strict mode". In this optional mode, the execution engine is supposed to perform some static analysis of the program before it begins. The engine is supposed to fail when a variety of illegal things are possible in the code. For example:

1. Writing to a const property.
2. Calling functions with the wrong number of arguments.
3. Referencing properties of class objects that don't exist.
4. Failing a type check.

The great thing is that all of this happens before the code is executed. It's done entirely with static analysis. If anyone ever bothers to implement this mode (it's optional), then JavaScript is going to become my new favorite scripting language!

I should point out that there are few guarantees about strict mode. Different browsers are going to check for different things in strict mode. Therefore, it is only useful in development. I predict that developers will run the most strict web browser on their development machines and publish without strict mode turned on.

I'm going to claim that this is strong support for my work on a Lua static analysis program. They are coming extremely close to saying that in order to write large applications, a scripting language requires strong type checking, and static analysis might be able to relieve the runtime of some of its need for that. Since Lua's runtime has no static type checking, it needs static analysis as well.

Yeah. I'm going to claim that many of my previous rants are backed up by this committee!

Function overloading. Function overloading is a trick that's only available to languages that can define the type of an object. ES4's version is slower than Java's version because it has to happen at runtime. However, the important thing is that it's possible.

Functions are values of variables in JavaScript just like strings or numbers. You might ask how it's possible to assign more than one function to a single variable name. They do it in two ways.

The first is something they call a generic function object. This is an object that can hold more than one function in it. It exists as a single value. It's a bit clunky, but I couldn't come up with anything better.

Speaking of ugly, there's another way to overload functions. They added a switch statement that works on the type of the value. Here's the example from their overview paper:

switch type (v) {
case (s: string) { ... }
case (d: Date) { ... }
}

That looks like a pathetic attempt at overloading to me, but it could well be how generic function objects are implemented internally. It may be that this could be used to create a more flexible generic function object. However, I predict that consultants 5 years from now will make lots of money going to companies to give talks condemning the use of it.

Packages and namespaces. This is used to hide the activities of different components in an application. This is clearly lacking in ES3 even with small scale libraries and applications. Library authors tend to go to great lengths to hide as much of their code as possible from the global namespace. With the small applications I've written, it's been working fine, but I can see its limitations.

Overall, I'm pleased with where ES4 is trying to go. They're trying to make it safe to build large applications with JavaScript. Given where we're seeing web applications going, this is a great thing. However, I can't imagine that it'll work anytime soon since Google Web Toolkit gives ES3 programmers compile time type safety right now.

Mostly, however, I'm pleased that the committee is trying to add type safety to an untyped language in almost exactly the same way that I would.

This originally appeared on PC-Doctor's blog.

The Cost of Complexity

This article is going to have more questions in it than answers. It's about a problem in software development that I'm not sure I've worried about enough. I've certainly thought about it for specific cases, but this is the first time I've tried to think about the problem in general.

My main question revolves around the cost of complexity in software. There is certainly a large cost in making software more complex. Maintenance becomes more difficult. Teaching new employees about the project becomes harder. In the end, you will get fewer engineers who understand a complex project than a simple one.

Unfortunately, almost any non-refactoring work will add to the complexity of a project. However, some changes can have a large effect on the complexity in a short period of time. Adding a new library or technique to the code base, for example, will make it so that the new technology will have to be understood by people working on the project.

What I really want to know is how much can this cost of complexity be mitigated? Besides switching libraries to add, what can be done to decrease the cost? My question is based on the assumption that some complexity is essential. So, given that you're going to add a new library to the code base, for example, what can be done to reduce the cost?

Make it fun?

Some types of complexity are actually fun for programmers to deal with. After all, if you don't like learning new things, you wouldn't last long as one. For example, a new library may be complicated, but it may also do some really nice things. If it's a fun library to use, then is its cost of introduction reduced?

Unfortunately, fun is difficult to predict. Certainly a hot technology is going to generate more interest with engineers. For example, I'd much rather develop a new mobile application using Android than WAP. WAP is probably a lot simpler, but Android is breaking news. WAP is dying. Would I choose Android over WAP just for this? Probably not, but I suspect that Android's problems are reduced a bit because of its novelty.

I looked reasonably hard for some discussion of this. I couldn't find anyone who wanted to admit that this could be a significant factor. Am I all alone here? Somehow, I doubt it. I prefer to believe that everyone ignores this.

Of course, without some measurements, it's just speculation. Hmmm... Maybe you could make some sort of measurement based on fake job ads and resume counts?

Ease of use

No one seems to think of libraries as something with usability considerations. However, an API is really just another interface that happens to be used only by programmers. If a library is easy to use, its cost will be reduced. What can be done to make a new technology easier to use?

Microsoft is pretty good at this, actually. Lots of people are going to complain at that statement because they've got a long ways to go. However, they put a lot effort into making high quality tools and documentation. Heck, they even created a publishing company to create how-to books for their libraries. They put a lot of energy and time into getting things working that aren't related to the API itself. (It's too bad their APIs frequently make me want to kick kittens.)

Libraries that do this well will make themselves cheaper to use. Once a library is chosen, though, what can be done about making it easier?

When I first came to work for PC-Doctor, I was told to create a new web application using Ruby on Rails. None of us knew how to use either Ruby or Rails. It turns out that the online documentation for Rails was pretty close to miserable. (I sure hope they've fixed that!) We bought many copies of some O'Reilly books on the subject, and this helped a lot.

Spend a bit of money to educate engineers. Different people learn in different ways, though. I love to read. Andy, our current Rails expert, is a big fan of some Rails videos that he found. Find the right support for each developer. Buy whatever training is required. The cost of a book is pretty low when compared to a developer who is forced to stumble around the internet looking for answers.

Genuine need

If everyone understands that a library really is needed, then people will be a lot more interested in learning it. This may be related to the fun factor mentioned above.

Complexity that seems like a bad idea afterwards is frustrating. Poorly written code is a great example of unneeded complexity. I've seen first hand what large amounts of horrible, old code can do to someone's moral. Andy, I'm thinking of you...

What did I miss?

Let me know. As I mentioned, I'm way behind in thinking seriously about this subject.

This originally appeared on PC-Doctor's blog.

The Visitor Pattern as an Alternative to OOP

The visitor pattern from the GoF is frequently overlooked by programmers who are used to object oriented programming. However, in some cases, it is significantly cleaner and easier to use than an overridden function. Unfortunately, it's easier to misuse as well, and, when it is used poorly, it can be a real mess.

I was going to tell you about my static analysis project and how I'm using the visitor pattern there. Then I took a glance at the wikipedia article on the visitor pattern. It's clearly written by a OOP fanatic who's never seen the alternatives, so I'm going to contrast my implementation of visitor with the one there.

The contrast is useful because wikipedia's implementation is written using object oriented principles. Part of my goal with this post is to explain about OO alternatives. My implementation is written using compile time polymorphism rather than runtime polymorphism. As we'll see, this is significantly prettier and more flexible than runtime polymorphism.

Java-Style Visitors

I recommend clicking on the wikipedia link and reading a bit. Like all good OOP C++ programmers, he's got loads of virtual functions in a variety of interfaces.

Some of those are used to implement a completely unnecessary runtime double dispatch mechanism. The double dispatch functions can be eliminated by avoiding the use of the interfaces in the first place. This immediately cleans up his classes a bit.

If the compiler always knows the type of a class, then the accept() and visit() messiness disappear. The accept function essentially acts as a safe cast from the base interface to the derived type. If we never let the compiler forget what the derived type is, then we don't need a cast.

Yes, I'll admit that I laughed when the author confidently says that those functions are required. They're only required because the author wanted to do dispatch at runtime instead of compile time. The visitor pattern does not require this.

There's another interesting point to notice about the interface. He's got one virtual function for every single derived class in his visitor. There are no functions that handle a collection of derived classes. This is because he's forced to use the class hierarchy to tell the compiler which function to call. He cannot use any other properties of the derived classes for this. Without that flexibility, he'll often be forced to write a separate function for each derived class.

Traditional OOP techniques

I'd like to briefly touch on what would happen if a visitor pattern wasn't used at all.

In this case, the visitor class in the wikipedia code gets replaced by a virtual function that gets implemented for every single derived class in the hierarchy. If you want to perform that function, you simply call it. This is often the correct thing to do, too.

However, it's worth looking at some of the disadvantages that are solved by using a visitor. First, the code in each of those functions gets spread out over the entire class hierarchy. If those functions are more tightly coupled to each other than to the object that they're attached to, then this will be awkward to maintain.

Second, each one of those derived classes has to be known and available for modification. You can't make it so that third parties can add additional derived classes, for example. Every derived class has to be found as well. In some cases, that can be a serious problem.

Finally, the functionality provided by your new function has to be advertised to every single author and user of the hierarchy. If the functionality is obscure and only useful in limited cases, then a visitor (or a free function) should be considered instead. The only one who has to know about the functionality provided by the visitor is the author of the visitor. Nothing else gets touched.

Compile Time Polymorphism

The visitors that I'm writing for my static analysis project are dramatically different.

They act on the abstract syntax tree (AST) of the parsed Lua program. There are about 40 or so different grammatical constructs in Lua, and so there are about 40 classes in the AST.

The visitors themselves act on each of these classes, but they frequently only have a few functions in them. For example, I've got one visitor that calls an aggregated visitor on each node in the abstract syntax tree.

The ForEach visitor has to know about several different ways that the classes can hold child nodes, but it can act on each of those techniques in a single function. For example, it's got a function to handle a vector of pointers to child nodes. It's got another one for a single pointer to a child node. It's got a few others, but it certainly doesn't have 40 member functions in it! I suspect that that's what the author of the wikipedia article would have ended up doing, and it would have been miserable.

I've got a bunch of visitors other than the ForEach visitor. Each of these describe an algorithm that acts on the AST. The algorithms end up almost completely separated from the data structure that the algorithm acts on. I can add a new algorithm (and visitor) without recompiling or editing the data structure code. This separation is what the visitor pattern is great at.

The reverse is certainly not true, however. If the data structure code changes, then the visitors will at least have to be recompiled. In my case, I've written a lot of the visitors generically enough that most of the code doesn't have to change, but a recompile of C++ code that contains a lot of template metaprogramming can be expensive even without having to edit the code. I wanted to be somewhat immune to changes in the data structures, though.

For example, Lua has a "repeat...until" statement as well as a "while" statement. (They do exactly what you'd expect.) Internally, I decided that the repeat...until statement should store the test and statement block in the reverse order of the while loop. I want to be able to change that without changing the ForEach visitor. I want the ForEach visitor to be mostly independent of the internal organization of the AST classes. Because ForEach uses template metaprogramming instead of manual coding to figure out how to traverse the AST, this works perfectly.

All of this works reasonably well with compile time polymorphism. Most of this would be impossible without it.

In my case, the disadvantages aren't all that bad. However, they do exist, so let's look at them.

The largest problem is that small amounts of template metaprogramming were required to pull this off. This means that compile times are longer than a Java programmer would think was possible. (It takes a 5 seconds or so per source file for me.)

It also means that you get some really ugly functions with lots of the "typename" keyword messing up the flow of the code. I suppose you're supposed to get used to that, but I hate it. This isn't really a problem with the visitor pattern, however. It's really a problem with C++. It may be cleaner in other languages.

Overall, however, there weren't many disadvantages to using this type of visitor. However, traversing an AST appears to be exactly what visitors are good for; The GoF book uses that as their example, and quite a few web pages have emulated them. In retrospect, it makes me feel a bit foolish for writing this article!

This originally appeared on PC-Doctor's blog.

Alternatives to Object Oriented Programming

Object oriented programming is extremely popular these days. It's so popular that some people aren't even aware of alternatives to it. The reason its popular is clear: OOP works well a lot of the time. Traditional object oriented programming styles have some significant disadvantages in some circumstances, however. Some of the alternatives are worth looking into when those disadvantages become awkward.

As part of the static analysis project that I'm working on, I'm trying to use alternatives wherever I can. In part, this is because the advantages are substantial for the project I'm working on, but I'm also curious how far it can go and what will happen when I push it too far.

So far, I love it. Inheritance is a relationship between classes that is only a small step from C++ friendship. The derived class becomes extremely tightly coupled to the base class, and, in some cases, the base class can even become coupled to the derived class. The temptation to add functionality to the base class can be large as well.

I'll talk about two ways of partially avoiding inheritance. Both of them rely on compile time polymorphism and cannot (or should not) be used if runtime polymorphism is required.

How often do OO programmers actually need the runtime polymorphism that they enjoy so much? Certainly it's needed some of the time, but it's not nearly as useful as it looks at first. For example, my static analysis project contains a different class for each of several dozen different Lua constructions. This sounds a lot like a case for inheritance, but it's only got one virtual function in the whole project, and that's there only to merge the C and C++ code. If the whole thing had been in C++, it wouldn't have been needed.

Free Functions

Many programmers in the OOP world will happily add new functions to the public interface of classes whenever they can. For example, the C++ string class that PC-Doctor uses has a public member function to return a uuencoded version of the string. This is an extreme case, but it's still worth looking at.

In this case, we've got some functionality that we want to give to a small number of users of a class. There aren't many places in our code base that use this function, and essentially everything uses the string class. Furthermore, the function can easily be implemented using the existing public interface to the string. In this case, it's pretty obvious that everyone would be happier if the function was a free function. As a free function, most users of the string won't ever have to see it. In fact, they don't have to include the appropriate header file or even link to the appropriate module. The interface to string becomes a bit easier to understand for the majority of string users, too.

Furthermore, if you wanted to implement uuencoding for multiple types of strings, you could still do it. For example, if you had different types for UTF-8 and UTF-16 strings, you could overload the free function for both them.

As I said, this was an extreme case. There are disadvantages to free functions, however. Let's look at the other extreme for a bit. For this, let's see what Herb Sutter has to say about free functions in Exceptional C++ Style. He claims that all you should construct your interface to classes by exposing the minimal set of public member functions with everything else as a free function. His argument in the book also looks at a string class, std::basic_string.

Strings, however, are a bad example to generalize from. Some of his arguments get much weaker if you look at a highly specialized class that will only be used in a few places in a single program. Since the vast majority of code that I write is exactly that, I'd rather study this case.

With that in mind, I've made the 40 classes that form the abstract syntax tree for Lua into classes that only have constructors, destructors, and access to internal data. This is, perhaps, a bit more than even Herb Sutter would recommend. I give public access to all of the member data so that there isn't a chance that any member functions could be needed.

I've written most of the code, and it works fine. However, it hasn't survived the maintenance phase, and it's not clear that it will.

However, I'm not going to change the way I write normal application code. At PC-Doctor, I'll write many more classes that get used by only a few other classes. I won't create many free functions for them. Why?

First, free functions clutter the namespace they reside in. I only want that function to be seen by the small number of programmers that might be interested in the class I just wrote. Considerably more people will see the namespace that the class is in.

Let's look at an example. Suppose I want to write a function that appends an alert to a collection of alerts that will be shown to the user. The function might be named "append". If this is a free function, it'll get lost. I want users of my AlertCollection class to know that they can append alerts to it. I don't want them to have to dig around. My users are not going to be using it for long, and they don't want to remember the details later. They just want a complete catalog of everything they can do so they can quickly do what needs to be done.

If a programmer at PC-Doctor decided that they were fans of handling alerts and they wanted to actually remember my API, then putting some of the functions as free functions is, again, a problem. There's one extra bit of information that the user has to remember for each function.

Finally, languages like Java and C# can't have free functions. This is their loss, unfortunately. While I can't give a hard and fast rule for when to use free functions, I can say that they are a valuable tool when developing some APIs.

Visitor Pattern

Well, that was more than I wanted to write in one week. (Remember, I'm a programmer!) The visitor pattern will have to wait until next week. It's probably worth a whole post on its own anyway. It's tricky to use effectively, but it's occasionally extremely effective.

This originally appeared on PC-Doctor's blog.

Requirements of a Language to Statically Analyze

For those of you just tuning in, I'm working on a project to statically analyze an untyped code base to try to bring some of the advantages of typed languages to the code base.

The first step is to figure out which language I should write a static analysis tool for. This is obviously an important decision with quite a few implications both at the beginning, during the creation of the parser, and at the end when we try to find an actively developed code base to look at.

The first requirement is that it be a relatively popular, untyped language. Let's look at some languages:

1. JavaScript, ECMA Script, or JScript. This is used by millions.
2. Lua. This is a popular language to embed in applications. I know it extremely well, too.
3. Python. This is really popular, and it's a pretty clean language, too.
4. Ruby. This is getting to be a popular language. (I really like the language, too.)
5. PHP. This is also a popular language.
6. Perl. I've gone through life without having to learn COBOL, Fortran, or Perl. I'm a really happy guy. Do people still use it? I wouldn't know.

Yes, there are some others, but I'll limit my discussion to these.

I'll reject Perl immediately because it's designed to be complex. This is just a hobby project, and I'm not going to be able to spend lots of time dealing with unneeded complexities. I also have no interest in learning it.

I'm also going to reject PHP for similar reasons. I just have no interest in it. Now we're down to harder choices.

We're down to four languages: Ruby, Python, JavaScript, and Lua. These are all languages that I've enjoyed using, and some of them I know pretty well.

Let's start with Ruby. Ruby is a wonderful scripting language. I love it for its terse, expressive syntax. I'm a bit worried by the quantity of syntactic sugar in it, but most of that can be stripped away after parsing it.

However, Ruby code is frequently written in a different style than conventional, object oriented code. Ruby programmers are used to doing things that would be utterly opaque to any reasonable static analysis tool. Here's an extreme example of some Ruby on Rails code that scares me:

lang_code = 'en'
obj = MyModel.find_by_name 'name of obj'
result = obj.send :"language_#{lang_code}"

For the non-Ruby geeks out there, this pulls a MyModel object out of the my_models table in the database. The object is populated with some members based on the database schema. That's mildly scary all by itself, since I'd rather not spend my time dealing with DB schemas. However, the last line is even worse! This calls the get_language_en member function in obj, but the only way for a program like mine to figure that out is to look at the value of lang_code. I'd much rather ignore values and only look at types. (Many scripting languages treat functions as ordinary values that can be moved around. As we'll see in future installments, this isn't always a big problem.)

Other languages can do this, too, but Ruby programmers enjoy doing it a bit too much.

Python is another well designed language that would be fun to use. I can't claim that I'm an expert at it, so there may be other problems with it. However, the standard libraries for it scare me a bit. There are a huge number of them. As far as I can tell, Python programmers use whatever they feel like using from these, so an automated way of deducing the argument types and return values of functions would be required. I'm sure that a doxygen summary of the functions could be found somewhere, but I'd prefer to not rely too heavily on infrastructure that doesn't sound like much fun to work on.

Lua is an extremely simple language that's designed to be embedded in applications. As such, it avoids both the large amount of syntactic sugar in Ruby and, at least in most cases, the huge library of Python. However, it does mean that you'd have to find the correct application of Lua to look at. Let's assume that such an application exists.

Like most (or all?) of these languages, Lua treats functions as first class values. Because of this, it is possible to pick the function to call based on a variable. Here's an example:

selector = 'a'
obj = { a: function(num) return num+1 end, b: function(str) return str..'!' end }
obj[selector]('string')

The last line is the worrisome one. This calls a function, passing a string into a function that probably requires a number. (There are ways to modify the behavior of types in Lua. Off the top of my head, I don't remember if the latest versions of Lua allow strings to have overloaded operators.) If we assume that this isn't possible, we'd like to detect such an error. That's extremely hard.

Realistically, however, if we reject Lua because of this problem, then we'll also reject all other scripting languages that treat functions as normal values. As far as I know, that's all of the ones on my list. Fortunately, this behavior is not a frequent pattern in the Lua code that I've seen and written. There are other ways of accomplishing the same task in Lua that are significantly simpler, more powerful, and, therefore, more popular.

The last language on the list is JavaScript. JavaScript can be used in a lot of different ways, but by far the most common and exciting way is in client side scripting on web pages. This provides an enormous body of code that could be analyzed. In addition, there are other tools out there that create type safe JavaScript by cross compiling from another language. This code would make an excellent test case for my tool.

JavaScript doesn't suffer from the same problems that Ruby and Python have, either. While you can do what I described in the Lua example above in JavaScript as well, it's not especially common for exactly the same reason. (Both Lua and JavaScript support closures. Closures are much more powerful, and, even though Internet Explorer has some nasty bugs related to them, they are extremely popular.)

Web browsers do have a mildly large library embedded in them, but the security restrictions are so large that the library is inherently limited. ActiveX controls and Mozilla Plugins and extend the API in annoying ways, but the body of code out there is so large and varied that pages that use plugins that I don't want to support can be thrown out.

The one real disadvantage of JavaScript is the optional semicolon rule in the parser. The parser is required to insert semicolons in a bunch of places, and this does sound mildly annoying to parse. It can't be that bad, though. (Lua has a similar rule involving newlines, but it's much more obscure.)

Up until now, JavaScript looks like an exciting possibility. Unfortunately, I do a lot of work here at PC-Doctor using JavaScript, and I'd rather do something completely different. I really don't want a useless hobby project to feel like work! If I need another excuse, it's that others have already written limited tools like this for JavaScript.

Lua 5.1 is it.

This originally appeared on PC-Doctor's blog.

Mixing C and C++ Code

One of the early steps to my static analysis project is to parse the language that I'm going to analyze. I'd like to form a relatively clean Abstract Syntax Tree that I can play with later.

C++ has a lot of advantages over C for this sort of thing. It's got an enormous amount of machinery that can be used to build high level abstractions without sacrificing much more runtime overhead than you're willing to pay for.

However, C is also still a useful language. For example, it's extremely simple when compared to C++. Perhaps in part because of this, a lot of code generators out there still create C code. If you want to use one of these code generators with anything but C or C++, you can't do much to tweak the output they generate. C++ could well be unique in its ability to mix the old style C code with modern programming techniques.

I've been using some code generated by Flex and ACCENT recently, and it's nice being able to use a lot of C++'s features with the code. (ACCENT still uses K&R function definitions. It's pretty old and primitive, I guess.)

I've worked on a few projects that required a mix of the two, but I can't claim that I've ever thought about exactly how it should be done. Part of the problem is that it's extremely easy to mix the two. C++ allows much more integration with a C library than most languages. In C#, for example, about all you can do when dealing with a C library is make calls into it. C++ allows you to define types that can be used by the C library, you can play with #defines just like a C programmer can, and you can pass function pointers around without worrying whether they're from C or C++. (Though std::tr1::function is better!) You can even include random header files and make calls into the internals of a library.

Clearly, some thought should be done before mixing the two. I'm embarrassed to say that I haven't ever done this deliberately.

Currently, I'm using Flex, a library that exposes more than simply an API to call into. You are supposed to compile the code into your module, and it is possible to modify the code by creating some C compatible types and passing them in through #defines.

It's all very clunky and C-like, but it works great, and that's all I care about today. I'm happy to use it, but I don't really want to pass in a POD type. I want a full fledged C++ class to be used by Flex.

Mixing Flex's generated code and modern C++ code is entirely possible, but there is a lot of type safety that gets thrown away when going to the C code. For example, Flex thinks that each programming language construct and all of its parts are all made up of Symbol* objects. In C++, I don't want to have an abstract base class that defines all behavior that all of these constructs might ever need. Instead, each different type of construct is a different type in C++. This means, for example, that it's not possible to pass an object that isn't an expression to a function that requires an expression. I like that a lot, but Flex wants all of these objects to be the same.

The C code, therefore, will go through a facade that does a bunch of careful type conversions and then passes the resulting, typed objects through to the C++ code.

This is a frequent theme in other projects that I've done that involve mixing C and C++ code. C++ is capable of supporting a much richer set of types than C is, and there always seems to be some work involved in preserving C++'s type expressiveness in C.

Incidentally, the facade is incredibly ugly at the moment. There's lots of typeid operators and long if..then..else if...etc constructs generated by preprocessor macros. However, the rest of the C++ code always knows exactly what the type is, so it's all worth it.

Flex and Accent's generated code do have to perform operations on these objects, however. They end up using a long list of "member functions" that always take Symbol pointers. For example, there might be a function to create a C++ expression object by taking a unary operator and another expression object. In Accent's world, this looks like this:

Symbol* CreateUnaryOperation( Symbol* op, Symbol* expression );

That's essentially a constructor for the Symbol* object. (Flex doesn't have to worry about whether or not it's a pointer or a struct. To Flex, it's just a copyable typedef.)

This is another common theme of mixing C and C++. You don't have to stop object oriented programming in C. You just have to wrap it all up in a bunch of free functions. It's even possible to have virtual functions by manually creating the vtbl.

It also nicely displays another annoying theme of mixing C and C++. In C++, you always know what the rules for the lifetime of an object is. If a function returns a value directly, then the caller gets control over the lifetime. If the function returns a smart pointer, then the smart pointer gets control over the lifetime. (Smart pointers also come with a set of rules about what the caller is allowed to do with the object.) If a reference is returned, then the object's lifetime is controlled elsewhere. It's all wonderfully unambiguous.

In C you always get either a value or a pointer. It's true in my project, too. All of my fake constructor functions return a Symbol*. I really want it to be an auto_ptr, though! If Flex or Accent were to misplace a pointer, then it would be lost forever. So far, they don't seem to do that, but it's certainly filled with ambiguity.

I haven't come up with a satisfactory solution to this problem. My current solution is to always do exactly the same thing with all of the objects returned by my facade's functions. If the programmer has to remember a set of rules at all times, then it'd better be a simple set of rules.

It looks like this is the beginning of officially working on statically analyzing an untyped language. Next week, I might talk about what language I picked and why. Or perhaps I'll talk about my crazy idea for a completely clean decorator pattern implementation so that I don't have to mess up my nice, clean AST.

This originally appeared on PC-Doctor's blog.