It is now time for some very intensive programming. (If you prefer the assignments where you just solve problems at the end of the chapters in the textbook, you'll have to wait for Assignment #4.) This assignment is due Thursday, October 18 for undergraduates, and Wednesday, October 22 for graduates.

Readings: Read as many on-line tutorials or book chapters on Ruby and JavaScript as is reasonable without seriously impacting your personal life. Also read a bit about C if you are rusty. If you have [Thomas], read Chapters 1-10, and 12.

Version Control (Undergraduates only): Make sure you've set up a version control repository. You can use the CVS repository that comes with your lab account, or a personal repository (CVS or SVN) hosted elsewhere. You should add at least the following files to your repository (you may add more):

  /homework/cmsi386/src/main/ruby/listutil.rb
  /homework/cmsi386/src/test/ruby/listutiltest.rb
  /homework/cmsi386/src/main/js/listutil.js
  /homework/cmsi386/src/test/js/listutiltest.html
  /homework/cmsi386/src/main/c/listutil.h
  /homework/cmsi386/src/main/c/listutil.c
  /homework/cmsi386/src/test/c/listutiltest.c

For this project, you will be writing three versions of the same basic library: one in C, one in Ruby, and one in JavaScript. You will also write unit test suites for each library. This is a good assignment because trying to do the exact same thing in multiple languages helps to highlight similarities and differences between languages. You will also uncover cases where it really isn't practical, or doesn't even make sense, to do exactly the same thing in different languages.

The library will consist of six utility functions that:

1. Compute the right rotation of a list, i.e., the list that would result from repeatedly removing the last element and adding it to the front, a given number of times. Treat a request to rotate a negative number of times as being equivalent to rotating zero times.
2. Reduce a binary operation over the items in a list from right to left, throwing an exception if the list is initially empty (assuming, of course, that your language even has the concept of throwing exceptions). Note that sometimes this operation is called "fold" or "inject".
3. Return a list containing the squares of the numbers in the input list, sorted in descending order.
4. Return the number of items in a list that, when treated as as second argument to a given binary predicate P, satisfy P(x, y), for a given x. In languages that let you create functions dynamically, P should be curried.
5. (Recursively) flatten a list.
6. Compute the frequency of each item in a list.

None of these operations should modify any of their input arguments.

In this assignment, we will be investigating the best ways to carry out these tasks in three different languages: Ruby, JavaScript, and C. (In the next homework assignment we will carry out these tasks in still two more languages: Java and Standard ML.)

Ruby

Your Ruby library should be in the form of a Ruby module. I've started it for you:

module ListUtil
  def rotate(k, a) ...
  def right_reduce(p, a) ...
  def descending_numeric_squares(a) ...
  def partial_filter(p, x, a) ...
  def flatten(a) ...
  def histogram(a) ...
end

The intent of each operation is best expressed by illustrating some ready-to-run unit tests (remember that Ruby has a unit test framework in its core library). Please note that a proper test suite will have many, many more assertions than are shown here.

    assert_equal rotate(4, [1,2,3,4,5,6]), [3,4,5,6,1,2]
    assert_equal rotate(0, ["A", "b"]), ["A", "b"]
    assert_equal rotate(-7, ["A", "b"]), ["A", "b"]

    max = Proc.new {|x, y| x > y ? x : y}
    g = Proc.new {|x, y| 2 * x - y}
    assert_equal right_reduce(max, [5, 7, 1]), 7
    assert_equal right_reduce(g, [5, 7, 1]), -3
    assert_raise right_reduce(g, []);

    assert_equal
        descending_numeric_squares([-1, 2.999, 8, "dog"]),
        [64, 6.994001, 1];

    less_than = Proc.new {|x| Proc.new {|y| y < x}}
    assert_equal partial_filter(less_than, 7, [5,8,9,1,10,7,9,1]), 3

    assert_equal flatten([[3,5],[],[3,[[1]],1]]), [3,5,3,1,1]

    assert_equal histogram([2,6,5,5,2,3,5]), {2=>2,6=>1,5=>3,3=>1}

JavaScript

Your JavaScript functions should be gathered up into a single object, with this format:

var list_util = {
    rotate: function(k, a) {...},
    right_reduce: function(f, a) {...}
    descending_numeric_squares: function (a) {...},
    partial_filter: function(p, x, a) {...},
    flatten: function(a) {...},
    histogram: function(a) {...}
}

One difference between JavaScript and Ruby is that you can not use JavaScript objects for the results of your histogram. So you will need to return the histogram as an array of arrays. Sorry. (Another difference is that JavaScript has no built-in flatten method!)

You can use JSUnit for testing, or code up your own framwork with functions such as assert and assert_arrays_equal. Your tests will look something like this:

    assert_arrays_equal(
        list_util.rotate(4, [1,2,3,4,5,6]), [3,4,5,6,1,2]);
    assert_arrays_equal(
        list_util.rotate(0, ["A", "b"]), ["A", "b"]);
    assert_arrays_equal(
        list_util.rotate(-7, ["A", "b"]), ["A", "b"]);

    var max = function(x, y) {return x > y ? x : y;}
    var g = function(x, y) {return 2 * x - y;}
    assert(list_util.right_reduce(max, [5, 7, 1]) == 7);
    assert(list_util.right_reduce(g, [5, 7, 1]) == -3);

    assert_arrays_equal(
        list_util.descending_numeric_squares([-1, 8, "dog"]),
        [64, 1]);

    var less_than = function(x) {return function(y) {return y < x}}
    assert(list_util.partial_filter(less_than, 7, [5,8,9,1,10,7,9,1]) == 3)

    assert_arrays_equal(
        list_util.flatten([[3,5],[],[3,1,1]]),
        [3,5,3,1,1]);

    assert_objects_equal(
        list_util.histogram([2,6,5,5,2,3,5]),
        [[2,2], [6,1], [5,3], [3,1]]);

C

C isn't a language particularly well suited to writing these six functions: there's no built-in list type and the static typing is annoying, requiring us to use macros or void* expressions to get around. We can give up and make our library work only on integers. Since this is only a one-semester class, let's do the giving up thing.

The C header file should look like this (note I am using C99):

#include <stdlib.h>
#include <stdbool.h>

typedef bool binaryPredicate(int x, int y);
typedef int binaryFunction(int x, int y);
typedef struct {int key; int value;} pair;
typedef struct node {int data; struct node* next} *list;

list rotate(int n, list a);
int rightReduce(binaryFunction f, list a);
list descendingNumericSquares(list a);
int partialFilter(binaryPredicate p, int x, list a);
list flatten(int** a, int arraySize);
pair* histogram(list a);

Again, here are a few unit test expressions to help you understand how each function is supposed to work.

    list x = listOf("1 2 3 4 5 6 7");
    assert(equalLists(x, rotate(-6, x));
    assert(equalLists(x, rotate(0, x));
    assert(equalLists(x, rotate(7, x));
    assert(equalLists(listOf("5 6 7 1 2 3 4"), rotate(3, x));
    assert(equalLists(listOf("6 7 1 2 3 4 5"), rotate(777779, x));

    int twoXplusY(x, y) {return 2 * x + y;}
    x = listOf("4 5 6 2");
    assert(equalLists(rightReduce(twoXplusY, x), 32));

    x = listOf("4 5 6 2");
    assert(equalLists(descendingNumericSquares(x), listOf("36 25 16 4")));

    x = listOf("4 5 6 2");
    bool lessThan(x, y) {return y < x;}
    assertEquals(partialFilter(lessThan, 6, x), 3);

    /* TODO asserts for flatten */

    x = listOf("20 20 1 6 5 1 1 1 1 1 1");
    /* todo assert histogram */

Note these tests assume some list "helper" methods, such as

list newNode(int data, list next) {
    list result = malloc(sizeof(struct node));
    result->data = data;
    result->next = next;
    return result;
}

/*
 * Returns a linked list made from a string by taking all clumps of digits.
 * For example,
 *
 *   "4 5  % 67675;;r34" ==> [4,5,67675,34]
 */
list listOf(char* s) {
    list result = NULL;
    list last = NULL;
    int value = 0;
    bool readingNumber = false;
    for (char* p = s; true; p++) {
        if ('0' <= *p && *p <= '9') {
            /* Continue accumulating the number */
            value = (value * 10) + (*p - '0');
            readingNumber = true;
        } else {
            if (readingNumber) {
                /* Done reading the number, add to end of  list */
                if (result == NULL) last = result = newNode(value, NULL);
                else last = last->next = newNode(value, NULL);
            }
            readingNumber = false;
            value = 0;
        }
        /* Finished off the string */
        if (*p == 0) return result;
    }
}

bool equals(list a, list b) {
    if (a == NULL) return b == NULL;
    if (b == NULL) return false;
    return a->data == b->data && equals(a->next, b->next);
}