For inspiration on prolog in perl, you might want to take a look at chapter 24 of Paul Graham's On Lisp. He creates an embedded prolog-like language in about 200 lines of Common Lisp. I'd be willing to bet that a Perl implementation wouldn't be too much longer.
-- All code is 100% tested and functional unless otherwise noted.