AI-Prolog
view release on metacpan or search on metacpan
lib/AI/Prolog/Article.pod view on Meta::CPAN
=head1 Logic Programming in Perl
=head2 Introduction
A programmer who hasn't been exposed to all four of the imperative,
functional, objective, and logical programming styles has one or more
conceptual blindspots. It's like knowing how to boil but not fry.
Programming is not a skill one develops in five easy lessons.
-- Tom Christiansen
By now, many Perl programmers know that the language offers support for
imperative, objective, and functional programming. However, logic programming
seems to be a lost art. This article attempts to shed a little light on the
subject. It's not that Prolog can do things that Perl cannot or vice versa.
Instead, Prolog does some things more naturally than Perl -- and vice versa.
In fact, while I introduce you to Prolog, I won't be teaching a bunch of nifty
tricks to make your Perl more powerful. I can't say what needs you may have
and, in any event, the tools that allow logic programming in Perl are generally
alpha quality, thus making them unsuitable for production environments.
=head2 What is Logic Programming?
Logic programming is somewhat of a mystery to many Perl programmers because,
unlike imperative, objective, and functional styles, Perl does not have direct
support for logic programming. There is, however, much interest in bringing
logic programming to Perl 6. With luck the information presented here will not
be merely theoretical.
Logic programming is not as alien as programmers might think. Regular
expressions, SQL and grammars are all closely related to logic programming.
The shared component of these seemingly disparate technologies is how they
I<describe> their goals rather than state how to achieve it. This is the
essence of logic programming. Rather than tell the computer how to achieve a
given goal, we tell the computer what the goal looks like and let it figure out
how to get there. Because of this, some refer to logic programming as
"specification-based programming" because the specification and the program are
one and the same.
This article will focus on C<AI::Prolog>. Prolog, though not a "pure" logic
programming language, is the most widely used in the field. C<AI::Prolog> is a
Prolog engine written entirely in Perl and it's very easy to install and use.
However, if you start doing serious work in Prolog, I strongly recommend you
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).
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
lib/AI/Prolog/Article.pod view on Meta::CPAN
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
[ 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]
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.
( run in 1.105 second using v1.01-cache-2.11-cpan-5837b0d9d2c )