AI-Prolog
view release on metacpan or search on metacpan
lib/AI/Prolog/Article.pod view on Meta::CPAN
take a look at Salvador FandiE<241>o's C<Language::Prolog::Yaswi>. This module
allows access to SWI-Prolog (http://www.swi-prolog.org/) from within Perl.
It's more difficult to compile and get running, but it's faster and much more
powerful. Luke Palmer's new C<Logic> distribution takes a somewhat different
approach to the same problem space.
=head2 3 Things to Learn
Most programming in Prolog boils down to learning three things: facts, rules,
and queries. The basics of these can be learned in just a few minutes and will
let you read many Prolog programs.
=head3 Facts
Facts in Prolog are stored in what is called the I<database> or I<knowledge
base>. This isn't a PostgreSQL or SQLite database, but a plain-text file. In
fact, you would call it a program and I'd be hard-pressed to argue with you, so
I won't. In fact, I'll often refer to these as Prolog "programs" just to avoid
confusion.
Facts look like this:
gives(tom, book, sally).
B<Note:> While the order of the arguments is technically not relevant, there
is a convention to more or less read the arguments left to right. The above
fact can be read as "tom gives the book to sally." Of course, it is sometimes
read as "sally gives the book to tom", but whichever order you adopt, you must
keep it consistent.
A fact consists of a I<functor> (also known as the I<head>) and 0 or more
arguments, followed by a period. Allowed names for functors generally follow
allowed named for subroutines in Perl.
The number of arguments to the functor are known as the I<arity>. The functor,
followed by a slash and the arity ("gives/3" in this example) is called the
I<predicate>. A predicate can have as many clauses as you like.
gives(tom, book, sally).
gives(tom, book, martin).
gives('George Bush', grief, liberals).
gives('Bill Clinton', grief, conservatives).
Note that those are not function calls. Those are merely facts stating the
relationship of the arguments to one another. Additionally, "tom" and "book"
are each repeated. In Prolog, those each refer to the same entity.
Of course, facts can have a varying number of arguments, even for the same
functor. The following are all legal:
parent(bob, tim). % parent/2
parent(sue, alex, william). % parent/3
male(sue). % male/1
female(sue). % female/1
frobnitz. % frobnitz/0
You can name a predicate just about anything that makes sense, but note that
some predicates are built-in and their names are reserved. The document
C<AI::Prolog::Builtins> has a list of the predicates that C<AI::Prolog>
directly supports. If you're in the C<aiprolog> shell (explained later), you
can type C<help.> to get a list of built-in predicates and
C<help('functor/arity')> (e.g., C<help('consult/1')>) to get description of how
a particular built-in predicate works.
And that pretty much covers most of what you need to know about facts.
=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).
lib/AI/Prolog/Article.pod view on Meta::CPAN
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
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]
Of course, by now you should know that we can reuse this. We can use it to
figure out which list to append to C<X> to create C<Z>.
?- append([1,2,3], Y, [1,2,3,4,5]).
Y = [4,5]
We can also use this to figure out all combinations of two lists can be
appended together to create C<Z>.
?- append(X, Y, [1,2,3,4,5]).
X = [], Y = [1,2,3,4,5]
X = [1], Y = [1,2,3,4]
X = [1,2], Y = [1,2,3]
X = [1,2,3], Y = [1,2]
X = [1,2,3,4], Y = [1]
X = [1,2,3,4,5], Y = []
And the Perl equivalent:
use AI::Prolog;
my $prolog = AI::Prolog->new(<<"END_PROLOG");
append([], X, X).
append([W|X], Y, [W|Z]) :- append(X, Y, Z).
END_PROLOG
my $list = $prolog->list( qw/1 2 3 4 5/ );
$prolog->query("append(X,Y,[$list]).");
while ( my $results = $prolog->results ) {
my ( $x, $y, $z ) = @{ $results }[ 1, 2, 3 ];
$" = ', '; # Array separator
print "[@$x], [@$y], [@$z]\n";
}
As you can see, Prolog lists will be returned to Perl as array references.
C<< $results->[0] >> is the name of the predicate, C<append>, and the next three
elements are the successive values generated by Prolog.
=head1 Problems with Prolog
This article wouldn't be complete without listing some of the issues that have
hampered Prolog.
Perhaps the most significant is the depth-first exhaustive search algorithm
used for deduction. This is slow and due to the dynamically typed nature of
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)
lib/AI/Prolog/Article.pod view on Meta::CPAN
=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.
( run in 0.670 second using v1.01-cache-2.11-cpan-df04353d9ac )