Assignment 8: Sorting Lists in Mercury

Due Monday, December 16 at 11:59 PM

Goals for This Assignment

By the time you have completed this work, you should be able to:

Write procedures with appropriate mode annotations in Mercury
Handle complex operations on lists in Mercury

Provided files:

Overview

In this assignment, you will implement insertion sort, merge sort, and quicksort in Mercury. The implementations of these algorithms may not look very similar to their imperative counterparts, though the algorithms are the same. This assignment overall shows off some good parts of Mercury (e.g., this can be fast, types are very helpful, the libraries can be useful, and the test suite is easy to define), as well as some bad (e.g., mode annotations can be annoying, the compiler sometimes isn't smart enough to understand that a computation is deterministic, imperative algorithms don't look nice in non-imperative languages).

Step-by-Step Instructions

Step 1: Get your Mercury Environment Setup

You'll be using Mercury for this assignment. Binary packages are available for Windows (requires Visual Studio 2013), and older versions of Debian. Mercury can also be installed from scratch, though this process takes 4-6 hours(!) of compiling.

For these reasons, a compiled version of Mercury has been provided on k200.ecs.csun.edu, specifically in /home/users5/kdewey/mercury_public. You can easily access the relevant binaries by adding the following line to your ~/.profile file on k200:

PATH=$PATH:/home/users5/kdewey/mercury_public/bin

After adding the above line, if you log out and log back into k200, you should have immediate access to the binaries. You can test this with the following command:

which mmc

This command asks where the mmc executable is located, which is the compiler we'll be using for Mercury. You should see output like the following:

/home/users5/kdewey/mercury_public/bin/mmc

If you instead see output that says something like:

/usr/bin/which: no mmc in ...

...then this means that there is something wrong with your .profile file.

No matter which path you take, you will need the mmc executable available.

Step 2: Download and Compile Required Files

Once mmc is available, download sorting.m and sorting_tests.m. Before doing anything else, try compiling them with the following command:

mmc --make sorting_tests

You should see output like the following:

Making Mercury/int3s/sorting.int3
Making Mercury/ints/sorting.int
Making Mercury/cs/sorting.c
Making Mercury/os/sorting.o
Making sorting_tests

This code should compile as-is. If you see any errors or other problems, then there is probably something wrong with your Mercury setup.

The result of the compilation includes a test suite, which can be immediately run. You can run this test suite with the following command:

./sorting_tests

You should get fairly lengthy output detailing test failures, starting with the following:

Insertion Sort (insertion_sort): 20 FAILURES
Test input: [0, 1, 0]
Expected: [0, 0, 1]
Received: [0, 1, 0]
------
Test input: [0, 2, 0]
Expected: [0, 0, 2]
Received: [0, 2, 0]
------

If you see something different from the above, then something is wrong with your Mercury setup.

Step 3: Familiarize Yourself with the Code

Read through the code in sorting.m and sorting_tests.m. You should be able to understand what most of this code does, except perhaps some of the trickier bits in sorting_tests.m. Some details follow about how this code is structured:

This is structured as two modules: sorting (in sorting.m) and sorting_tests (in sorting_tests.m).
sorting exports three procedures, each corresponding to a different sorting algorithm implementation:
1. insertion_sort
2. merge_sort
3. quick_sort
The above sorting procedures simply return the input list as if it were sorted, without doing any real work. This was done so that this code will compile out of the box, though it is obviously incorrect.
sorting_tests contains the main procedure. main will run the test suite for each of the three sorting procedures.
The test suite itself is automatically generated, using the same sort of approach previously used in the class for automatically generating test inputs. Specifically, this will generate all lists of length 0 - 3, with elements in the range 0 - 2.

Step 4: Implement Sorting Routines

Implement the sorting routines in sorting.m. The comments in that file provide additional details.

There are several things you should keep in mind for your implementation, along with some potential hints:

You may use as many helper procedures as you wish, and it's expected that you'll need to define a variety of helpers.
You are permitted to use all of the helpers in Mercury's list library, EXCEPT for the *sort* routines.
You may edit the code in sorting_tests.m, though this code will not be submitted. As such, your code should work correctly no matter what sorting_tests.m contains.
The provided pred and mode annotations for the sorting routines (in the interface section) are correct; do not change these. Any changes will break how the testing is performed.
It's recommended to try to implement one sorting routine at a time, and then perform testing by recompiling and running ./sorting_tests.
Once all the tests are passing for all the sorting routines, you should try increasing the number of tests performed to see if things still work. This can be easily done by changing the bound passed to failing_tests in sorting_tests.m. Specifically, this is the first parameter to failing_tests on line 73 of sorting_tests.m. The current bound of 3 yields dozens of tests, whereas a bound of 6 yields over 1,000 tests.

Step 5: Turn in Your Solution Using Canvas

Log into Canvas, and go to the COMP 410 class. Click “Assignments” on the left pane, then click “Assignment 8”. From here, you need to upload the following files:

sorting.m

In addition, if you collaborated with anyone else, be sure to download collaborators.txt and write the names of the people you collaborated with in the file, one per line. Please submit this file along with the other file.

You can turn in the assignment multiple times, but only the last version you submitted will be graded.