Visit boost variant with extra arguments

Question

I am trying to implement the Tseitin transformation over boolean formulas. The idea is that you transform boolean formulas in CNF, using transformation rules. For example, if the formula f = l OR r, we assign to each formula a new variable, let's say v_f, v_l and v_r, and we transform f = l OR r into (!v_f OR v_l OR v_r) AND (v_f OR !v_l) AND (v_f OR !v_r).

I use something like (v_f, v_l and v_r are replaced by p, p1 and p2. m is a variable that permits us to now what next variable we can use) :

int m = 0;
std::vector<std::vector<int> > formules;

struct op_or  {};
struct op_and {};
struct op_not {};
struct op_impl {};

typedef int var;
template <typename tag> struct binop;
template <typename tag> struct unop;

typedef boost::variant<var, 
               boost::recursive_wrapper<unop <op_not> >, 
               boost::recursive_wrapper<binop<op_and> >,
               boost::recursive_wrapper<binop<op_or> >,
               boost::recursive_wrapper<binop<op_impl> >
        > expr;

template <typename tag> struct binop 
{ 
    explicit binop(const expr& l, const expr& r) : oper1(l), oper2(r) { }
    expr oper1, oper2; 
};

template <typename tag> struct unop  
{ 
    explicit unop(const expr& o) : oper1(o) { }
    expr oper1; 
};

struct tseitin : boost::static_visitor<void>
{
    tseitin() {}

    void operator()(const var& v, int p = 0) {}
    void operator()(const binop<op_and>& b, int p = m++) { proceed(0, b.oper1, b.oper2, p); }
    void operator()(const binop<op_or>& b, int p = m++) { proceed(1, b.oper1, b.oper2, p);}
    void operator()(const unop<op_not>& u, int p = m++) {}


    void proceed(int nop, const expr& l, const expr& r, int p)
    {
        int p1 = m+1;
        int p2 = m+2;
        m += 2;
        // Do the transformation
        recurse(l, p1);
        recurse(r, p2);
    }

private:
    template<typename T, typename U>
    bool recurse(T const& v, U const& p) 
        { return boost::apply_visitor(*this, v, p); }

};

And in the main, I call this transformation with : boost::apply_visitor(tseitin(), result, 0);

But I encounter errors like : error: no matching function for call to ‘apply_visitor(tseitin, expr&, int)’ boost::apply_visitor(tseitin(), result, 0); And : error: request for member ‘apply_visitor’ in ‘visitable’, which is of non-class type ‘const int’

I don't really understand the error, do you have any ideas ?

As you may notice, I used How to calculate boolean expression in Spirit and boost spirit tutorial to implement the operators over the transformation.

I you need the whole code, let me now.

Thanks in advance !

Answer 1

I don't really understand the error, do you have any ideas ?

You are calling the binary version of boost::variant::apply_visitor. But you pass it a variant and an int. An int, as the error message announces, is not visitable.

To make this work, just bind the argument:

boost::apply_visitor(boost::bind(tseitin(), _1, 0), result);

This means that the _1 placeholder will receive the variant element and the second parameter is passed through.

You will also want to carry this through in recurse:

bool recurse(T const& v, U const& p) 
    { return boost::apply_visitor(boost::bind(*this, _1, p), v); }

Update

Here's the demo of the linked answer, but using extra bound arguments instead of a stateful printer functor:

struct printer : boost::static_visitor<void>
{
    //
    void operator()(std::ostream& os, const var& v) const { os << v; }

    void operator()(std::ostream& os, const binop<op_and>& b) const { print(os, " & ", b.oper1, b.oper2); }
    void operator()(std::ostream& os, const binop<op_or >& b) const { print(os, " | ", b.oper1, b.oper2); }

    void print(std::ostream& os, const std::string& op, const expr& l, const expr& r) const
    {
        os << "(";
        boost::apply_visitor(boost::bind(*this, boost::ref(os), _1), l);
        os << op;
        boost::apply_visitor(boost::bind(*this, boost::ref(os), _1), r);
        os << ")";
    }

    void operator()(std::ostream& os, const unop<op_not>& u) const
    {
        os << "(";
        os << "!";
        boost::apply_visitor(boost::bind(*this, boost::ref(os), _1), u.oper1);
        os << ")";
    }
};

Full Code:

Live On Coliru

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/variant/recursive_wrapper.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/bind.hpp>

namespace qi    = boost::spirit::qi;
namespace phx   = boost::phoenix;

struct op_or  {};
struct op_and {};
struct op_not {};

typedef std::string var;
template <typename tag> struct binop;
template <typename tag> struct unop;

typedef boost::variant<var,
        boost::recursive_wrapper<unop <op_not> >,
        boost::recursive_wrapper<binop<op_and> >,
        boost::recursive_wrapper<binop<op_or> >
        > expr;

template <typename tag> struct binop
{
    explicit binop(const expr& l, const expr& r) : oper1(l), oper2(r) { }
    expr oper1, oper2;
};

template <typename tag> struct unop
{
    explicit unop(const expr& o) : oper1(o) { }
    expr oper1;
};

struct eval : boost::static_visitor<bool>
{
    eval() {}

    //
    bool operator()(const var& v) const
    {
        if (v=="T" || v=="t" || v=="true" || v=="True")
            return true;
        else if (v=="F" || v=="f" || v=="false" || v=="False")
            return false;
        return boost::lexical_cast<bool>(v);
    }

    bool operator()(const binop<op_and>& b) const
    {
        return recurse(b.oper1) && recurse(b.oper2);
    }
    bool operator()(const binop<op_or>& b) const
    {
        return recurse(b.oper1) || recurse(b.oper2);
    }
    bool operator()(const unop<op_not>& u) const
    {
        return !recurse(u.oper1);
    }

    private:
    template<typename T>
        bool recurse(T const& v) const
        { return boost::apply_visitor(*this, v); }
};

struct printer : boost::static_visitor<void>
{
    //
    void operator()(std::ostream& os, const var& v) const { os << v; }

    void operator()(std::ostream& os, const binop<op_and>& b) const { print(os, " & ", b.oper1, b.oper2); }
    void operator()(std::ostream& os, const binop<op_or >& b) const { print(os, " | ", b.oper1, b.oper2); }

    void print(std::ostream& os, const std::string& op, const expr& l, const expr& r) const
    {
        os << "(";
        boost::apply_visitor(boost::bind(*this, boost::ref(os), _1), l);
        os << op;
        boost::apply_visitor(boost::bind(*this, boost::ref(os), _1), r);
        os << ")";
    }

    void operator()(std::ostream& os, const unop<op_not>& u) const
    {
        os << "(";
        os << "!";
        boost::apply_visitor(boost::bind(*this, boost::ref(os), _1), u.oper1);
        os << ")";
    }
};

bool evaluate(const expr& e)
{ return boost::apply_visitor(eval(), e); }

std::ostream& operator<<(std::ostream& os, const expr& e)
{ boost::apply_visitor(boost::bind(printer(), boost::ref(os), _1), e); return os; }

template <typename It, typename Skipper = qi::space_type>
    struct parser : qi::grammar<It, expr(), Skipper>
{
        parser() : parser::base_type(expr_)
        {
            using namespace qi;

            expr_  = or_.alias();

            or_  = (and_ >> '|'  >> or_ ) [ _val = phx::construct<binop<op_or > >(qi::_1, qi::_2) ] | and_   [ _val = qi::_1 ];
            and_ = (not_ >> '&' >> and_)  [ _val = phx::construct<binop<op_and> >(qi::_1, qi::_2) ] | not_   [ _val = qi::_1 ];
            not_ = ('!' > simple       )  [ _val = phx::construct<unop <op_not> >(qi::_1)     ]     | simple [ _val = qi::_1 ];

            simple = (('(' > expr_ > ')') | var_);
            var_ = qi::lexeme[ +(alpha|digit) ];

            BOOST_SPIRIT_DEBUG_NODE(expr_);
            BOOST_SPIRIT_DEBUG_NODE(or_);
            BOOST_SPIRIT_DEBUG_NODE(and_);
            BOOST_SPIRIT_DEBUG_NODE(not_);
            BOOST_SPIRIT_DEBUG_NODE(simple);
            BOOST_SPIRIT_DEBUG_NODE(var_);
        }

        private:
        qi::rule<It, var() , Skipper> var_;
        qi::rule<It, expr(), Skipper> not_, and_, or_, simple, expr_;
};

int main()
{
    const std::string inputs[] = {
        std::string("true & false;"),
        std::string("true & !false;"),
        std::string("!true & false;"),
        std::string("true | false;"),
        std::string("true | !false;"),
        std::string("!true | false;"),

        std::string("T&F;"),
        std::string("T&!F;"),
        std::string("!T&F;"),
        std::string("T|F;"),
        std::string("T|!F;"),
        std::string("!T|F;"),
        std::string("") // marker
    };

    for (const std::string *i = inputs; !i->empty(); ++i)
    {
        typedef std::string::const_iterator It;
        It f(i->begin()), l(i->end());
        parser<It> p;

        try
        {
            expr result;
            bool ok = qi::phrase_parse(f,l,p > ';',qi::space,result);

            if (!ok)
                std::cerr << "invalid input\n";
            else
            {
                std::cout << "result:\t" << result << "\n";
                std::cout << "evaluated:\t" << evaluate(result) << "\n";
            }

        } catch (const qi::expectation_failure<It>& e)
        {
            std::cerr << "expectation_failure at '" << std::string(e.first, e.last) << "'\n";
        }

        if (f!=l) std::cerr << "unparsed: '" << std::string(f,l) << "'\n";
    }

    return 0;
}