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).
lib/AI/Prolog/Article.pod view on Meta::CPAN
}
__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
( run in 0.745 second using v1.01-cache-2.11-cpan-e1769b4cff6 )