AI::Prolog::Introduction 0.739

AI::Prolog::Introduction Perl module contains the what and the why of logic programming.

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 http://www.perlmonks.org/?node_id=424075.

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

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

However, thats 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).

(Theres actually often something called a "cut" after the first definition, but well 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 its 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/.