http://qs1969.pair.com?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.

Replies are listed 'Best First'.
Re: Bringing Logic Programming to Perl
by ihb (Deacon) on Jan 22, 2005 at 17:08 UTC

    Something my teacher repeatedly say during the lectures was "in logic programming we express relations". Remember this, ponder it, and you'll save yourself some trouble, especially if you already are comfortable with functional languages. Relations are named by predicates and predicates are not functions.

    If that is as clear as the sky above the clouds then you can stop reading now. All I'm going to try to do in the rest of this post is to give examples of how these relations work and how they allow you to express programs differently than in other languages that look similar, like Haskell.

    Moving on...

    A predicate is true if the relation can be true. If there's any uninstantiated variables in the predicate Prolog gives them values that fulfill the relation and keep them for the rest of the scope. This works a bit like capturing groups and backreferences in regexes (like /(.*?)\1/).

    An interesting example of this is how the assignment operator = works in Prolog. It's not really an assignment operator. It's a very simple predicate named = and X = Y can be written as =(X, Y). We could've called it eq and written it as

    eq(X, X).
    which basically says that the first argument must match the second argument. As you see, it's symmetrical, so X = 2 is the same as 2 = X.

    I don't expect anyone without prior knowledge of Prolog to understand the following example, but I think it's nice anyway, and those familiar with functional programming may recognize the example.

    If we want to manually define the natural numbers, 0 ... Inf, we can do that by writing an inc predicate used as inc(X, Xplus1) and have a base (atom) just called zero. If we define inc as

    inc(X, succ(X)). % you don't have to understand this.
    the number 2 would be represented by succ(succ(zero)). But here's where the fun comes in. Since predicates express relations we can use it to decrease a value too: inc(Xminus1, X). Here I've said nothing about whether X needs to be instantiated or not. If fact, neither in inc(X1, X2) needs to be instantiated. It just says that after that predicate, X1 and X2 will be two successive numbers:
    foo :- inc(X, Y), % Implicit RELATION. X = zero, % MATCH X against the atom zero, impliclity mat +ch Y. something(X, Y). % same as something(zero, succ(zero)). bar :- inc(X, Y), % Same implicit relation. Y = succ(zero), % Implicitly match X against zero. something(X, Y). % same as something(zero, succ(zero)).
    It's all about relations.

    ihb

    See perltoc if you don't know which perldoc to read!
    Read argumentation in its context!

Re: Bringing Logic Programming to Perl
by spurperl (Priest) on Jan 22, 2005 at 08:46 UTC
    Another extremely well-documented reference for Prolog can be PAIP- Peter Norvig's terrific Paradigms of Artificial Intelligence Programming in Lisp. Lisp is a good language to implement Prolog in, because Lisp also likes lists and generally complex data structures are simpler in it. Norvig includes in his book, along with a whole chapter explaining the motivation of learning Prolog, a nearly full implementation of the language in Lisp. I saw some complete implementations on the web based on the book's code.
Re: Bringing Logic Programming to Perl
by hv (Prior) on Jan 22, 2005 at 15:50 UTC

    One of the new features in perl6 that may be useful for this is a switch for rules (patterns) that tells it to find every way this pattern can match, rather than finding only one match for each possible start position. I'm not sure what it's called this week, but it would mean you could say something like:

    "abcd" =~ m:every/^(.*)(.*)$/;
    .. and get the five matches that represent the five ways of splitting the string into two parts.

    I'd also love to see the pattern matching concept extended from simple strings to data structures, but I don't think anyone yet knows of a good paradigm for expressing the patterns. The only halfway useful approach I know of is expat XPath, and the way it expresses its patterns is ugly as hell.

    Hugo

      Hm. Doesn't XPath do just that?

      Makeshifts last the longest.

        Oops, I meant XPath rather than Expat.

        Hugo

      I'm not sure what it's called this week

      :exhaustive or :ex for short, some where in S05/Modifiers

Re: Bringing Logic Programming to Perl
by grantm (Parson) on Jan 23, 2005 at 00:47 UTC
    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).

    I believe that's what Fergal Daly's Test::Deep does.

        The only thing is that capturing data from deep inside the structure does not happen. It's been the todo list since the beginning but I've never really needed it.

        If you fancy adding it, it would be fairly simple. I'll have a look tonight.

Re: Bringing Logic Programming to Perl
by duelafn (Parson) on Jan 22, 2005 at 18:04 UTC
    I got the most enlightenment about logic programming from reading the description of the monkey and the banana toy problem as described here.

      Well, this works, but it does show some limitations in the code. I'm adding this to my examples/ directory. Thanks for the pointer.

      use strict; use warnings; use aliased 'AI::Prolog::Parser'; use aliased 'AI::Prolog::Term'; use aliased 'AI::Prolog::Engine'; my $database = Parser->consult(<<'END_PROLOG'); perform(grasp, state(middle, middle, onbox, hasnot), state(middle, middle, onbox, has)). perform(climb, state(MP, BP, onfloor, H), state(MP, BP, onbox, H)). perform(push(P1,P2), state(P1, P1, onfloor, H), state(P2, P2, onfloor, H)). perform(walk(P1,P2), state(P1, BP, onfloor, H), state(P2, BP, onfloor, H)). /* getfood(state(_,_,_,has)). */ /* I'll have to fix this soonish! */ getfood(state(Bogus1,Bogus2,Bogus3,has)). getfood(S1) :- perform(Act, S1, S2), nl, print(S1), print(Act), getfood(S2). END_PROLOG my $parser = Parser->new("getfood(state(atdoor,atwindow,onfloor,hasnot +))."); my $query = Term->new($parser); my $engine = Engine->new($query,$database); print $engine->run;

      Cheers,
      Ovid

      New address of my CGI Course.

kudos for explanation
by ww (Archbishop) on Jan 21, 2005 at 17:54 UTC
    This is a big help; now I actually have some (SOME, not much, but some) idea of where you're headed and why... and it looks interesting! Pls keep us updated.
OT - Prolog for data store
by zby (Vicar) on Jan 23, 2005 at 18:41 UTC
    If, with my limited knowledge of Prolog, I do understand it well, the way of working with Prolog is to write a set of rules (a program), load it, and then query it. Would it be possible to mix the phases - that is adding rules with quering the whole set? With that Prolog systems could be used as data base. With SQL you can mix modifying of data and quering it.

      At the current time, no you can't do that. You would have to recreate the the set of rules and reload them. However, AI::Prolog is now on its way to the CPAN so you will soon be able to download it and see for yourself.

      Cheers,
      Ovid

      New address of my CGI Course.

Re: Bringing Logic Programming to Perl
by Anonymous Monk on Jan 21, 2005 at 18:31 UTC
    That is very interesting.
Kudos. Yet.. Misconception.
by RocketInABog (Initiate) on Jul 25, 2006 at 06:30 UTC

    Wonderful addition to Perl.

    My very first posting on the internet was on the subject of prolog programming (I just couldn't bear reading one person mislead another).

    I usually only speak up when I have a criticism, so people tend to hate me.
    Yet, we should always help each other progress, so....

    It looks to me like your conception of the word 'append' is backwards.

    All said and done. Kudos for pushing Prolog.
    I'm using your code and appreciate it. Thanks.

    BTW Have you heard of Prolog++ ? It's an object oriented prolog.
    I bought the book. (No. I'm not affiliated in any way).
    (1994, Addison-Wesley published "Prolog++: The Power of Object-Oriented and Logic Programming" by Chris Moss)
    I think you can implement the object oriented language in prolog (a prolog meta-interpreter).
    Too much for me to chew right now.

    Thanks again.
    -RocketInABog