Re: [boost] [proto] Review

From: Eric Niebler (eric_at_[hidden])
Date: 2008-03-06 19:54:49

Phil Endecott wrote:
> My Proto review follows.
> 
> I'll say straight away that Proto should certainly be accepted.  What 
> it provides is useful, demonstrated by its use in e.g. Spirit; I 
> suspect that even Eric will be surprised by how many and varied the 
> future applications for it will be.  The key to that wide usage will be 
> the documentation.  That that currently exists is excellent, but more 
> can only help.  Eric, why not write a book?

Thanks for the vote. Funny, Dave Jenkins also once suggested a Proto 
book. And when writing Proto's docs, I had the feeling like I was 
writing a book, because it seemed to go on forever ...

> This review is the result of about 4 hours playing.  I think I've only 
> scratched the surface of what's possible.

 From what follows, it looks like you covered 2/5 of Proto -- expression 
construction and evaluation. Proto's expression extension features 
(proto::extends<>) would be very helpful for your use case, and grammars 
and transforms would be an alternate way to solve the locking problem.

> My initial prejudice was that I would find incomprehensible error 
> messages resulting from even the smallest syntax error, making it 
> impossible for me to deviate far from the examples.  And very long 
> run-times that make the compiler swap.  

You clearly mean compile times here, not run times. I've worked hard to 
keep Proto's compile times reasonable.

> This was based on my experience 
> with Spirit a few years ago.  But I was pleasantly surprised:  I'm not 
> sure if that's me getting better at parsing the long error messages 
> that you get from heavily-templated code, or whether the compiler or 
> library had something to do with it.  Anyway, I was very pleased with 
> the amount of progress that I made in the time.

Regarding compiler errors, I've seen Proto generate some whoppers. But 
with Proto grammars, you have a tool to dramatically improve the error 
messages for the *users* of your DSEL -- define the grammar of your DSEL 
and validate expressions against the grammar at API boundaries before 
the template instantiation backtrace becomes too deep.

That only helps your users, though. You have to endure the pain on their 
behalf.

> As an example I decided to try to implement the following.  Say I have 
> a multi-threaded application with variables, mutexes and perhaps 
> condition variables bundled like this:
> 
> template <typename T>
> struct Locked {
>    T var;
>    Mutex mut;
>    Condition cond;  // maybe
> };
> 
> Locked<int> a;
> Locked<bool> b;
> 
> I'd like to be able to write something like:
> 
> b = (a==3 || a>10);
> 
> and for that to lock the mutexes belonging to a and b, evaluate the 
> expression, and then
> unlock the mutexes:
> 
> a.mut.lock();  // Or use a multiple-mutex-locking algorithm with back-off
> b.mut.lock();
> b.var = (a.var==3 || a.var>10);
> b.mut.unlock();
> a.mut.unlock();

An interesting use case. In the real world, you might have to impose a 
lock ordering, or else implement a try-lock/fall-back scheme. Tricky.

> Is that possible with Proto?  Yes!
> 
> A variation is to be able to write:
> 
> wait_until(a==3 || a>10);
> 
> That would need to lock a's mutex, evaluate the expression, and if it's 
> not true wait on the condition variable and retry.  (This gets more 
> complex with more than one variable in the expression as we don't have 
> a way to wait on any one of a set of condition variables.)
> 
> So the first thing that I need to be able to do is to build a set of 
> all the Locked<> variables in the expression.  I need to define an 
> evaluation context in which Locked<> variables return a singleton set 
> of themselves, other terminals return an empty set, and non-terminals 
> return the union of the sets returned by their operands.  I'll need to 
> change my Locked<> class slightly so that I can store a set of pointers 
> to them:
> 
> struct Locked_base {
>    Mutex mut;
>    Condtion cond; // optional
> };
> 
> template <typename T>
> struct Locked: public Locked_base {
>    T var;
> };
> 
> typedef std::set<Locked_base*> locked_var_set;
> 
> I'm not very enthusiastic about using a std::set here, since the set 
> will presumably actually be constructed and iterated through at 
> run-time, which has some overhead compared to the code with the 
> explicit mut.lock() and mut.unlock() calls above.  Is there some sort 
> of fusion-set or other metaprogramming magic that I could use?  
> Apparently there is and I'll come back to that.

Using a std::set imposes a lock ordering -- a nice feature IMO. But you 
can do without the dynamic memory allocation...

> Anyway, for now I'll define an evaluation context that builds a std::set:
> 
> struct get_locked_vars_context:
>    proto::callable_context<get_locked_vars_context const>
> {
<snip>
> };
> 
> So I can now write:
> 
> get_locked_vars_context ctx;
> locked_var_set vs = proto::eval( a==proto::as_expr(3) || b, ctx );
> // I failed to find as_expr() in the documentation.
> 
> But while I was writing that I realised that I could just store the 
> locked_var_set in the context and get much simpler code:
> 
> struct get_locked_vars_context:
>    proto::callable_context<get_locked_vars_context>
> {
>    locked_var_set var_set;
> 
>    typedef void result_type;
> 
>    template <typename T>
>    void operator()(proto::tag::terminal, Locked<T>& l) {
>      var_set.insert(&l);
>    }
> 
>    template <typename T>
>    void operator()(proto::tag::terminal, const T&) {
>    }
> 
>    template <typename Left, typename Right, typename TagT>
>    void operator()(TagT, Left& left, Right& right) {
>      proto::eval(left,*this);
>      proto::eval(right,*this);
>    }
> };

Yes, contexts are stateful ... that's part of their job. Even simpler, try:

struct get_locked_vars_context
   : proto::callable_context<
         get_locked_vars_context
       , proto::null_context
     >
{
     typedef void result_type;

     template<typename T>
     void operator()(proto::tag::terminal, Locked<T>& l)
     {
         var_set.insert(&l);
     }

     locked_var_set var_set;
};

This uses the null_context as a fall-back, which just calls proto::eval 
on each child expression. This handles n-ary expressions seamlessly.

With callable_context<>, you only need to write overloads for the 
expression types that need special handling.

> and then write:
> 
> get_locked_vars_context ctx;
> proto::eval( a==proto::as_expr(3) || b, ctx );
> locked_var_set vs = ctx.var_set;

<snip>

> struct eval_context:
>    proto::callable_context<eval_context const>
> {
>    typedef int result_type;
>    // ???? The result type for each subexpression will be different, so 
> I don't want
>    // to have to define a result_type here.  Presumably this is 
> something that I can
>    // do if I don't use the callable_context convenience, right?  How 
> should I do that?

It uses the result_of protocol, so instead of a single result_type 
typedef, you can use a nested result<> template.

>    // Use the default behaviour for everything, except that for the 
> Locked<> terminals
>    // we read the contained variable.
> 
>    template <typename T>
>    T operator()(proto::tag::terminal, Locked<T>& l) const {
>      return l.var;
>    }
> };
> 
> // Here's a function that does the locking, evaluation and unlocking:
> 
> template <typename ExprT>
> int eval_locked_expr(ExprT expr)  // same question as above about the 
> result type
> {
>    get_locked_vars_context glv_ctx;
>    proto::eval(expr, glv_ctx);
>    lock_all(glv_ctx.var_set);
>    eval_context eval_ctx;
>    int r = proto::eval(expr, eval_ctx);
>    unlock_all(glv_ctx.var_set);
>    return r;
> }
> 
> // It's used like this:
> 
> Locked<int> a;
> Locked<bool> b;
> eval_locked_expr( a==proto::as_expr(3) || b );

Nice.

> So the only thing that's missing is the actual assignment.  Proto 
> doesn't overload operator= because the language only allows it to be 
> overloaded as a member, not as a binary free function. But I can 
> overload operator= inside my Lockable<> class.  Would it be possible 
> for me to write:
> 
> proto::complicated-expr-type
> MyClass::operator=(proto::other-compilcated-type) {
>    return something...;
> }
> ?
 >
> Or maybe MyClass can inherit from proto::something and get definitions 
> of operator=, operator+= etc. etc.  Is that done or do-able?

I think you want proto::extends<>.

> I've no idea how to start coding that, but instead I can do something a 
> bit simpler for this case:
> 
> template <typename T>
> struct Locked: public Locked_base {
>    T var;
> 
>    template <typename ExprT>
>    T operator=(ExprT expr) {
>      mut.lock();
>      T r = var = eval_locked_expr(expr);
>      mut.unlock();
>      return r;
>    }
> };
> 
> Now that can be used as follows:
> 
> Locked<int> a;
> Locked<bool> b;
> Locked<bool> c;
> c = ( a==proto::as_expr(3) || b );
> 
> (There's a pretty serious flaw with this, which is that if the target 
> of the assignment also appears in the expression then it will attempt 
> to lock it twice.)
> 
> So the only thing that's needed to "perfect" that is to get rid of the 
> proto::as_expr() noise, which could be done if the 'a' in 'a==3' were a 
> proto expression.  Can I do that by adding a conversion to 
> proto::some-complicated-type in Locked<>?

If Locked used proto::extends, then a and b would be proto terminals, 
and you wouldn't need as_expr().

> Perfect.  Except that it will build and iterate through a std::set at 
> run time.  So, can I instead build and iterate through a compile-time set?

I'm sending along my take on this interesting problem. Hopefully this 
will shed some light on the other 3/5 of Proto you didn't use. :-)

> 
> I think that what I need to do is to apply the fold_tree transformation 
> to the expression to get a fusion container of the Locked<> terminals, 
> and then to fusion::for_each to do the locking and the unlocking.   
> Having never used fusion I'm not going to try that now - it's getting 
> late, and it's not going to change my vote! - but if someone would like 
> to work it out for me I'd love to see how to do it.

Below is my take on this problem. You don't want a Fusion container 
because you want to be able to sort the mutexes by their address so you 
can lock them in order. The key realization is that you know the maximum 
number of mutexes at compile time, so you can allocate a buffer for them 
on the stack. Std::sort imposes a lock ordering and std::unique 
guarantees you don't try to take any locks more than once.

More work would be needed to disable Proto's other assignment operators 
(op+=, et.al.). For that you would define a grammar and a domain. See 
the Vector example for the details.

#include <iostream>
#include <algorithm>
#include <boost/mpl/plus.hpp>
#include <boost/xpressive/proto/proto.hpp>
#include <boost/xpressive/proto/context.hpp>
#include <boost/xpressive/proto/transform.hpp>

using namespace boost;
using namespace proto;

struct Mutex
{
     Mutex() {}
     void lock() {}
     void unlock() {}
};

inline void lock_mutex(Mutex *m) { m->lock(); }
inline void unlock_mutex(Mutex *m) { m->unlock(); }

template<typename T>
struct Lockable
{
     Lockable(T const &t)
       : value(t)
       , mutex()
     {}

     typedef T value_type;
     T value;
     mutable Mutex mutex;
};

// Count of lockables in an expression.
struct CountLockable
   : or_<
         when<terminal<Lockable<_> >, mpl::int_<1>()>
       , when<terminal<_>, mpl::int_<0>()>
       , otherwise<fold<_, mpl::int_<0>(), mpl::plus<CountLockable, 
_state>()> >
     >
{};

// Fills an array of mutexes.
struct FillMutexContext
   : callable_context<FillMutexContext, null_context>
{
     FillMutexContext(Mutex **m)
       : mutexes(m)
     {}

     typedef void result_type;

     template<typename T>
     void operator()(tag::terminal, Lockable<T> const &l)
     {
         *mutexes++ = &l.mutex;
     }

     Mutex **mutexes;
};

// Evaluates a lock expression
struct EvalContext
   : callable_context<EvalContext const>
{
     template<typename Sig>
     struct result;

     template<typename This, typename T>
     struct result<This(tag::terminal, Lockable<T> const &)>
     {
         typedef T const &type;
     };

     template<typename T>
     T const &operator()(tag::terminal, Lockable<T> const &l) const
     {
         return l.value;
     }
};

template<typename T>
struct Locked
   : extends<typename terminal<Lockable<T> >::type, Locked<T> >
{
     explicit Locked(T const &t = T())
       : extends<typename terminal<Lockable<T> >::type, Locked<T> >(
             terminal<Lockable<T> >::type::make(Lockable<T>(t))
         )
     {}

     template<typename Expr>
     Locked &operator=(Expr const &expr)
     {
         static int const cntMutexes = CountLockable::result<void(Expr, 
int, int)>::type::value + 1;
         Mutex *mutexes[cntMutexes] = {&proto::arg(*this).mutex};
         // Write the addresses of all the mutexes into the array
         FillMutexContext filler(mutexes + 1);
         proto::eval(expr, filler);
         // sort the array and make it unique
         std::sort(mutexes, mutexes + cntMutexes);
         Mutex **end = std::unique(mutexes, mutexes + cntMutexes);
         // lock all the mutexes
         std::for_each(mutexes, end, lock_mutex);
         // evaluate the expression and do the assignment
         this->get() = proto::eval(expr, EvalContext());
         std::for_each(mutexes, end, unlock_mutex);
         return *this;
     }

     T &get()                { return proto::arg(*this).value; }
     T const &get() const    { return proto::arg(*this).value; }
};

int main()
{
     Locked<int> a;
     Locked<bool> b;
     Locked<bool> c;

     // Locks a, b and c in order, evaluates
     // the expression, performs the assignment,
     // and unlocks a, b and c.
     c = a > 0 || b;

     return 0;
}

-- 
Eric Niebler
Boost Consulting
www.boost-consulting.com