Prolog Tutorial for EECS 492 WN 2021

• Written by EECS 492 WN 2021 Teaching Group.
• Latest Update: 3:10 A.M, EST. Feb 24, 2021.
• Demo files: demo1.pl, demo2.pl

Facts, Rules, and Queries

Prolog programming is all about writing knowledge bases (KB), collection of facts and rules. The basic formatting is as follows:

1. Period . at the end
2. constants: lower-case
3. VARIABLES: upper-case

Facts

The basic format for a fact is predicate(arguments).

Example 1: Use the following predicates to describe the facts:

1
eecs(X): X is an EECS course.
2
math(X): X is an MATH course.

To describe eecs280, eecs281, eecs445, eecs492 and math214, we could write:

xxxxxxxxxx
5
1
eecs(eecs280).
2
eecs(eecs281).
3
eecs(eecs245).
4
eecs(eecs292).
5
math(math214).

The predicate may take more than 1 argument.

Example 2: Use the following predicates to describe the facts:

xxxxxxxxxx
3
1
prerequisite(X, Y): X is a prerequisite of Y.
2
taken(X, Y): X has taken course Y.
3
teach(X, Y): X teaches course Y.

Given that martin has taken eecs445, and teaches eecs280 and eecs492, we could write:

​x
1
prerequisite(eecs280, eecs281).
2
prerequisite(eecs203, eecs281).
3
prerequisite(eecs281, eecs492).
4
prerequisite(eecs281, eecs445).
5
prerequisite(math214, eecs445).
6
​
7
teach(martin, eecs492).
8
teach(martin, eecs280).
9
taken(martin, eecs445).

Rules

The basic format for a fact is predicate(arguments) :- predicate(arguments). The :- should be read as “if”, or “is implied by”.

Example 1: Use the following predicates to describe the facts:

xxxxxxxxxx
1
1
teach(X, Y) => taken(X, Y): If X teaches Y, X must have taken Y.

To describe this rule, we could write:

xxxxxxxxxx
1
1
taken(X, Y) :- teach(X, Y).

Queries

Store your KB in a .pl file, open it in the SWI-prolog, you should see something similar to this:

xxxxxxxxxx
8
1
Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.22-114-g7e1bb6838)
2
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
3
Please run ?- license. for legal details.
4
​
5
For online help and background, visit https://www.swi-prolog.org
6
For built-in help, use ?- help(Topic). or ?- apropos(Word).
7
​
8
?- 

To question the KB if a fact is true, one make a query after ?-.

Example 1: Is math214 an eecs course?

xxxxxxxxxx
2
1
?- eecs(math214).
2
false.

Example 2: Is math214 a prerequisite of eecs492 ?

xxxxxxxxxx
2
1
?- prerequisite(math214, eecs492).
2
false.

Example 3: Have martin taken eecs492 ?

xxxxxxxxxx
2
1
?- taken(martin, eecs492).
2
true.

Note that although taken(martin, eecs492) is not directly stated in the KB, prolog makes the logical inference from the fact that teach(martin, eecs492) and taken(X, Y) :- teach(X, Y). In other words, since Martin is teaching EECS 492, he must have taken this course earlier.

Example 4: List all courses that martin has taken?

xxxxxxxxxx
5
1
?- taken(martin, X), print(X), nl, fail.
2
eecs445
3
eecs492
4
eecs280
5
false.

Recursion

You may have noticed that in the earlier example, the logic is not complete. If one has taken one course, he/she must have taken the prerequisites.

One may write a new rule like:

xxxxxxxxxx
1
1
taken(X, Y) :- taken(X, Z), prerequisite(Y, Z).

It seems fine when you make the query:

xxxxxxxxxx
2
1
?- taken(martin, eecs281).
2
true .

However, the problem arises when you try to check all course that Martin has taken:

xxxxxxxxxx
12
1
?- taken(martin, X), print(X), nl, fail.
2
eecs445
3
eecs492
4
eecs280
5
eecs281
6
math214
7
eecs281
8
eecs280
9
eecs203
10
eecs280
11
eecs203
12
​

Oops! Looks like your program gets stuck in an infinite loop! Prolog applies backward chaining and depth-first search to do logic inference, and this will lead to an infinite search tree. Check the Recursion section for details.

To stop Prolog from an infinite loop, press ctrl + C, and press A to abort.

xxxxxxxxxx
13
1
?- taken(martin, X), print(X), nl, fail.
2
eecs445
3
eecs492
4
eecs280
5
eecs281
6
math214
7
eecs281
8
eecs280
9
eecs203
10
eecs280
11
eecs203
12
Action (h for help) ? abort
13
% Execution Aborted

A better way is to avoid recursion in Prolog. Use a new predicate instead.

xxxxxxxxxx
2
1
know(X, Y) :- taken(X, Y).
2
know(X, Y) :- taken(X, Z), prerequisite(Y, Z).

And the query works fine here:

xxxxxxxxxx
8
1
?- know(martin, X), print(X), nl, fail.
2
eecs281
3
math214
4
eecs281
5
eecs445
6
eecs492
7
eecs280
8
false.

Definite Clause Grammars

Context Free Grammars

CFG is a finite collection of rules indicating that...

• Which sentences are grammatical/syntactically correct;
• What their grammatical structure actually is.

CFG captures constituents and ordering.

• Need something else for grammatical relations and dependency relations.

CFG consists of...

• Set of terminals (words);

• Set of non-terminal (the constituent of language);

  • e.g., s , np , vp , det , n , v.

• Sets of rules of the form A -> $\alpha$, where $\alpha$ is a string of zero or more terminals and non-terminals.

An exemplar CFG is like:

xxxxxxxxxx
12
1
s   ->  np  vp
2
np  ->  n
3
np  ->  det  n
4
vp  ->  v
5
vp  ->  v  np
6
​
7
det ->  a
8
det ->  the
9
n   ->  student
10
n   ->  prolog
11
v   ->  likes
12
v   ->  hates

Consider a sentence (a string of words): the student likes prolog. The question is, is this grammatical according to our little grammar? And if it is, what structure does it have?

A derivation is a sequence of rules applied to a string that accounts for that string:

• Covers all the elements in the string;
• Covers only the elements in the string.

It can be represented in:

[s [np [det the] [n student]] [vp [v likes] [np [n prolog]]]]

In tree form, it looks like:

xxxxxxxxxx
9
1
             s
2
     ________|________
3
    np               vp
4
 ___|___         ____|____
5
det    n         v       np
6
|      |         |        |
7
the student     likes     n
8
                          |
9
                       prolog

Definite Clause Grammars

DCG is a notation for writing grammar that hides the underlying difference list variables.

Translate the previous CFG into DCG is straightforward:

xxxxxxxxxx
12
1
s   --> np, vp.
2
np  -->  n.
3
np  -->  det, n.
4
vp  -->  v.
5
vp  -->  v, np.
6
​
7
det -->  [a].
8
det -->  [the].
9
n   -->  [student].
10
n   -->  [prolog].
11
v   -->  [likes].
12
v   -->  [hates].

Example 1: find out whether the student likes prolog is a sentence.

xxxxxxxxxx
2
1
?- s([the, student, likes, prolog],[]).
2
true .

Example 2: find out if the student is a noun phrase (np).

xxxxxxxxxx
2
1
?- np([the, student],[]).
2
true.

Example 3: generate all the sentences in the grammar.

xxxxxxxxxx
9
1
?- s(X,[]), print(X), nl, fail.
2
[student,likes]
3
[student,hates]
4
[student,likes,student]
5
[student,likes,prolog]
6
...
7
[the,prolog,hates,the,student]
8
[the,prolog,hates,the,prolog]
9
false.

FAQ

General

How to locate the *.pl file in prolog?

Suppose you have a directory eecs492/prolog and all your prolog files are under this directory. You can go to this directory first, and then start Prolog /user/eecs492/xsb. Once you are in the Prolog environment, you can load the file by typing [filename].

When I load up my file, I receive some warnings about singleton variables. Does that matter?

The reason is that you have variables defined in your predicates that have not been referenced or used in the body. You can replace those variables with an anonymous variable _ (underscore).

For example, if you define the following "member" predicate, "Y" is not used, so you will have a "singleton" warning.

xxxxxxxxxx
2
1
member(X,[X|Y]. 
2
member(X,[Y|T]) :- member(X,T) 

If you define it as the following, you should be fine.

xxxxxxxxxx
2
1
member(X,[X|]). 
2
member(X,[|T]) :- member(X,T). 

Family Tree Problem

I have a problem with duplicate answers, is that ok?

The reason for this to happen is that you have multiple facts/rules that are matched by the prolog interpreter. Since the tutorial didn't mention how to prevent that, it is ok for your program to produce duplicate results. (no points will be taken from you in this regard). One way to fix it is to use the built-in “setoff”.

So you can make the following changes to avoid duplicates.

xxxxxxxxxx
2
1
brother0(X,Y) :- .... 
2
brother(X,Y) :- setof(_, brother0(X,Y), _). 

I'm having trouble figuring out how to prevent a "reflexive" type of relationship from happening. For example, Harry should not be Harry's brother and the same for his sister.

To avoid this, you will need to specify that X and Y cannot be the same as in the following:

xxxxxxxxxx
1
1
sister(X, Y) :- child(X, Z), child(Y, Z), female(X), X \== Y.

Block World Problem

For a "taken" response should "on" be changed to "off"? For example, my current code returns the following. Should it respond with "I have taken the cone off the square."?

xxxxxxxxxx
3
1
?- command([take,the,cone,on,the,square]). 
2
I have taken the cone on the square. 
3
yes 

No you don't need to change "on" to "off" in the "take" case. Basically, "on ..." is modifying the thing that should be taken. In your example, "on the square" is modifying "the cone".

How do I print out the response?

One way of doing it is to take the input list (e.g., [put, the, red, block, on, the, green, circle]), and convert it to another output list. To come up with this output list, you need to check each member of the original list to see whether it requires any change. Once you have the output list, you can simply write each member of the output list out using "write". The key here is to do some list operations.

When implementing the predicate "command", this command will take an argument and do some processing, then provide output.

An example could be:

xxxxxxxxxx
2
1
command(X) :- X==[],!, write(' it is an empty list'). 
2
command(X) :- write('it is not an empty list"). 

Then you can test it:

xxxxxxxxxx
6
1
?- command([]). 
2
this is an empty list 
3
yes 
4
?- command([a,b,c]). 
5
this is not an empty list 
6
yes

Certainly the above is only an example, you will need to re-implement “command” to fit that to our problem here.

I have np defined as follows. The problem is that the last definition of np never halts.

xxxxxxxxxx
3
1
np --> det, adj, n. 
2
np --> det, n. 
3
np --> np, pp. 

Your third rule np-->np, pp will loop infinitely. You can change np-->np, pp to "np-->det, n, pp, etc.

Is it alright to have an infinite number of chains for the prepositional section of the sentence? For example, is [put,the,cone,on,the,cone,on,the,cone,on,the,cone,on,the,cone....] valid input, or should this terminate after 1 or 2 prepositions?

It should be able to support an arbitrary number of pps as valid input. But all the testing cases will not go beyond the ones you've seen in the training data.

A valid sentence is take the ball, but it looks like put the ball is not. I'm not sure how to accept take but not put for my one rule that accepts a noun with an empty pp.

Good catch here! There is indeed a difference between “put” and “take”. We have not talked about lexicalized grammar, so we will not worry about this difference for now. My testing cases will be strictly following the training examples, will not be testing anything like “put that ball”.

However, for your information, to distinguish “put” and “take” in this use, we can have lexicalized grammar. Basically, instead of a general “V”, we can separate it to “V-Put” and “V-Take”. Then other grammar rules will be updated accordingly to use “V-Put” and “V-Take”.

Are cubes, cones, and blocks the only nouns that can have action taken against them? (e.g., you cannot take a square or circle)

You made a very good observation. To make the problem simpler, here we mainly focus on the syntax, without worrying about the semantics, e.g., what objects can or cannot be taken. So all the nouns should behave the same even though we do not see "take the square" in the example.