Assignment 2: Prototype-based Inheritance and Virtual Dispatch in JavaScript

Goals for This Assignment

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

• Understand a code's specification from a test suite
• Work with the basics of the syntax of JavaScript
• Use prototype-based inheritance to reuse code
• Use virtual dispatch to encode different behaviors

• list.js

// COMP 333 Assignment 2 // // WORKING WITH NODE // You will need node.js (https://nodejs.org/en/) installed and working // to run this.  It's also possible, with some tweaking, to get it working // in a Web browser.  In that case, you probably will want to replace // `console.log` with some output routine. // // To work with node from the command line, you can do the following: // 1.) Go to the directory containing the file (using the cd command) // 2.) Start node.js with the `node` command // 3.) Within the node.js prompt, type `.load list.js` and hit enter. //     This will read your program. // 4.) Run the tests by typing `runTests()` and hitting enter. //     This will execute the `runTests()` function in this file. // // ASSIGNMENT: IMMUTABLE SINGLY-LINKED LIST IMPLEMENTATION // In this assignment, you'll be defining code for an immutable // singly-linked list.  Lists are constructed with two kinds of objects: // - A `Cons` object represents a non-empty list.  It holds a single //   element of the list, along with the rest of the list. // - A `Nil` object represents an empty list, containing no elements, //   and no other elements. // These objects are not wrapped around anything; if you take a list, // you take `Cons` or `Nil` objects. // // This list is intended to be used in an immutable way.  This means // For example, there is an `append` operation, but `append` does // not modify the list it was called on.  Instead, `append` will // return a new list, representing the result of the append.  For // example, if we append `[1, 2]` onto `[3, 4, 5]`, `append` will // return a new list representing `[1, 2, 3, 4, 5]`, and the // original lists `[1, 2]`, and `[3, 4, 5]` will be unchanged. // // Your goal with this assignment is to get all the tests to pass, // without modifying any of the testing code.  There are enough // unit tests that they serve as a (possibly incomplete) specification // of what the code needs to do.  Some of the provided tests pass // out of the box without any changes you need to do on your end. // // HINTS: // 1.) The behaviors for `append`, `contains`, `length`, `filter`, //     and `map` differ depending on whether or not they are called //     on `Cons` or `Nil`. Some tests force you to use virtual //     dispatch to encode this difference. // 2.) Singly-linked lists are a recursive data structure, and //     the methods can most naturally be implemented with recursion. // 3.) My reference solution contains less than 50 lines of code. //     If you start needing dramatically more than 50 lines, talk //     to me to make sure you're on the right track. //  // join // // Parameters: // - A List of elements // - A delimeter to separate them by // Returns a single string, which results from calling // toString on each element, separated by the delimeter. // // For example: // join(new Nil(), ", ")                     // "[]" // join(new Cons(1, new Nil()), ", ")        // [1] // join(new Cons(2, new Cons(3, new Nil())), // [2, 3] // function join(list, delim) {     let retval = "[";     while (list instanceof Cons &&            !(list.tail instanceof Nil)) { XXXXXXXXXXretval += list.head.toString() + delim; XXXXXXXXXXlist = list.tail;     }     if (list instanceof Cons) { XXXXXXXXXXretval += list.head.toString();     }     retval += "]";     return retval; } // join  function List() {}  List.prototype.join = function(delim) {     return join(this, delim); }; List.prototype.toString = function() {     return this.join(", "); };  function Cons(head, tail) {     this.head = head;     this.tail = tail; }  Cons.prototype = new List(); Cons.prototype.isEmpty = function() {     return false; }  function Nil() {}  Nil.prototype = new List(); Nil.prototype.isEmpty = function() {     return true; };   // ---BEGIN CODE FOR TESTING--- // Do not modify!  When I test your code myself, // I won't use this code below, so I won't be working // with any of your modifications! function runTest(test) {     process.stdout.write(test.name + ": ");     try { XXXXXXXXXXtest(); XXXXXXXXXXprocess.stdout.write("pass\n");     } catch (error) { XXXXXXXXXXprocess.stdout.write("FAIL\n"); XXXXXXXXXXconsole.log(error);     } } // runTest  function assertEquals(expected, received) {     if (expected !== received) { XXXXXXXXXXthrow ("\tExpected: " + expected.toString() + "\n" +                "\tReceived: " + received.toString());     } } // assertEquals  function test_nil_join() {     let nil = new Nil();     assertEquals("[]", XXXXXXXXXXnil.join(", ")); } // test_nil_join  function test_nil_toString() {     let nil = new Nil();     assertEquals("[]", XXXXXXXXXXnil.toString()); } // test_nil_toString  function test_nil_instanceof_list() {     let nil = new Nil();     assertEquals(true, XXXXXXXXXXnil instanceof List); } // test_nil_instanceof_list  function test_nil_has_no_head() {     let nil = new Nil();     assertEquals(false, XXXXXXXXXXnil.hasOwnProperty("head")); } // test_nil_has_no_head  function test_nil_has_no_tail() {     let nil = new Nil();     assertEquals(false, XXXXXXXXXXnil.hasOwnProperty("tail")); } // test_nil_has_no_tail  function test_nil_isEmpty() {     let nil = new Nil();     assertEquals(true, XXXXXXXXXXnil.isEmpty()); } // test_nil_isEmpty  function test_nil_length() {     let nil = new Nil();     assertEquals(0, XXXXXXXXXXnil.length()); } // test_nil_length  function test_nil_filter() {     let nil = new Nil();     let f = function(e) { return true; };     assertEquals("[]", nil.filter(f).toString()); } // test_nil_filter  function test_nil_map() {     let nil = new Nil();     let increment = function(e) { return e + 1; };     assertEquals("[]", nil.map(increment).toString()); } // test_nil_map  function test_cons_instanceof_list() {     let list = new Cons(1, new Nil());     assertEquals(true, XXXXXXXXXXlist instanceof List); } // test_cons_instanceof_list  function test_cons_join_single_element() {     let list = new Cons(1, new Nil());     assertEquals("[1]", XXXXXXXXXXlist.join(":")); } // test_cons_join_single_element  function test_cons_join_two_elements() {     let list = new Cons(1, new Cons(2, new Nil()));     assertEquals("[1:2]", XXXXXXXXXXlist.join(":")); } // test_cons_join_two_elements  function test_cons_join_three_elements() {     let list = new Cons(1, new Cons(2, new Cons(3, new Nil())));     assertEquals("[1:2:3]", XXXXXXXXXXlist.join(":")); } // test_cons_join_three_elements  function test_cons_toString_single_element() {     let list = new Cons(1, new Nil());     assertEquals("[1]", XXXXXXXXXXlist.toString()); } // test_cons_toString_single_element  function test_cons_toString_two_elements() {     let list = new Cons(1, new Cons(2, new Nil()));     assertEquals("[1, 2]", XXXXXXXXXXlist.toString()); } // test_cons_toString_two_elements  function test_cons_toString_three_elements() {     let list = new Cons(1, new Cons(2, new Cons(3, new Nil())));     assertEquals("[1, 2, 3]", XXXXXXXXXXlist.toString()); } // test_cons_toString_three_elements  function test_cons_head() {     let list = new Cons(1, new Nil());     assertEquals(1, XXXXXXXXXXlist.head); } // test_cons_head  function test_cons_empty_tail() {     let list = new Cons(1, new Nil());     assertEquals("[]", XXXXXXXXXXlist.tail.toString()); } // test_cons_empty_tail  function test_cons_nonempty_tail() {     let list = new Cons(1, new Cons(2, new Nil()));     assertEquals("[2]", XXXXXXXXXXlist.tail.toString()); } // test_cons_nonempty_tail  function test_cons_isEmpty() {     let list = new Cons(1, new Nil());     assertEquals(false, XXXXXXXXXXlist.isEmpty()); } // test_cons_isEmpty  function test_cons_length_1() {     let list = new Cons("a", new Nil());     assertEquals(1, XXXXXXXXXXlist.length()); } // test_cons_length_1  function test_cons_length_2() {     let list = new Cons("a", new Cons("b", new Nil()));     assertEquals(2, XXXXXXXXXXlist.length()); } // test_cons_length_2  function test_cons_filter_has_element() {     let list = new Cons(1, new Nil());     let isOdd = function(e) { return e % 2 == 1; };     assertEquals("[1]", XXXXXXXXXXlist.filter(isOdd).toString()); } // test_cons_filter_has_element  function test_cons_filter_has_no_element() {     let list = new Cons(2, new Nil());     let isOdd = function(e) { return e % 2 == 1; };     assertEquals("[]", XXXXXXXXXXlist.filter(isOdd).toString()); } // test_cons_filter_has_no_element  function test_cons_filter_multi_1() {     let list = new Cons(2, new Cons(4, new Nil()));     let isOdd = function(e) { return e % 2 == 1; };     assertEquals("[]", XXXXXXXXXXlist.filter(isOdd).toString()); } // test_cons_filter_multi_1  function test_cons_filter_multi_2() {     let list = new Cons(2, new Cons(5, new Nil()));     let isOdd = function(e) { return e % 2 == 1; };     assertEquals("[5]", XXXXXXXXXXlist.filter(isOdd).toString()); } // test_cons_filter_multi_2  function test_cons_filter_multi_3() {     let list = new Cons(3, new Cons(4, new Nil()));     let isOdd = function(e) { return e % 2 == 1; };     assertEquals("[3]", XXXXXXXXXXlist.filter(isOdd).toString()); } // test_cons_filter_multi_3  function test_cons_filter_multi_4() {     let list = new Cons(3, new Cons(5, new Nil()));     let isOdd = function(e) { return e % 2 == 1; };     assertEquals("[3, 5]", XXXXXXXXXXlist.filter(isOdd).toString()); } // test_cons_filter_multi_4  function test_cons_filter_multi_5() {     let list = new Cons(1, new Cons(5, new Cons(2, new Cons(6, new Cons(3, new Cons(7, new Cons(4, new Nil())))))));     let f = function(e) { return e 

Step-by-Step Instructions

Step 1: Get JavaScript Working

For this assignment, you'll be using JavaScript. It's possible to make this assignment work in any Web browser, though it may require some modification to make the output reasonable. It's recommended to useNode.jsas your implementation, which can be installed on all major platforms. Node.js can also be run directly in the browserhere, if you prefer.

Step 2: Implement a Singly-Linked List

A significant of code has been provided inlist.js, including a test suite of significant size. Your goal with this assignment is to get all the tests passing, without modifying any of the testing code. The comments in the file provide further details. Note that the tests themselves are a rich source of information, both in terms of defining what you need to implement (i.e., they serve as a specification), and how JavaScript works.

you need to send me the following files:

• list.js