AI-Prolog
view release on metacpan or search on metacpan
lib/AI/Prolog/Article.pod view on Meta::CPAN
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).
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
lib/AI/Prolog/Article.pod view on Meta::CPAN
= 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.
lib/AI/Prolog/Article.pod view on Meta::CPAN
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:
append([], X, X).
append([HEAD|X], Y, [HEAD|Z]) :-
append(X, Y, Z).
You'll probably want to put that in a file named I<append.pro> and in the
shell C<consult('append.pro')> to follow along with some of the examples
you're about to see.
Explaining how that works would take a bit of time, so I recommend you work it
out on your own. Instead, I'll focus on its implications.
It looks like a lot of work to define how to append two lists. Perl is much
simpler:
my @Z = (@X, @Y);
In fact, that hides quite a bit of complexity for us. Anyone who has had to
concatenate two arrays in C can appreciate the simplicity of the Perl approach.
So what would the complexity of the C<append/3> predicate gain us? Naturally,
we can use this to append two lists. (The following output is similar to what
one would see in regular Prolog systems. It's been reproduced here for
clarity.)
?- append([1,2,3], [4,5], Z).
Z = [1,2,3,4,5]
lib/AI/Prolog/Article.pod view on Meta::CPAN
=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.
( run in 0.836 second using v1.01-cache-2.11-cpan-39bf76dae61 )