Blag

He's not dead, he's resting

Generic Lambda Visitors, or Writing Haskell in C++0x (Part 1)

A good FORTRAN programmer can write FORTRAN in any language. Now, I present Haskell written in C++0x!

struct Base { };
struct FirstDerived : Base { };
struct SecondDerived : Base { };
struct ThirdDerived : Base { };

int main(int, char *[])
{
    OneOf<int, std::string, FirstDerived, SecondDerived, ThirdDerived> s(123), t(std::string("monkey"));

    when(t,
            [] (int x)                   { std::cout << "t is int " << x << std::endl; },
            [] (const std::string & x)   { std::cout << "t is string " << x << std::endl; },
            [] (const Base &)            { std::cout << "t is a Base subclass" << std::endl; },
            [] (const FirstDerived &)    { std::cout << "t is Base subclass FirstDerived" << std::endl; }
        );

    s = SecondDerived();

    std::cout << when(
            when(s,
                [] (int & x)               -> std::string { return std::string(++x, 'x'); },
                [] (std::string & x)       -> int         { x.append(" spanker"); return x.length(); },
                [] (const Base &)          -> int         { return 42; },
                [] (const ThirdDerived &)  -> double      { return 3.14; }
                ),
            [] (const int x)           -> int { return x; },
            [] (const std::string & x) -> int { return x.length(); },
            [] (const double x)        -> int { return x > 3 ? 4 : 3; }
            ) << std::endl;

    return EXIT_SUCCESS;
}

Ok, that one’s rather silly. But there is a point to this: it’s a variation on the visitor pattern, with the visiting externalised rather than being a part of the classes itself. That in turn means classes can be part of different visitable hierarchies in different places — one example would be in handling Gentoo style dependency-like structures, where certain constructs make sense in certain contexts but not others (e.g. || ( ) blocks are legal in dependencies but not SRC_URI, and blockers are legal in dependencies but not provides). Rather than forcing all visitors to implement all methods, or having entirely independent hierarchies for similar things, or losing type safety, you can externalise the visiting parts.

As an added bonus, it’s a good way of getting to grips with variadic templates and type lists. The excessive return type cleverness for the second when above is of questionable real world use, but the techniques required to get it working may be of interest.

Let’s start with the bare minimum:

#include <string>
#include <memory>
#include <utility>
#include <cstdlib>

template <typename... Types_>
struct OneOfValueBase
{
    virtual ~OneOfValueBase() = 0;
};

template <typename... Types_>
OneOfValueBase<Types_...>::~OneOfValueBase() = default;

template <typename Type_, typename... Types_>
struct OneOfValue :
    OneOfValueBase<Types_...>
{
    Type_ value;

    OneOfValue(const Type_ & type) :
        value(type)
    {
    }
};

template <typename... Types_>
class OneOf
{
    private:
        std::unique_ptr<OneOfValueBase<Types_...> > _value;

    public:
        template <typename Type_>
        OneOf(const Type_ & value) :
            _value(new OneOfValue<Type_, Types_...>{value})
        {
        }

        OneOf(const OneOf & other) = delete;

        OneOf(OneOf && other) :
            _value(std::move(other._value))
        {
        }

        template <typename Type_>
        OneOf & operator= (const Type_ & value)
        {
            _value.reset(new OneOfValue<Type_, Types_...>{value});
            return *this;
        }

        OneOf & operator= (const OneOf & other) = delete;

        OneOf & operator= (OneOf && other)
        {
            _value = std::move(other._value);
            return *this;
        }
};

int main(int, char *[])
{
    OneOf<int, std::string> s(123);
    s = std::string("monkey");

    return EXIT_SUCCESS;
}

Note that we’ve made the type moveable but not copyable or default constructible; extending the type to clone its value and to support an uninitialised state isn’t particularly difficult, but isn’t necessary for what we’re after.

We have a problem, though:

    OneOf<int, std::string> s(123);
    s = 1.23;

Oops. So we need a way of checking whether a particular type is in a typelist:

struct UnknownTypeForOneOf;

template <typename Want_, typename... Types_>
struct SelectOneOfType;

template <typename Want_>
struct SelectOneOfType<Want_>
{
    typedef UnknownTypeForOneOf Type;
};

template <typename Want_, typename Try_, typename... Rest_>
struct SelectOneOfType<Want_, Try_, Rest_...>
{
    typedef typename std::conditional<
        std::is_same<Want_, Try_>::value,
        Try_,
        typename SelectOneOfType<Want_, Rest_...>::Type
            >::type Type;
};

Then we can make sure we’re only creating valid children:

template <typename... Types_>
class OneOf
{
    public:
        template <typename Type_>
        OneOf(const Type_ & value) :
            _value(new OneOfValue<typename SelectOneOfType<Type_, Types_...>::Type, Types_...>{value})
        {
        }

        template <typename Type_>
        OneOf & operator= (const Type_ & value)
        {
            _value.reset(new OneOfValue<typename SelectOneOfType<Type_, Types_...>::Type, Types_...>{value});
            return *this;
        }
};

Yay. But none of this is much use if all we can do is create and assign legal things to our values. We need to be able to do things to the underlying value too. Let’s start with a very simple visitor pattern. We need a visitor base class:

template <typename Type_>
struct OneOfVisitorVisit
{
    virtual void visit(const Type_ &) = 0;
};

template <typename... Types_>
struct OneOfVisitor :
    OneOfVisitorVisit<Types_>...
{
};

We need to make our value holders able to accept a visitor:

template <typename... Types_>
struct OneOfValueBase
{
    virtual ~OneOfValueBase() = 0;

    virtual void accept(OneOfVisitor<Types_...> &) = 0;
};

template <typename... Types_>
OneOfValueBase<Types_...>::~OneOfValueBase() = default;

template <typename Type_, typename... Types_>
struct OneOfValue :
    OneOfValueBase<Types_...>
{
    Type_ value;

    OneOfValue(const Type_ & type) :
        value(type)
    {
    }

    virtual void accept(OneOfVisitor<Types_...> & visitor)
    {
        static_cast<OneOfVisitorVisit<Type_> &>(visitor).visit(value);
    }
};

And for convenience we’ll put an accept method in OneOf too:

template <typename... Types_>
class OneOf
{
    public:
        void accept(OneOfVisitor<Types_...> & visitor) const
        {
            _value->accept(visitor);
        }
};

Now we can try it out:

struct IntStringVisitor :
    OneOfVisitor<int, std::string>
{
    virtual void visit(const int & x)
    {
        std::cout << "int " << x << std::endl;
    }

    virtual void visit(const std::string & x)
    {
        std::cout << "string " << x << std::endl;
    }
};

int main(int, char *[])
{
    OneOf<int, std::string> s(123);
    s = std::string("monkey");

    IntStringVisitor visitor;
    s.accept(visitor);

    return EXIT_SUCCESS;
}

In part two, we’ll make visitors more flexible.

Advertisements

2 responses to “Generic Lambda Visitors, or Writing Haskell in C++0x (Part 1)

  1. Pingback: Generic Lambda Visitors, or Writing Haskell in C++0x (Part 2) « Ciaran McCreesh’s Blag

  2. Pingback: Generic Lambda Visitors, or Writing Haskell in C++0x (Part 3) « Ciaran McCreesh’s Blag

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s