Reference no: EM132901975

COMP 3722 Theory and Practice of Computation - Flinders University

Task  - Declarative Paradigms Background

Our versions of Scheme and Prolog are interpreters (of the code or an intermediate represetntation). You can type definitions straight into the interpreter, but the easiest way to write code is to type it into a file, then (re)load the file into the interpreter.

Here's how to load files in MIT Scheme on a unix system - the system you download may including an editing environment, but this can be bypassed by removing the edit flat in the shortcut:
$ scheme # start the interpreter
=> (load "source.scm") # load source file (sort '(1 3 2 4)) # test it out
... # edit the source file
=> (load "source.scm") # reload the file
=> ^D or ^Z # exit scheme, cf. (exit)

And here's how in (SICStus) Prolog:
$ sicstus % start the interpreter
?- sort([1,3,2,4],X). % use built in sort (ascending) X = [1,2,3,4]?
yes
?- [source.pr]. % load the file "source.pl"
?- ['source.pr']. % load the file "source.pr"
% note the dot at end of line
?- ^D or ^Z % exit prolog, cf. halt.

If an associated editing environment is not available or not familiar or not fast enough, it is recommended that you have an editing window open alongside the shell window running the code. You can then reedit and save in one window, reload and run in the other window.
Note that .pl is a commonly used file extension for both Prolog and Perl and is the default ending assumed by Sicstus. If you just say [source], it will try it with the .pl automatically. In some variants of Prolog you need to use [- source] to force it to reload the program rather than load a second copy (which becomes confusing).

Note that source here represents a filename that fits the definition of an atom (that is it is starts with a lower case letter and consists of only letters, digits or underscore).

Often it will be the name of the primary predicate defined in that file (although there may be help predicates, and it will often need to be run with arguments).

You will find useful resources under Tutorial Resources - note instructions there re loading the relevant SICStus or SWIpl PROLOG2 compatibility library.

Benchmarking report

You should benchmark all these for comparison with the sorting done in other languages in the other assignments. You can stop your benchmarks once runtimes exceed half an hour. Do not expect these languages to be as efficient as Java and C. You could benchmark by doubling the size of the list at each step - or even just incrementing it if doubling breaks it too soon. For comparison also benchmark the builtin sorts - which are probably written in C. Try to show them in the same graphs and scales as your previous Java examples/built-ins - but if an algorithm is not (expected/average/amortized) O(NlogN) you may need to have an additional graph with a more appropriate scale.

1. Permutation sort in Prolog
Write a predicate ordered/1 that checks if a list is in order and use that to find ordered permutations and hence to define a permutation sorting predicate psort/2.

?- ordered([]). yes
?- ordered([1,2,3]). yes
?- ordered([3,2,1]). no
?- psort([3,2,1],S). S = [1,2,3]

2. quicksort in Prolog
Write a predicate partition/4 that partitions its second argument, a List of integers, on the basis of its first argument, a Pivot integer, so that the third argument contains only elements less than Pivot and the fourth argument contains only elements greater than Pivot. Elements equal to the pivot may be eliminated. Use this to write quicksort/2 that partitions on the first element, if any, recursively sorts the two partitions, and appends them to give a sorted result. Warning the versions in textbooks and on the web are not very good, and must be acknowledged if referenced.

You may use append/3 as defined in lectures, but it is more efficient (and worth 0.5 marks) to define qsortap/3 that takes a third argument which is a list to append to the sorted list. This saves an additional pass through the first list to do the append, and also makes it much more efficient as it becomes semi tail recursive (one of the two recursive calls can be laast call optimized). In this case the original call to quicksort/2 simply results in a call qsortap/3 to do the actual work. If you do a version with integrated append you should also benchmark the version with append to see what the efficiency gain was.

The library predicate statistics prints comprehensive statistics about time, memory usage, garbage collection etc. to standard output, whilst statistics(runtime,[Time,Inc]) and statistics(walltime,[Time,Inc]). return info about the time since the start of Prolog and since the last time it was called. Also use_module(library(random)) provides real and integer random numbers as well as a sequence of K unique integers in the range 1 to N>=K.

There is no need to implement a version that sorts the smaller partition first, but include a note about how you could do this efficiently without an explicit and costly call to length/2 or equivalent.

?- partition(4,[2,5,7,5,4,3,2,5,8], L, G). L = [2,3,2]
G = [5,7,5,5,8]
?- quicksort([2,5,7,5,4,3,2,5,8],X). X = [2,3,4,5,7,8]

3. quicksort in Scheme

Now implement partition (which should return a list of two lists and may discard pivot values) and quicksort in Scheme. There is no need to do the smaller first optimization, but do try to avoid append (worth 0.5 marks again). For benchmarking (runtime) and (random 1000000) might be useful. One potentially important decision is how to deal with a problem that involves two returned results (e.g. partitions) that need to be processed by one calling function. You may want to use helper functions to do partition - e.g. separate scans looking for bigger and smaller elements, or a function partapp that does a partition and append and uses two additional arguments to accumulate the lists. quicksort may use bigger and smaller directly if you implement them. You must not try to use global variables or set/setq - you only need the functions discussed in lectures.

=> (partition '5 '(1 3 5 7 9 8 6 4 2))
((1 3 4 2) (5 7 9 8 6))
=> (quicksort '(5 1 3 5 7 9 8 6 4 2))
(1 2 3 4 5 6 7 8 9)

Task - mergesort comparison

For the purposes of questions 1 and 2 of this task, zipping two lists produces an ordered list that contains all of the elements of both lists, but with no duplicates - viz. it merges them. Here are some samples:
(1 2 3) (4 5 6) -> (1 2 3 4 5 6)
(1 2 3) (3 4 5) -> (1 2 3 4 5)
(1 2 3) (1 2 3) -> (1 2 3)
(1 3 5) (2 4 6) -> (1 2 3 4 5 6)

In writing your code, you may assume that all lists are already in sorted order and contain no duplicates. The point of this assignment is to learn the spirit and advantages of logic programming and functional programming - you don't just write the same code the same way, but write it in the way the paradigm lends to. In the case of the functional version of MergeSort there are many different ways of doing it in a functional spirit. One potentially important decision is how to deal with a problem that involves two returned results (sublists) that need to be processed by one calling function. Note that it is not necessary to worry about the efficiency of making one pass instead of two - any savings are probably lost by the cost of dealing with the more complex data structure that the one pass version necessitates. If you do return a complex structure it is possible to use let to hold the result while you unpack it, or alternatively to define a separate function to do the unpacking and further processing. So again, feel free to use subpredicates/subfunctions to extract just what you need.

1. List zipping and mergesort in Scheme

Write a Scheme function, zip that takes two list arguments and returns the list that results from zipping them together, and use it to implement mergesort. You must not try to use global variables, set/setq - you only need the functions discussed in lectures. The function should behave as follows:
=> (zip '(1 2) '(3 4))
(1 2 3 4)
=> (zip '(1 2) '(2 3))
(1 2 3)
=> (zip '(1 2) '(1 2))
(1 2)
=> (zip '(1 3) '(2 4))
(1 2 3 4)
=> (zip '(1 4) '(2 3))
(1 2 3 4)

2. List zipping and mergesort in Prolog
Define a Prolog relation on three sorted lists, zip/3, where the third argument is the list that is a zipping of the first and second, and use it to implement mergesort. The relation should allow queries of the following form.

Note that the last two examples relate to unzipping one sorted lists into two sorted subsets, and when the first two arguments are indeterminate this is non-deterministic so should backtrack over all possible pairs of lists that are consistent. Half a mark will be allocated for a reversible form of the predicate, but you only need to benchmark the actual sorting.

?- zip([1, 2], [3, 4], [1,
yes
?- zip([1, 2], [3, 4], [1, 2,

2, 3, 4]).

3]).
no
?- zip([1,2],
X = [1,2,3,4]
?- zip([1,2], [3,4],

[2,3], X).

X).
X = [1,2,3]
?- zip([1,3],
[2,4],
X).
X = [1,2,3,4]
?- zip([1,4],
[2,3],
X).
X = [1,2,3,4]
?- zip(X, [1,2], [1,2,3]). # lists that zip with [1,2] to give [1,2,3]
X = [1,2,3] ? ;
X = [1,3] ? ;
X = [2,3] ? ;
X = [3] ? ;
no
?- zip(X, Y, [1,2]). # pairs of lists that zip to give [1,2] X = [], Y = [1,2] ? ;
X = [1,2], Y = [] ? ;
X = [1], Y = [1,2] ? ;
X = [1,2], Y = [1] ? ;
X = [1,2[, Y = [1,2] ? ;
X = [1], Y = [2] ? ;
X = [1,2], Y = [2] ? ;
X = [2], Y = [1] ? ;
X = [2], Y = [1,2] ? ;
no

3. Insertion or selection sort in Prolog
For comparison, it is useful to implement insertion sort and/or selection sort: Insertion sort takes each element in turn and inserts it into the correct position in the sorted list being built up. Selection sort removes the minimum or maximum of a list and adds it to the beginning or end of the sorted list being built up.

Implement one or the other - you do not need to implement both. Ensure that each pass through the data (e.g. for insertion into a list or finding the minimum of a list) is just that - one single pass. Avoid rescanning the data (e.g. to delete the minmum or to add to the end of the list).

These take expected quadratic time and will not be able to be benchmarked on long lists.

You may want to do your sorting algorithms in both powers of two as well as powers of ten to facilitate different graphs and comparing with other declarative algorithms versus the Java implementations of the previous assignments - you should provide graphs allowing comparison of all sorts developed.

Attachment:- Theory and Practice of Computation.rar