view release on metacpan or  search on metacpan

lib/AI/Prolog/Article.pod  view on Meta::CPAN

 ?- consult('gives.pro').

The second notation allows you to consult multiple files and add all of them to
the knowledge base.

After issuing the C<consult/1> command, the shell will appear to hang.  Hit
I<Enter> to continue.  We'll explain this behavior in a moment.

Now that you've loaded the program into the shell, issue the following query:

 ?- gives(X,Y,Z).

The shell should respond:

 gives(tom, book, bob) 

It will appear to hang.  It wants to know if you wish for more results or if
you are going to continue.  Typing a semicolon (;) tells Prolog that you want
it to I<resatisfy> the goal.  In other words, you're asking Prolog if there are
more solutions.  If you keep hitting the semicolon, you should see something
similar to the following:

 ?- gives(X,Y,Z).

 gives(tom, book, bob) ;

 gives(tom, book, alice) ;

 gives(alice, ring, bob) ;

 gives(tom, book, harry) ;

  No
 ?- 

That final "No" is Prolog telling you that there are no more results which
satisfy your goal (query).  (If you hit I<Enter> before Prolog prints "No", it
will print "Yes", letting you know that it found results for you.  This is
standard behavior in Prolog.)

One thing you might notice is that the last result, C<gives(tom, book, harry)>,
does not match the rule we set up for C<gives/3>.  However, we get this result
because we chose to hard-code this fact as the last line of the Prolog program.

=head2 How this works

At this point, it's worth having a bit of a digression to explain how this
works.

Many deductive systems in artificial intelligence are based on two algorithms:
backtracking and unification.  You're probably already familiar with backtracking
from regular expressions.  In fact, regular expressions are very similar to
Prolog in that you specify a pattern for your data and let the regex engine
worry about how to do the matching.

In a regular expression, if a partial match is made, the regex engine remembers
where the end of that match occurred and tries to match more of the string.  If
it fails, it backtracks to the last place a successful match was made and sees
if there are alternative matches it can try.  If that fails, it keeps
backtracking to the last successful match and repeats that process until it
either finds a match or fails completely.

Unification, described in a fit of wild hand-waving, attempts to take two
logical terms and "unify" them.  Imagine you have the following two 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, undef )

If corresponding terms of the two lists are both bound (has a value) but not
equal, the lists will not unify:
 
 ( 1, 23, undef, undef, undef )
 ( 1,  2,     3,     4, undef )

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 values 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, the engine will try to unify
them along with the other known variables.

That's a bad explanation, so here's how it works in Prolog. Imagine the
following knowledge base:

 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 that states that someone is a father if they
are a parent and they are male.

 father(Person) :-
   parent(Person, _),
   male(Person).

In the above rule, the underscore is called an "anonymous vairable" and means
"I don't care what this value is."  Prolog may still bind the variable
internally (though this behavior is not guaranteed), but its value will not be
taken into account when trying to determine if terms unify.

Taking the first term in the rule, the logic engine might try to unify this
with the first fact in the knowledge base, C<parent(sally, tom)>. C<Person>
unifies with I<sally>.  The underscore, C<_>, unifies with I<tom> but since
we stated this unification is unimportant, we can ignore that.

We now have a fact which unifies with the first term in the rule, so we push
this information onto a stack.  Since there are still additional facts we can
try, we set a "choice point" in the stack telling us which fact we last tried.
If we have to backtrack to see a choice point, we move on to the next fact and
try again.

Moving on to the next term in the rule, C<male(Person)>, we know that "sally"
is unified to C<Person>, so we now try to unify C<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
C<parent(bill, tom)>. C<Person> gets unified with I<bill>. Then in moving to
the next rule we see that we unify with C<male(bill)>. Now, we check the first
item in the rule and see that it's C<father(Person)>. and the logic engine
reports that I<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 the fathers are.

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

=head2 Executing Prolog in Perl

Getting back to Perl, how would we implement that in a Perl program?

The basic process for using C<AI::Prolog> looks something like this:

 use AI::Prolog;
 my $prolog = AI::Prolog->new($prolog_code);

Create a new C<AI::Prolog> object, passing Prolog code as the argument.  If you
prefer, you can wrap the constructor in a C<BEGIN> block:

 my $prolog;
 BEGIN {
   $prolog = AI::Prolog->new(<<'  END_PROLOG');
     % some Prolog code goes here
   END_PROLOG
 }

This is not strictly necessary, but if your Prolog code has a syntax error, it
will be a compile-time error, not a run-time error, and you'll get an error
message similar to:

 Unexpected character: (Expecting: ')'.  Got (.)) at line number 12.
 BEGIN failed--compilation aborted at test.pl line 7.

Note that the line number for "Unexpected character" is relative to the Prolog
code, not the Perl code.

After the contructor, issue your query:

 $prolog->query($some_query);

And do something with the results:

 while ( my $results = $prolog->results ) {
     print "@$results\n";
 }

Results are usually each returned as an array reference with the first argument
being the functor and subsequent arguments being the values.  If any value is a
list, it will be represented as an array reference.  We'll see more on that
later as we cover lists.

Now let's see the full program:

 #!/usr/bin/perl
 use strict;
 use warnings;
 use AI::Prolog;
 
 my $prolog;
 
 # If reading from DATA, we need a CHECK block to ensure that
 # DATA is available by the time the constructor is called
 CHECK {
   $prolog = AI::Prolog->new( do { local $/; <DATA> } );
 }
 
 $prolog->query( 'father(WHO).' );
 while ( my $results = $prolog->results ) {
     print "@$results\n";
 }
 
 __DATA__

lib/AI/Prolog/Article.pod  view on Meta::CPAN

Prolog, many of the optimizations that have been applied to databases cannot be
applied to Prolog.  Many Prolog programmers, understanding how the language
works internally, use the "cut" operator, C<!> (an exclamation point), to prune
the search trees.  This leads to our next problem.

The "cut" operator is what is known as an "extra-logical" predicate.  This,
along with I/O and predicates that assert and retract facts in the database
are a subject of much controversy.  They cause issues because they frequently
cannot be backtracked over and the order of the clauses sometimes becomes
important when using them.  They can be very useful and simplify many problems,
but they are more imperative in nature than logical and can introduce subtle
bugs.

Math is also handled poorly in Prolog.  Consider the following program:

  convert(Celsius, Fahrenheit) :-
       Celsius is (Fahrenheit - 32) * 5 / 9.

You can then issue the query C<convert(Celsuis, 32)> and it will dutifully
report that the celsius value is zero.  However, C<convert(0, 32)> fails.  This
is because Prolog is not able to solve the right hand side of the equation
unless C<Fahrenheit> has a value at the time that Prolog starts examining the 
equation.  One simplistic way of getting around this limitation is with multiple
predicates and testing which argument is an unbound variable:

 convert(Celsius, Fahrenheit) :-
     var(Celsius),
     not(var(Fahrenheit)),
     Celsius is (Fahrenheit - 32) * 5 / 9.

 convert(Celsius, Fahrenheit) :-
     var(Fahrenheit),
     not(var(Celsius)),
     Fahrenheit is (Celsius * (9/5)) + 32.

This has a variety of problems, not the least of which is that it offers no
advantages over imperative programming.

ISO-Prolog does not define it, but many Prolog implementations support
constraints and these, though beyond the scope of this article, can get around
this and other issues.  They can allow "logical" math and ensure that
"impossible" search branches are never explored.  This can help to alleviate
many of the aforementioned concerns.

=head1 Conclusion

We've barely scratched the surface of what the Prolog language can do.  The
language has many detractors and some criticisms are quite valid.  However, the
language's simplicity and ease-of-use has kept it around.  It's an excellent
starting point for understanding logic programming and exploration of AI.  In
fact, many common uses for Prolog are heavily used in the AI arena:

=over 4

=item * Agent-based programming

=item * Expert Systems

=item * Fraud prevention (via inductive logic programming)

=item * Natural language processing

=item * Rules-based systems

=item * Scheduling systems

=item * And much more (it was even embedded in Windows NT) 

=back

At the present time, I would not recommend C<AI::Prolog> for production work.
Attempts to bring logic programming to Perl are still relatively recent and no
module (to this author's knowledge) is currently ready for widespread use.  The
C<AI::Prolog> distribution has a number of sample programs in the C<examples/>
directory and two complete, albeit small, games in the C<data/> directory.

=head1 References

=head2 Online Resources

=over 4

=item Adventure in Prolog

http://amzi.com/AdventureInProlog/index.htm

I highly recommend Amzi! Prolog's free online book "Adventure in Prolog."  It's
clearly written and by the time you're done, you've built Prolog programs for
an adventure game, a genealogical database, a customer order inventory
application and a simple expert system.

=item Building Expert Systems in Prolog

http://amzi.com/ExpertSystemsInProlog/xsipfrtop.htm

This free online book, also by Amzi!, walks you through building expert
systems.  It includes expert systems for solving Rubik's cube, tax preparation,
car diagnostics and many other examples.

=item Databases Vs AI

http://lsdis.cs.uga.edu/~cartic/SemWeb/DatabasesAI.ppt

This Powerpoint presentation discusses AI in Prolog and compares it to SQL
databases.

=item W-Prolog

http://goanna.cs.rmit.edu.au/~winikoff/wp/

Dr. Michael Winikoff kindly gave me permission to port this Java application to
Perl.  This formed the basis of the earliest versions.

=item X-Prolog

http://www.iro.umontreal.ca/~vaucher/XProlog/

Jean Vaucher, Ph.D., allowed me to borrow from X-Prolog for the first
implementation of math in C<AI::Prolog>.  Currently, C<AI::Prolog> is a hybrid
of these two applications, but it has evolved in a much different direction.