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 [cpan://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 + $.len }
Leaf: $/.len = { 1 }
Cons: $/.len = { $.len + $.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.
p.s.: if [luqui] reads this: there is a typo in the SYNOPSIS of [cpan://Language::AttributeGrammar]:
# find the global minimum and propagate it back down the tree
ROOT: $/.gmin = { $/.min }
Branch: $.gmin = { $/.gmin }
| $.gmin) = { $/.gmin }
^
|
this is superfluous
Cons: $/.len = { $/; $.len + $.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', 'grammar line 4');
}
versus
$_AG_ATTR->get($_AG_SELF)->get('len')->set(sub {
$_AG_N1->get('len', 'grammar line 4') + $_AG_N2->get('len', 'grammar 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.
Ciao!
zz zZ Z Z #!perl
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. @
zz zZ Z Z #!perl