Boost logo

Boost :

Subject: Re: [boost] [yap] review part 3: tests + misc + summary
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2018-02-20 15:29:34


On 02/19/2018 08:38 PM, Zach Laine via Boost wrote:
> On Mon, Feb 19, 2018 at 11:13 AM, Steven Watanabe via Boost <
> boost_at_[hidden]> wrote:
>> <snip>
>> General Notes:
>> - There are three primary modes for processing an
>> expression tree, which I will describe as:
>> 1. transform: Takes a tree and produces another tree.
>> 2. evaluate: Takes a tree and evaluates it in some way.
>> 3. for_each: Processes each node and returns nothing.
>> yap::transform can handle all three as long as you explicitly
>> handle all nodes. The default behavior is (1), which
>> makes (2) and (3) somewhat inconvenient. Your solution
>> in the examples seems to be transform/evaluate for (2)
>> and returning a dummy result for (3). Unfortunately,
>> transform/evaluate doesn't work well if evaluation
>> involves any special constructs that affect control-flow.
>> Just try to handle something like this:
>> let(_a=2) [ _a + 1 ] // evaluates to 3
> That does not look problematic to me, though I don't know what the intended
> semantics are.

> If _a is a terminal and refers to something for which "= 2"
> and "+1" are well-formed, I would expect even evaluate() to do the right
> thing.

  _a is a placeholder. _a = 2 is not an assignment
to some external object. It is a variable definition
that is scoped within the let expression. It's not really
possible to transform this into something that can be
evaluated in a single pass. I claim that it is impossible
to implement `let` using Yap without duplicating all the
work of evaluate. (Keep in mind that `let` can be nested
and can be mixed with if_else.)

>> Returning a dummy result is a bit annoying, but shouldn't
>> cause any real problems, as long as terminals are captured
>> by reference in the result. All in all, I'd like to have
>> some way to change the default behavior of transform, or
>> perhaps have separate functions with different default behavior.
>> Just an idea: switch the default behavior based on the
>> result of transforming the subexpressions:
>> Expression/non-Expression/void.
> I don't yet get what you're suggesting here. Right now, transform()
> returns whatever you tell it to,

  The issue is not what I'm telling it to do,
but rather what it does on its own when I
don't tell it anything.

> except that it doesn't special-case void
> return. You can (I have have extensively in the examples) return an
> Expression or non-Expression from a transform, or from any subset of
> overloads your transform object provides. What is the behavior that you're
> suggesting?

  You've chosen to make it impossible to customize
the behavior of evaluate. I believe that Brook
brought up evaluate_with_context, which is basically
what I want.

>> This has the side effect that you must explicitly wrap
>> terminals when returning, but I think that's actually a
>> good thing, as a transform that returns unwrapped terminals,
>> expecting them to be wrapped by the caller, may have
>> inconsistent behaviour.
>> In addition, there is another possible mode that has
>> better type safety which I will call:
>> 4. manual: No default behavior. If a node is not handled
>> explicitly, it is a hard compile error.
> But this isn't transform() at all, because it doesn't recurse. It only
> matches the top-level expression, or you get a hard error. Why not just
> write my_func() that takes a certain expression and returns another?

  You're right. The only benefit is that tag
transforms are a bit more convenient. Also,
it allows for a more consistent interface.

> Calling it with the wrong type of expression will result your desired hard
> error. Wait, is the use case that I think my transform matches all
> subexpressions within the top-level expression, and I want to verify that
> this is the case? I don't know how often that will come up. I can't think
> of a single time I've written a Yap transform expecting it to match all
> nodes, except to evaluate it. It could be useful in those cases now that I
> think of it.

  If you're building a completely new grammar
whose meaning has no relationship to the built
in meaning of the operators, (e.g. Spirit),
then you basically have to handle everything

>> - Combining transforms isn't exactly easy, because of
>> the way transforms recurse. For example, if I have
>> two transforms that process disjoint sets of nodes,
>> I can't really turn them into a single transform.
> I'm not necessarily opposed to the idea, but how would combining transforms
> work? Would each node be matched against multiple transform objects, using
> whichever one works, or something else?

  Probably the behavior is to choose the
first one that matches. That would make
it easy to write a transform that overrides
some behavior of another transform. (Note
that I really have no idea how to make
something like this actually work.)

>> - How useful is it to separate the Expression concept
>> from the ExpressionTemplate concept?
> Types and templates are not the same kind of entity. I don't know how to
> even go about combining these. Moreover, I think they should remain
> separated, because sometimes a function takes an Expression, sometimes not,
> sometimes it requires an ExpressionTemplate template parameter, and
> sometimes not. These are orthogonal requirements for the caller, no?
>> For example,
>> transform requires an ExpressionTemplate for nodes
>> that are not handled explicitly, but that isn't very
>> clear from the documentation, which just says that
>> it takes an Expression.
> I don't understand what you mean. transform() does not require an
> extrinsic ExpressionTemplate template parameter, and does not use one. It
> just recycles the ExpressionTemplate that was originally used to
> instantiate whatever it needs to copy.

Let me rephrase the question:
Is it useful to allow Expressions that are not
instantiations of an ExpressionTemplate, given
that transform can choke on such classes.

>> - You say that it's fine to mix and match expressions that
>> are instantiated from different templates. Why would
>> I want to do this? The first thing that comes to mind
>> is combining two independent libraries that both use YAP,
>> but I suspect that that won't work out very well.
>> It seems a bit too easy for a transform to inadvertently
>> recurse into an unrelated expression tree in this case.
> I have two types, M and S (m and s are two objects of those respective
> types). M is matrix-like, and has m*m in its set of well-formed
> expressions; m[x] is ill-formed for any x. S is string-like, and has
> s[int(2)] in its set of well-formed expressions; s*s is ill-formed. M and
> S are in the same library, one that I maintain.
> If I want to use these in Yap expressions, I probably want to be able to
> write m*m and s[5], but not m[2] or s*s. So I write two expression
> templates with the right operations defined:
> template <...>
> struct m_expr
> {
> // ...
> };
> template <...>
> struct s_expr
> {
> // ...
> };
> Now I can write a Yap expression like:
> lookup_matrix(S("my_matrix")) * some_matrix
> and transform() it how ever I like. Requiring the two *_expr templates to
> be unified would be weird.

  It seems a bit odd to have matrices and strings in
one library, rather than matrices and vectors, but
I get your point. Please consider adding something
like this to the documentation.

> - The value of a terminal cannot be another expression.
>> Is this a necessary restriction?
> Not really; I probably put that restriction there due to lack of
> imagination. Terminals' values should be treated as simple types, but I'm
> pretty sure there's no real reason those types can't happen to model
> Expression.
>> (This is related to
>> mixing different libraries using YAP, as the most
>> common form is for library A to treat the expressions
>> from library B as terminals. Since a terminal can't
>> hold an Expression, we would need to somehow un-YAP
>> them first.)
> As I outlined above, I don't think that's going to be the most common case
> of mixing ExpressionTemplates in a single Yap expression.

  That's why I said mixing different *libraries*, not
just mixing different templates from a single library
(which are most likely intended to work together).
The basic idea is that library A creates expressions
that are models of some concept C, while library B
expects a terminal that models the same concept C.
library A and library B know nothing about each other,
and are only connected because they both know about C.

>> - Unwrapping terminals redux:
>> Unwrapping terminals is convenient when you have
>> terminals of the form:
>> struct xxx_tag {};
>> auto xxx = make_terminal(xxx_tag{});
>> AND you are explicitly matching this terminal with
>> auto operator()(call_tag, xxx_tag, T...) or the like.
>> I expect that matching other terminals like double
>> or int is somewhat more rare in real code. If you
>> are matching any subexpression, then unwrapping
>> terminals is usually wrong.
> Why do you say that? The only way it is the way it is now is convenience,
> as you might have guessed. When I know I want to match a particular
> terminal of a particular type, I'd rather write:
> auto operator(some_unary_tag, some_type && x);
> auto operator(some_unary_tag, some_type const & x);
> versus:
> auto operator(some_unary_tag, my_expr<yap::expr_kind::terminal, some_type
> &&> const & x);
> auto operator(some_unary_tag, my_expr<yap::expr_kind::terminal, some_type
> const &> const & x);
> This latter form is what I started with, and I very quickly grew tired of
> writing all that.

You can always use a typedef or alias. i.e. my_term<some_type&&>.

> If I match a generic expression that may or may not be a terminal, I do
> have to use yap::as_expr(), which is definitely an inconvenience:
> template <typename Expr>
> auto operator(some_unary_tag, Expr const & x) {
> return some_function_of(yap::as_expr(x));
> }

  My intuition is that this is the most common pattern,
and should be what we optimize for. Also, changing
terminals to yap::expression may cause random
weirdness if the transform returns an Expression.
In addition, I feel that needing to call as_expr
is more surprising than needing to write out the
the terminal as an expression.

  Actually... I have a much better idea. Why
don't you allow transform for a non-expr to match
a terminal tag transform?


In Christ,
Steven Watanabe

Boost list run by bdawes at, gregod at, cpdaniel at, john at