Archive

Posts Tagged ‘C++0x’

Linq to C++ (or something much better)

October 31, 2011 9 comments

A really long time ago (26th Jan 2009 to be exact), I got excited about lambdas in C++0x, and the idea of bringing a Linq-like lazily-evaluated sequence filtering system to C++. I wrote a blog post about this idea partly as a pedagogical exercise in explaining the parallels/divergences in how an iteratable sequence is represented in C++ and C#.

Whenever I’m asked if this would make sense as a real library, I’ve replied that in the real world it would make much more sense to build on the stuff in Boost, especially the range library.

And guess what? At that very moment someone was already working on it (only with a far more elegant, extensible interface), and the following month a set of extensions to range were put up for review, and were accepted… then a long time passed (they’re very careful) until summer of 2010, when finally the new features were released in Boost 1.43.

I only discovered this just now. People still seem to be finding that old blog post, so it only seems proper to get up-to-date. My first stab looked like this:

#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/adaptor/filtered.hpp>
#include <boost/range/adaptor/transformed.hpp>

#include <boost/lexical_cast.hpp>

#include <vector>
#include <iostream>
#include <string>

int main()
{
	using namespace boost::adaptors;

	std::vector<int> numbers;
	numbers.push_back(0);
	numbers.push_back(-1);
	numbers.push_back(4);
	numbers.push_back(-3);
	numbers.push_back(5);
	numbers.push_back(8);
	numbers.push_back(-2);
	
	auto quoted_positives = numbers 
		| filtered([] (int n) { return n >= 0; })
		| transformed([] (int x) { 
                    return "\"" + boost::lexical_cast<std::string>(x) + "\""; 
                  });

	boost::for_each(quoted_positives, [] (std::string n) { 
            std::cout << n << std::endl; 
        });
	return 0;
}

As you can see, the key is the use of operator| to make a piping syntax, so that we can naturally read from left to right (you may have seen the same approach used in F#). So I start with a vector of plain integers called numbers, I then pipe that through the filtered adaptor so as to get just the positives (corresponding to Where in Linq), and finally through the transformed adaptor to turn each positive into a quoted string (corresponding to map in most functional frameworks and to Select in Linq).

Except… it doesn’t work.

The problem is that boost is not yet entirely C++11 lambda-friendly. It’s unfortunate that the boost documentation (and other online information) is peppered with the word lambda signifying something else, so I may just be missing something. But the gist of the problem appears to be that transformed wants a functor with a member type called result_type. So you are supposed to write something like this:

struct quote
{
    typedef std::string result_type;

    std::string operator()(int x) const 
    {
        return "\"" + boost::lexical_cast<std::string>(x) + "\""; 
    }
};

C++11 lambdas don’t have that result_type inside them, so they don’t directly fit. It goes without saying that we don’t like this, because the whole point of lambdas is to avoid writing a separate class somewhere else.

It is surely possible to extend boost’s function_traits so that they can reflect on lambdas. In the past they have not been written to work on general functors because a functor can have multiple overloads of operator(), so you are required to manually pick one of those members before you ask questions. But this position is no longer sensible (if indeed it ever was). The majority of functors will now be lambdas, with a single overload of operator(), and it is (as we can see from this example) perfectly reasonable to want to know the return type of that single overload. A lambda is an alternative to a plain function, and whatever is useful for a function will be useful for a lambda.

But in the meantime, it is interesting to see how many hoops we have to jump through to make the above sample code work as expected.

If you read my last update on this sordid subject you’ll know that I don’t want to have to state the type of something that can be inferred, so I’m not going to be satisfied by a wrapper template that just adds a manually specified result_type member to my lambda. Ugh! It must be inferred automatically.

Fortunately this is just a matter of using a few simple steps in metaprogramming. Firstly, a template designed to match a member function:

template <class T>
struct mem_fun_traits { };

Of course in this general form it will match anything. But we’ll only bother to specialise it for one case: a pointer to a const member function that accepts one argument:

template <class R, class C, class A>
struct mem_fun_traits<R (C::*)(A) const> 
{
    typedef R result_type;
    typedef A argument_type;
};

So if you pass mem_fun_traits the type of a pointer to the operator() within a lambda, you know what it accepts and returns. But how do you get that type argument? With decltype that’s easy-peasy:

template<typename T>
struct functor_member {
    typedef decltype(&T::operator()) type;
};

Armed with these tools, we can write a traits class for our simple one-argument, single-overload functors (and hence, by an extraordinary coincidence, also for C++11 lambdas):

template <class F>
struct functor_traits
{
    typedef typename functor_member<F>::type member_t;
    typedef mem_fun_traits<member_t> traits;

    typedef typename traits::result_type result_type;
    typedef typename traits::argument_type argument_type;
};

This is the thing that should be integrated into boost’s function_traits, to make lambdas work as true replacements for functions. I’m sure someone’s working on it.

In the event that this doesn’t happen, we can shoehorn it together anyway by making a function template that adds type metadata to any single-argument functor:

template <class F>
class functor_with_traits_t
{
    F f;

public:
    functor_with_traits_t(F f_) : f(f_) {}

    typedef typename functor_traits<F>::result_type result_type;
    typedef typename functor_traits<F>::argument_type argument_type;

    result_type operator()(argument_type a) const { return f(a); }
};

template <class F>
inline functor_with_traits_t<F> functor_with_traits(F f) { return functor_with_traits_t<F>(f); }

So if you have a plain old lambda like this:

auto l = [] (int x) { 
    return "\"" + boost::lexical_cast<std::string>(x) + "\""; 
};

You can “fix” it to have type metadata like so:

auto l2 = functor_with_traits(l);

This makes it compatible with boost’s transformed! Although manually putting in that wrapper each time is pretty tedious. We can work around that by defining our own adapter (let’s call it selected in slavish imitation of Linq) that just plugs together functor_with_traits and transformed. Sounds simple, though as always the difficulty is in figuring out the types:

template <class F>
inline um... selected(F f)
{
    return boost::adaptors::transformed(functor_with_traits(f)); 
}

The um... is “whatever type we’re returning”. Wouldn’t it be nice if we could put auto there? Well, we almost can: decltype to the rescue as usual:

decltype(
    boost::adaptors::transformed(
        functor_with_traits(make_ref<F>())
    )
)

That is: give me the type that would be returned if I called transformed, passing it the result of a call to functor_with_traits, passing it an F. Of course we can’t assume that F can be default constructed, hence the use of that funny make_ref function that always comes in handy with decltype.

So our completed adaptor is:

template <class F>
decltype(
    boost::adaptors::transformed(
        functor_with_traits(make_ref<F>())
    )
)
selected(F f)
{
    return boost::adaptors::transformed(functor_with_traits(f)); 
}

We can use selected in place of transformed and everything is hunky dory. Full example:

#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/adaptor/filtered.hpp>
#include <boost/range/adaptor/transformed.hpp>

#include <boost/lexical_cast.hpp>

#include <vector>
#include <iostream>
#include <string>

template <class T>
T *make_ptr() { return (T *)0; }

template <class T>
const T &make_ref() { return *(make_ptr<T>()); }

template <class T>
struct mem_fun_traits { };

template <class R, class C, class A>
struct mem_fun_traits<R (C::*)(A) const> 
{
  typedef R result_type;
  typedef A argument_type;
};

template<typename T>
struct functor_member {
    typedef decltype(&T::operator()) type;
};

template <class F>
struct functor_traits
{
	typedef typename functor_member<F>::type member_t;
	typedef mem_fun_traits<member_t> traits;

	typedef typename traits::result_type result_type;
	typedef typename traits::argument_type argument_type;
};

template <class F>
class functor_with_traits_t
{
	F f;

public:
	functor_with_traits_t(F f_) : f(f_) {}

	typedef typename functor_traits<F>::result_type result_type;
	typedef typename functor_traits<F>::argument_type argument_type;

	result_type operator()(argument_type a) const { return f(a); }
};

template <class F>
functor_with_traits_t<F> functor_with_traits(F f) { return functor_with_traits_t<F>(f); }

template <class F>
decltype(boost::adaptors::transformed(functor_with_traits(make_ref<F>()))) selected(F f)
{
	return boost::adaptors::transformed(functor_with_traits(f)); 
}

int main()
{
	using namespace boost::adaptors;

	std::vector<int> numbers;
	numbers.push_back(0);
	numbers.push_back(-1);
	numbers.push_back(4);
	numbers.push_back(-3);
	numbers.push_back(5);
	numbers.push_back(8);
	numbers.push_back(-2);
	
	auto quoted_positives = numbers 
		| filtered([] (int n) { return n >= 0; })
		| selected([] (int x) { 
                    return "\"" + 
                      boost::lexical_cast<std::string>(x) +
                      "\"";
                  });

	boost::for_each(quoted_positives, [] (std::string n) {
            std::cout << n << std::endl; 
        });
	return 0;
}

(Tested on MSVC++ 16.00.40219.01 and GNU G++ 4.5.3.)

Categories: Uncategorized Tags: , , , ,

VC++16 has decltype in Beta 1 (so Linq to C++0x looks a little nicer)

May 22, 2009 8 comments

Updated 2011-10-31 – Major update based on boost range adaptors!!

A while ago I wrote up a little demo of using lambdas to implement convenient lazy list comprehension in C++0x, but at the time the VC++ compiler I was using lacked decltype, and I found a need for it.

I just tried out the Beta 1 that was released this week, and it has decltype, so here’s the updated sample:

Read more…

Categories: C++0x Tags: