Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Ovid (2709)

Ovid
  (email not shown publicly)
http://publius-ovidius.livejournal.com/
AOL IM: ovidperl (Add Buddy, Send Message)

Stuff with the Perl Foundation. A couple of patches in the Perl core. A few CPAN modules. That about sums it up.

Journal of Ovid (2709)

Tuesday January 08, 2008
04:11 PM

Complex data structure unification

[ #35334 ]

While I still don't have a search algorithm yet (maybe that should have been first?), I've gotten complex data structure pattern matching to work just fine (almost like regexes against data structures). Here's a sample from my test suite:

ok $data->add_facts(
    [
        qw/ gives ovid /,
        {
            book  => 'library',
            money => [qw/charity nonprofits/]
        }
    ],
  ),
  'We should be able to add complex data structures as facts';

var my $what;
var my $group1;
var my $group2;

ok $results = $data->query(
    'gives', qr/^o/,
    {
        book  => $what,
        money => [ $group1, $group2 ]
    }
  ),
  '... we should be able to issue complex queries';
ok $results->next, '... and get results';
is $what->value, 'library', '... and fetch simple hash key variables';
is_deeply [ $group1->value, $group2->value ], [qw/charity nonprofits/],
  '... and items from arrays';

That query says, everybody whose name begins with 'o' gives books to 'what' and money to 'which groups'.

Frankly, I'm rather surprised it was so easy. To solve the problem, I made a post on Perlmonks about efficient partial deep cloning and in the process of posting that, I explained the process well enough to understand a tentative solution. I'm not arguing that my solution is the best, but it seems to work really well.

The next() method wound up being really simple and looks like this:

sub next {
    my $self = shift;

    # we're out of facts
    return if $self->{index} > $self->{max};

    my $query = $self->{query};
    foreach my $path ( @{ $self->{paths} } ) {

        # unbind all logic variables
        eval "\$query->$path->unbind";
    }

    # get the next fact we found in the db
    my $fact = $self->{facts}[ $self->{index} ];
    $self->{index}++;

    # the query matched the fact
    if ( my $result = eval { unify( $query, $fact ) } ) {

        # so lets bind all of the logic variables and return
        foreach my $path ( @{ $self->{paths} } ) {
            eval "\$query->$path->bind( \$result->$path )";
        }
        return 1;
    }
    else {

        # otherwise, try the next fact
        $self->next;
    }
}

Those 'evals' give me the willies, but they're the key to making all of this happen.

What I'd like to do is this:

var my $what;
var my @groups;

ok $results = $data->query(
    'gives', qr/^o/,
    {
        book  => $what,
        money => \@groups,
    }
  ),
  '... we should be able to issue complex queries';
ok $results->next, '... and get results';
is $what->value, 'library', '... and fetch simple hash key variables';
is_deeply [ $groups->values ], [qw/charity nonprofits/],
  '... and items from arrays';

That would allow me to match arbitrary length arrays, but there are some severe technical issues with that. Logic programming can work with arbitrary length lists, but that is only because Prolog's data structures are so limited. Perl's are so rich that the semantics are very complicated.

Update: I should thank Luke Palmer for the nice declaration of logic variables. I stole that idea from Logic.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • Did you ever read that? I did last summer and thought it'd be sweet to port to perl. Never did of course.
    • Nope. Given how easy it is to implement predicate logic in Scheme, though, I should really pay more attention to that language.