The Zebra Puzzle (Prolog in Lisp)

I am delighted to have got Peter Norvig's Lisp interpreter for Prolog working (in its simplest form) from Chapter 11 of his book, "Paradigms of Artificial Intelligence programming".

I tested it on his Zebra puzzle, where he states:

"This took 278 seconds, and profiling (see page 288) reveals that the function prove was called 12,825 times. A call to prove has been termed a logical inference, so our system is performing 12825/278 = 46 logical inferences per second, or LIPS.

Good Prolog systems perform at 10,000 to 100,000 LIPS or more, so this is barely limping along."

On my Windows 10 HP laptop, the computation took 7 seconds with 29,272 calls to 'prove'.

I guess that's 4,182 LIPS for compiled Lisp from LispWorks - program totally unoptimised.

His book is rather old (1992).

---

The Zebra puzzle

"Here is an example of something Prolog is very good at: a logic puzzle. There are fifteen facts, or constraints, in the puzzle:

1. Five houses in a line, each with an owner, a pet, a cigarette, a drink, and a color.
2. The Englishman lives in the red house.
3. The Spaniard owns the dog.
4. Coffee is drunk in the green house.
5. The Ukrainian drinks tea.
6. The green house is immediately to the right of the ivory house.
7. The Winston smoker owns snails.
8. Kools are smoked in the yellow house.
9. Milk is drunk in the middle house.
10. The Norwegian lives in the first house on the left.
11. The man who smokes Chesterfields lives next to the man with the fox.
12. Kools are smoked in the house next to the house with the horse.
13. The Lucky Strike smoker drinks orange juice.
14. The Japanese smokes Parliaments.
15. The Norwegian lives next to the blue house.

The questions to be answered are: who drinks water and who owns the zebra?"

The translation into Prolog in Lisp uses a Lisp-like syntax for Prolog facts and rules (both are clauses). Here's the Prolog 'program' coding the above problem.

;;; --- Lisp code follows - comments from Norvig's book  ---
;;;
;;; To solve this puzzle, we first define the relations nextto (for "next to") and
;;;  iright (for 'immediately to the right of'). They are closely related to member,
;;; which is repeated here.
;;;

(<- (member ?item (?item . ?rest )))
(<- (member ?item (?x . ?rest) ) (member ?item ?rest))

(<- (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))
(<- (= ?x ?x))

;;; We also defined the identity relation, =. It has a single clause that says that any x is
;;; equal to itself. One might think that this implements eq or equal. Actually, since
;;; Prolog uses unification to see if the two arguments of a goal each unify with ?x, this
;;; means that = is unification.

;;; Each house is of the form:
;;; (house nationality pet cigarette drink house-color)
;;; ?h is the variable representing the list of the five houses

(<- (zebra ?h ?w ?z)

  (= ?h  ((house norwegian ? ? ? ?) ? (house ? ? ? milk ?) ? ? ) )              ; 1, 10, 9
  (member (house englishman ? ? ? red) ?h)                                             ; 2
  (member (house spaniard dog ? ? ?) ?h)                                                 ; 3
  (member (house ? ? ? coffee green) ?h)                                                  ; 4
  (member (house ukrainian ? ? tea ?) ?h)                                                 ; 5
  (iright (house ? ? ? ? ivory)                                                                     ; 6
             (house ? ? ? ? green) ?h)
  (member (house ? snails winston ? ?) ?h)                                               ; 7
  (member (house ? ? kools ? yellow) ?h)                                                 ; 8
  (nextto (house ? ? chesterfield ? ?)                                                         ; 11
             (house ? fox ? ? ?) ?h)
  (nextto (house ? ? kools ? ?)                                                                   ; 12
              (house ? horse ? ? ?) ?h)
  (member (house ? ? luckystrike orange-juice ?) ?h)                              ; 13
  (member (house japanese ? parliaments ? ?) ?h)                                   ; 14
  (nextto (house norwegian ? ? ? ?)                                                          ; 15
              (house ? ? ? ? blue) ?h)

;; Now for the questions:

   (member (house ?w ? ? water ?) ?h)                                                     ; Q1
   (member (house ?z zebra ? ? ?)  ?h) )                                                   ; Q2

; Here's the query

  (?- (zebra ?houses ?water-drinker ?zebra-owner))

; .. and here's the result

?HOUSES = ((HOUSE NORWEGIAN FOX KOOLS WATER YELLOW)
                       (HOUSE UKRAINIAN HORSE CHESTERFIELD TEA BLUE)
                       (HOUSE ENGLISHMAN SNAILS WINSTON MILK RED)
                       (HOUSE SPANIARD DOG LUCKYSTRIKE ORANGE-JUICE IVORY)
                       (HOUSE JAPANESE ZEBRA PARLIAMENTS COFFEE GREEN))
?WATER-DRINKER = NORWEGIAN
?ZEBRA-OWNER = JAPANESE;

---

I'll publish the Lisp code for the Prolog interpreter separately (here):

http://interweave-consulting.blogspot.co.uk/2017/02/a-simple-prolog-interpreter-in-lisp.html