50Ply Blog

Building Things

PPfAI Chapter 1 in Clojure Core.Logic

| Comments

David Nolen mentioned Ivan Bratko’s Prolog Programming For Artificial Intelligence at a talk he gave recently demoing cKanren extensions in Core.Logic. I eagerly picked up an old edition of the book for $5 and got to work.

My other exposure to logic programming has been through the prolog compiler that Peter Norvig presents in Paradigms of Artificial Intelligence Programming and studying mini-Kanren via Friedman’s The Reasoned Schemer. Dan Friedman and William Byrd also gave a presentation at a Clojure conj.

Chapter 1 of Ivan Bratko’s book introduces an example logic program that reasons about relationships in a family.

The program starts out by defining some facts:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/* pam is bob's parent, and so on... */
parent(pam, bob)
parent(tom, bob)
parent(tom, liz)
parent(bob, ann)
parent(bob, pat)
parent(pat, jim)

/* pam is female... */
female(pam)
male(tom)
male(bob)
female(liz)
female(ann)
female(pat)
male(jim)

We can translate this into Clojure Core.Logic fairly directly:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

;; define the relations and their arity
(defrel parent p c)
(defrel male p)
(defrel female p)

;; add facts to the relations. Again, :pam is :bob's parent
(fact parent :pam :bob)
(fact parent :tom :bob)
(fact parent :tom :liz)
(fact parent :bob :ann)
(fact parent :bob :pat)
(fact parent :pat :jim)

;; and :pam is female
(fact female :pam)
(fact male :tom)
(fact male :bob)
(fact female :liz)
(fact female :ann)
(fact female :pat)
(fact male :jim)

At this point we can ask the program to recite the facts back to us. For example, who are Bob’s parents?

In prolog:

1

?- parent(X, bob)

and prolog answers:

1
2

X = tom
X = pam

In Clojure’s Core.Logic:

1
2

(run* [q]
  (parent q :bob))

and Core.logic answers:

1

(:tom :pam)

Things get more interesting when we start adding rules to the program so that the system can start deriving new facts. For example, we can add a rule describing what a mother is:

In prolog:

1
2
3

mother(X, Y) :-
  parent(X, Y),
  female(X)

This reads: “X is the mother of Y if X is the parent of Y and X is female.”

In Core.logic:

1
2
3
4

(defn mother [x y]
  (fresh []
    (parent x y)
    (female x)))

Now we can ask who Bob’s mother is:

1
2
3
4
5

(run* [q]
  (mother q :bob))

;; answer
(:pam)

Or, we can move the variable and ask we has Pam as a mother:

1
2
3
4
5

(run* [q]
  (mother :pam q))

;; answer
(:bob)

I’ll provide the rest of the Core.logic version of the family program without much explanation. The important things you need to know to understand this code are:

  1. run* executes a logic program for all of its solutions
  2. fresh creates new lexically scoped, unbound variables. All clauses inside fresh are logically AND’d together
  3. conde similar to an OR. Each conde clause is asserted independently of the others.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

;; C is the offspring of P if P is the parent of C
(defn offspring [c p]
  (parent p c))

;; X is the grandparent of Z if, for some Y, X is the parent
;; of Y and Y is the parent of Z
(defn grandparent [x z]
  (fresh [y]
    (parent x y)
    (parent y z)))

;; X is the grandmother of Y if X is the grandparent of Y and
;; X is a female
(defn grandmother [x y]
  (fresh []
    (grandparent x y)
    (female x)))

;; X is the sister of Y if, for some Z, Z is the parent of X
;; and that same Z is the parent of Y and X is female and
;; Y and X are not the same person.
(defn sister [x y]
  (fresh [z]
    (parent z x)
    (parent z y)
    (female x)
    (!= x y)))

;; X is a predecessor of Z if X is the parent of Z or if
;; X is the parent of some Y and that Y is a predecessor
;; of Z
(defn predecessor [x z]
  (conde
    [(parent x z)]
    [(fresh [y]
       (parent x y)
       (predecessor y z))]))

The final rule is especially interesting because it introduces logical recursion. Notice that predecessor is defined in terms of itself.

Now some examples of what this program can derive:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

(run* [q]
  (predecessor q :jim))

;; answer
(:pat :bob :tom :pam)

(run* [q]
  (grandparent q :ann))

;; answer
(:tom :pam)


(run* [q]
  (grandmother q :ann))

;; answer
(:pam)

Now, go forth and build your family tree! Or, better yet, go solve Daily Programmer #65 without building a graph!

EDIT: There was a typo in my first example. Thank you zerokarmaleft for pointing it out.

Comments