[boost] [proto] Review

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-03-06 18:10:48

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?

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

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.  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.

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();

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.

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>
{
   typedef locked_var_set result_type;

   // Return a singleton set for Locked<T>:
   template <typename T>
   locked_var_set operator()(proto::tag::terminal, const Locked<T>& l) 
const {
     // It took me a while to work out out what the prototype for this 
should be;
     // I didn't find anything similar in the examples.
     locked_var_set s;
     s.insert(&l);
     return s;
   }

   // Return an empty set for other terminals:
   template <typename T>
   locked_var_set operator()(proto::tag::terminal, const T&) const {
     return locked_var_set();
   }

   // For the operators we need something like this:
   template <typename Left, typename Right, typename TagT>
   locked_var_set operator()(TagT, const Left& left, const Right& right) 
const {
     locked_var_set s = proto::eval(left,*this);
     locked_var_set r = proto::eval(right,*this);
     std::copy(r.begin(),r.end(),std::insert_iterator<locked_var_set>(s,s.end()));
     return s;
   }
   // I'm not sure about the TagT thing up there, but it seems to work.
   // Presumably something would also be needed for unary expressions.
};

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

and then write:

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

Now I need the locking and unlocking, and the actual expression 
evaluation (which needs a
different context):

void lock_all(const locked_var_set& vs) {
   for (locked_var_set::const_iterator i = vs.begin();
        i != vs.end(); ++i) {
     (*i)->mut.lock();
   }
}

void unlock_all(const locked_var_set& vs) {
   for (locked_var_set::const_reverse_iterator i = vs.rbegin();
        i != vs.rend(); ++i) {
     (*i)->mut.unlock();
   }
}

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?

   // 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 );

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'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<>?

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 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.

Review questions:

- What is your evaluation of the design?

Looks good.  It would be great if it could all be simpler, but I doubt 
that's possible.

- What is your evaluation of the implementation?

I haven't looked inside the source files.  I have not encountered any 
warnings or errors, which is a good sign.

- What is your evaluation of the documentation?

Good.  But the complexity of the subject means that the quality of the 
documentation will be critical to the widespread uptake of the library.

- What is your evaluation of the potential usefulness of the library?

Considerable.

- Did you try to use the library?  With what compiler?  Did you have 
any problems?

Yes, with g++ 4.1.3 on Linux.  No problems.

- How much effort did you put into your evaluation? A glance? A quick 
reading? In-depth study?

About 4 hours.

- Are you knowledgeable about the problem domain?

Not especially.

Regards,  Phil.