But it seems to me that these data structures have meta-information which you aren't currently storing. If you want efficiency you should store that information rather than recalculate it via a search.

One way to do this would be to wrap accesses to the data structure so that when a logic var is added to it, it's position is remembered (perhaps in some kind of inside-out object attribute stash). I'd do it this way, with a class around the data structure (add a "addLogicVar" method) although you could use TIE I guess.

I forgot about cycles, so yes, I need to worry about those. Damn.

Cheers,
Ovid

New address of my CGI Course.

Can't you use something like the reference of the current "thing" and the "thing" to be considered to be copied as a key in a hashset? Everytime you encounter those two things in that relationsip, process it once and only once?

Or.. create an algorithm to do a breadth first search (can be less memory intense) to discover all edges and copy them in a graph?

FYI: I do have a sample implementation which works. From the tests:

  $data = {
      foo => 3,
      bar => [ qw/ this that 3 / ],
      3   => undef,
      baz => {
          trois => 3,
          quatre => [ qw/ 1 2 3 4 / ],
      }
  };
  ok $paths = path( $data, 3 ),
    'Fetching paths for matching data should succeed';
  my @expected = sort (
      '{bar}[2]',
      '{baz}{trois}',
      '{baz}{quatre}[2]',
      '{foo}'
  );

  $paths = [ sort @$paths ];
  is_deeply $paths, \@expected,
      '... and we should be able to match complex data structures';

  foreach my $path (@$paths) {
      is eval "\$data->$path", 3,
        '... and each element should have the correct value';
  }
[download]

And the some rough code:

  use Scalar::Util 'reftype';

  my %path = (
      ARRAY => \&_array_path,
      HASH  => \&_hash_path,
  );

  sub path {
      my ( $data, $search ) = @_;
      my $type = reftype $data;
      my $find_paths = $path{$type};
      return $find_paths->( $data, $search );
  }

  sub _array_path {
      my ( $data, $search ) = @_;
      my @paths;
      foreach my $i (0 .. $#$data) {
          my $item = $data->[$i];
          my $type = reftype $item;
          my $current_index = "[$i]";
          if ( !$type && $item eq $search ) {   # XXX
              push @paths => $current_index;
          }
          elsif ( my $find_paths = $path{$type} ) {
              my @current_paths = map { "$current_index$_" }
                  @{ $find_paths->( $item, $search ) };
              push @paths => @current_paths;
          }
      }
      return \@paths;
  }

  sub _hash_path {
      my ( $data, $search ) = @_;
      my @paths;
      foreach my $key (keys %$data) {
          my $item = $data->{$key};
          my $type = reftype $item;
          my $current_key = "{$key}";
          if ( !$type && $item eq $search ) {   # XXX
              push @paths => $current_key;
          }
          elsif ( my $find_paths = $path{$type} ) {
              my @current_paths = map { "$current_key$_" }
                  @{ $find_paths->( $item, $search ) };
              push @paths => @current_paths;
          }
      }
      return \@paths;
  }
[download]

The code itself works fine, but the tests show that using it (the string eval) seems really clumsy. It works fine for what I need, but still looking for a better approach (cleaner and faster).

my @path = qw( A 2 H foo H bar A 1 );

my $data = [
 "foo",
 "bar",
  {
    foo => {
      bar => [
        5,
        6,
      ],
    },
  },
];

while ( @path ) {
  my $type = shift @path;
  my $index = shift @path;

  if ( $type eq 'A' ) {
    $data = $data->[$index];
  } else {
    $data = $data->{$index};
  }
}
print $data; # prints "6" (I hope)
[download]

When to generate or update the flattened representation would depend on how these structures are populated. If you were to generate all of them at once, then yes, recursively walk the data structure. I don't think localizing the stack helps, though -- I think that would require copying the whole stack every time you localized it with the old value plus one new path token. Better to just push the token on and pop it back off after you're done. Actually, if you're doing it my way (with a string representation of the path), then you would just call bind(..., $path . $token) recursively and it will manage your stack for you.

And if you're maintaining the flattened version at all times, you just need to have the path so far available anywhere you're mutating things.

Why are you worried about this particular optimization already? It sounds like you aren't done with the rest of the algorithm. You might want to make it work first, just in case this optimization turns out to be invalid. Can variables be non-leaf nodes in your structures? If so, then you may have to do full searches rather than simple cached path lookups. Can the same variable appear more than once? If so, then you have to do speculative bindings or loop through all possibilities or something. Can the right-hand side also contain variables? Then you need to be able to bind the two variables together, and if they can appear more than once, I think the speculation gets hairier.

By the way, I think your function bind() should be called unify(). The terminology I am familiar with is that you unify the two structures, resulting in a set of bindings (possibly recorded via calls to bind()). But perhaps you're doing things differently from what I remember; I can't figure out when you would ever want to unify a single structure with multiple other structures in succession. Then again, it's been a very long time since I last thought about this stuff.

Unification and data binding, in this context, are different things. Prolog:

  gives(tom, book, SOMEONE) :-
    person(SOMEONE),
    likes(tom, SOMEONE).
[download]

Let's look at the like( tom, SOMEONE ) bit. Prolog would fetch all of the like/2 facts and attempt to unify those facts, one at a time, with like( tom, SOMEONE ). As soon as a fact matches (unifies), then the SOMEONE variable will be bound to the corresponding value. So if we have these facts:

  likes( mary, tom ).
  likes( tom, susan ).
[download]

The first fact won't unify and SOMEONE won't be bound to tom. When the second fact is encountered, unification occurs and SOMEONE is bound to the value susan. Once that's bound, then the engine goes to person(SOMEONE) and since the variable is already bound, we are attempting to unify this fact with a fact in the database which asserts that susan is, in fact, a person. If we find that fact, we get to the top of the rule and know that tom gives a book to susan.

So the terminology is right, but this means we tend to have exhaustive, depth-first backtracking searches. If we have lots of facts in our database, these searches can be very slow. Having done a lot of work in this area before, I know how incredibly common (and slow) the binding and unbinding of data can be, so while I generally tell people not to do premature optimization, like many others, I caution folks that this isn't always true. If you're writing a ray-tracing program and you need it to be fast, you know you're probably not going to reach for Perl first. (Of course, if you want predicate logic, you also don't want to reach for Perl first, but I'm strange that way).

Cheers,
Ovid

New address of my CGI Course.

For example:

use B::XPath;

sub some_function
{
  my $struct =
  [
    'whaa!',
    undef,
    [
      undef,
      undef,
      {
        foo => 3
      }
    ],
    {
      bar => 'baz'
    },
  ];
}

my $node = B::XPath->fetch_root( \&some_function );

print_children($node, 0);
sub print_children
{
  my $node= shift;
  my $indent= shift;
  foreach my $child ($node->get_children())
  {
    print " " for (0..$indent);
    print $child->get_name()."=".$child."\n";
    $indent++;
    print_children($child, $indent);
    $indent--;
  }
}
[download]