On Wed, Feb 7, 2018 at 3:50 PM, Brook Milligan via Boost < boost@lists.boost.org> wrote:
On Feb 5, 2018, at 8:53 AM, Louis Dionne via Boost < boost@lists.boost.org> wrote:
The formal review of Zach Laine's Yap library starts Monday, February 5th and ends on Wednesday, February 14th.
I have not heard any discussion of Yap yet, so I’ll jump in and start it off.
My review will come later, but for the moment I want to raise an issue for discussion.
First, a bit of context. I have been using Yap in production for the last year (thanks Zach for your help along the way). In my application, I am dealing with arbitrary, user-coded expression trees. Some of the terminals can be function objects that in turn evaluate other user-coded expression trees. Ideally, evaluation of these expressions would work for any types wrapped in the appropriate expression classes. Indeed, this is the case, which is great.
However, I also have a common use case that requires changing how the evaluation works depending on context. For example, it would be useful to write something analogous to evaluate(expr,context) with a stateful context object that would influence how certain terminals are evaluated.
The official stance on this [1] is that one should instead use transform(expr,xform), where xform could play the role of context above because transforms can “do anything”, including evaluate the expression using contextual information contained within the xform object.
The problem I see with using transform() is that the entire recursion through the expression tree that is provided by the implementation of evaluate() must be duplicated in some way by the user in order to implement the necessary overloads in xform. This is because “if xform(N) is a well-formed C++ expression, that xform(N) is used, and no nodes under N in expr are visited” [2]. Therefore, the user has to provide whatever recursion is needed to mimic what evaluate() would otherwise do.
This situation raises several questions. It is my hope that this post will raise a discussion about the appropriate design considerations at work.
- Is context-dependent evaluation a use-case that is valuable to support by the library? Based on my experience, the answer is clearly yes, but perhaps others wish to weigh in.
- Is it appropriate for a library to require users to reimplement something as intricate as this recursion in order to support a use case like that?
- Is it appropriate for Yap to have something like evaluate_with_context(eval,context,…) that would implement a recursion similar to evaluate() but allow a context argument to control the evaluation at appropriate customization points. Note, the variadic part is for placeholders, which are supported by evaluate(), and not really part of the issue. Again, from my experience it seems that implementing this once correctly in the library would save much pain on the users’ part.
I hope this will stimulate some discussion and look forward to seeing where it goes.
Ok, some things to note: evaluate() currently has two modes, speaking roughly. The first mode is to evaluate an expression by doing whatever the built-in operators and existing function calls in the expression would do. This can be extremely useful in many situations when you write code using Yap, especially transforms where you want to at least partially default-evaluate some subexpression. The second is to evaluate the expression using custom code that the user has specified using customization points; there are customization points for every overloadable operator, among others. This second mode is essentially a way of doing implicit transforms, and is really only there for Proto parity. I've never liked it, and am on the fence about cutting the customization points entirely. The implicit nature of the customization is at the heart of my problem with this feature. A good abstraction is used explicitly, but hides its implementation details. These customization points do the implementation hiding bit just fine, but you can't even tell you're using them when looking at a particular line of code -- does yap::evaluate(a + b) yield a sum, or launch a missile? Who's to say? I have to go code spelunking to find out. This is at odds with good code practice emphasizing local reasoning. If I had not wanted Proto feature parity, I *never* would have implemented a library like this. So, were I to add a new evaluate_with_context(), it would mean that we would perpetuate this customization-point mis-feature. This I do not like. Did I mention that the customization points are implemented done via ADL trickery, requiring new types and/or namespaces to get slightly different behaviors? I also don't like this aspect. So, I have been very resistant to adding another new evaluation mode. Instead, I think something like this should be usable in most cases: // Let's assume the existence of a my_make_term() function that takes a Yap terminal // and a Context &, and returns a new Yap terminal. template <typename Context> struct transform_terminals_with_context { // Base case. Note that I'm ignoring placeholders entirely for this // example (they're easy to special-case if necessary). template <typename T> auto operator() (yap::terminal_tag, T && t) { return my_make_term(std::forward<T>(t), context_); } // Recursive case: Match any binary expression. template <typename Tag, typename LExpr, typename RExpr> auto operator() (Tag, LExpr const & left, RExpr const & right) { return yap::make_expression<yap::detail::kind_for<Tag>>( boost::yap::transform(left, *this), boost::yap::transform(right, *this)); } // Recursive case: Match any unary expression. template <typename Tag, typename Expr> auto operator() (Tag, Expr const & expr) { return yap::make_expression<yap::detail::kind_for<Tag>>( boost::yap::transform(expr, *this)); } // Ternary and call are added as necessary. Context & context_; }; This transforms all your terminals to new terminals, using your custom code that applies your terminal + context operation. You can then just eval() the transformed expression using the default evaluate(), transform() it again with a different transform, etc. I had to make up the constexpr function kind_for<>() that maps expression-kind tag types to yap::expr_kind values (which I'll probably add now that I see it is needed *TODO*), but the reset is just typical Yapery. Now, this has the downside that if you have a very large number of terminals, you may have some expensive copies going on, because you are copying the entire tree. This implies to me that the most important issue is whether the evaluate-as-you-transform-because-the-tree-is-huge use case is of primary or secondary concern. My expectation is that it is of secondary concern. To expect otherwise is probably to optimize prematurely -- even if this issue is important, how often do users see real perf impact? I don't know the answer to that yet, but if it is a common enough perf problem, I'm quite happy to come up with a solution. If not, making your own transform that evaluates in place actually sounds like the right answer to me. In most cases, users also don't care about every possible expression kind -- they are designing a mini-language that uses a subset. Using a transform like the one above, evaluate(), or the proposed evaluate_with_context() allows subexpressions that are not in the purview of your mini-language. A custom transform has better type safety. Zach