Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

AI::Perlog Unification

by belkajm (Beadle)
on Aug 19, 2002 at 07:09 UTC ( #191098=perlmeditation: print w/ replies, xml ) Need Help??

This was originally posted on Aug 18, 2002 at 21:57 as a reply to Ovid's AI::Perlog Unification help node, but after encouragement from Ovid, i've reposted as a root node.

The following takes place between 12am and 1am on the night of the.....

Sorry about that, but I just had to get it out of my system. Over here in the UK, 24 just finished tonight, and I think I can safely say that it has been one of the best programmes on tv for a long time :)

Anyway, to business. I've been following this for a couple of weeks now, and thought that it'd be a good choice with which to get back into coding perl. After spending a good portion of my friday evening working through the problem, i wrote up some code to do unification. After making sure there were no obvious bugs that i could see, i sent it off to Ovid to get his opinion. I'm happy to say that he liked it, so here's my post on the subject. I'm not going to include the code with this post as it is already 10k in size, but until Ovid posts the updated release i'll be storing a copy at http://downloads.aardvark-ss.com/AI-Perlog-.1.tar.gz for anyone who wants a look.

What I'm going to (attempt to) discuss in this post, is how my unification code actually works, and the change I made to the output structure. Now this is my first substantial post here on permonks, and i'm not sure how good i'll actually be at explaining this, but i'll give it a shot.

Cheers,
Yoda


Output Structure

To make it easier to find what was returned for each individual unified variable, I changed the output from an AoA, to an AoH, where each unified variable is placed into each hash by name. Therefore, the output will look like this:

[ { Var1 => Value1, Var2 => Value2 }, { Var1 => Value3, Var2 => Value4 } ]
Unification Code
Note before starting: important arguments are those where the user has specified undef, the empty string, or an underscore as the argument value, and means that they do not care what value that argument takes on.

Stage 0
I called this stage 0, because it occurs before the main unification code. This stage checks if only one of the arguments passed in was a variable. If this is the case, then we can just get a list of all the possible values for that argument position, and create our AoH from that, because at this stage, we have already checked that all of the constant arguments exist in their positions.

Stage 1
First of all we take our array of arguments, and convert it into another array where any constants are replaced with their vertex id's, and everything else is blank. We'll call this array @new_args. This code was in Ovid's original attempt at unification, although I am going to use it differently to Ovid.

Stage 2
In this stage we prepare the first important element of @new_args in readiness for stage 3. If the element is empty, it means that this argument must be a variable. In this case, we retrieve the list of possible values for the argument, and place this structure into the array element:

[ [vertex_1_id, undef], ...., [vertex_n_id, undef] ]
To make things simpler later on in this explanation, we will consider this to be an array of pairings.
If the array element contained a value, it means that this argument must be a constant, and that the value is the vertex_id of that constant. In this case we create the same structure as above, but with just that one vertex_id.

We are now ready for the next stage, where we operate on two elements of @new_args at a time. Carrying out this preparation, means that in the next stage the 1st element being operating upon is always prepared for us, thereby removing the need for any special cases in the loop.

Stage 3
We will now loop through the important elements of our new_args array, two at a time. If we have three elements, we will therefore operate on elements 0&1, and then 1&2. What we do at each cycle of the loop is dependant on what is contained in the 2nd of the two elements we are operating on at any one time.

If the element contains a value, then as before that element is constrained to only take on that value. First we replace the value with an empty array. Then we loop over every pairing in the 1st element, and check if it possible to get from the value in the pairing to our fixed value from the 2nd element. If it is, then we will add a new pairing to our array. However, instead of having undef as the 2nd value of the pair, we put in a reference to the pairing from the 1st element we are working on.

Alternatively, if the element was empty, things are slightly more involved. We now have to loop every pairing in the 1st element, and find every possible value for the 2nd element that we can get to, adding linked pairings every time as above.

Stage 3 example
To make this slightly easier to understand (hopefully), i'll provide an example at this stage.
We will start with these facts (taken from the unification tests file):

$pg->add_fact( gnarfle => qw/ foo bar baz / ); $pg->add_fact( gnarfle => qw/ foo tac toe / ); $pg->add_fact( gnarfle => qw/ tic tac toe / );
We can now make this query:
$data = $pg->gnarfle( qw/ $one tac $three / )

And we will get a @new_args array as follows (arguments displayed to the side of the actual array):

[ [ [7, undef], [2, undef] ], ' $one ^ ^ [ [5, | ], [5, | ] ], ' tac ^ ^ [ [6, | ], [6, | ] ] ' $three ]

Note that this is a simple example, and with more complicated ones you can get more than one pairing pointing at the same parent.

Stage 4
We now want to take our @new_args array and convert it into a AoH to return to the user. Each result to be returned is made up of a chain of pairings starting from one of the pairings in the final element of @new_args. From our example above then, we would have the sequences 6->5->7, and 6->5->2.

To retrieve and convert these sequences, i simply loop over the pairings in the final element, and then follow the chains for each one, adding values to the output hashes whenever one of the arguments represents a variable. So, as the result of converting the @new_args from our example, we get:

[ { $one => 'foo', $three => 'toe' }, { $one => 'tic', $three => 'toe' } ]
and this is what we return to the user.

Comment on AI::Perlog Unification
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://191098]
Approved by grep
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (4)
As of 2014-11-21 03:36 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (104 votes), past polls