Blag

He's not dead, he's resting

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

In parts one and two, we built up a OneOf holder that could contain one of a number of different types of values, and developed a flexible variation on the visitor pattern to do things with the underlying values. Now we’ll adapt that to use lambdas.

We’ll need some helper classes so we can figure out the parameter types and return type of a lambda. A lambda itself is just fancy syntax for a struct with an operator(), so combined with the new decltype operator we can do this:

template <typename Type_>
struct ParameterTypes;

template <typename C_, typename R_, typename P_>
struct ParameterTypes<R_ (C_::*)(P_)>
{
    typedef P_ FirstParameterType;
    typedef R_ ReturnType;
};

template <typename C_, typename R_, typename P_>
struct ParameterTypes<R_ (C_::*)(P_) const>
{
    typedef P_ FirstParameterType;
    typedef R_ ReturnType;
};

template <typename Lambda_>
struct LambdaParameterTypes
{
    typedef typename ParameterTypes<decltype(&Lambda_::operator())>::FirstParameterType FirstParameterType;
    typedef typename ParameterTypes<decltype(&Lambda_::operator())>::ReturnType ReturnType;
};

Then we can use this to implement an adapter that turns a number of lambda functions into a visitable class. For starters we’ll ignore the return type:

template <typename... Funcs_>
struct LambdaVisitor;

template <>
struct LambdaVisitor<>
{
    void visit(struct NotReallyAType);
};

template <typename Func_, typename... Rest_>
struct LambdaVisitor<Func_, Rest_...> :
    LambdaVisitor<Rest_...>
{
    Func_ & func;

    LambdaVisitor(Func_ & f, Rest_ & ... rest) :
        LambdaVisitor<Rest_...>(rest...),
        func(f)
    {
    }

    void visit(typename LambdaParameterTypes<Func_>::FirstParameterType & v)
    {
        func(v);
    }

    using LambdaVisitor<Rest_...>::visit;
};

Note the using statement, so all the visit methods defined have equal visibility for overload resolution. Also note how we define a dummy visit method in the base class, since it’s illegal to using something that doesn’t exist.

Incidentally, so far as I can see we have to use the “lots of inheritance” technique here. We can’t inherit using the ... operator, since there doesn’t seem to be a way of applying the ... operator to a using statement. Thus we can’t quite do something like:

template <typename Func_>
struct LambdaVisitorVisit
{
    Func_ func;

    LambdaVisitorVisit(Func_ & f) :
        func(f)
    {
    }

    void visit(typename LambdaParameterTypes<Func_>::FirstParameterType & v)
    {
        func(v);
    }
};

template <typename... Funcs_>
struct LambdaVisitor :
    LambdaVisitorVisit<Funcs_>...
{
    LambdaVisitor(Funcs_ & ... funcs) :
        LambdaVisitorVisit<Funcs_>(funcs)...
    {
    }

    /* Can't do this: */
    using LambdaVisitorVisit<Funcs_>::visit...;
};

I’m not sure whether this is an intentional omission from the standard, or an oversight, or whether it’s just not considered useful.

That aside, now we just have to concoct the when function:

template <typename Val_, typename... Funcs_>
void when(Val_ && val, Funcs_ && ... funcs)
{
    accept(val, LambdaVisitor<Funcs_...>(funcs...));
}

And here we go:

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

    when(s,
            [] (int & x)               { std::cout << "int " << ++x << std::endl; },
            [] (const std::string & x) { std::cout << "string " << x << std::endl; }
        );

    const OneOf<int, std::string> t(std::string("monkey"));

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

    return EXIT_SUCCESS;
}

What about return types? We could switch to using when_returning, but there’s another option: we could use the return type of the first lambda as our return type instead.

template <typename Result_, typename... Funcs_>
struct LambdaVisitor;

template <typename Result_>
struct LambdaVisitor<Result_>
{
    void visit(struct NotReallyAType);
};

template <typename Result_, typename Func_, typename... Rest_>
struct LambdaVisitor<Result_, Func_, Rest_...> :
    LambdaVisitor<Result_, Rest_...>
{
    Func_ & func;

    LambdaVisitor(Func_ & f, Rest_ & ... rest) :
        LambdaVisitor<Result_, Rest_...>(rest...),
        func(f)
    {
    }

    Result_ visit(typename LambdaParameterTypes<Func_>::FirstParameterType & v)
    {
        return func(v);
    }

    using LambdaVisitor<Result_, Rest_...>::visit;
};

template <typename Val_, typename FirstFunc_, typename... Rest_>
typename LambdaParameterTypes<FirstFunc_>::ReturnType
when(Val_ && val, FirstFunc_ && first_func, Rest_ && ... rest)
{
    return accept_returning<typename LambdaParameterTypes<FirstFunc_>::ReturnType>(
            val,
            LambdaVisitor<typename LambdaParameterTypes<FirstFunc_>::ReturnType, FirstFunc_, Rest_...>(first_func, rest...));
}

And using it:

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

    std::cout << when(s,
            [] (const int x)           { return x; },
            [] (const std::string & x) { return x.length(); }
        ) << std::endl;

    return EXIT_SUCCESS;
}

There we have it: a useful, highly generic alternative to visitors that makes use of lambdas. The code in full:

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

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;
};

template <typename Type_>
struct ParameterTypes;

template <typename C_, typename R_, typename P_>
struct ParameterTypes<R_ (C_::*)(P_)>
{
    typedef P_ FirstParameterType;
    typedef R_ ReturnType;
};

template <typename C_, typename R_, typename P_>
struct ParameterTypes<R_ (C_::*)(P_) const>
{
    typedef P_ FirstParameterType;
    typedef R_ ReturnType;
};

template <typename Lambda_>
struct LambdaParameterTypes
{
    typedef typename ParameterTypes<decltype(&Lambda_::operator())>::FirstParameterType FirstParameterType;
    typedef typename ParameterTypes<decltype(&Lambda_::operator())>::ReturnType ReturnType;
};

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

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

template <typename Visitor_, typename Underlying_, typename Result_, typename... Types_>
struct OneOfVisitorWrapperVisit;

template <typename Visitor_, typename Underlying_, typename Result_>
struct OneOfVisitorWrapperVisit<Visitor_, Underlying_, Result_> :
    Visitor_
{
    Underlying_ & underlying;
    std::function<Result_ ()> execute;

    OneOfVisitorWrapperVisit(Underlying_ & u) :
        underlying(u)
    {
    }
};

template <typename Visitor_, typename Underlying_, typename Result_, typename Type_, typename... Rest_>
struct OneOfVisitorWrapperVisit<Visitor_, Underlying_, Result_, Type_, Rest_...> :
    OneOfVisitorWrapperVisit<Visitor_, Underlying_, Result_, Rest_...>
{
    OneOfVisitorWrapperVisit(Underlying_ & u) :
        OneOfVisitorWrapperVisit<Visitor_, Underlying_, Result_, Rest_...>(u)
    {
    }

    Result_ visit_returning(Type_ & t)
    {
        return this->underlying.visit(t);
    }

    virtual void visit(Type_ & t)
    {
        this->execute = std::bind(&OneOfVisitorWrapperVisit::visit_returning, this, std::ref(t));
    }
};

template <typename Underlying_, typename Result_, typename... Types_>
struct OneOfVisitorWrapper :
    OneOfVisitorWrapperVisit<OneOfVisitor<Types_...>, Underlying_, Result_, Types_...>
{
    OneOfVisitorWrapper(Underlying_ & u) :
        OneOfVisitorWrapperVisit<OneOfVisitor<Types_...>, Underlying_, Result_, Types_...>(u)
    {
    }
};

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

    virtual void accept(OneOfVisitor<Types_...> &) = 0;
    virtual void accept(OneOfVisitor<const Types_...> &) const = 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);
    }

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

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

    public:
        template <typename Type_>
        OneOf(const Type_ & value) :
            _value(new OneOfValue<typename SelectOneOfType<Type_, Types_...>::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<typename SelectOneOfType<Type_, Types_...>::Type, Types_...>{value});
            return *this;
        }

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

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

        OneOfValueBase<Types_...> & value()
        {
            return *_value;
        }

        const OneOfValueBase<Types_...> & value() const
        {
            return *_value;
        }
};

template <typename Visitor_, typename Result_, typename OneOf_>
struct OneOfVisitorWrapperTypeFinder;

template <typename Visitor_, typename Result_, typename... Types_>
struct OneOfVisitorWrapperTypeFinder<Visitor_, Result_, const OneOf<Types_...> &>
{
    typedef OneOfVisitorWrapper<Visitor_, Result_, const Types_...> Type;
};

template <typename Visitor_, typename Result_, typename... Types_>
struct OneOfVisitorWrapperTypeFinder<Visitor_, Result_, OneOf<Types_...> &>
{
    typedef OneOfVisitorWrapper<Visitor_, Result_, Types_...> Type;
};

template <typename Result_, typename OneOf_, typename Visitor_>
Result_
accept_returning(OneOf_ && one_of, Visitor_ && visitor)
{
    typename OneOfVisitorWrapperTypeFinder<Visitor_, Result_, OneOf_>::Type visitor_wrapper(visitor);
    one_of.value().accept(visitor_wrapper);
    return visitor_wrapper.execute();
}

template <typename OneOf_, typename Visitor_>
void accept(OneOf_ && one_of, Visitor_ && visitor)
{
    accept_returning<void>(one_of, visitor);
}

template <typename Result_, typename... Funcs_>
struct LambdaVisitor;

template <typename Result_>
struct LambdaVisitor<Result_>
{
    void visit(struct NotReallyAType);
};

template <typename Result_, typename Func_, typename... Rest_>
struct LambdaVisitor<Result_, Func_, Rest_...> :
    LambdaVisitor<Result_, Rest_...>
{
    Func_ & func;

    LambdaVisitor(Func_ & f, Rest_ & ... rest) :
        LambdaVisitor<Result_, Rest_...>(rest...),
        func(f)
    {
    }

    Result_ visit(typename LambdaParameterTypes<Func_>::FirstParameterType & v)
    {
        return func(v);
    }

    using LambdaVisitor<Result_, Rest_...>::visit;
};

template <typename Val_, typename FirstFunc_, typename... Rest_>
typename LambdaParameterTypes<FirstFunc_>::ReturnType
when(Val_ && val, FirstFunc_ && first_func, Rest_ && ... rest)
{
    return accept_returning<typename LambdaParameterTypes<FirstFunc_>::ReturnType>(
            val,
            LambdaVisitor<typename LambdaParameterTypes<FirstFunc_>::ReturnType, FirstFunc_, Rest_...>(first_func, rest...));
}

In part four we’ll start do some clever things with the return type, mostly because we can, rather than because it’s definitely useful.

Advertisements

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

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

  2. Crazy Eddie June 25, 2011 at 12:32 am

    I’m checking this out for my own kind of visitor framework. I extended your param fetcher to encompass functions:

    
    template < typename Fun >
    struct param_type
      : std::remove_reference
        <
          typename boost::mpl::back
          <
            typename boost::function_types::parameter_types<Fun>::type
          >::type
        >
    {};
    
    template < typename X >
    struct functor_operator_type
    {
      typedef decltype(&X::operator()) type;
    };
    
    template < typename Fun >
    struct visited_type
      : param_type
        <
          typename boost::mpl::eval_if
          <
            boost::function_types::is_callable_builtin<Fun>
          , boost::mpl::identity<Fun>
          , functor_operator_type<Fun>
          >::type
        >
    {};
    
  3. Piotr Rak October 26, 2012 at 12:19 pm

    I’ve noticed, that is pretty convenient relax bit lambda parameter matching and do *second pass* when SelectOneOfType::Type would result in UnknownTypeForOneOf, but with std::is_base.

    That’s sometimes useful when some our types have common base, and lets us
    void(OneOf& b)
    {
    when(b,
    [] (B1&) { }, // handles B1
    [] (int&) { } // handle int
    [] (A&) { } // handles B2 or B3
    );
    }

    while still omitting last lambda function in example leads to compilation error, when we want it to be.

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