AI::Perlog Unificationby belkajm (Beadle)
|on Aug 19, 2002 at 07:09 UTC||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.
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:
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.
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.
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
We can now make this query:
And we will get a @new_args array as follows (arguments displayed to the side of the actual array):
Note that this is a simple example, and with more complicated ones you can get more than one pairing pointing at the same parent.
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:
and this is what we return to the user.