CSCI 310 Logic Programming Project

Date Due: 7 March 2008

In this project you will practice writing programs from a logical point of view. You are to use SWI Prolog (installed in the labs, available free on line) to write your programs. You should load your programs from a file, and capture the output from the debug window to another file using cut and paste. You should turn in your program file as well as your output file by emailing it to me, allisodl@oneonta.edu, as a single zip file. Be sure to include comments in your program file (at least giving your name) and also include any supporting functions you needed to write. For this assignment, you are allowed to use any of the Prolog functions we discussed or wrote in class. Anything else you need, you should include code for in your program file.

1. To get warmed up, write a function, hlbackwards, that takes a list as input, and returns a list in which the elements of the toplevel list are in reverse order. Here is a sample execution:

?- hlbackwards([a,b,[c,d],e],X).

X=[e, [c, d], b, a]

Yes

2. To continue warming up, write a function, llbackwards, that takes a list as input, and returns a list in which every list and sublist is in reverse order. Here is a sample program execution:

?- llbackwards([a,[b,c],[[d,e,[f],g],h,i]],X).

X=[[i, h, [g, [f], e, d]],[c, b], a]

Yes

3. Write a function, palindrome, that takes a list as input and returns Yes if the list is a palindrome, ie reads the same in both directions, and No otherwise. Here is a sample run:

?- palindrome([a,b,[c,d],e]).

?- palindrome([a,[b,c,[d]],[[d],c,b],a]).

Yes

4. Write a function, permutations, that takes a list as input and generates a list containing all possible permutations of the list elements. Here is a sample application:

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

X=[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Yes

5. Write a function, hanoi, that takes a single number as input and prints out the solution to the Towers of Hanoi problem for that many disks. This is the problem of moving a stack of k disks of decreasing size from bottom to top, from the first peg to the third peg with another peg that may be used as well, subject to the condition that a larger disk is never put on top of a smaller one, and only one disk may be moved at a time. Here is a sample run:

?- hanoi(3).

move disk from peg 1 to peg 3

move disk from peg 1 to peg 2

move disk from peg 3 to peg 2

move disk from peg 1 to peg 3

move disk from peg 2 to peg 1

move disk from peg 2 to peg 3

move disk from peg 1 to peg 3

Yes

6. Write a function, fibonacci, that takes a single integer as input and prints out a list containing that many terms of the Fibonacci sequence. Here is a sample execution:

?- fibonacci(7,X).

X=[1,1,2,3,5,8,13]

Yes

1. Write a program to argue with yourself. Your program should take statements that are typed in as a list and change the pronouns and negate them. For instance, you should change to I, are should change to am not, and so on. Here is a possible sample session:

?- argue([you,are,a,stupid,computer],X).

X=[i,am,not,a,stupid,computer]

Yes

?- argue([you,are],Y).

Y=[i,am,not]

Yes

?-argue([are],Z).

Z=[am,not]

Yes

Notice that bad things can happen if the input is not chosen carefully (for instance, you are too becomes I am not too). Try to cover as many standard English patterns as you can to minimize the cases in which nonsense is returned.

2. Write a function, bubblesort, that takes a list of numbers as input and returns the list sorted in ascending order using a bubblesort.

?- bubblesort([1,3,7,11,2,5,8,6,4],X).

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

Yes.

To help you with this program, here should be a quicksort, done in Prolog:

quicksort([X|Xs],Ys) :-

partition(Xs, X, Littles, Bigs),

quicksort(Littles, Ls),

quicksort(Bigs, Bs),

append(Ls, [X|Bs], Ys).

quicksort([],[]).

partition([X|Xs], Y, [X|Ls], Bs) :- X =< Y, partition(Xs, Y, Ls, Bs).

partition([X|Xs], Y, Ls, [X|Bs]) :- X > Y, partition(Xs, Y, Ls, Bs).

partition([], Y, [], []).