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.