Trees and Language::AttributeGrammar

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} });
}
[download]

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
[download]

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";
[download]

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.
[download]

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...

rg0now

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
[download]

Comment on Trees and Language::AttributeGrammar Select or Download Code

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 }` [download] 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});` [download] 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'); }` [download] versus `$_AG_ATTR->get($_AG_SELF)->get('len')->set(sub { $_AG_N1->get('len', 'grammar line 4') + $_AG_N2->get('len', 'gramm +ar line 4'); }` [download] 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;` [download] 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} } ) ] }; }` [download] so that the values don't go away. Remember to invalidate `_ll_cache` whenever new children are added. Ciao! -nuffin zz zZ Z Z #!perl	[reply] [d/l] [select]
Re^2: Trees and Language::AttributeGrammar by rg0now (Chaplain) on Mar 06, 2006 at 21:01 UTC
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... rg0now	[reply] [d/l]
Re^3: Trees and Language::AttributeGrammar by nothingmuch (Priest) on Mar 06, 2006 at 22:02 UTC
Haskell? 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. -nuffin zz zZ Z Z #!perl	[reply]
Re^4: Trees and Language::AttributeGrammar by Anonymous Monk on Mar 22, 2006 at 20:48 UTC
Re^5: Trees and Language::AttributeGrammar by rg0now (Chaplain) on Mar 22, 2006 at 21:48 UTC
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	[reply]
Re^2: Trees and Language::AttributeGrammar by rg0now (Chaplain) on Mar 06, 2006 at 14:25 UTC
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. rg0now	[reply] [d/l]


Don't ask to ask, just ask
	PerlMonks