Important notes about grading:

  1. Compiler errors: Programs that cannot be compiled will receive an automatic zero. If you are having trouble getting your assignment to compile, please visit recitation or office hours.
  2. Late assignments: Please carefully review the course website's policy on late assignments, as all assignments handed in after the deadline will be considered late. Submitting an incorrect version before the deadline and realizing that you have done so after the deadline will be counted as a late submission.

Compile and run your code:

  1. You will need to implement your code in assignment4/assignment4.pl. assignment4/assignment4.plt is the testcase file and assignment4/plunit.pl is for unit testing.

  2. To run your implementation, you have two options:
    Option (1): Use iLab. Please see the document here.

    Option (2): Download and install the SWI-Prolog interpreter here. After the interpreter GUI is openned, you can use it to launch your program and make queries. In the installed GUI, after the ?- query symbol, type consult("/path/to/your/assignment4/assignment4.pl"). to load the assignment soure file. Please specify the path correctly to where you have saved assignment4/assignment4.pl. You will see a number of warnings. Please ignore them. Type "range(1,2,0)." (see Problem 1) after the ?- query symbol to make your first query. The result should be false.

  3. Unit testing:
    (1) In iLab, cd into the folder that contains assignment4.pl, assignment4.plt and plunit.pl.

    (2) swipl -t "use_module(plunit), load_test_files([]), run_tests." -s assignment4

    (3) You will then see how many test-cases your solution passed. Unit testing on your own machine requires swipl on the system path or where the computer can find the installed swipl program clearly specified.

Submission:

Please submit to Sakai assignment4.pl only.

Some "strange" things about SWI-Prolog you need to know:

I cannot quit the SWI-Prolog interpreter.

Type "halt." after the ?- query symbol to quite the Prolog interpreter.

I get a number of singleton variables warnings.

Warning: /../../../assignment4.pl:14: Singleton variables: [X]

This is because you introduced some variables in your program that are never used, which could be replaced with _. You can ignore this type of warnings. In fact, you can ignore any warnings in the console.

I get a number of 'PL-Unit: Test xxxx: Test succeeded with choicepoint' warnings.

Warning: /../../../assignment4.plt:25: PL-Unit: Test xxxx: Test succeeded with choicepoint

This is because the interpreter used backtracking and choicpoints to execute your program. You can ignore this type of warnings. In fact, you can ignore any warnings in the console.

I get one solution when I expect multiple solution.

?- member(X, [1,2,3]).

X = 1

The problem is that you expect to see X = 2 and X = 3 but it seems that the interperter gets stuck there.

?- member(X, [1,2,3]).

X = 1; <-- It is waiting for you to type ;

X = 2; <-- It is waiting for you to type ;

X = 3

Please explicitly type a semicolon there to let the interpreter resume the search.

I get true, then false when I expect just true.

Sometimes after the last solution, when you expect the interpreter to just stop, it instead waits for you to type ; one more time. For example:

?- member(1, [1,2,3]).

true ; <-- It is waiting for you to type ;

false.

This is because the interpreter is not smart about knowing if it has explored all the correct solutions. Consider the following situation:

A woman walks into a hardware store and says to the owner "I’m driving in fence posts, I need a really big hammer" The owner shows her a hammer. She says "No, I need a bigger hammer than that". The owner says "hold on, I have a bigger one in back".

He comes back a couple minutes later and says "Sorry, must have sold it. That’s the biggest we have." The first solution is offered (the first hammer). She rejects it, and the storeowner tries again. This time he fails. He thought he might have another solution, but he doesn’t.

You do not need to eliminate the false answer. It has no effect on program execution.

Built-in Predicates

Some of the predicates we learn in class are actually built-in. Feel free to use them in your assignment. Examples are append, length, and arithmetic predicates including +,*, /, <, =<, >, >=, etc. Please do not use other library functions not covered in class.

Warmup

Problem 1

Implement a predicate range(S,E,M) which holds if the integer M is within the range S to E including S and E.

In [1]:
/* YOUR CODE HERE (delete the following line) */
range(S,E,M) :- false.

Added 1 clauses(s).

Test-cases

In [2]:
?- range(1,2,2).
/* expected output: true. */

?- not(range(1,2,3)).
/* expected output: true. */

true.
true.

Programming with Lists

Let's implement some programs over lists.

Problem 2

Implement reverse of a list using the predicate reverseL(X,RevX) where RevX is the reverse of the list X. You might want to use append.

In [3]:
/* YOUR CODE HERE (delete the following line) */
reverseL(X,RevX) :- false.

Added 2 clauses(s).

Test-cases

In [4]:
?- reverseL([],X).
/* expected output: X = [  ]. */

?- reverseL([1,2,3],X).
/* expected output: X = [ 3, 2, 1 ]. */

?- reverseL([a,b,c],X).
/* expected output: X = [ c, b, a ]. */

X = [  ] .
X = [ 3, 2, 1 ] .
X = [ c, b, a ] .

Problem 3

Implement list membership predicate memberL(X,L) which holds if $X \in L$. Addtionally, if $L = \emptyset$, return false.

In [5]:
/* YOUR CODE HERE (delete the following line) */
memberL(X,L) :- false.

Added 3 clauses(s).

Test-cases

In [6]:
?- not(memberL(1, [])).
/* expected output: true. */

?- memberL(1,[1,2,3]).
/* expected output: true. */

?- not(memberL(4,[1,2,3])).
/* expected output: true. */

?- memberL(X, [1,2,3]).
/* expected output: see below */

true.
true.
true.
X = 1 ;
X = 2 ;
X = 3 .

Problem 4

Implement the predicate zip(Xs, Ys, XYs) that relates three lists, where the third list XYs contains pairs whose elements are the elements at the same indices of the first two lists Xs and Ys. In Prolog, we use A-B for a pair of elements A and B. For example, 1-2 is a pair (1,2).

The third list XYs will always be as long as the shorter of the first two lists; additional elements in the longer list are discarded.

In [7]:
/* YOUR CODE HERE (delete the following line) */
zip(Xs, Ys, XYs) :- false.

Added 3 clauses(s).

Test-cases:

In [8]:
?- zip([1,2],[a,b],Z).
/* expected output: Z = [1-a, 2-b]. */

?- zip([a,b,c,d], [1,X,y], Z).
/* expected output:: Z = [a-1, b-X, c-y]. */

?- zip([a,b,c],[1,X,y,z], Z).
/* expected output:: Z = [a-1, b-X, c-y]. */

?- length(A,2), length(B,2), zip(A, B, [1-a, 2-b]).
/* expected output:: A = [1,2], B = [a,b]. */

Z = [ 1-a, 2-b ] .
X = _1908, Z = [ a-1, b-_1908, c-y ] .
X = _1926, Z = [ a-1, b-_1926, c-y ] .
A = [ 1, 2 ], B = [ a, b ] .

Problem 5

Implement the predicate insert(X, Ys, Zs) that is a relation between an integer X , a sorted list of integers Ys, and a sorted list of integers Zs. Zs is the result of inserting X to Ys. It contains the first argument X and all the elements of Ys.

In [9]:
/* YOUR CODE HERE (delete the following line) */
insert(X, Ys, Zs) :- false.

Added 3 clauses(s).

Test-cases:

In [10]:
?- insert(3, [2,4,5], L).
/* expected output: L = [2,3,4,5]. */

?- insert(3, [1,2,3], L).
/* expected output: L = [1,2,3,3]. */

?- not(insert(3, [1,2,4], [1,2,3])).
/* expected output: true. */

?- insert(3, L, [2,3,4,5]).
/* expected output: L = [2,4,5]. */

?- insert(9, L, [1,3,6,9]).
/* expected output: L = [1,3,6]. */

?- insert(3, L, [1,3,3,5]).
/* expected output: L = [1,3,5]. */

L = [ 2, 3, 4, 5 ] .
L = [ 1, 2, 3, 3 ] .
true.
L = [ 2, 4, 5 ] .
L = [ 1, 3, 6 ] .
L = [ 1, 3, 5 ] .

Problem 6

Write a Prolog predicate remove_duplicates(L1,L2) that is true if L2 is equal to the result of removing all duplicate elements from L1. In the result, the order of the elements must be the same as the order in which the (first occurences of the) elements appear in L1.

In [11]:
/* YOUR CODE HERE (delete the following line) */
remove_duplicates(L1,L2) :- false.

Added 4 clauses(s).

Test-cases:

In [12]:
?- remove_duplicates([1,2,3,4,2,3],X).
/* expected output: X = [1, 2, 3, 4] */

?- remove_duplicates([1,4,5,4,2,7,5,1,3],X).
/* expected output: X = [1, 4, 5, 2, 7, 3] */

?- remove_duplicates([], X).
/* expected output: x = [] */

X = [ 1, 2, 3, 4 ] .
X = [ 1, 4, 5, 2, 7, 3 ] .
X = [  ] .

Problem 7

Write a Prolog predicate intersectionL(L1,L2,L3) that is true if L3 is equal to the list containing intersection of the elements in L1 and L2 without any duplicates. In other words, L3 should contain the elements that both in L1 and in L2. The order of the elements in L3 should be the same as the order in which the elements appear in L1.

In [13]:
/* YOUR CODE HERE (delete the following line) */
intersectionL(L1,L2,L3) :- false.

Added 4 clauses(s).

Test-cases:

In [14]:
?- intersectionL([1,2,3,4],[1,3,5,6],[1,3]).
/* expected output: true. */

?- intersectionL([1,2,3,4],[1,3,5,6],X).
/* expected output: X = [1,3]. */

?- intersectionL([1,2,3],[4,3],[3]).
/* expected output: true. */

true.
X = [ 1, 3 ] .
true.

Problem 8

Implement partition(L,P,S) such that

  • P is the prefix of L and
  • S is the suffix of L and
  • append(P,S,L) holds
  • If L is [], then P and S are [].
  • If L is [H], then P is [H] and S is [].
  • Otherwise,

You may need to use the length,prefix,suffix,append predicates that we have seen in class.

In [15]:
prefix(P,L) :- append(P,X,L).                                                       
suffix(S,L) :- append(X,S,L).                                                       

/* YOUR CODE HERE (delete the following line) */
partition(L,P,S) :- false.

Added 5 clauses(s).

Test-cases

In [16]:
?- partition([a],[a],[]).
/* expected output: true. */

?- partition([1,2,3],[1],[2,3]).
/* expected output: true. */

?- partition([a,b,c,d],X,Y).
/* expected output: Y = [ c, d ], X = [ a, b ]. */

true.
true.
Y = [ c, d ], X = [ a, b ] .

Problem 9

Implement the predicate merge(X,Y,Z) where X and Y are sorted, and Z contains the same elements as U where append(X,Y,U) but Z is also additionally sorted.

In [17]:
/* YOUR CODE HERE (delete the following line) */
merge(X,Y,Z) :- false.

Added 4 clauses(s).

Test-cases

In [18]:
?- merge([],[1],[1]).
/* expected output: true. */

?- merge([1],[],[1]).
/* expected output: true. */

?- merge([1,3,5],[2,4,6],X).
/* expected output: X = [ 1, 2, 3, 4, 5, 6 ]. */

true.
true.
X = [ 1, 2, 3, 4, 5, 6 ] .

Problem 10

Implement predicate mergesort(L,SL) where SL is the sorted version of L. Use the predicate partition to partition the list L into two segments, sort each on separately (using mergesort) and combine the individual sorted list using merge.

In [19]:
/* YOUR CODE HERE (delete the following line) */
mergesort(L,SL) :- false.

Added 3 clauses(s).

Test-cases

In [21]:
?- mergesort([3,2,1],X).
/* expected output: X = [ 1, 2, 3 ]. */

?- mergesort([1,2,3],Y).
/* expected output: Y = [ 1, 2, 3 ]. */

?- mergesort([],Z).
/* expected output: Z = [  ]. */

?- mergesort([1,3,5,2,4,6],X).
/* expected output: X = [ 1, 2, 3, 4, 5, 6 ]. */

X = [ 1, 2, 3 ] .
Y = [ 1, 2, 3 ] .
Z = [  ] .
X = [ 1, 2, 3, 4, 5, 6 ] .