The Background
AI::Prolog generated a fair amount of interest when it came out, but it had some serious limitations. First, it was far too slow for "serious" work. Second, you had to know Prolog and embed that in Perl. I could have gotten around the second problem, but the first problem remained even after I heavily optimized AI::Prolog. Further, because you had to embed a Prolog interpreter in Perl, you couldn't use Perl data structures. This, needless to say, was frustrating for many people.
By playing around with tiny_prolog.rb, I've had to learn a bit of ruby (well, a lot, really), and I've noticed that this predicate logic implementation is fairly fast. I say "predicate logic" because it's pure ruby, no Prolog! (Though you can see Prolog's roots). This means I could potentially port it to Perl. Adam Kennedy, though, wondered if this predicate logic implementation is fast enough for "useful" work.
That's an excellent question. A long time ago he asked me about this for some work he was doing with a client and I warned him that AI::Prolog was going to be too slow for their needs. This might be overcome now, though, depending on what the needs are (still not fast enough for your needs, though, Adam. Sorry 'bout that).
The Benchmark
Note: for the benchmarks below, uncomment the 'print/puts' lines and drop iterations to 1 to see that they're logically equivalent.
In Prolog, one of the classic benchmarks is something called the 'naive reverse'. This is a predicate used to reverse a list and it's O(n^2) with the length of the list it's applied to. With a 30 element list, it takes 496 logical inferences to compute. "Logical Inferences Per Second" (LIPS) is how logic programs are usually benchmarked. Today, serious Prolog implementations run at many millions of LIPS [1] and if you need that sort of power, use a real language that specializes in this (even toy implementations in Scheme and other languages cannot approach this dedicated power). However, you may not need this sort of power.
So taking a look at Perl, here's the benchmark with AI::Prolog:
use AI::Prolog;
my $benchmark = <<"END_BENCHMARK";
append([],X,X).
append([X|Xs],Y,[X|Z]) :- append(Xs,Y,Z).
nrev([],[]).
nrev([X|Xs],Zs) :- nrev(Xs,Ys), append(Ys,[X],Zs).
END_BENCHMARK
my $prolog = AI::Prolog->new($benchmark);
my $query = 'nrev([1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0],X).';
for (1 .. 100) {
#use Data::Dumper;
$prolog->query($query);
while (my $result = $prolog->results) {
#print Dumper($result);
}
}
This takes about 28 seconds to run on my Solaris box at work. At 496 logical inferences to reverse that list and doing this 100 times, we get the following:
( 496 * 100 ) / 28 ~~ 1770 LIPS
Translating this to ruby:
require 'tiny_prolog'
append = pred 'append'
append[nil, :A, :A].fact
append[cons(:A, :X), :Y, cons(:A, :Z)] <<= append[:X, :Y, :Z]
nrev = pred 'nrev'
nrev[nil,nil].fact
nrev[cons(:X, :XS), :ZS] <<= [ nrev[:XS,:YS], append[:YS, list(:X), :ZS] ]
for foo in 1..100
resolve nrev[list(1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0), :X] do |env|
# puts env[:X]
end
end
As this takes approximately 7.5 seconds, we get:
( 496 * 100 ) / 7.5 ~~ 6610 LIPS
The Conclusion
The Ruby code is almost four times faster than the Perl. This is due, in part, because the Perl code is based on w-Prolog and x-Prolog, two Prolog systems originally written in Java and not optimized for dynamic languages. As a result, since we know that Perl tends to run faster than Prolog and since I've already seen quite a number of areas I can optimize (though I'm not doing that right now), I fully expect that I can produce a Perl predicate logic implementation that may be as much as an order of magnitude faster than AI::Prolog and may even allow Perl data structures.
Further, the resulting code is simpler, easier to understand, and parts of it may even be suitable for porting to C. We might actually be in a position of being able to do small scale logic programming in Perl. Whether this actually proves to be of benefit to anyone remains to be seen. Of course, for heavy lifting, you'd still need to fall back on something serious like Prolog, Oz or Mercury.
That being said, I'm leaving on holiday for a over a week, so don't hold your breath. But then, you know that about me by now :)
1. By way of comparison, my iBook solves the zebra puzzle in about 30 seconds in Ruby, but in far less than a second with SWI-Prolog.