NAME

AI::Prolog - Perl extension for logic programming.

SYNOPSIS

use AI::Prolog ':all';
my $database = Parser->consult(<<'END_PROLOG');
append([], X, X).
append([W|X],Y,[W|Z]) :- append(X,Y,Z).
END_PROLOG

my $query  = Term->new("append(X,Y,[a,b,c,d]).");
my $engine = Engine->new($query,$database);

print "Which lists append to form a known list?\n";
print "'append(X,Y,[a,b,c,d]).'\n";
while (my $result = $engine->results) {
    print "$result\n";
}

ABSTRACT

AI::Prolog is merely a convenient wrapper for a pure Perl Prolog compiler.
Regrettably, at the current time, this requires you to know Prolog.  That
will change in the future.

DESCRIPTION

A pure Perl predicate logic engine.

In predicate logic, instead of telling the computer how to do something, you tell the computer what something is and let it figure out how to do it. Conceptually this is similar to regexes:

my @matches = $string =~ /XX(YY?)ZZ/g

If the string contains data that will satisfy the pattern, @matches will contain a bunch of "YY" and "Y"s. Note that you're not telling the program how to find those matches. Instead, you supply it with a pattern and it goes off and does its thing.

To learn more about Prolog, see Roman Barták's "Guide to Prolog Programming." http://kti.ms.mff.cuni.cz/~bartak/prolog/index.html. Amongst other things, his course uses the Java applet that AI::Prolog was ported from, so his examples will generally work with this module.

Fortunately, Prolog is fairly easy to learn. Mastering it, on the other hand, can be a challenge.

USING AI::Prolog

There are three basic steps to using AI::Prolog.

Create the Prolog program.

Create a query.

Run the query.

For quick examples of how that works, see the examples/ directory with this distribution. Feel free to contribute more.

Creating a Prolog program

This module is actually remarkable easy to use. To create a Prolog program, you simply Parser->consult($prolog_code). Note that in Prolog, the result is what is known as a database.

my $database = Parser->consult(<<'END_PROLOG');
   steals(PERP, STUFF) :-
       thief(PERP),
       valuable(STUFF),
       owns(VICTIM,STUFF),
       not(knows(PERP,VICTIM)).
   thief(badguy).
   valuable(gold).
   valuable(rubies).
   owns(merlyn,gold).
   owns(ovid,rubies).
   knows(badguy,merlyn).
END_PROLOG

Creating a query

To create a query for the database, use Term.

my $query = Term->new("steals(badguy,X).");

Running a query

my $engine = Engine->new($query, $database);
while (my $result = $engine->results) {
    print "$result\n";
}

RATIONALE

You can skip this if you already know logic programming.

In Perl, generally you can append one list to another with this:

my @Z = (@X, @Y);

In Prolog, it looks like this:

append([], X, X).
append([W|X],Y,[W|Z]) :- append(X,Y,Z).

(There's actually often something called a "cut" after the first definition, but we'll keep this simple.)

What the above code says is "appending an empty list to a non-empty list yields the non-empty list." This is a boundary condition. Logic programs frequently require a careful analysis of boundary conditions to avoid infinite loops (similar to how recursive functions in Perl generally should have a terminating condition defined in them.)

The second line is where the bulk of the work gets done. In Prolog, to identify the head (first element) of a list and its tail (all elements except the first), we use the syntax [head|tail]. Since ":-" is read as "if" in Prolog, what this says if we want to concatenate (a,b,c) and (d,e,f):

• Given a list with a head of W and a tail of X:

  @list1 = qw/a b c/; (qw/a/ is W, the head, and qw/b c/ is X, the tail)

• If it's appended to list Y:

  @Y = qw/d e f/;

• We get a list with a head of W and a tail of Z:

  @list2 = qw/a b c d e f/;

• Only if X appended to Y forms Z:

  X is qw/b c/. Y is qw/d e f/. Z is qw/b c d e f/.

But how do we know if X appended to Y forms Z? Well, it's recursive. You see, the head of X is 'b' and it's tail is 'c'. Let's follow the transformations:

append([a,b,c],[d,e,f],[a,b,c,d,e,f])
 if append([b,c],[d,e,f],[b,c,d,e,f])
 if append([c],[d,e,f],[c,d,e,f])
 if append([],[d,e,f],[d,e,f])

As you can see, the last line matches our boundary condition, so the program can determine what the concatenation is.

Now that may seem confusing at first, but so was the Schwartzian transform when many of us encountered it. After a while, it becomes natural. Sit down and work it out and you'll see what's going one.

So what does this give us? Well, we can now append lists X and Y to form Z:

append([a], [b,c,d], Z).

Given Y and Z, we can infer X.

append(X, [b,c,d], [a,b,c,d]).

And finally, given Z, we can infer all X and Y that combine to form Z (again, like the regular expression, only easier).

append(X,Y,[a,b,c,d]).

Note that you get all of that from one definition of how to append two lists. You also don't have to tell the program how to do it. It just figures it out for you.

Translating all of this into AI::Prolog looks like this:

use AI::Prolog qw/:all/;
my $database = Parser->consult(<<'END_PROLOG');
append([], X, X).
append([W|X],Y,[W|Z]) :- append(X,Y,Z).
END_PROLOG

my $query  = Term->new("append(X,Y,[a,b,c,d]).");
my $engine = Engine->new($query,$database);
while (my $result = $engine->results) {
    print "$result\n";
}

GRAMMAR

The language is given by the following simple grammar (pulled directly from Dr. Winikoff's page):

Program   ::= Rule | Rule Program
Query     ::= Term

Rule      ::= Term . | Term :- Terms .
Terms     ::= Term   | Term , Terms
Term      ::= Number | Variable | AtomName | AtomName(Terms)
                | [] | [Terms] | [Terms | Term]
                | print(Term) | nl | eq(Term , Term)
                | if(Term , Term , Term) | or(Term , Term ) | not(Term) | call(Term) | once(Term)
Number    ::= Digit | Digit Number
Digit     ::= 0 | ... | 9
AtomName  ::= LowerCase NameChars
Variable  ::= UpperCase NameChars
NameChars ::= NameChar | NameChar NameChars
NameChar  ::= a | ... | z | A | ... | Z | Digit

Comments begin with a % and terminate at the end of the line or begin with /* and terminate with */.

Also, this will not work:

p(X) :- X. /* does not work */

Use this instead:

p(X) :- call(X).

Built-ins.

• call(X).

  Invokes X as a goal.

• eq(X, Y).

  Succeeds if X and Y are equal.

• if(X, Y, Z).

  If X succeeds as a goal, try Y as a goal. Otherwise, try Z.

  thief(badguy).
  steals(PERP, X) :-
    if(thief(PERP), eq(X,rubies), eq(X,nothing)).

• nl

  Prints a newline.

• not(X).

  Succeeds if X cannot be proven. This is not negation as we're used to seeing it in procedural languages.

• once(X)

  Stop solving for X if X succeeds. Defined as:

  once(X) :-
    X, !;

• or(X, Y)

  Succeeds as a goal if either X or Y succeeds.

• print(Term).

  Prints the current Term.

LIMITATIONS

These are known limitations that I am not terribly inclined to fix. See the TODO list for those I am inclined to fix.

IF -> THEN; ELSE not allowed.

Use if(IF, THEN, ELSE) instead.

= and \= not available.

Use eq(X,Y) and not(eq(X,Y)) instead.

TODO

There are many things on this list. The core functionality is there, but I do want you to be aware of what's coming.

• Anonymous variables

  steals(badguy, _).

  Currently, that doesn't work. Make up a variable name and only use it once.

• Improve printing.

  print(X).

  Currently, you can print variables, but to print strings is cumbersome:

  print(some_data), print(X).

  This will print some_data and the current value of X (or an internal representation of its state if its not bound to a variable.) There is no way to print a space.

• Math.

  Math is hard. So we don't have it, but we will and we'll probably have it in the form of system predicates that call out to Perl. We can define most of what we need logically, but it's very slow and complicated, so we won't do that.

• Database access

  No, we're not talking DBI. We're talking about clause, assert and retract. We don't have that yet.

• Add cut.

  Currently, we can use once(X) to simulate it. Think of this predicate as being equivalent to:

  once(X) :- X, !;

  Frankly, I'm not overly worried about this but feel free to convince me I'm wrong (preferably with a patch :).

Additionally, one can "trace" the program execution by setting this property to a true value before fetching engine results:

Engine->trace(1);
while (my $result = $engine->results) {
    print "$result\n";
}

This sends trace information to STDOUT and allows you to see how the engine is trying to satify your goals. Naturally, this slows things down quite a bit.

BUGS

I'm sure there are bugs. I don't know of any right now. Let me know if (when) you find them. See the TODO list before that, though.

EXPORT

None by default. However, for convenience, it's recommended that you choose ":all" functions to be exported. That will provide you with Term, Parser, and Engine.

If you choose not to export the functions, you may use the fully qualified package names instead:

use AI::Prolog;
my $database = AI::Prolog::Parser->consult(<<'END_PROLOG');
append([], X, X).
append([W|X],Y,[W|Z]) :- append(X,Y,Z).
END_PROLOG

my $query  = AI::Prolog::Term->new("append(X,Y,[a,b,c,d]).");
my $engine = AI::Prolog::Engine->new($query,$database);
while (my $result = $engine->results) {
    print "$result\n";
}

I have no idea why you would want to do this :)

SEE ALSO

W-Prolog: http://goanna.cs.rmit.edu.au/~winikoff/wp/

Michael Barták's online guide to programming Prolog: http://kti.ms.mff.cuni.cz/~bartak/prolog/index.html

AUTHOR

Curtis "Ovid" Poe, <moc tod oohay ta eop_divo_sitruc>

Reverse the name to email me.

This work is based on W-Prolog, http://goanna.cs.rmit.edu.au/~winikoff/wp/, by Dr. Michael Winikoff. Many thanks to Dr. Winikoff for granting me permission to port this.

COPYRIGHT AND LICENSE

Copyright 2005 by Curtis "Ovid" Poe

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

cpanm AI::Prolog

perl -MCPAN -e shell
install AI::Prolog