http://www.perlmonks.org?node_id=424075

I feel rather chastened. Both Purdy and zatoichi have asked about the rationale behind AI::Prolog and I realize that many (most) programmers have never encountered logic programming and, as a result, have no idea what it implies. First, many are aware of the following famous Tom Christiansen quote:

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.

Well, that sounds nice, but what does it mean? Most Perl programmers write imperative code. Many write OO code, but frequently this is merely an OO wrapper around imperative code as many Perl programmers do not come from an OO background. However, Perl does support writing code in an OO style.

Perl also supports programming in a functional style. Dominus has an entire book about this coming out soon and I'm eager to get it. In fact, much of the benefit of logic programming is often obtained from functional languages.

Getting back to logic programming, Perl really has no native facilities for this. (adrianh presented us with a nifty working example, but it's very difficult for many to follow -- including me.) Perl does have regular expressions which are similar to logic programming, but they're not quite as powerful. In fact, I even tried to use regexes for this, but there are some limitations with Perl's regex engine. However, searching the CPAN is rather interesting.

  • AI::Proplog by princepawn. This only appears to allow boolean queries.
  • Math::Predicate::Logic by Luke Palmer. This is not finished.
  • Language::Prolog::Interpreter by Lee Goddard. This is not finished.
  • Prolog::Alpha. It's disappeared from the CPAN.
  • Language::Prolog::Yaswi by Salvador Fandino Garcia. An interface to SWI Prolog, it's difficult to compile, in alpha and it's apparently unmaintained. It also does not work with the latest version of SWI-Prolog and the author has not responded to email. Still, it seems to be the best of the bunch.
  • Language::Prolog::SWI by Robert Barta. Very little documentation. I couldn't get it to compile.

So, from the list above, we can see that many smart people want to bring logic programming to Perl, but for a variety of reasons, none have had complete success. Since I want logic programming in Perl, I've decided to port WProlog to Perl (with the author's permission) and I have the bulk of the work done. But why am I porting instead of writing one myself? Because like those above, I found it very hard. In fact, on my first attempt, with no prior experience in this, I found myself debugging the following line of code:

$array_ref->[$j]{$args->[$j]}[$i]{$args->[$i]} = $args->[$i];

Now if you think that's bad, trust me, it gets worse, that AoHoAoH was actually stuffed inside of a hash of hashes, thus leaving me with a HoHoAoHoAoH. That's when I remembered I had Minefield installed on my computer.

That code begs an interesting question, though. How would you debug it? Test::More has an interesting function called is_deeply that allows you to do a comparison of complex data structures to determine if they match. Read through the Test::More code for is_deeply. It's complex and rather hairy. It works well, but let's think about my data structure again. I had an HoHoAoHoAoH. Now look at that last "A". What if I didn't care how many elements were in that array? What if I didn't care if it contained hashes or scalars? That's really, really tough to do on the fly in Perl. What I would love to see is a like_deeply function in Test::More that would allow us to describe the form of a complex data structure without an exact match (and pull out bits that we're interested in). This would, however, really involve writing a regular expression engine for data structures instead of strings.

Now it seems like we're taking a curious detour, but we really are getting close to the goal of understanding, vaguely, what logic programming is. To further our understanding, let's take a closer look at regular expressions.

Consider the string "XXYYZZ". That string is not very interesting. Now let's make it a regular expression:

qr/XXYYZZ/

Well, that's still not very interesting, but it's more interesting than it was. Let's make it more interesting still.

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

Now that's interesting. When we're done, @matches will quite possibly contain a bunch of "YY" and "Y"s. We're used to this and it seems like old hat, but notice what we've not done: we've not told Perl how to do this. We've provided a string and a pattern and let Perl figure it out for itself. In fact, if we really want to strain ourselves, we can do curious tricks with regexes. Consider the following snippet:

# Thanks to aristotle for making the regex simpler my $string = "abcd"; my @perms; my $regex = qr/(\G[abcd]{0,4}(?{print "# [$&][$'][$string]\n"}))/ x 2; $string =~ $regex;

If you run that, it prints this:

# [abcd][][abcd] # [abc][d][abcd] # [ab][cd][abcd] # [a][bcd][abcd] # [][abcd][abcd] # [abcd][][abcd]

Now what is that? Well, it's all the variations of two strings, X and Y, that can be concatenated to form "abcd." It also has an annoying leftover at the end that I can't figure out how to easily get rid of, but it does show why regexen are not good for stuff like this. That's where we get to logic programming.

Instead of strings, let's think about lists. If we decided to append two lists together in Perl, it might look like this:

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

We could wrap that in a function, but it would be silly. Instead, we just tell the program to do it. However, that's what imperative programming does. We tell the computer what to do. We have not defined what "append" means. As a human, we could actually gather more information from that snippet. Given @Z and @X, we could deduce @Y. In fact, given @Z, we could deduce all possible combinations of @X and @Y would be needed to form @Z (kind of like our regex snippet above.)

Imperative languages generally don't do this. Logic languages do. First, you would have to define what the append function looks like. Here it is in Prolog:

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:

[a,b,c],[d,e,f],[a,b,c,d,e,f] if [b,c],[d,e,f],[b,c,d,e,f] if [c],[d,e,f],[c,d,e,f] if [],[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 how it works out.

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.

If you download my (very alpha!) code (but it's pure Perl), you can run the following program:

#!/usr/local/bin/perl -l use strict; use warnings; use lib '../lib/'; use aliased 'AI::Prolog::Parser'; use aliased 'AI::Prolog::Term'; use aliased 'AI::Prolog::Engine'; my $parser = Parser->new("append([a],[b,c,d],Z)."); my $query = Term->new($parser); my $engine = Engine->new($query,Parser->consult(append_prog())); print "Appending two lists 'append([a],[b,c,d],Z).'"; print $engine->run; while (my $result = $engine->more) { print $result; } $parser = Parser->new("append(X,[b,c,d],[a,b,c,d])."); $query = Term->new($parser); $engine = Engine->new($query,Parser->consult(append_prog())); print "\nWhich lists appends to a known list to form another known lis +t 'append(X,[b,c,d],[a,b,c,d]).'"; print $engine->run; while (my $result = $engine->more) { print $result; } $parser = Parser->new("append(X,Y,[a,b,c,d])."); $query = Term->new($parser); $engine = Engine->new($query,Parser->consult(append_prog())); print "\nWhich lists append to form a known list 'append(X,Y,[a,b,c,d] +).'"; print $engine->run; while (my $result = $engine->more) { print $result; } sub append_prog { "append([], X, X)." ."append([W|X],Y,[W|Z]) :- append(X,Y,Z)."; }

And the output:

Appending two lists 'append([a],[b,c,d],Z).' append([a],[b,c,d],[a,b,c,d]) Which lists appends to a known list to form another known list 'append +(X,[b,c,d],[a,b,c,d]).' append([a],[b,c,d],[a,b,c,d]) Which lists append to form a known list 'append(X,Y,[a,b,c,d]).' append([],[a,b,c,d],[a,b,c,d]) append([a],[b,c,d],[a,b,c,d]) append([a,b],[c,d],[a,b,c,d]) append([a,b,c],[d],[a,b,c,d]) append([a,b,c,d],[],[a,b,c,d])

Note that my alpha code has no documentation and virtually no tests. It's merely a proof of concept and it's avaialable via my Web site because I was asked. You've been warned :)

If you're interested in learning more about Prolog, check out Guide to Prolog Programming by Roman Barták. He actually has a link to the Java applet implementation of W-Prolog so you can practice online. W-Prolog is the Java program on which my code was based and it (currently) has the same limitations. Wikipedia has an article on Prolog that discusses some of the things Prolog is used for. In addition to what's mentioned there, I should point out that Prolog is excellent for rules-based systems and expert systems.

Cheers,
Ovid

New address of my CGI Course.