Bill Clementson's Blog

Allegro Prolog - A Prolog in Lisp

Sunday, September 19, 2004

I recently posted about AllegroCache, the new object prevalence product that Franz is developing. One of the things that IMO is unique with the product is that it has built-in support for AI inferencing engines. Initially, Allegro Prolog and LISA will be supported but it will be possible to use alternative inferencing engines as well. This prompted me to take a closer look at Allegro Prolog (I plan to look at LISA in a later post). Allegro Prolog was only just released a couple of months ago and is based on the Prolog implementation developed (in CL) by Peter Norvig in his book Paradigms of Artificial Intelligence Programming (PAIP). Franz claims in their documentation that their implementation has "been further optimized and useful extensions provided, making an industrial-strength Prolog programming environment with a flexible calling interface in both directions between Common Lisp and Prolog". I decided to check out how fast their Prolog implementation really is.

First of all, I compared Allegro Prolog with the Peter Norvig's Prolog implementation in PAIP by running the Zebra Problem, a classic Prolog constraint-resolution problem (source for the problem is provided in Norvig's examples.lisp file and in the Allegro Prolog documentation). Allegro Prolog solved the problem on my Win2000 PC (with 1GB of memory and a 1200MHz CPU) almost instantaneously. The PAIP code took several minutes to execute. However, this result was to be expected as Franz stated that their product is based on an optimized version of the PAIP Prolog code.

I then decided to compare Allegro Prolog's performance against plain CL code using a similar example problem that does inferencing and back-chaining. The problem I chose to use for the comparison was Einstein's Riddle, a problem similar to the Zebra Problem (Einstein's Riddle attempts to solve the question "Who owns the fish?"). Edi Weitz had previously looked at this problem and documented a number of different CL solutions for solving it. I have a lot of respect for Edi and his CL programming skills, so I decided to use his best-performing solution as the basis for comparison with Allegro Prolog. Here is what I did:

• To start off, I coded the problem in CL as "einstein-prolog.lisp" using the Allegro Prolog library. Here is my code:

  (in-package :user)
  (eval-when (compile load eval)
    (require :prolog)
    (use-package :prolog))
  (eval-when (compile) (setf excl:*load-xref-info* nil))
  (<-- (nextto ?x ?y ?list) (iright ?x ?y ?list))
  (<-  (nextto ?x ?y ?list) (iright ?y ?x ?list))
  (<-- (iright ?left ?right (?left ?right . ?rest)))
  (<-  (iright ?left ?right (?x . ?rest))
       (iright ?left ?right ?rest))
  (<-- (einstein ?h ?f)
       (= ?h ((house norwegian ? ? ? ?)  
              ?
              (house ? ? ? milk ?) ? ?)) 
       (member (house british ? ? ? red) ?h)
       (member (house swedish dog ? ? ?) ?h)
       (member (house danish ? ? tea ?) ?h)
       (iright (house ? ? ? ? green)     
  	     (house ? ? ? ? white) ?h)
       (member (house ? ? ? coffee green) ?h)
       (member (house ? bird pallmall ? ?) ?h)
       (member (house ? ? dunhill ? yellow) ?h) 
       (nextto (house ? ? dunhill ? ?) 
               (house ? horse ? ? ?) ?h)
       (member (house ? ? ? milk ?) ?h)
       (nextto (house ? ? marlboro ? ?)      
               (house ? cat ? ? ?) ?h)
       (nextto (house ? ? marlboro ? ?)      
               (house ? ? ? water ?) ?h)
       (member (house ? ? winfield beer ?) ?h)
       (member (house german ? rothmans ? ?) ?h)
       (nextto (house norwegian ? ? ? ?) 
               (house ? ? ? ? blue) ?h)
       (member (house ?f fish ? ? ?) ?h)
       )

• Edi's best-performing CL code was einstein-minimize.lisp. However, his code pretty-printed the result and I didn't want I/O to be a factor in the comparison. Therefore, I replaced the "'(pprint result)" line in his file with "nil" and saved the modified file as "einstein-cl.lisp".
• I then compiled and ran both the Allegro Prolog and the straight-CL implemenations, running 100 iterations of each. Here is a snapshot of the REPL history for the session:

  CL-USER> (compile-file "einstein-cl.lisp")
  ;;; Compiling file einstein-cl.lisp
  ;;; Writing fasl file einstein-cl.fasl
  ;;; Fasl write complete
  #p"einstein-cl.fasl"
  NIL
  NIL
  CL-USER> (compile-file "einstein-prolog.lisp")
  ;;; Compiling file einstein-prolog.lisp
  ; Fast loading c:\bin\acl-7.0\code\PROLOG.fasl
  ;;; Writing fasl file einstein-prolog.fasl
  ;;; Fasl write complete
  #p"einstein-prolog.fasl"
  NIL
  NIL
  CL-USER> (load "einstein-cl.fasl")
  ; Fast loading c:\usr\home\lisp\einstein\test\einstein-cl.fasl
  T
  CL-USER> (load "einstein-prolog.fasl")
  ; Fast loading c:\usr\home\lisp\einstein\test\einstein-prolog.fasl
  ;   Fast loading c:\bin\acl-7.0\code\PROLOG.fasl
  T
  CL-USER> (time (dotimes (n 100) (solve)))
  ; cpu time (non-gc) 41,560 msec user, 0 msec system
  ; cpu time (gc)     70 msec user, 0 msec system
  ; cpu time (total)  41,630 msec user, 0 msec system
  ; real time  42,832 msec
  ; space allocation:
  ;  1,024,031 cons cells, 2,401,168 other bytes, 0 static bytes
  NIL
  CL-USER> (time (dotimes (n 100) (prolog (einstein ?houses ?fish-owner) !)))
  ; cpu time (non-gc) 11,937 msec user, 0 msec system
  ; cpu time (gc)     30 msec user, 0 msec system
  ; cpu time (total)  11,967 msec user, 0 msec system
  ; real time  12,307 msec
  ; space allocation:
  ;  133,669 cons cells, 950,456 other bytes, 9,344 static bytes
  NIL
  CL-USER> 

CL-USER> (?- (einstein ?houses ?fish-owner))
?HOUSES = ((HOUSE NORWEGIAN CAT DUNHILL WATER YELLOW)
           (HOUSE DANISH HORSE MARLBORO TEA BLUE)
           (HOUSE BRITISH BIRD PALLMALL MILK RED)
           (HOUSE GERMAN FISH ROTHMANS COFFEE GREEN)
           (HOUSE SWEDISH DOG WINFIELD BEER WHITE))
?FISH-OWNER = GERMAN