Parsing, C++ Style. Part 1

I'm going to let you in on a secret: I hate rote busywork programming. I can't stand boring, trivial code. Oh, I know it needs to be done, but if I've done it 20 times before, odds are I'm going to find a way to keep from having to do it a 21st time. That's one of the things that's nice about using C++.

One task I detest with a passion is writing a parser. We've all had to do it. Load a text file, tokenize it based on some pattern or whatever, look for the data you're interested in, check for errors in formatting, etc. It's easy and boring. And, more importantly, highly error prone.

The latter is a real sticking point. The only thing I hate more than writing a praser is having to debug one. Adding to that is the fact that debugging a parser is not like unit testing or something of that nature; it's a totally input driven process. If you forget a particular case, or didn't anticipate something, it will come back to bite you.

Fact is, I shouldn't have to parse code manually. I should have some API or library or something that I can apply to a text file and read it. Worst case, I should be able to define the format of the file, run the file through the parser with that format, and get a parse tree representation of the file, or an error if the file is not formatted properly. Best case, instead of a parse tree, my code simply gets called during the act of parsing the file in question.

Now, there are two utilities in particular that I personally rely upon for 95% or more of my parsing needs. The first is LibXML2. It's a C-based library (though there's an unpleasant C++ front end with an obnoxious license available, if you really need it), so it doesn't qualify as C++ Limit Science.

So, I lean on XML a lot. However, though XML is a nice language for the person writing the document, it's not particularly nice for the person reading it. Even with LibXML2, you have to do a lot of rote parsing work.

For formats that tend to be generated from code rather than by an external user, I prefer a combination of Lua and Luabind. Lua is a very easy to use scripting language, but the origin of Lua was in configuration languages. As such, Lua makes a handy file format. All you do is have the Lua script store its data as a large table, likely with nesting. Imagine a gigantic arbitrary struct with any data you can imagine. It can be passed around as plain text, but it can also be compiled into Lua bytecode for size purposes. And thanks to Luabind (a C++ library), actually accessing the contents of the object is much easier than with the Lua C API. It is very easy to generate files and it is likewise easy to read them. And if someone wrote the file in a syntactically erroneous way, Lua will simply report an error at compile time.

Taken together, they cover most of my parsing needs. XML is used for things the user will modify or create, and Lua is used for most everything else.

But then comes the big problem. What do you do when you have no control over the file format?

This is more likely than you might think at first glance. HTML and XML may be derived from the same source (SGML), but they are not compatible. And HTML certainly isn't Lua. Or maybe you're trying to write a scripting system yourself. Unless you're going to force your users to script in XML (yuck), you will need to write a parser of some kind. Or maybe you need to be able to parse some simple strings that the user enters, such as for a text adventure or some such.

And that's where Boost comes in. Or rather, Boost.Spirit.

Spirit is a very large, header-only library, but it's founded on a simple predicate: make text parsing easy. It is designed for low-to-medium scale parsing; high scale parsing, as for a highly grammatically complex language like C++, is at the very far end of Spirit's capabilities. It can do it, but you will certainly not like what it does to your compile times.

This is to contrast Spirit with it's primary alternatives, the preprocessing-based Lex/Yacc and Flex/Bison. These alternatives require the user to write a grammar in a special syntax and add specialized preprocessing commands into their build pipeline to generate C files for doing the parsing. They're functional, but rather arcane, requiring external executables and so forth.

Spirit, by contrast, leverages a preprocessor that you already have: your C++ template preprocessor. Spirit is a template metaprogramming library that allows the user to define a grammar using a syntax that is not unlike Enhanced Backus Naur Form. It also allows the user to provide semantic actions, functions that will be called when a certain parsed element is reached.

Higher-level Spirit functions, built on the base functionality described above, allow for the creation of an entire parse tree of the document, defined by special semantic actions. And of course, Spirit has the Phoenix functional programming library in it (which it uses internally), which makes it easier to build semantic actions for various bits of functionality.

The core foundation of Spirit isn't really a parser per se: it is a tokenizer and recognizer. It is, in essence, a schema language. It takes a string and a grammar and returns true if the string fits the grammar and false otherwise. Along the way, it will call various user-defined functions on the parsed text if it matches.

Here is a very simple example of a Spirit parser:

using boost::spirit;

bool RecognizeNumberSequence(const char *strInput)
    {
        return parse(strInput, real_p >> *(',' >> real_p), space_p).full;
    }

This will return true if strInput is a comma-separated list of real numbers.

The second input to the function is a Spirit parser. The expression real_p >> *(',' >> real_p) produces a parser object that can be used as input to the parse function. The variable real_p is a predefined Spirit parser that parses real numbers in all of their various forms.

The object space_p is a parser recognizing spaces. Used as the third argument to boost::spirit::parse(), it represents the "skip parser". This parser tells the parse function how to tokenize the input. That is, what to ignore when parsing. This keeps the main grammar cleaner.

Let us break down the main parser expression, "real_p >> *(',' >> real_p)". The '>>' operator means that the operand on the left will occur before the one on the right. The '()' means what it seems like; the grouping operator. The '*' operator (C++'s dereference, not multiply) means that the operand will be repeated zero or more times.

So, this parser means that there will be a real number, followed by zero or more repetitions of a comma followed by a real number. Basically, a comma-separated list of real numbers. And the space_p skip parser means that spaces can occur between any of these elements, but not within a real number.

As mentioned, this is not a terribly useful function, as it does not actually do anything with what it parses. It simply detects whether the input is well-formed as stipulated by the two parsers. In the next part, we will deal with actually doing something while parsing.

Functional Programming in C++ 3

I'm skipping part 2, because I'm having some difficulty coming up with a really good example of why you need functional programming. Oh, sometimes it's nice, but I've yet to see a point where it's necessary.

We've actually had a slight introduction to functional programming, or some aspects of it before. The article involving Boost::Bind, for example. At the end, I mention the ability to compose bound functions to create new ones. And Boost::Bind has the ability to convert the parameters of a functor from one to another.

Of course, that's not nearly good enough for real functional programming.

In terms of getting this done in C++, there are several options. Boost (the fount from which all good things flow), of course, has a library called Lambda. This allows you to generate functions of the form:

cout << (1 + _1)

This creates a function object inline. This function object takes one parameter, adds one to it, and prints it to standard out.

However, Boost::Lambda has a number of limitations. Chief among them, having only 3 arguments, which can be quite limiting. Also, it replicates Boost::Bind (and is incompatible with Boost::Bind), but replicates it without the powerful Boost:MemFn functionality, so you can't use member functions in Boost::Lambda.

In short, Boost::Lambda doesn't take things to the limit, doesn't give us all of functional programming. So, how do we do it?

Within Boost lies the greatness that is Spirit. Spirit is a parser framework; you build parsers with it in a style that seems very similar to Extended Backus–Naur Form. But that's not why we're talking about Spirit. For within the Spirit slumbers a beast of great power: Spirit::Phoenix.

Phoenix is functional programming. It is Boost::Bind combined with Boost::Lambda, mixed with stuff that you never expected to see in C++. Behold:

for_each(c.begin(), c.end(),
        if_(arg1 % 2 == 1)
        [
            cout << arg1 << ' '
        ]
    );

Yes. That does exactly what it looks like. Yes, that is an 'if' statement. Yes, that 'if' statement is in a place where no 'if' statement ever belongs. And yes, that entire expression generates a function object that is passed to for_each and does what it says it does.

So, let's take things slow.

Remember back to our discussion of Boost::Bind. It used entities named '_1', '_2', etc to represent the first argument, second argument, etc. Phoenix uses 'arg1', 'arg2', etc. Personally, I prefer Phoenix's style, since it uses something close to a word, and I'm pretty wordy in my naming.

Let's start with a basic example:

cout << arg1;

This statement does not execute 'cout <<'. It merely creates a functional object of one parameter that outputs that parameter.

Note that the functional object created does not know nor care what the type of that object is. As long as the operator << has been overloaded for whatever argument you pass in (and that the overload takes the appropriate type, in this case an output stream object), then you may call this function.

This goes back to our discussion in part 1, where we said that a function 'f(x) = log(x)' could only take positive values of X or 0, because the function log(x) is undefined on negative numbers. This is the same thing.

Note that there is one thing we cannot do, just as we couldn't do with Boost::Bind: catch this function and store it directly. Oh, 'for_each' can do it, but that's only because 'for_each' is templated on the type of that function object. It can store it because it doesn't need to type out what that type is.

The type of 'cout << arg1' is not for the feint of heart. And that doesn't even get into some of the functional programming statement stuff.

Then again:

boost::function<void (int)> integerOutputer = cout << arg1;
integerOutputer(5);

Maybe we can ;)

Thanks to Boost::Function, we can capture one of these lazy functions and store it. The only limitation is that, because C++ is strongly typed, we can only capture it in a strongly typed object. So we loose a lot of the type genericness that we would normally have with lazy functions.

A minor limitation, but one we can accept. Especially since most of the time you're wanting to capture it (for say, a registered callback), you can easily tie down a specific argument list.

Another thing we can do is get local variables involved:

int iSomeValue;
for_each(someVector.begin(), someVector.end(), cout << (variable(iSomeValue) + arg1));

This will create a reference to iSomeValue, store it in the functional object, and use it on each envocation. If you have a list, and wish to take the summation of that list:

int iSomeValue;
for_each(someVector.begin(), someVector.end(), variable(iSomeValue) += arg1);

Much easier, and much more intuitive, than making a functor call.

It's important to note that 'variable(iSomeValue)' itself is, much like 'arg1', a functional object. So, you could execute, 'variable(iSomeValue)()', if you like really convoluted ways of getting the value of something.

Though I haven't discussed Boost::Signal, it is one of the chief places where you're going to want to use functional programming, aside from std::algorithms. There is a big difference, though: std::algorithms will immediately use your functional object and then destroy it. Signals, pretty much by definition, will call it whenever it feels like.

That's bad when you use 'variable(iSomeValue)'. That's because this variable will not exist by the time the Signal calls it. Remember: the variable() function stores a reference to the variable. And likewise remember that references to stack variables can be hugely dangerous if someone stores them and uses them outside of your scope.

Just FYI.

To get a bit more formal about things, what 'cout << arg1' is, in Phoenix parlance, is a "lazy function". This means that it is only evaluated when it's arguments are called. However, it is important to note that anything that is a Phoenix lazy function can also have certain things done to it. Like this:

(cout << arg1)(arg2, arg1)

This creates a new lazy function. This new lazy function takes two arguments. But the original one only took one.

Fortunately, Phoenix doesn't care. What this will do is create a lazy function can can only be evaluated to produce an answer if it is given two (or more) parameters. Because of how this function was constructed, the first argument will be discarded, and the second will be sent to standard out.

This becomes very interesting when you start using non-lazy functions as lazy function. AKA, when you start doing Boost::Bind-like stuff:

bind(&SomeFunc)

This returns a lazy function. It takes the arguments that the function, functor, or member function took. However, that may not be what you want, especially if that is a member function.

Just like with Boost::Bind, the first argument to a member function is the 'this' pointer. If 'this' isn't going to be an argument you expect the caller to use, you need to add it yourself:

bind(&TheClass::SomeFunc2)(*this, arg1, arg2)

Notice that it takes a reference to the class rather than a pointer. This means that using a smart pointer is impossible, so you need to make sure that your code makes it impossible for this code to be called beyond the lifetime of this object. Fortunately, Phoenix version 2 will allow the use of references, pointers, or smart pointers.

Because Phoenix is a lot more powerful than Boost::Bind, it can do some of the things that we only wished Bind could do:

bind(&TheClass::SomeFunc2)(*this, arg1, arg2 + bind(&TheClass::SomeFunc3)(*this, arg3));

Which creates a functor that takes 3 arguments and does functional composition. Even modifying the return value of the call to SomeFunc3 before passing it to SomeFunc2. You can do all kinds of nifty stuff with this.

The farthest limit of Phoenix however, comes from so-called 'lazy statements'. I scared you with this at the beginning:

for_each(c.begin(), c.end(),
        if_(arg1 % 2 == 1)
        [
            cout << arg1 << ' '
        ]
    );

The 'if_' construct is a lazy statement that evaluates it's contents (within the square brackets) only if the condition is true. Just like a regular 'if' statement.

Except that, since it's functional programming, it creates a function object that does this. And 'if_' is just the tip of the iceberg. Just about every C++ flow control construct exists as a lazy statement (except goto. But we don't use that anyway). Blocks of code can be multi-line, through the use of comma-separated elements:

        if_(arg1 % 2 == 1)
        [
            cout << arg1 << ' ',
            cout << (arg1 + 5) << endl  //Note: no comma on the last line.
        ]

This is incredibly powerful.

However, it's important not to go thinking you can just write anything as a lazy statement. For performance reasons (or potential ones; these constructs have not been deeply profiled), it's generally a good idea to use lazy statements for rapid development, then factor them out into real functions that get called. The thing I like about them is that you can use std::for_each() and make it look like a regular for() statement.

This article is getting long, so I'll punt on closures. They're not the most important or interesting part of Phoenix anyway.

In any case, what you've seen here is merely the beginning. Through Boost::Function and Phoenix, you can have serious functional programming. You can create unnamed functions, compose functions, pull functions from standard C++ functions, and even build functions in a pseudo-C++ language.

Functional Programming in C++ 1

What is functional programming?

The answer to that question is strange. If you've graduated from high school, odds are you've seen functional programming... in math class. As such, I'm going to use that as an analogy to explain what functional programming is.

In Math, you learned that a function looks like this:

f(x) = x + 4

The function f takes a single parameter 'x', and returns the value of x added to 4. Algebra tells us that the function f can legally take any value of x. That is, x can be any number, real or imaginary. And the result of the function f is also any number, real or imaginary.

Here's another example of a math function:

f(x) = 1 / x

Algebra tells us that f can take any number, real or imaginary, except 0. That would make the result of f undefined, as 1/0 is illegal. Therefore, the function cannot take that as an input. Also, the function f can return any output, real or imaginary, except 0.

Another example that's even more limited:

f(x) = log(x)

f can only take positive real numbers or 0 (we'll ignore complex numbers, as the log of a complex number is... wierd). And it will only ever return positive real numbers or 0.

Something a bit more complex:

f(x, y) = x / y

This time, f takes two parameters. The parameter x can be any number, but y must not be 0. And the function can return any number as well.

And now for something a bit weird:

f() = 3 + 4

This is a function that takes no parameters. And it returns only one number: 7.

So, what was the point of that? Well, that was functional programming.

Not convinced that this could be considered programming of any kind? Well, let's proceed.

Let's say we have these functions:

f(x) = x * 5
g(x, y) = x + (4 * y)

Two functions now. I'll skip the input/output analysis and move on to composition. Let's say you want to do this:

h(x, y) = g(f(y), x)

Well, determining what the function h is is pretty simple:

h(x, y) = (y * 5) + (4 * x)

See that? We just did functional programming. We took two functions, composed them together, and created a third function.

You can do more with functional composition. You can lose parameters:

h(x) = f(g(x, x))

Add new ones:

h(x, y, z) = g(x, y) + f(z)

And so on.

By now, you're probably kinda annoyed with this math lesson. What does this have to do with programming? Well, it's simple.

Forget the fact that what I'm about to write is not legal C/C++.

float f(float x)
{
  return x * 5;
}
float g(float x, float y)
{
  return x + (y * 4);
}

float h(float x, float y) = g(f(y), x);

That last line is totally bogus C++. But... what if it wasn't? What would it mean if it were real and legal?

Well, actually, it wouldn't be too amazing, because you can do:

float h(float x, float y)
{
  return g(f(y), x);
}

But, what you can't do is:

void main()
{
  float h(float x, float y) = g(f(y), x);

  h(4, 5);
}

You cannot dynamically define functions. And that is the fundamental difference between functional programming and procedural programming.

In functional programming, functions can be thrown around, created, destroyed, composed, etc. They're no different from any other construct; they're just like an integer, a float, or an object.

So, back to that question: what would it mean for C++ if you could do this? Forget the fact that we defined this all as math so far; it's now just C++ function calls. In fact, the math stuff is C++ function calls. After all, operator +, *, etc will call functions when provided with objects for operands. So even those are function calls.

Now that you understand what functional programming is, next time we'll discuss what you could do with it if it worked in C++. In the third article, we'll discuss, well, turning this from an academic "what if" into the truth: that C++ is very capable of all of this. Once you use the right library, of course.