Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

(OT) Pushing inductive systems to their limit

by Ovid (Cardinal)
on Jul 29, 2005 at 19:13 UTC ( #479511=perlmeditation: print w/ replies, xml ) Need Help??

This is an expansion of something in my use.perl journal where I explained how logic programming works. What follows is a brief and over-simplified overview of what lies at the core of automated deduction and logical inference systems the world over. In short, it's at the heart of many AI projects. Even though it's one programming paradigm that's not natively supported by Perl, it's surprisingly simple.

If the following interests you, check out AI::Prolog, Logic or Language::Prolog::Yaswi. If you'll be at OSCON, I'll be talking about the first module.

I was looking at Luke Palmer's Logic module on the CPAN and it got me to thinking a bit about logic programming in general, as opposed to the specific implementation of Prolog I've been focusing on. To implement logic programming, you basically have to implement two things, backtracking and unification.

You already understand backtracking from regular expressions. If you fail to find a match (in our case, if we fail to unify two data structures), back up to the last point in the string (stack) where we can make a different decision and try again. It's pretty straightforward.

Unification is also fairly simple. You know it from makefiles or SQL, but we'll look at logic programming in particular. Imagine that you have two five element lists:

( 1, 2, undef, undef, 5 ) ( 1, 2, 3, 4, undef )

Imagine that undef means "unknown". We can unify those two lists because every element that is known corresponds in the two lists. This leaves us with a list of the integers one through five.

( 1, 2, 3, 4, 5 )

However, what happens if the last element of the first list is unknown?

( 1, 2, undef, undef, undef ) ( 1, 2, 3, 4, undef )

We can still unify the two lists. In this case, we get the same five element list, but the last item is unknown.

( 1, 2, 3, 4, unknown )

Logic programming works by pushing these lists onto a stack and walking through the stack and seeing if you can unify everything (sort of). But how to unify from one item to the next? We assign names to the unknown variables and see if we can unify them. When we get to the next item in the stack, we check to see if any named variables have been unified. If so, we unify the individual variables prior to trying to unify items with their counterparts in our lists.

Thats a bad explanation, so here's how it works. Imagine the following "knowledge base" of lists:

(parent, sally, tom) (parent, bill, tom) (parent, tom, sue) (parent, alice, sue) (parent, sarah, tim) (male, bill) (male, tom) (male, tim)

Now let's assume we have a rule which states that someone is a father if they are a parent and they are male. Maybe we'd define it something like this (imagine that the angle brackets mean "read this and say 'if'"):

( <father, $person>, (parent, $person, $anyone), (male, $person) )

Taking the first term in the rule, the logic engine might try to unify this with the first fact in the knowledge base, "(parent, sally, tom)". $person unifies with "sally" and $anyone unifies with "tom". We then push this information onto a stack. If subsequent facts fail to unify and we come back here, because there are still more facts we can try, we set a "choice point" in the stack telling us which fact we last tried. If we come back and see a choice point, we move on to the next fact and try again.

Moving on to the next term in the rule, "(male, $person)", we know that "sally" is unified to $person, so we now try to unify "(male, sally)" with all of the corresponding rules in the knowledge base. Since we can't, the logic engine backs up to the last item where we could make a new choice and sees "(parent, bill, tom)". $person gets unified with "bill" and $anyone gets unified with "tom". Then in moving to the next rule we see that we unify with "(male, bill)". Now, we check the first item in the rule and see that it's "(father, $person)" and the logic engine reports that "bill" is a father.

Note that we can then force the engine to backtrack and by continuously following this procedure, we can determine who all of the fathers are. ($anyone is ignored and in Prolog, it's marked with an underscore: "_". This means that it's an anonymous variable whose value we really don't care about.)

And that's how logic programming works. Simple, eh? (well, individual items can be lists or other rules, but you get the idea).

Getting back to Perl (and Prolog), the above can be implemented in AI::Prolog like so:

#!/usr/bin/perl use strict; use warnings; use AI::Prolog; my $prolog = AI::Prolog->new(<<END_PROLOG); parent(sally, tom). parent(bill, tom). parent(tom, sue). parent(alice, sue). parent(sarah, tim). male(bill). male(tom). male(tim). father(Person) :- parent(Person, _), male(Person). END_PROLOG $prolog->query('father(Whom)'); while (my $results = $prolog->results) { print "@$results\n"; } __END__ father bill father tom

(Note: see also Bringing Logic Programming to Perl for some code with an older version of this module)

Now that's all well and good, but Luke Palmer's code has me thinking a bit. Generally we're unifying lists. What if we try to unify arbitrary data structures? What if we also want to unify hashes, or typeglobs or URI objects? What should happen if I tried to unify a regular expression against a string?

In other words, I'm seriously interested in an entirely separate module which allows robust unification of perl data structures. Consider how unification works. First, if a particular item has a value we say it is "bound" to that value. We can then unify two items if they fall under one of the following three conditions:

  1. They are both bound to the same value ("bob" and "bob").
  2. The are both unbound (unknown and unknown).
  3. One is bound and the other is not ("bob" and "unknown").

(There's something else called an "occurs check", but that's beyond the scope of this meditation)

So what happens if we add a fourth condition: one item is bound and another item is "conditionally bound". If one item is "bob" and the second item is qr/[[:alpha:]]/, then both terms could be bound to "bob". If one item is the HTML of a Web page and the second item is a URI object, they could be bound to the HTML if the entity body of the URI matches the HTML. So for each type of "conditionally bound" object, we'd have to specify unification criteria. Imagine a Number::Prime object which only unifies with prime numbers. This could simplify quite a bit of logic code.

The main problem that I see is what happens when one tries to unify two conditionally bound objects? Should a junction be the result? Should the unification fail because we have nothing real to bind to? Should they only be allowed to unify iff they are identical? Is there any merit to this idea at all?

Update: Fixed typo that AReed pointed out.

Cheers,
Ovid

New address of my CGI Course.

Comment on (OT) Pushing inductive systems to their limit
Select or Download Code
Re: (OT) Pushing inductive systems to their limit
by blokhead (Monsignor) on Jul 29, 2005 at 21:39 UTC
    Sounds interesting. I have had unification on my mind a lot lately as well. Unification just makes life really nice, as you can be declarative instead of imperative. Modern functional languages like OCaml and (especially) Haskell use tons of unification. The most notable application is for the various forms of case statements you'll find in these languages (either explicit case statements or implicit conditional behavior, like function overloading & multimethods), so I think of unification mainly as a method for conditional behavior based on the structure of the data involved.

    I don't know a lot about heavy-duty logic programming, so I'm wondering what (if any) kinds of logic programming paradigms aren't easily do-able with nothing but a good unification-based case statement (perhaps in the guise of multimethod dispatch)?

    In other words, I'm seriously interested in an entirely separate module which allows robust unification of perl data structures.
    Again, the application to case statements makes this sound like it's in a similar vein to P6's "~~" smart match operator.
    The main problem that I see is what happens when one tries to unify two conditionally bound objects? Should a junction be the result? Should the unification fail because we have nothing real to bind to? Should they only be allowed to unify iff they are identical? Is there any merit to this idea at all?
    A junction/intersection is the only interpretation that makes any sense to me.

    If you think of unification using a geometric interpretation, the unbound variables in the unification problem are the basis of a vector space, the constraints are linear/affine (in)equalities in that space, and the solution of the unification is the intersection of all the affine constraints. Think of unifying (x,x,y) with (x,y,y). The 2-d vector space of assignments to {x,y} collapses to a 1-d vector space.

    Of course the constraints you are considering aren't affine, and the spaces aren't exactly vector spaces, but the intuition is the same. Under this interpretation, it's clear that you would want to take the intersection of the ranges of two "conditionally bound" objects.

    blokhead

Re: (OT) Pushing inductive systems to their limit
by Anonymous Monk on Jul 29, 2005 at 22:54 UTC
    This sounds very much like constraint programming to me. For the most part, unification is an equality constraint between two variables. If the two are unbound, there's no change, if one is bound, the value is propagated to the other, if both are bound, the values must be equivalent or the network is inconsistent. On an inconsistency, remove the last constraint and try placing it somewhere else. The more complex "conditional unification" you're talking about are procedural constraints; the constraint is satisfied iff the body of the URI matches the HTML.
    You may want to look at this.
Re: (OT) Pushing inductive systems to their limit
by salva (Abbot) on Jul 30, 2005 at 16:45 UTC
    Ovid, in prolog, attributed variables is what you are looking for.

    Attributed variables are unbound variables but with a set of conditions or attributes attached. When an attributed variable is unified with anything else, its attached attributes (that are effectively callback predicates) are called, and their success or failure determines also the success or failure of the unification.

    Most free prolog implementations (SWI-Prolog, YAP, XSB ) support them (unfortunately Language::Prolog::Yaswi doesn't), and it should be too difficult to extend AI::Prolog to also do so.

    Attributed variables are mostly used in prolog to implement constraint logic programing (CLP). A good introduction to CLP is available on Bratko's Prolog Programing for Artificial Intelligence.

Re: (OT) Pushing inductive systems to their limit
by adrianh (Chancellor) on Jul 30, 2005 at 18:47 UTC

    The unification as part of the language idea reminded me of matching in Lisp and Pop-11 (see chapter 7 of the Pop-11 Primer] and chapter 19 of On Lisp). Not exactly what you're talking about but might be worth a look.

    Consider how unification works. First, if a particular item has a value we say it is "bound" to that value. We can then unify two items if they fall under one of the following three conditions

    Like the Var class in Perl and Prolog and Continuations... oh my! :-)

    The main problem that I see is what happens when one tries to unify two conditionally bound objects? Should a junction be the result? Should the unification fail because we have nothing real to bind to? Should they only be allowed to unify iff they are identical? Is there any merit to this idea at all?

    I don't see why it would be different from unification of "normal" unbound variables. The logic is the same, it's just the equality test that's different.

Re: (OT) Pushing inductive systems to their limit
by jdporter (Canon) on Jul 31, 2005 at 16:27 UTC
    The main problem that I see is what happens when one tries to unify two conditionally bound objects? Should a junction be the result? Should the unification fail because we have nothing real to bind to? Should they only be allowed to unify iff they are identical?
    Which leads me to wonder if Perl6's any/all will address this space, either by default or via straightforward extension. (Or, for that matter, if Perl6's rules will be able to. I would assume they can operate on structures, not just on text source...)
Re: (OT) Pushing inductive systems to their limit
by halley (Prior) on Jul 31, 2005 at 21:50 UTC
    If all you want is simple unification as described above, you might want to check out my Data::Binder data structure. It's not a complicated module, but it helps when I want to collect a number of tuples unless they conflict.

    --
    [ e d @ h a l l e y . c c ]

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (5)
As of 2014-12-25 08:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (159 votes), past polls