CS 217: Prolog Introductory Lab

Work through the following lab, and finish up in your own time if you need it. Turn in your code for Part 4 #4 within a week. Keep in mind that in addition to this lab, there are Prolog resources linked on the course page if you need help. You may turn this in in pairs.

The questions that you find intermixed throughout the lab are for you to think about. Ask in lab or in class if the answers aren't in clear.

Part 1: Compiling and running a program

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).

In a terminal window, change to the appropriate directory where you stored the above program, and type pl to start up Prolog.
Inside Prolog, type ['prog1.prolog']. to load in the that rules you have entered. Make sure you include the period at the end.

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).

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

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:
1. Both have the same predicate.
2. Both have the same number of terms following the predicate.
3. 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.
Enter the following queries and examine the results. How is this consistent with the above statements?
```
prereq(introCS,dataStructs).
required(introCS,progLangs).
```
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?
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.
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. You may have to occasionally click back on the terminal window and hit the semicolon if it seems that the debugger is stuck.
```
required(Course,NextCourse) :- prereq(Course,NextCourse).
required(Course,NextCourse) :-
    required(SomeOtherCourse,NextCourse),prereq(Course,SomeOtherCourse).
```

Part 3: Lists in Prolog

Prolog has lists in much the same fashion as Scheme and SML. A list is written with similar syntax to SML (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]).
Prolog provides pattern matching, much like SML, for separating information out of lists. Try the following queries:
```
countTo(4,[H | T]).
countTo(4,[H1, H2 | T]).
countTo(4,[_, X | _]).
countTo(2,[H1, H2 | T]).
countTo(2,[H1, H2, H3 | T]).
```
What do you see? Why? What purpose does the underscore (_) serve?
Try the following example, and see what it does:

append([a,b],[q,r,x],Answer).
The predicate append is built into Prolog, but you could easily define it yourself. Let's do it. We'll create a predicate called appendTo, 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.
```
appendTo([],L,L).
appendTo([H | T1],L2,[H | T3]) :- appendTo(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.)
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]).
```
Similarly, write our own memberOf predicate. Here's a broken headstart for you to clean up. Submit your code in a file called memberOf.prolog.
```
memberOf(X, [X | _]).
memberOf(X, [H | T]) :- memberOf(H,T).
```

Part 4: Prolog Mathematical Operators

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.
Try out this query.

1+2=3.

"1+2" is an expression, which is not the same as the symbol "3". There are thus two more ways of representing equality in Prolog. Try these out:
```
2 is 1+1.
1+1 is 2.
2 =:= 1+1.
1+1 =:= 2.
X = 3*4.
X is 3*4.
X =:= 3*4.
X = 3*4, X = 12.
X = 3*4, X is 12.
X = 3*4, X =:= 12.
```
You might find it useful to read the help info on these predicates. Try:
```
help(=:=).
help(=).
help(is).
```

What does the following mystery predicate do? Why?

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

Write a factorial predicate to be able to successfully answer the query factorial(6,X). Submit your code in a file called factorial.prolog. Note that adding functionality to work the other way around, e.g. factorial(N,120). is trickier, and something we will do in class after we have covered the Prolog that we will need.

Part 5: Now You're Cooking