Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Contact Us
Online Help
Domain Status
Man Pages

Virtual Servers

Topology Map

Server Agreement
Year 2038

USA Flag



Man Pages

Manual Reference Pages  -  AI::PROLOG::INTRODUCTION (3)

.ds Aq ’


AI::Prolog::Introduction - The what and the why of logic programming.



 $Id: Introduction.pod,v 1.2 2005/02/20 18:27:55 ovid Exp $


You can skip this if you already know logic programming.

Note that most of this was pulled from my write-up about logic programming in Perl at <>.

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

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

However, that’s telling the language what to do. As sentient beings, we can look at that and infer more information. Given @Z and @X, we could infer @Y. Given just @Z, we could infer all combinations of @X and @Y that can be combined to form @Z.

Perl cannot do that. In logic programming, however, by defining what append() looks like, we get all of that other information.

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):
o 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)

o If it’s appended to list Y:

 @Y = qw/d e f/;

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

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

o 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:

  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.


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;
 use Data::Dumper;

 my $prolog = AI::Prolog->new(append_prog());
 $prolog->raw_results(0) # Disable raw results
 while (my $result = $prolog->results) {
     print Dumper($result->X); # array references
     print Dumper($result->Y);

 sub append_prog {
     return <<    END_PROLOG;
     append([], X, X).
     append([W|X],Y,[W|Z]) :- append(X,Y,Z).


W-Prolog: <>

X-Prolog: <>

Roman Barta\k:'online guide to programming Prolog: <>


Curtis Ovid Poe, <moc tod oohay ta eop_divo_sitruc>

Reverse the name to email me.

This work is based on W-Prolog,, by Dr. Michael Winikoff. Many thanks to Dr. Winikoff for granting me permission to port this.


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.

Search for    or go to Top of page |  Section 3 |  Main Index

perl v5.20.3 AI::PROLOG::INTRODUCTION (3) 2011-03-26

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.