[antlr-interest] Appropriate use of honey badger listeners

[Kyle Ferrio]

Hi Ter,

I don't have answers, but I have questions which might at least cut off
some dead ends...

I agree that point #2 seems pretty clear.  And I realize that this:

    newtree = listener.someEvent(oldtree);
    if ( newtree!=oldtree ) replace-oldtree-with-newtree;

is pseudo-code.  You probably have this all worked out, but it occurs to me
that comparing two trees may be more expensive than necessary.  Despite the
fact that walking a tree of n nodes is O(n), and so comparing two trees
(non-naively) is also O(n), there may be a lot of data in those nodes to
compare.  If all we care about is detecting changes, a significant speedup
is possible if the interface for a tree object (or for listeners acting on
trees?) includes a flag that gets flipped by any operation which has the
possibility of changing the tree.  (N.B. Possibility, not guarantee.  A
guarantee would require the eval we're trying to avoid.)  This tiny bit of
added API built into a Listener baseclass for processing tree changes
(which are all covered by a small, finite set of generic operations) would
turn the subsequent O(n) comparison into O(1).  I'm not sure how this fits
with your design.  Of course, all bets are off if someone messes with the
tree directly.  (N.B. Alternatively, a hash on trees would be almost as
cheap and require no extra API, but that only works if we're willing to
treat topologically equivalent trees with different memory layouts (e.g.
flipping a tree left-to right) as different.)

Ok, now point #1.  Not sure how to approach this, but...

Thought: If the root of a rule r which returns a value does not declare the
type of value expected, two questions arise. One, where/when does the antlr
tool perform type-checking for the rules which consume rule r?  Two,
where/when does the antlr tool perform type-checking of the retvals from
listeners for different alts of r?  Perhaps an explicit
decoration/declaration of a type T at the root of r is the easiest,
clearest and safest way to communicate to all of the listeners of all of
the alts of r that they must return type T.  My thinking here is probably
clouded by my preternaturally strong preference for static typing.

Thought: If we try to be clever about types, then there seems to be a
trade-off between elegance in a grammar and elegance in the implementation
of listeners.  I am not convinced that this is fundamental, but that's
where my thinking is this minute.

Thought: Java will almost always lose to Python in syntactic beauty
contests.  So don't compare them to each other.  (Compare them to
JavaScript, and they both look gorgeous!  Shucks, adding fields dynamically
is one thing js does do nicely.)  For my part, I think that

    public void exitRule(AParser.multContext ctx) { results.put(ctx,
results.get(ctx.a) * results.get(ctx.b)); }

does not look any worse than a lot of Java which I consider to be overly
verbose anyway.  The question for me is, is it clear?  And my answer is
yes.   But as I mentioned in another thread, I am just starting to absorb
the listener model for v4,

Well, I'm not sure if any of this helps.  But I'm reasonably confident that
it does not hurt.

Kyle





On Wed, Jan 11, 2012 at 5:39 PM, Terence Parr <parrt at cs.usfca.edu> wrote:

> hi Kyle,
>
> I have 2 questions about the current listener mechanism:
>
> 1. How do we return values from listener methods so that we can do
> computations?
> 2. How do we alter a parse tree?
>
> For 2, I think we return a new tree as a return value and the parse tree
> walker will incorporate that into the tree if it sees a different tree come
> back. In other words, it will do something like this in the walker:
>
> newtree = listener.someEvent(oldtree);
> if ( newtree!=oldtree ) replace-oldtree-with-newtree;
>
> For 1, I don't have a great answer. To make this more concrete, imagine we
> have an expression rule and we want to use listener events to compute the
> value of an expression. So, instead of having actions in the grammar  like:
>
> e returns [int v]
>      : a=e '*' b=e {$v = $a.v * $b.v;}
>
> we would simply match it
>
> e : e '*' e -> mult …
>
> and then have listener events compute values. but where does of the
> listener object store the intermediate results of a subtree computation?
> Certainly we don't want to have to add "returns [int v]" to the grammar for
> every different paths we make over the parse tree. Without a return value
> from a listener event (which I want to use for tree rewriting), how do we
> get a value up the tree in a computation?  We can't really use temporary
> fields of the listener object because it's hard to tell which value gets
> associated with which listener method. we would need a temporary fields to
> hold result values from each listener. actually, I'm not even sure that
> would work. We need to associate result values with sub tree roots (i.e.
> contexts). In other words, we need a way to dynamically add fields to
> contexts for the specific purpose of a particular parse tree walk. One can
> imagine that I have a pass for computing the type of expression and another
> pass for computing the value. In both cases, I need result values for each
> subtree (type and then value).
>
> Maybe that is just a hash table from ctx node to value;
> Map<ParserRuleContext, Object>. maybe. That presents a few issues for me
> because I use hashCode/equals in a weird way for use with grammar analysis,
> but that would be the idea.
>
> class MyGListener extends BlankGListener {
>        Map<ParserRuleContext, Integer> results = …;
>
>        public void exitRule(AParser.multContext ctx) { results.put(ctx,
> results.get(ctx.a) * results.get(ctx.b)); }
>        public void exitRule(AParser.addContext ctx) { results.put(ctx,
> results.get(ctx.a) + results.get(ctx.b)); }
> }
>
> not very pretty in Java. Python would look better:
>
> results[ctx] = results[ctx.a] * results[ctx.b];
>
> This way we can associate any values we need to for any node, in effect,
> decorating the parse tree as needed.
>
> What do people think about the solution? is there a way I can automate
> some of this? I think that Python and Ruby would make short work of that
> because they allow dynamically adding fields (normally a horrible thing to
> do) ;) Is there a better way to do decorations in Java?
>
> Ter
>
> On Jan 11, 2012, at 1:49 PM, Kyle Ferrio wrote:
>
> > Excellent, congratulations and thank you.
> >
> > I just spent about half an hour playing with variations on A.g4 (since it
> > worked right out of the box I had to keep going...)  and this is really
> > nice.  This is the first time I've looked at the new-in-antlr listener
> > paradigm.  I will need a while to fully appreciate the doors this opens.
> > Honey Badger makes things easy, so I want to stay on his (?) good side.
> >
> > Q: how do you tell a boy Honey Badger from a girl Honey Badger?
> >
> > A: you don't.  they're both bad-ass.
>
> nice!
>
> Ter
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe:
> http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>