cps721: questions about the 2nd assignment.

Questions related to the 2nd assignment

This page contains questions from students and my answers to them. If a question is asked that has already been answered, then I will not post another answer. So if your questions seems to go unanswered, you should check over previous questions.

Visit this Web page to download an open source version of ECLiPSe Prolog that uses "not" for a negation-as-failure operator instead of unreadable \+

Q1
I was wondering if rearranging elements in a list makes it different. For example if these two lists are equal [ l, i, m, e ] and [ m, i, l, e] or not? Does Prolog recognise them as equal lists?
A1
Two lists are identical if they are identical element by element. So, the list [l, i, m, e] is different from [m, i, l, e] simply because their first elements are different. The head of [l,i,m,e] is the element l, but the head of [m,i,l,e] is the element m.

Q2
Can we use other programs to write recursive programs in Part 2 ?
A2
You allowed to use only predicates member, append, length that we discussed in class. But do not use them without reason. You are not allowed to use any other predicates from the system library or from the lecture notes. However, you can write rules for your own helping predicates (if it is really necessary). Whenever possible, try to write recursive rules directly (i.e., without using any other predicates). This will help you to practice how to write recursive programs.
I would discourage in general the tendency to rely on the library predicates without prudence. I noticed that some cps721 students try to use library predicates all the time, even in cases when obviously a predicate can be easily defined in terms of itself. This often leads to confusion, and getting off the right track. For example, imagine someone who tries to implement length(List,N) or sum(List,S) using member(X,List) or append(L1,L2,List). We discussed in class that there are straightforward recursive implementations of length(List,N) or sum(List,S) that do not use any other predicates.

Q3
I keep getting an "instantiation fault in ... in module eclipse". Not sure how I can go about fixing that error. What do you suggest I do.
A3
Start tkeclipse (ECLiPSe Prolog with a GUI). Click File/Compile to consult your program. Click Tools/Tracer: this opens a new "ECLiPSe Tracer" window with extensive facilities for debugging. Type a query in the main window and click "run". This activates your Tracer window. Click on "creep" each time to see execution of your program step-by-step. If you are not interested in some predicates (e.g., you know there is no bug there), you can click on "Skip" when execution gets to that predicate, but then keep clicking on "creep' to locate your error.

Q4
In Assignment 2: Are we allowed to use "is"?
A4
You have to use is whenever you assign a value of an arithmetical expression to a variable. Your arithmetical expressions can be built from numbers, variables, and arbitrary arithmetical operators on them. Remember that when you write Z = 2 + 5 the value of the variable Z will not be 7, as you might expect, but it will be 2+5, i.e., the addition will not be performed. However, if you write

X is 2, Y is 5, Z is X + Y. then the variable Z will be assigned the value 7. Note also, that if you write Z is 2 + 5, Z is 1+2 in your rule, then this conjunction is false, because once a variable Z got an arithmetical value 7 from the assignment 2+5, is cannot be assigned another value 3. However, if you write 6 is 2+4, then in this case the operator is works as =:=, and this expression is true, because the LHS is the number 6 equal to the value of the arithmetical expression on the RHS.

Q5
I have one question about the different ways of representing list. For e.g. [a|B] could that be converted to [a,B] given that B = [f], so you could replace B with [] there fore, [a|[f]] -> [a, f] or is it not allowed because [a|b] cannot be switched to [a,b] similarly, [a|B] cannot be [a, B] ??
A5
If you have the list [a|[f]], then according to the vertical bar notation, this is the same as [a,f]. However, in a general case, if you have the list [X|Y], and you do not know what the variable Y stands for, then because the variables X and Y can match any list, you cannot re-write [X|Y] as [X,Y] simply because Y can be a list with arbitrary many elements, but when you write [X,Y] then it means that you have a list with 2 elements only: X and Y. For example, [X|[a,b,c]]=[X,a,b,c]. The lecture notes include many examples, read them carefully. Also, the quiz on lists included 6 pairs of lists.

Q6
For the Xth set in the first question, this was my answer: <...skip...> Two lists can be made identical by setting the correct variables. <...skip...> Ignoring the correctness of the answer, is this sufficient explanation to obtain full marks?
A6
No this explanation is not good enough for several reasons. First, you start with stating an answer and it remains the mistery how did you guess it. Then, you use your answer to do transformations. This is not right. You have to do transformations using rules of the two list notations that we studied, going from the lists given to you to other intermediate lists, and then gradually go to a final syntactic form. The correct answer should emerge in the result of these transformations. Once you have transformed lists to similar syntactic forms, I always recommend to write one list above another, compare them element by element, and only from this comparison you can make a conclusion whether lists are identical or not, and if yes. what are the values of variables. Second, you explanation is too cryptic and difficult to read. Write English words: it will be easier for a TA to mark this and see your line of reasoning. Remember that the 1st Part is about doing transformations between lists in general and demonstrating that you got skills of doing transformations.

Q7
I have a question regarding part I of the assignment. Generically, do these two lists match?

              [X, a] and [b, X]

Because to me, matching is.. for example, when you have a predicate, predicate([X, a]) in your knowledge base and you perform a query of the predicate ?- predicate([b, X]), this would return yes since the X in the query will be given the value a. So the X in the knowledge base will be different than the X in the query. So wouldn't these two lists match since the query can successfully call the predicate passing in the list as an argument? Or would they NOT match because X must be the same in both lists, even though one X is in the query and one X is in the predicate. I thought this process of matching the list with the argument in the predicate was the definiton of matching.
A7
First of all, write these 2 lists one above another:

        [X , a]
        [b , X]

Now, if we match them element by element we can match the opening bracket in the top list with the opening bracket in the 2nd list. We can match X=b because a variable X can match anything. We can match commas in both lists too. Also, we can match the second elements in both lists a=X and the closing brackets. Once we have did matching, we got some equations that must have a solution if two lists are equal. In this case, we got 2 equations:

             X=b  and  a=X

but obviously it is not possible for X to be equal both to "a" and to "b" at the same time. Hence, these two lists do not match. Of course, if you have lists

        [X , a]
        [a , X]

then they will match: X=a in both cases. Similarly, in the example that you mentioned, predicate([X, a]) in a knowledge base cannot match the query ? - predicate([b, X]) because X cannot be both "a" and "b" at the same time.

Q8
Can we use the predicates max(X,Y,M) and is_list(L) from the standard library anywhere in the Part 4 of the 2nd assignment?
A8
Yes, this is the only case when you can use the library predicates not discussed in class. But you cannot use any other library predicates. You lose marks if you try to use any other library predicates. In the 2nd assignment, your task is to learn how to write recursive programs directly, without using externally implemented predicates.

Q9
The FAQs mentioned that we are not allowed to use any library predicates. But say I want to use the functionality of somePredicate(...), which is a library predicate, can I just develop a program for this predicate and use it in my program?
A9
No, do not reimplement library predicates in the 2nd assignment: see Q2/A2 above. The questions in the 2nd assignment are relatively straightforward. You are expected to write the programs directly using only the predicate given to you. Practically speaking, during the exams and labs, you are asked to write recursive programs without access to the library predicates.
Note each program has its own logic. To develop your program, do the exhaustive case analysis. For each mutually exclusive case, write its own rule. Then, your program is simply the rules you write for all cases.

Q10
In the program for predicate sum(List,S) that we discussed in class, can we do addition in the 2nd argument of sum([Head | Tail], Head +M) assuming that sum(Tail,M) is true ?
A10
No, this would be an error. All arithmetical oeprations must be done outside of your predicates. Note that predicates are not function. They encode logical statements. For example, if you are given the atomic statements about an area and height, then the following is a correct program to compute volume V of a brick b.

area(b,25).
height(b,4).
volume(Br,V) :- area(Br,A), height(Br,H), V is A*H.  /* query ?- volume(b,X). */

Note the order of predicates in the body of the rule. We have to call "area" and "heigh" first to retrieve the values for variables A,H, and only then we compute the value of V. Recall, we cannot use equality, i.e., V = A*H would be wrong, but we must use "is" operator to compute volume.

Q11

A11

Q12

A12

Q13

A13

Q14

A14

Q15

A15

Q16

A16

Q17

A17

Q18

A18

Q19

A19

Q20

A20

CPS721