How to implement a visitor pattern over an AST

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

How to implement a visitor pattern over an AST

Boost - Users mailing list
Hello,

I have an AST successfully building, generating text file, and
subsequently Spirit Qi parsing for verification purposes.

Now I want to implement a visitor pattern over that AST, somehow...
For "calculators" and such, "evaluating" those expressions is one
thing; however, this AST is not that. It is closer akin to a parsed
Xml or Json model/tree.

In other words, I'd like for it to feel sort of like an iterator if
that's even possible. It should have contextual awareness where it is
at all times, etc, perhaps "incrementing" is a depth first analysis.

In particular I have in mind to iterate the expected and actual AST
results in order to perform the verification. In other words, I might
do something like this:

auto expected_it = ast_visitor{&expected};
auto actual_it = ast_visitor{&actual};

REQUIRE(expected_it);
REQUIRE(actual_it);

REQUIRE(*expected_it == *actual_it);

// Rinse and repeat
++expected_it;
++actual_it;
REQUIRE(*expected_it == *actual_it);

I wonder if something like this is even possible from the Boost
libraries? Or interested to hear any insights on the subject.

For that matter, I wonder it is more appropriate to simply implement
the logical operators.

Thanks!

Michael Powell
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: How to implement a visitor pattern over an AST

Boost - Users mailing list
AMDG

On 12/10/2018 12:04 PM, Michael Powell via Boost-users wrote:

>
> I have an AST successfully building, generating text file, and
> subsequently Spirit Qi parsing for verification purposes.
>
> Now I want to implement a visitor pattern over that AST, somehow...
> For "calculators" and such, "evaluating" those expressions is one
> thing; however, this AST is not that. It is closer akin to a parsed
> Xml or Json model/tree.
>
> In other words, I'd like for it to feel sort of like an iterator if
> that's even possible. It should have contextual awareness where it is
> at all times, etc, perhaps "incrementing" is a depth first analysis.
>

It's possible to do this, but making an iterator
over a tree is quite a bit more complex than just
using a depth-first visitation whenever you need
to process the tree.

> In particular I have in mind to iterate the expected and actual AST
> results in order to perform the verification.

For this case, the simplest method is a binary
visitor.

For example, variant equality looks something like this:

struct equal_to_visitor
{
  using result_type = void;
  template<class T>
  bool operator()(const T& lhs, const T& rhs)
  {
    return lhs == rhs;
  }
  template<class T, class U>
  bool operator()(const T&, const U&)
  {
    return false;
  }
};
...
bool operator==(const variant<...>& lhs, const variant<...> rhs)
{
  return boost::apply_visitor(equal_to_visitor{}, lhs, rhs);
}

Note that since we always return false if the types
are different, a slight variation can make this
work with a unary visitor.

> In other words, I might
> do something like this:
>
> auto expected_it = ast_visitor{&expected};
> auto actual_it = ast_visitor{&actual};
>
> REQUIRE(expected_it);
> REQUIRE(actual_it);
>
> REQUIRE(*expected_it == *actual_it);
>
> // Rinse and repeat
> ++expected_it;
> ++actual_it;
> REQUIRE(*expected_it == *actual_it);
>
> I wonder if something like this is even possible from the Boost
> libraries? Or interested to hear any insights on the subject.
>
> For that matter, I wonder it is more appropriate to simply implement
> the logical operators.
>

In Christ,
Steven Watanabe
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: How to implement a visitor pattern over an AST

Boost - Users mailing list
On Mon, Dec 10, 2018 at 3:00 PM Steven Watanabe via Boost-users
<[hidden email]> wrote:

>
> AMDG
>
> On 12/10/2018 12:04 PM, Michael Powell via Boost-users wrote:
> >
> > I have an AST successfully building, generating text file, and
> > subsequently Spirit Qi parsing for verification purposes.
> >
> > Now I want to implement a visitor pattern over that AST, somehow...
> > For "calculators" and such, "evaluating" those expressions is one
> > thing; however, this AST is not that. It is closer akin to a parsed
> > Xml or Json model/tree.
> >
> > In other words, I'd like for it to feel sort of like an iterator if
> > that's even possible. It should have contextual awareness where it is
> > at all times, etc, perhaps "incrementing" is a depth first analysis.
> >
>
> It's possible to do this, but making an iterator
> over a tree is quite a bit more complex than just
> using a depth-first visitation whenever you need
> to process the tree.

It is; I actually have a similar pattern in a "string rendering
visitor" in which I have internally specialized template methods for
the particular nodes of visitation. One might call that a unary
visitor, given a single operand.

In this case, I rinse and repeat given the binary case, two operands:

template<typename T>
bool equals(const T& x, const T& y) const {
    const auto message = "Comparator type '" +
std::string(typeid(T).name()) + "' unsupported";
    throw std::exception(message.c_str());
}

template<>
bool equals<ast::TopLevelType>(const ast::TopLevelType& x, const
ast::TopLevelType& y) const {
    // ...
}

And so on... Which also guarantees that I am also walking both tree's
at the same moment and in like fashion.

> > In particular I have in mind to iterate the expected and actual AST
> > results in order to perform the verification.
>
> For this case, the simplest method is a binary
> visitor.
>
> For example, variant equality looks something like this:
>
> struct equal_to_visitor
> {
>   using result_type = void;
>   template<class T>
>   bool operator()(const T& lhs, const T& rhs)
>   {
>     return lhs == rhs;
>   }
>   template<class T, class U>
>   bool operator()(const T&, const U&)
>   {
>     return false;
>   }
> };
> ...
> bool operator==(const variant<...>& lhs, const variant<...> rhs)
> {
>   return boost::apply_visitor(equal_to_visitor{}, lhs, rhs);
> }
>
> Note that since we always return false if the types
> are different, a slight variation can make this
> work with a unary visitor.
>
> > In other words, I might
> > do something like this:
> >
> > auto expected_it = ast_visitor{&expected};
> > auto actual_it = ast_visitor{&actual};
> >
> > REQUIRE(expected_it);
> > REQUIRE(actual_it);
> >
> > REQUIRE(*expected_it == *actual_it);
> >
> > // Rinse and repeat
> > ++expected_it;
> > ++actual_it;
> > REQUIRE(*expected_it == *actual_it);
> >
> > I wonder if something like this is even possible from the Boost
> > libraries? Or interested to hear any insights on the subject.
> >
> > For that matter, I wonder it is more appropriate to simply implement
> > the logical operators.
> >
>
> In Christ,
> Steven Watanabe
> _______________________________________________
> Boost-users mailing list
> [hidden email]
> https://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: How to implement a visitor pattern over an AST

Boost - Users mailing list
AMDG

On 12/10/2018 01:14 PM, Michael Powell via Boost-users wrote:

> On Mon, Dec 10, 2018 at 3:00 PM Steven Watanabe via Boost-users
> <[hidden email]> wrote:
>>
>> On 12/10/2018 12:04 PM, Michael Powell via Boost-users wrote:
>>>
>>> I have an AST successfully building, generating text file, and
>>> subsequently Spirit Qi parsing for verification purposes.
>>>
>>> Now I want to implement a visitor pattern over that AST, somehow...
>>> For "calculators" and such, "evaluating" those expressions is one
>>> thing; however, this AST is not that. It is closer akin to a parsed
>>> Xml or Json model/tree.
>>>
>>> In other words, I'd like for it to feel sort of like an iterator if
>>> that's even possible. It should have contextual awareness where it is
>>> at all times, etc, perhaps "incrementing" is a depth first analysis.
>>>
>>
>> It's possible to do this, but making an iterator
>> over a tree is quite a bit more complex than just
>> using a depth-first visitation whenever you need
>> to process the tree.
>
> It is; I actually have a similar pattern in a "string rendering
> visitor" in which I have internally specialized template methods for
> the particular nodes of visitation. One might call that a unary
> visitor, given a single operand.
>
> In this case, I rinse and repeat given the binary case, two operands:
>
> template<typename T>
> bool equals(const T& x, const T& y) const {
>     const auto message = "Comparator type '" +
> std::string(typeid(T).name()) + "' unsupported";
>     throw std::exception(message.c_str());
> }
>
> template<>
> bool equals<ast::TopLevelType>(const ast::TopLevelType& x, const
> ast::TopLevelType& y) const {
>     // ...
> }
>
> And so on... Which also guarantees that I am also walking both tree's
> at the same moment and in like fashion.
>

Yep.  Although you can implement tree iterators
using coroutines as demonstrated here:

https://www.boost.org/doc/libs/1_68_0/libs/coroutine/doc/html/coroutine/motivation.html#coroutine.motivation._same_fringe__problem

you lose information about the tree structure.  This is
a good thing in that example, but not so much for your
use case.

In Christ,
Steven Watanabe
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: How to implement a visitor pattern over an AST

Boost - Users mailing list
In reply to this post by Boost - Users mailing list
On 12/10/18 2:14 PM, Michael Powell via Boost-users wrote:

> On Mon, Dec 10, 2018 at 3:00 PM Steven Watanabe via Boost-users
> <[hidden email]> wrote:
>>
>> AMDG
>>
>> On 12/10/2018 12:04 PM, Michael Powell via Boost-users wrote:
>>>
>>> I have an AST successfully building, generating text file, and
>>> subsequently Spirit Qi parsing for verification purposes.
>>>
>>> Now I want to implement a visitor pattern over that AST, somehow...
>>> For "calculators" and such, "evaluating" those expressions is one
>>> thing; however, this AST is not that. It is closer akin to a parsed
>>> Xml or Json model/tree.
>>>
>>> In other words, I'd like for it to feel sort of like an iterator if
>>> that's even possible. It should have contextual awareness where it is
>>> at all times, etc, perhaps "incrementing" is a depth first analysis.
>>>
>>
>> It's possible to do this, but making an iterator
>> over a tree is quite a bit more complex than just
>> using a depth-first visitation whenever you need
>> to process the tree.
>
> It is; I actually have a similar pattern in a "string rendering
> visitor" in which I have internally specialized template methods for
> the particular nodes of visitation. One might call that a unary
> visitor, given a single operand.
>
> In this case, I rinse and repeat given the binary case, two operands:
>
> template<typename T>
> bool equals(const T& x, const T& y) const {
>      const auto message = "Comparator type '" +
> std::string(typeid(T).name()) + "' unsupported";
>      throw std::exception(message.c_str());
> }
>
> template<>
> bool equals<ast::TopLevelType>(const ast::TopLevelType& x, const
> ast::TopLevelType& y) const {
>      // ...
> }
>
> And so on... Which also guarantees that I am also walking both tree's
> at the same moment and in like fashion.
>
[snip]
Hi Michael,

I'm spitballing here, but my novice view of karma is that it takes an
AST and, like your "string rendering visitor" turns it into a string
on std::cout or some other ostream.  So, I'm guessing you could
look at karma to see how it does it, and duplicate that method,
only instead of rendering to a ostream, you'd just "render" as a bool
result.

Again, I could largely misunderstand what karma does, so take the
above with a "large grain of salt".

-regards,
Larry


_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: How to implement a visitor pattern over an AST

Boost - Users mailing list
On Mon, Dec 10, 2018 at 7:19 PM Larry Evans via Boost-users
<[hidden email]> wrote:

>
> On 12/10/18 2:14 PM, Michael Powell via Boost-users wrote:
> > On Mon, Dec 10, 2018 at 3:00 PM Steven Watanabe via Boost-users
> > <[hidden email]> wrote:
> >>
> >> AMDG
> >>
> >> On 12/10/2018 12:04 PM, Michael Powell via Boost-users wrote:
> >>>
> >>> I have an AST successfully building, generating text file, and
> >>> subsequently Spirit Qi parsing for verification purposes.
> >>>
> >>> Now I want to implement a visitor pattern over that AST, somehow...
> >>> For "calculators" and such, "evaluating" those expressions is one
> >>> thing; however, this AST is not that. It is closer akin to a parsed
> >>> Xml or Json model/tree.
> >>>
> >>> In other words, I'd like for it to feel sort of like an iterator if
> >>> that's even possible. It should have contextual awareness where it is
> >>> at all times, etc, perhaps "incrementing" is a depth first analysis.
> >>>
> >>
> >> It's possible to do this, but making an iterator
> >> over a tree is quite a bit more complex than just
> >> using a depth-first visitation whenever you need
> >> to process the tree.
> >
> > It is; I actually have a similar pattern in a "string rendering
> > visitor" in which I have internally specialized template methods for
> > the particular nodes of visitation. One might call that a unary
> > visitor, given a single operand.
> >
> > In this case, I rinse and repeat given the binary case, two operands:
> >
> > template<typename T>
> > bool equals(const T& x, const T& y) const {
> >      const auto message = "Comparator type '" +
> > std::string(typeid(T).name()) + "' unsupported";
> >      throw std::exception(message.c_str());
> > }
> >
> > template<>
> > bool equals<ast::TopLevelType>(const ast::TopLevelType& x, const
> > ast::TopLevelType& y) const {
> >      // ...
> > }
> >
> > And so on... Which also guarantees that I am also walking both tree's
> > at the same moment and in like fashion.
> >
> [snip]
> Hi Michael,
>
> I'm spitballing here, but my novice view of karma is that it takes an
> AST and, like your "string rendering visitor" turns it into a string
> on std::cout or some other ostream.  So, I'm guessing you could
> look at karma to see how it does it, and duplicate that method,
> only instead of rendering to a ostream, you'd just "render" as a bool
> result.
>
> Again, I could largely misunderstand what karma does, so take the
> above with a "large grain of salt".

No worries, yes, I did consider Karma for this purpose, but I figured
it may be "simple enough" to approach it otherwise. I may change my
mind downstream, however. ;-)

> -regards,
> Larry
>
>
> _______________________________________________
> Boost-users mailing list
> [hidden email]
> https://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: How to implement a visitor pattern over an AST

Boost - Users mailing list
In reply to this post by Boost - Users mailing list
On Mon, Dec 10, 2018 at 3:15 PM Michael Powell via Boost-users <[hidden email]> wrote:

And so on... Which also guarantees that I am also walking both tree's
at the same moment and in like fashion.

For comparison, you might consider the use of Boost.Coroutine to allow you to interleave recursive steps through your two trees:
(originally discussed here:)

_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: How to implement a visitor pattern over an AST

Boost - Users mailing list
On Tue, Dec 18, 2018 at 6:02 PM Nat Goodspeed via Boost-users
<[hidden email]> wrote:

>
> On Mon, Dec 10, 2018 at 3:15 PM Michael Powell via Boost-users <[hidden email]> wrote:
>
>> And so on... Which also guarantees that I am also walking both tree's
>> at the same moment and in like fashion.
>
>
> For comparison, you might consider the use of Boost.Coroutine to allow you to interleave recursive steps through your two trees:
> https://www.youtube.com/watch?v=3SvkWY7JSeY
> (originally discussed here:)
> https://groups.google.com/forum/#!msg/boost-list/AZQgtk6jMho/fIFowJ72AgAJ

That's an interesting idea, but I'm afraid it was my fault for not
communicating that clearly enough. There is little (if any) similarity
between "nodes" in my tree/graph, apart from thin slices, like "has
name" or "has number", etc. Additionally, rather than an explicit
connection, "edge", the connectivity between AST nodes is implicit;
the existence of which via either boost::variant or std::vector
inclusion.

Along these lines. Appreciate the feedback, however.

> _______________________________________________
> Boost-users mailing list
> [hidden email]
> https://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users