Lab #4: Prolog Introductory Lab

Part 1: Compiling and running a program

1. Create the program prog1.prolog in your favorite text editor, and enter and save the following facts.

prereq(introCS,dataStructs).
prereq(dataStructs,progLangs).
prereq(dataStructs,graphics).
prereq(linAlg,graphics).

2. In an xterm window, change to the appropriate directory where you stored the above program, and type pl to start up Prolog.

3. Inside Prolog, type ['prog1.prolog']. to load in the rules you have entered. Make sure you include the period at the end.

4. Enter the following queries into Prolog. Whenever you get a prompt for more answers, enter a semicolon (;) to see if there are any more. What responses do you get? Why?

prereq(dataStructs,graphics).
prereq(introCS,linAlg).
prereq(dataStructs,ai).
prereq(linAlg,X).
prereq(dataStructs,Classes).
prereq(dataStructs,classes).
prereq(introCS,dataStructs).
prereq(introCS,progLangs).

5. Note that "introCS" is not considered as a prerequisite to "progLangs". Why? To correct this, we will create a new predicate called "required" which will take this into account. Add the following rules to the bottom of your program:

required(Course,NextCourse) :- prereq(Course,NextCourse).
required(Course,NextCourse) :-
prereq(Course,SomeOtherCourse),required(SomeOtherCourse,NextCourse).

Now try entering

required(X,progLangs).

Does this solve the problem? Why? What does the comma (,) mean in the rule above?

Part 2: How Prolog does it: matching and backtracking

1. Whenever you enter a query (also referred to as a goal), Prolog tries to find all rules and facts to match that query. More specifically, a fact or a head (left side) of a rule matches a goal if all three of the following conditions are true:

a. Both have the same predicate.

b. Both have the same number of terms following the predicate.

c. Matching terms from the query and the fact (or rule head) are equal. If at least one of them is a variable, the variable is bound to match the other.

2. Enter the following queries and examine the results. How is this consistent with the above statements?

prereq(introCS,dataStructs).
required(introCS,progLangs).

3. When Prolog gets to the point where it can't match a goal, it backtracks to the point where a choice had to be made, and tries a different choice. For example, enter the following query:

required(introCS,progLangs).

What kind of backtracking did Prolog have to do to answer this question?

4. To see a trace of Prolog's work, enter the following at a Prolog prompt:

trace.

Then try to run the query again:

required(introCS,progLangs).

At each stopping point, hit enter to continue. You'll see Prolog work its way through the possibilities. You will sometimes see a variable with an underscore in front of it, like _G463. This indicates that Prolog has picked a default name for an as-of-yet unbound variable. When the query is done, type

nodebug.

to get Prolog out of debug mode.

5. The order in which you enter in Prolog rules can be important. Try changing the rules for "required" to the following and see what happens when you try the query "required(X,progLangs)." Tracing through the program may help.

required(Course,NextCourse) :- prereq(Course,NextCourse).
required(Course,NextCourse) :-
required(SomeOtherCourse,NextCourse),prereq(Course,SomeOtherCourse).

Part 3: Lists in Prolog

1. Prolog has lists in much the same fashion as Scheme and ML. A list is written with similar syntax to ML (e.g. [1,2,3,4]). Start editing a new Prolog program, and enter in the following:

countTo(1,[1]).
countTo(2,[1,2]).
countTo(3,[1,2,3]).
countTo(4,[1,2,3,4]).

Load in your code, then enter the following query:

countTo(4,[1,2,3,4]).

2. Prolog provides pattern matching, much like ML, for separating information out of lists. Try the following queries:

What do you see? Why? What purpose does the underscore (_) serve?

3. Try the following append example, and see what it does:

append([a,b],[q,r,x],Answer).

4. Append is built into Prolog, but you could easily define it yourself. Let's do it. We'll create a predicate called myAppend, which does exactly the same thing as append but we've defined it ourselves. The following code is a headstart, but there's a mistake in it. Find it and fix it. Why does this work?

myAppend([],L,L).
myAppend([H | T1],L2,[H | T3]) :- myAppend(T1,L2,T1).

(Note that Prolog sometimes gives warnings about "singleton variables." This means that you have a variable that exists in only one place, is used nowhere else in the rule, and an underscore is probably more appropriate.)

5. Prolog has a "member" predicate that is used to test if a given value is the member of a list. Try the following:

member(2,[5,2,3]).
member(X,[5,2,3]).

6. Similarly, we could write our own "myMember" predicate. Again, here's a broken headstart for you to clean up:

myMember(X, [X | _]).
myMember(X, [H | T]) :- myMember(H,T).

Part 4: Prolog Mathematical Operators

1. Try out the following queries to see what you get:

1=2.
X=2.
Y=X.
X=Y,X=zaphod.

Technically, = is a predicate just like any other and can be written like

=(X,2).

But the infix notation is standard and more readable.

2. Try out this query.

1+2=3.

The "plus" operator produces a symbolic result "1+2". To actually do the arithmetic, you need to force it. This is done with the is operator. Try these out:

2 is 1+1.
X is 3*4.
Y is Z+1.

Notice the error message from the last example: Prolog requires that the right hand side of an is relation be ground. Otherwise Prolog might have to so some serious equation solving!

3. What does the following mystery predicate do? Why?

mystery([],0).
mystery([_|T],N) :- mystery(T,M), N is M+1.

4. Write a factorial predicate to be able to successfully answer the query factorial(6,X).

Part 5: Now You're Cooking

1. Try out this creative use of the "append" predicate:

L=[1,2,3,4,5],append( V , [H|T] , L).

2. See if you can use this idea to create a predicate "perm", which produces all permutations of an input list. For example,

perm([1,2,3],X).

should produce