Re: [boost] Yap's formal review is starting now!

Subject: Re: [boost] Yap's formal review is starting now!
From: Zach Laine (whatwasthataddress_at_[hidden])
Date: 2018-02-08 21:15:12

On Wed, Feb 7, 2018 at 3:50 PM, Brook Milligan via Boost <
boost_at_[hidden]> wrote:

>
> > On Feb 5, 2018, at 8:53 AM, Louis Dionne via Boost <
> boost_at_[hidden]> 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