rg0now has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks!

I have largish data structures, organized into trees, and I have to perform rather complex transformations on this data. When I first encounterd with attribute grammars I immediately fell in love with the concept.

So I installed luqui's Language::AttributeGrammar, wrote a little tree data representation:

#!/usr/bin/perl use strict; use warnings; use Language::AttributeGrammar; package Leaf; sub new{ return bless { value => $_[1] }, 'Leaf'; } package Branch; sub new{ return bless { value => $_[1], _list => undef }, 'Branch'; } sub add_child{ my $self = shift; push @{ $self->{_list} }, @_; return $self; } sub list { if (@_) { bless { head => $_[0], tail => list(@_[1..$#_]) }, 'Cons'; } else { bless {}, 'Nil'; } } sub children{ return list( @{ $_[0]->{_list} }); }
and a simple attribute grammar to count the number of nodes in a tree
package main; my $grammar = new Language::AttributeGrammar <<'EOG'; Branch: $/.len = { 1 + $<children>.len } Leaf: $/.len = { 1 } Cons: $/.len = { $<head>.len + $<tail>.len } Nil: $/.len = { 0 } EOG
and an example
my $tree = Branch->new(3)->add_child( Branch->new(1.1)->add_child( Leaf->new(1), Leaf->new(1.2) ), Branch->new(2.0)->add_child( Leaf->new(2.1), # Leaf->new(2.15), Leaf->new(2.2), ) ); my $result = $grammar->apply($tree, 'len'); print "$result\n";
Everything works like charm as long as the line that is commented out remains commented out. As soon as I add the node back to the tree, I get
Deep recursion on subroutine "Language::AttributeGrammar::Thunk::get" +at (eval 29) line 5.
and the script runs into a seemingly infinite loop. Does anyone have a clue why this happens? I would greatly appreciate any ideas.

Update: sorry I mixed up: it works with 3 leafs, but stops working as soon as I comment out the offending line...

p.s.: if luqui reads this: there is a typo in the SYNOPSIS of Language::AttributeGrammar:

# find the global minimum and propagate it back down the tree ROOT: $/.gmin = { $/.min } Branch: $<left>.gmin = { $/.gmin } | $<right>.gmin) = { $/.gmin } ^ | this is superfluous

Replies are listed 'Best First'.
Re: Trees and Language::AttributeGrammar
by nothingmuch (Priest) on Mar 06, 2006 at 17:56 UTC
    First of all, the fix is this:
    Cons: $/.len = { $/; $<head>.len + $<tail>.len }
    As you can see mentioning $/, the attribute's invocant fixes this.

    You're probably asking yourself why...

    use Data::Dumper; $Data::Dumper::Deparse = 1; warn Dumper($grammar->{engine}{cases}{Cons});
    Comparing the two versions shows us something interesting:
    $_AG_ATTR->get($_AG_SELF)->get('len')->set(sub { $_AG_SELF; $_AG_N1->get('len', 'grammar line 4') + $_AG_N2->get('len', 'gramm +ar line 4'); }
    $_AG_ATTR->get($_AG_SELF)->get('len')->set(sub { $_AG_N1->get('len', 'grammar line 4') + $_AG_N2->get('len', 'gramm +ar line 4'); }
    So, what is the void thingy doing in there, you are probably wondering? Aha!
    'visit' => [ sub { ... # snipped my($_AG_SELF, $_AG_ATTR) = @_; ... # snipped $_AG_ATTR->get($_AG_SELF)->get('len')->set(sub { $_AG_SELF;
    Basically, $_AG_SELF causes the value to remain non-garbage collected (since it's captured in the closure it's reference count stays up). Since luqui is using a lazy evaluation strategy to produce results, and this probably means that somewhere inside $_AG_ATTR or whatever there's a table of objects to their attr values, the moment that $_AG_SELF dies (and it will die, because you are creating Cons thingies on the fly inside 'children') it can no longer be referenced in a thunk, because it's StrVal cannot be reproduced. Anyway, long story short, the evaluation scheme is somehow landing on an edge case with two children in the Cons/Nil thing, and thus it's causing the value to be recalculated over and over and over and over again. I think.

    The more elegant fix is to cache your linked list, something like

    sub children{ return @{ $_[0]{_ll_cache} ||= [ list( @{ $_[0]->{_list} } ) ] }; }
    so that the values don't go away. Remember to invalidate _ll_cache whenever new children are added.


    zz zZ Z Z #!perl
      Thanks for the nice response. Let's say I understand it...:-)

      Something however tells me that both of your solutions take away something very important from the elegance of the code: in my opinion the efficiency lies in that we let the Cons stuff just emerge and go away on the fly.

      My qustion is: do you have any better idea to represent trees and attribute grammars to manipulate them than mine? Once I adopted this "functional" approach I really do not want to go back to the "imperative" world...


        Seriously though, post a bug on rt.cpan.org - luqui should know about this and fix it somehow...

        luqui also said he will add support for attributes over aggregate types (e.g. @<children>.foo) eventually, if he can find a nice way.

        zz zZ Z Z #!perl
Re: Trees and Language::AttributeGrammar
by aquarium (Curate) on Mar 06, 2006 at 13:11 UTC
    my wild guess is that 2.15 should be a child of 2.1 and not a child of 2.0
    the hardest line to type correctly is: stty erase ^H
      I am not entirely sure I understand what you are talking about. The values associated with the nodes are completely optional and arbitrary -- they could very well be strings or other objects or even left undef. The code just tries to count how many nodes the tree has, independently of the values associated with these nodes.