Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

AI::Perlog Unification help

by Ovid (Cardinal)
on Aug 13, 2002 at 21:17 UTC ( [id://189943] : perlquestion . print w/replies, xml ) Need Help??

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

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.


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

Replies are listed 'Best First'.
Re: AI::Perlog Unification help
by Ferret (Scribe) on Aug 13, 2002 at 23:02 UTC

    I get to be amazed I understand as much as I do. I declare you an honorary masochist by virtue of coding Perl.

    I'm still working through it, particularly trying to understand what it is supposed to look like and behave like, and noticed something which _might_ be of service:

    If I understand it correctly, the _add_level method currently overwrites facts with the same first element. I imagine I'm trouncing all over established terminology, so let me illustrate instead.

    You have the two facts:

    $pg->add_fact( gnarfle => qw/ foo bar baz / ); $pg->add_fact( gnarfle => qw/ foo tac toe / );
    After doing some recursive dance I've not yet deciphered, the appropriate portion of the tree looks like:
    { '2' => [ undef, { '3' => 3 }, { '4' => 4 } ] }

    But after the foo bar baz rule begins, it looks like a terribly disappointing

    { '2' => [] }

    which is then fleshed out with the 5 and 6 entries. After it's done, instead of {foo => [undef,tac,toe]}, it's {foo => [undef,bar,baz]}

    The end result is that you lose part of the tree, and no longer get full results from doing rule requests.

    You've probably already noticed this one, and I don't yet have enough clue to fix it correctly (I have a feeling it'll require a data structure tweak, and I don't know enough about the module to do it yet). If this was confusing anyone else, I hope I've explained what was happening.

    I just learned about Data::Dumper::Deepcopy - useful when Dumper decides that all undefs are actually a reference to the same element. That was confusing, too.

    Thanks for the puzzle, Ovid!



      I just added the following line to the end of facts.t:

      ok( $pg->gnarfle( qw/ foo bar baz /), '... this should still match +' ); ok( $pg->gnarfle( qw/ foo tac toe /), '... as should this.' );

      The first one fails (as you said it would). I updated the number of tests and, for a lark, ran this against an older copy. Still fails. Bummer. Working on a fix now. Wish I knew how I missed that one.

      Update: Quick fix, fortunately. I needed to test to see if I had an array ref there to ensure that I added to it rather than overwriting it. You can download the new code (with updated tests) here.


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

AI::Perlog(2) unification proposition
by arhuman (Vicar) on Aug 14, 2002 at 14:19 UTC
    No sir, AI::Perlog isn't in limbo ;-)

    I've been playing with it lately (not as much as I wanted though )
    and it still makes me dream...

    Your code seems to assume that the positions do matter with the predicates
    args, while your explanation seems to suggest the contrary
    (Your funny relation with whiskey ;-)

    I don't recall how it was in Prolog,
    but I think that some predicates should be order dependant :
    should only be read "arhuman is disciple's father"
    it's definitly not the same as
    whereas some predicates obviously shouldn't
    could be also written

    It's probably not that important, but if AI::Perlog will have to handle
    both cases it may be a good idea to take it into account now.

    Anyway, to contribute I've coded AI::Perlog2.
    Don't be scare it's NOT a fork, takeover attempt or whatever,
    it's only my way to try to play with concepts and
    to experiment without messing too much with your code :-)
    Take it only as an implementation playground (and maybe a test/bench helper)
    to experiment/choose data structures.

    While poorly coded AI::Perlog2 might even includes some ideas
    which could be put into your module :
    • There's a rudimentary unification algorithm which (seems to) work(s).
    • I've tried to use simpler structures (that I could understand ;-)
    • It handles also "order independent" predicates
      (when first argument is a '?')
    • Included a dirty 'load_from_file' method
      which would allow to load facts easily regardless of the implementation
      (that's why I ruled serialization out))
      to enable use of both Perlog and Perlog2 on the same facts database...
    UPDATE : display function slightly edited.
Re: AI::Perlog Unification help
by belkajm (Beadle) on Aug 19, 2002 at 00:57 UTC
    Update: After encouragement from Ovid, I've reposted this as the following root node: AI::Perlog Unification. Sorry for any inconvenience.
Re: AI::Perlog Unification help
by arhuman (Vicar) on Aug 14, 2002 at 20:35 UTC
    I forgot to mention the database format :
    (You can understand it from the source, but I'll take a low profile as I provided no doc AT ALL :-)

    add_fact(theory=> qw(foo bar baz));
    add_fact(theory=> qw(foo tac toe));
    add_fact(theory=> qw(tic tac toe));
    add_fact(theory=> qw(tac lac toe));

    Now a little example on how to use it :

    #!/usr/bin/perl -w use strict; #use Devel::StealthDebug; use lib '.'; use Perlog; use Perlog2; #my $pg = AI::Perlog->new; my $pg2 = AI::Perlog2->new; #$pg->load_from_file('database.txt'); $pg2->load_from_file('database.txt'); # # Perlog2 should definitly export display ;-) # AI::Perlog2::display($pg2->theory(qw/$x tac $y/)); print "*********\n"; AI::Perlog2::display($pg2->theory(qw/? $x tac $y/)); print "*********\n"; AI::Perlog2::display($pg2->theory(qw/tic tac toe/)); print "*********\n"; AI::Perlog2::display($pg2->theory(qw/tIc tac toe/)); *******************<br>

    I've updated the display function's code in my previous post to handle 'false' answers.

    "Only Bad Coders Code Badly In Perl" (OBC2BIP)
Re: AI::Perlog Unification help
by adrianh (Chancellor) on Aug 29, 2002 at 03:26 UTC

    In the spirit of TMTOWTDI people might might find "Perl and Prolog and Continuations... oh my!" of interest.

    People might also find this next bit of info interesting.... but they also might find it that it spoils the fun of this thread (sorry Ovid :-). Hence the uuencoding. You have been warned.

    print unpack "u", <<'EOT'; M5&AE<F4@:7,@82!-871H.CI,;V=I8SHZ4')E9&EC871E(&]N($-004X@=&AA M="!D;V5S(&UO<W0@;V8@=VAA="!I="!L;V]K<R!L:6ME('EO=2!W86YT($%) 2.CI097)L;V<@=&\@9&\@.BTI EOT