AI-Prolog

 view release on metacpan or  search on metacpan

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

 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__
 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).

If you run this program, it will quite happily print out "father bill" and
"father tom."  In fact, if you really want to see what's going on internally,

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

At this point, there's a good chance that you're thinking that you would just
stuff this into a relational database. Of course, this assumes you need
relational data and want to go to the trouble of setting up a database and
querying it from Perl.  This is a good solution if you only need simple
relations.  In fact, Prolog is often used with relational databases as the two
are closely related.  SQL is a I<special purpose> declarative language whereas
Prolog is a I<general purpose> declarative language.

Firing up SQLite, let's create two tables and insert data into them.

 sqlite> CREATE TABLE parent_2 (parent VARCHAR(32), child VARCHAR(32));
 sqlite> CREATE TABLE male_1   (person VARCHAR(32));

 sqlite> INSERT INTO parent_2 VALUES ('sally', 'tom');
 sqlite> INSERT INTO parent_2 VALUES ('bill', 'tom');
 sqlite> INSERT INTO parent_2 VALUES ('tom', 'sue');
 sqlite> INSERT INTO parent_2 VALUES ('alice', 'sue');
 sqlite> INSERT INTO parent_2 VALUES ('sarah', 'tim');

 sqlite> INSERT INTO male_1   VALUES ('bill');
 sqlite> INSERT INTO male_1   VALUES ('tom');
 sqlite> INSERT INTO male_1   VALUES ('tim');

We can then find out who the fathers are with the following query.

 SELECT parent 
 FROM   parent_2, male_1 
 WHERE  parent_2.parent = male_1.person;

This is very similar to Prolog but we are forced to explicitly state the
relationship.  Many Prolog queries are conceptually similar to SQL queries but
the relationships are listed directly in the program rather than in the query.
When working with a relational database, we can get around this limitation with
a view:

 CREATE VIEW father AS
     SELECT parent 
     FROM   parent_2, male_1 
     WHERE  parent_2.parent = male_1.person;

And finding out who the fathers are is trivial:

 SELECT * FROM father;

Further, databases, unlike many Prolog implementations, support indexing,
hashing, and reordering of goals to reduce backtracking.  Given all of that,
why on earth would someone choose Prolog over SQL?

As stated earlier, Prolog is a general purpose programming language.  Imagine
if you had to write all of your programs in SQL.  Could you do it?  You could
with Prolog.  Further, there's one huge reason why one might choose Prolog:
recursion.  Some SQL implementations have non-standard support for recursion,
but usually recursive procedures are simulated by multiple calls from the
programming language using SQL.

Let's take a look at recursion and see why this is a win.

=head2 Recursion and Lists

In Prolog, lists are not data structures.  They're actually implemented in
terms of something referred to as the "dot functor" (./2).  For our purposes,
we'll ignore this and pretend they're really data types.  In fact, there's
going to be a lot of handwaving here so forgive me if you already know Prolog.
If you know LISP or Scheme, the following will be very familiar.

A list in Prolog is usually represented by a series of terms enclosed in square
brackets:

 owns(alice, [bookcase, cats, dogs]).

A list consists of a head and a tail.  The tail, in turn, is another list with
a head and tail, continuing recursively until the tail is an empty list.  This
can be represented as follows:

 [ HEAD | TAIL ]

Note that the head and tail are separated by the pipe operator.

Now if Alice owns things, how do we find out if she owns cats?  First, we need
to define a predicate that succeeds if a given term is an element of a given
list.

 member(X, [ X | _ ]).
 member(X, [ _ | TAIL ]) :-
    member(X, TAIL).

The first clause in this predicate states that C<X> is a member of a list if
it's the head of a list.  The second clause states that C<X> is a member of a
list if it's a member of the tail of the list.  Here's how this works out:

 ?- member(3, [1,2,3,4]).

Prolog checks the first clause and sees that 3 is not the head of the list:
C<member(3, [1|2,3,4])>.  It then checks to see if it's a member of the tail of
the list: C<member(3, [2|3,4])>.  Again this fails so Prolog tries again and
we succeed:  C<member(3, [3|4])>.

So how do we see if Alice has cats?

 has(PERSON, THING) :-
     owns(PERSON, STUFF),
     member(THING, STUFF).

And the query C<has(alice, cats)> will now succeed.  However, as mentioned
previously, Prolog predicates can often be reused to deduce information that
you and I could deduce.  Thus, we can find out who owns cats (C<has(WHO,
cats)>), everything Alice has (C<has(alice, WHAT)>), or everything that
everyone has (C<has(WHO, WHAT>).

Why does that work?  Well, going back to the C<member/2> predicate, we can find
out if a term is an element of a list:

 member(ovid, SOMELIST).

Or we can find all members of a list:

 member(X, SOMELIST). % assumes SOMELIST is bound to a list

Now that might seem kind of nifty, but appending lists in Prolog is truly
sublime.  Many consider understanding the power of the C<append/3> predicate
the true gateway to appreciating logic programming.  So, without further ado:

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

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.

=back

=head2 Books

=over 4

=item Programming in Prolog

http://portal.acm.org/citation.cfm?id=39071

This book is sometimes referred to simply as "Clocksin/Mellish".  First
published in the early 80s, this is the book that brought Prolog into the
mainstream.

=item The Art of Prolog

htp://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=8327

This excellent MIT textbook is very in-depth and covers "proving" Prolog
programming, second-order logic, grammars, and many working examples.

=back

=head1 Credits

Many thanks to Rebekah Golden, Danny Werner and David Wheeler for their
excellents comments and insights.