Prolog Introductory Lab

This is a team assignment. Work through the following lab, and finish up in your own time if you need it. There are two portions that you need to turn in, labeled with "***":

Turn in the results for Part 1 #5 in a file called courses.txt.
Turn in your code for Part 3 #6 in a file called memberOf.prolog.

You and your partner do not both need to submit the work, but both your names should be included in program comments (lines that begin with %).

Keep in mind that in addition to this lab, there are Prolog resources linked on the course page if you need help.

There are other questions intermixed throughout the lab for you to think about. You do not need to turn in answers to these. Ask if the answers aren't 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 swipl to start up Prolog.
Inside Prolog, type
```
['prog1.prolog'].
```
(make sure you include the single quotes, the brackets, AND THE PERIOD AT THE END) to load in the rules that you have entered.

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?

Copy and paste the output from this step and submit it. Add to that file your interpretation of what the comma means in the above Prolog code.

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, though the basic syntax is more like Python (brackets and commas). 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 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 your 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.

Part 5: Now You're Cooking