http://qs321.pair.com?node_id=189943

Ovid has asked for the wisdom of the Perl Monks concerning the following question:

I am returning to the AI::Perlog module, but I have been having trouble figuring out the best way to handle unification. I figured I can turn to my fellow Monks for help.

Currently, I only have a modest module with no real functionality beyond what I have described at use.perl. I would like to post it to the CPAN someday, but only after there's enough there for it to be useful. If you're interested in helping with it (and stroke my little ego), you can download it from my site. The documentation is minimal and I wouldn't even consider this alpha quality code. The only prerequisite is Test::More.

If you want to see what it does, you'll have to read the tests. If you want to see how it does it, you're crazy :) -- though it's not really difficult to figure out.

What I am struggling for is an initial solution to the Unification problem -- associating variables with their values. If you're interested in taking a stab at this, read on.

The only thing that would give you pause in the code is the HoHoAoHoAoH. That, believe it or not, is not as difficult as it appears.

Let's say I add one fact to the database -- database being a Prolog term, not what we usually think of:

$pg->add_fact( owns => ('Ovid', 'Cheap Whiskey'));

In this example, the predicate 'owns' gets an ID of 1, 'Ovid' gets an ID of 2 and 'Cheap Whiskey' gets an ID of 3. I should also add that the order of a predicate's arguments does not truly have meaning so long as it is consistent. Therefore, the above fact is just ask likely to mean that "Ovid owns cheap whiskey" as "cheap whiskey owns Ovid", but I prefer not to think about the latter.

The first item in that nasty data structure is a single key _arg_levels. In the above example, the predicate ID for 'owns', 1, becomes a key in the _arg_levels hash. In fact, every predicate 'owns' will have the same ID, just different arguments -- but the same number of arguments -- so what we have left is the AoHoAoH. The above fact generates the following array values for the predicate 'owns':

[0]{2}[1]{3} = {} [1]{3} = {}

What that means is that for the first argument we have 'Ovid' (id of 2) who has in the second argument position a value of 'Cheap Whiskey' (that's the first line). The second line says that for the second argument, we have the value of 'Cheap Whiskey' and no dependants. It can be confusing, but once you read through the code and get a feel for it, you'll see what this does and why. To verify a fact of X arguments, this data structure requires at most X-1 iterations. Space for time, space for time...

Inside the actual module, if you want to know if Ovid (2) owns (1) cheap whiskey (3), you can issue the following query:

# object ids are hashes and argument positions are arrays $self->{_arg_levels}{2}[0]{2}[1]{3};

The actual code for that I use:

$_ = $self->_get_vertex( $_ ) foreach @args; # @important is a list of argument positions that are # not null (e.g, undef, empty string, or '_') my $a = shift @important; while( my $z = shift @important ) { return if !$self->_check_path($predicate_id,$a,$z,@args[$a,$z] +); $a = $z; } return 1;

The problem I am having is using this data structure to easy answer questions like this:

$pg->add_fact( gnarfle => qw/ foo bar baz / ); $pg->add_fact( gnarfle => qw/ foo tac toe / ); $pg->add_fact( gnarfle => qw/ tic tac toe / ); my $results = gnarfle( qw/ $one _ $two / ); # or my $results = gnarfle( qw/ $one tac $two / );

In the first example the results should be:

foo baz foo toe tic toe

In the second query the results should be:

foo toe tic toe

Frankly, I'm not having enough free time to work on this problem and when I do get time to work on it, my solutions have all been unsatisfactory. The section of code that starts the unification process is line 194 of Perlog.pm.

Many hearty thanks in advance to anyone who even tries to help out with this problem. I owe you a beer or 17 if you solve it -- there may even be cheap whiskey involved.

Cheers,
Ovid

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.