Assignment 8: Sorting Lists in Mercury


Due Thursday, May 17 at 11:59 PM

Goals for This Assignment

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

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:

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:

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:

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.