The Lazy Programmer

November 18, 2008

Functional C++

Filed under: C#,Programming — ferruccio @ 9:56 pm
Tags: , ,

It’s been awhile since my last post. It was near the end of a product shipping cycle and, well, you know how that goes. Then I got a bit addicted to stackoverflow and spent way too much time each night reading and answering  questions. Eventually, I started a couple of side-projects which may eventually yield something interesting to write about.

Anyway, a little over a month ago, I answered a question on Stack Overflow titled “What is the one programming skill you always wanted to master but haven’t had time?” I didn’t have to think much to come up with an answer to that: Functional Programming.

I understand some of the fundamental concepts behind functional programming and occasionally I dabble a bit with LISP or I read a bit more of SICP but the practical applications of FP have been elusive to me.

I was amazed by how many votes that simple answer received.  Apparently, I’m not the only one who felt that way. Who knew?

C++ does not support functional programming directly. In order to support a functional style of programming, the STL introduced the concept of a functor, which is an object that represents a function. All that really means is that a functor is an object which implements operator().

Like most people, my initial use of functors was as a callback mechanism to various STL algorithms. Nothing more than a fancy function pointer mechanism. Suppose you had a list of integers and you wanted to find the first zero value in the list. You could always write a loop but you could also use the STL find_if algorithm:

#include <list>
#include <algorithm>
using namespace std;

void main()
{
    list<int> l;

    // fill l...

    struct not_zero
    {
        bool operator() (int value) { return value != 0; }
    };

    list<int>::iterator li = find_if(l.begin(), l.end(), not_zero());
}

So far this is the sort or run-of-the-mill C++ that I’ve gotten used to writing. I like to keep a link to this STL reference on my browser’s toolbar. One day, I happened to be looking at the documentation for the binary_compose function. On that page there is this odd-looking example:

list<int> L;
...
list<int>::iterator in_range =
     find_if(L.begin(), L.end(),
             compose2(logical_and<bool>(),
                      bind2nd(greater_equal<int>(), 1),
                      bind2nd(less_equal<int>(), 10)));
I stared at it for awhile. I certainly looks interesting, but I couldn’t help but think: “why would anyone do it that way?” If I wanted to search for the first value between one and ten, I would simply use the same model as the not_zero functor I described earlier:
#include <list>
#include <algorithm>
using namespace std;

void main()
{
    list<int> l;

    // fill l...

    struct between_1_and_10
    {
        bool operator() (int value) { return value >= 1 && value <= 10; }
    };

    list<int>::iterator li = find_if(l.begin(), l.end(), between_1_and_10());
}

Seems like a lot less trouble, no?

Then it dawned on me.

Duh!

Of course you wouldn’t do it that way! That would be stupid!
Well, “stupid” is a little harsh. Let’s just call it unnecessarily complex. The problem is that examples are usually short by necessity and don’t always represent the best way to do things in real code. I should have realized that at the time.

But, what you could do is compose a functor in pieces. Suppose, for example, that the expression to evaluate (1 <= x and x <= 10 in this case) came from an external source, such as a configuration file. Lets also suppose that the value that needed to be checked (x) could change at any time.

Now every time you need to see if the provided expression is true, you could call a parser, which would parse the expression and the evaluate it. This approach has two problems:

  1. You’re constantly parsing the same expressions over and over again, which is wasteful.
  2. The parser becomes tightly coupled with the evaluation logic.

Instead, what you could do is have the parser generate functors at each node of the expression tree. So given our example (1 <= x and x <= 10) when the parser processes (1 <= x), would generate a functor like so:

int x = 0;

unary_function<int, bool> ge = bind2nd(greater_equal<int>(), x);
When the parser calls ge(), it will return a unary functor which returns true if x is greater than or equal to one.
An le functor would work the same way when the parser ran across (x  <= 10):
unary_function<int, bool> le = bind2nd(less_equal<int>(), x);

And finally, the parser would need to combine those two generated functors when it parsed the “and” operator. Except that, I couldn’t figure out how to do it with the STL. It turns out the compose2() function described in that STL reference I mentioned earlier is an sgi (Silicon Graphics, Inc.) extension. Visual C++ had no idea what it was.

No problem, I’ll use Boost instead. I was hoping to use the STL exclusively for this example, but it turns out Boost has some pretty nice functional programming support. You need to add a couple of #includes:

#include <boost/bind.hpp>
#include <boost/function.hpp>
using namespace boost;

and the functors can now be written as:

int x = 0;

function<bool()> ge = bind(greater_equal<int>(), x, 1);
function<bool()> le = bind(less_equal<int>(), x, 10);
function<bool()> test = bind(logical_and<bool>(), bind(ge), bind(le));

If you call test() at this point, it will return false, indicating that 0 is not between 1 and 10.
Set x to a new value after the test() functor has been built and we run into a little problem:

int x = 0;
function<bool()> ge = bind(greater_equal<int>(), x, 1);
function<bool()> le = bind(less_equal<int>(), x, 10);
function<bool()> test = bind(logical_and<bool>(), bind(ge), bind(le));

x = 5;
Call test() after setting x to 5 and it will still return false. What’s going on?
The problem is that the call to bind() will bind ge to the value of x at the time of the bind() call. No matter what happens to  after that, ge will still only see that initial value of x.
The solution is to use the boost ref() function to create a reference to x at the time of the binding.
function<bool()> ge = bind(greater_equal<int>(), ref(x), 1);
function<bool()> le = bind(less_equal<int>(), ref(x), 10);
function<bool()> test = bind(logical_and<bool>(), bind(ge), bind(le));

Now, calling test() will always use the current value of x when called. At this point our hypothetical program would simply need to call test() whenever it needed to know if x met our condition. If the condition was dynamically generated, it doesn’t need to re-evaluate the input to its parser.

That’s it for now. Writing about it has made functional composition and this small application using Boost clearer in my mind. I hope it was of some value to you. If you know or figure out how to do it using STL functions only, let me know. I will still be using Boost for this type of thing, but I’d love to see an STL solution.

Advertisements

2 Comments

  1. Do you even need stl to do functional programming?
    Most lisps are actually written in plain c.

    you already have recursion in expressions and functions. You don’t need much more… Do you ?

    Comment by tinku99 — December 16, 2008 @ 7:37 pm

  2. Thanks for the post: I didn’t know logical_and and it seems really useful and powerful to me.
    PS: in these cases, I prefer lambdas over bind but, of course, it wasn’t the purpose of your post (so my apologies)… ^^’
    int x = 0;
    boost::function t = _1 > 1 && _1 < 10;
    cout << t(x) << endl;
    x = 5;
    cout << t(x) << endl;

    Comment by jp — April 22, 2009 @ 1:45 am


RSS feed for comments on this post.

Blog at WordPress.com.

%d bloggers like this: