view release on metacpan or  search on metacpan

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

=head3 Rules

Rules, like facts, are stored in the program.  Rules describe how we can infer
new facts, even though we haven't explicitly stated them.

 gives(tom, book, SOMEONE) :-
     person(SOMEONE),
     likes(tom, SOMEONE).

This rule states that "Tom will give a book to anyone who Tom likes." Note that
we are not telling Prolog how to figure out to whom Tom will give books.
Instead, we have merely defined the conditions under which Tom is willing to
part with his material possessions.

To understand rules, read the neck operator, C<:->, as "if" and commas outside
of argument lists as "and."  Further, arguments beginning with upper-case
letters are I<variables>, such as C<SOMEONE> in the rule above.  Note that only
the first letter needs to be capitalized; C<Someone> would also be a variable,
as would C<SomeOne> or C<SOmeoNe>.

Of course, we could simply enumerate the relationships:

 gives(tom, book, alice).
 gives(tom, book, bob).
 gives(tom, book, martin).
 gives(tom, book, charlie).
 gives(tom, book, ovid).

However, this quickly become unweildy as the number of people in our program
grows.

=head3 Queries

Now that we have a rough understanding of facts and rules, we need to know how
to get answers from them.  Queries are typically entered in the "interactive
environment." This would be analogous to the query window in a database GUI.
With C<AI::Prolog>, a shell named C<aiprolog> is included for demonstration
purposes though we'll mainly focus on calling Prolog from within a Perl
program.

 ?- gives(tom, book, SOMEONE).

This looks just like a fact, but with some minor differences.  The C<?-> at the
beginning of the query is a query prompt seen in interactive environments.

You'll also note that C<SOMEONE> is capitalized, making it a variable (only the
first letter needs to capitalized.)  Thus, this query is asking who Tom will
gives books to.

 ?- gives(WHO, book, SOMEONE).

This query looks like the previous one, but since the first argument is
capitalized, we're asking "who will give books to whom?".

 ?- gives(WHO, WHAT, WHOM).

Finally, because all arguments are variables, we're asking for everyone who
will give anything to anybody.

Note that no code changes are necessary for any of this.  Because Prolog facts
and rules define relationships between things, Prolog can automatically infer
additional relationships if they are logically supported by the program.

Let's take a closer look at this, first focusing on the C<aiprolog> shell.
Assuming you've installed C<AI::Prolog> and said "yes" to installing the
C<aiprolog> shell, enter the following text in a file and save it as
I<gives.pro>.  Note that lines beginning with a percent sign (C<%>) are
single-line comments.

 % who are people?
 person(bob).
 person(sally).
 person(tom).
 person(alice).
 
 % who likes whom?
 likes(tom, bob).
 likes(tom, alice).
 likes(alice, bob).
 
 % who has what
 has(tom, book).
 has(alice, ring).
 has(bob, luck).
 
 % who will give what to whom?
 gives(WHO, WHAT, WHOM) :-
     has(WHO, WHAT),
     person(WHOM),
     likes(WHO, WHOM).
 
 gives(tom,book,harry).
 
When starting the shell, you can read in a file by supplying as a name on the
command line:

 $ aiprolog gives.pro

Alternately, you can I<consult> the file from the shell:
 
 $ aiprolog

 Welcome to AI::Prolog v 0.732
 Copyright (c) 2005, Curtis "Ovid" Poe.
 AI::Prolog comes with ABSOLUTELY NO WARRANTY.  This library is free software;
 you can redistribute it and/or modify it under the same terms as Perl itself.

 Type '?' for help.

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

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

     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,
after you issue the query you can "trace" the execution:

 $prolog->query('father(Who)');
 $prolog->trace(1); # after the query, before the results
 while ( my $result = $prolog->results ) {
   ...

Running the program again produces a lot of output, the beginning of which 
matches our description of how logic programming works internally:

 = Goals: 
         father(A)
 ==> Try:  father(A) :- 
         parent(A, B),
         male(A)
 
 = Goals: 
         parent(A, C),
         male(A)
 ==> Try:  parent(sally, tom) :- null
 
 = Goals: 
         male(sally)
 ==> Try:  male(bill) :- null
  <<== Backtrack: 
 
 = Goals: 
         male(sally)
 ==> Try:  male(tom) :- null
  <<== Backtrack: 
 
 = Goals: 
         male(sally)
 ==> Try:  male(tim) :- null
  <<== Backtrack: 

 [etc.]

Now if you really want to have fun with it, notice how you can rearrange the
clauses in the program at will and Prolog will return the same results (though
the order will likely change).  This is because when one programs in a purely
declarative style, the order of the statements no longer matters.  Subtle bugs
caused by switching two lines of code usually go away.

=head2 Prolog versus Perl

Now that you have a beginning understanding of what Prolog can do and how it
works internally, let's take a look at some of the implications of this.  By
now, you know that the following can be read as "Ovid loves Perl":

 loves(ovid, perl).

Assuming you've consulted a file with that fact in it, querying to find out
what I love is simple:

 ?- loves(ovid, WHAT).

In Perl, it's also pretty simple:

 %loves = ( ovid => 'perl' );
 $what  = $loves{ovid};

But how do we find out who loves Perl?  In Prolog:

 loves(WHO, perl).

In Perl, however, we have two options, neither of them particularly good.  We
can scan the C<%loves> hash for entries whose value is Perl, but this is
C<O(n)> when we want to stick with our simple C<O(1)> check.  Thus, a more
common solution is to reverse the hash:

 %who_loves = reverse %loves;
 $who       = $who_loves{perl};

(C<AI::Prolog>, being written in Perl, is slow.  So the C<O(n)> versus
C<O(1)> argument doesn't hold.  Versions written in C are far more practical in
this regard.)

But this fails, too.  The first problem is that we have duplicated data.  If we
have to add additional data to the C<%loves> hash, we'll have to remember to
synchronize the hashes.  The second problem is that Perl is just a little too
popular:

 loves(ovid,    perl).
 loves(alice,   perl).
 loves(bob,     perl).
 loves(charlie, perl).

If we simply reverse the hash for those entries, we lose three of those names.
So we have to play with this some more.

 while ( my ($person, $thing) = each %loves ) {
     push @{ $who_loves{$thing} }, $person;
 }

Oh, wait.  This fails too.  You see, I'm fickle.

 loves(ovid, perl).
 loves(ovid, prolog).
 loves(ovid, 'Perl 6').

(The quotes around "Perl 6" tell Prolog that this is a single value and that
it's a constant, not a variable.)

How do I find out everything Ovid loves?  In Prolog, the query doesn't change:

 loves(ovid, WHAT).

In Perl, our original hash wasn't enough.

 my %loves = (
     ovid    => [ qw/perl prolog Perl6/ ],
     alice   => [ 'perl' ],
     bob     => [ 'perl' ],
     charlie => [ 'perl' ],
 );

 my %who_loves;
 while ( my ($person, $things) = each %loves ) {
     foreach my $thing ( @$things ) {
         push @{ $who_loves{$thing} }, $person;
     }
 }

Now that's starting to get really ugly.  To represent and search that data in
Prolog is trivial.  Now do you really want to have fun?

 gives(tom, book, sally).

How would you represent that in Perl?  There could be multiple gift-givers,
each gift-giver could give multiple things.  There can be multiple recipients.
Representing this cleanly in Perl would not be easy.  In fact, when handling
relational data, Perl has several weaknesses in relation to Prolog.

=over 4

=item * Data must often be duplicated to handle bi-directional relations.

=item * You must remember to synchronize data structures if the data changes.

=item * Often you need to change your code if your relations change.

=item * The code can get complex, leading to more bugs.

=back

=head2 Prolog versus SQL

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