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.
Re:Reasoned Schemer?
Ovid on 2008-01-09T10:27:02
Nope. Given how easy it is to implement predicate logic in Scheme, though, I should really pay more attention to that language.