Problem Set 3: Abstractions, Specifications, and Testing

Due Thursday, March 3, 11:00 pm.

• Tue 3/1: The signature of coeffOf in Problem 1 (polynomials) is the one given in the poly.sig file: int list * poly -> int. This page has been updated accordingly.
• Fri 2/25: Error in Problem 3 (written part) - subproblem 2 contained incorrect code. The mistake has now been corrected: expression TFun(4,g) has been changed to TFun(4,fn y:int => 5).

Instructions: For this problem set you will modify and submit the files poly.sig, poly.sml, multiset.sig, multiset.sml, and testms.sml There is also a written part in this assignment; this must be submitted in a file written.txt. You should submit each of these files separately via CMS. Your code must  compile; programs that do not compile or compile with warnings will receive an automatic zero. 

The focus of this assignment is more about how to design and specify a data abstraction, and how to test your code; there is less emphasis on the algorithmic part.  It is important to document your code with proper specifications. You must think about the appropriate specifications for your data abstractions, and write them carefully.

You will use the compilation manager (CM). The .sml and .sig files that CM manages are listed in sources.cm; do not modify this file. To compile the code with CM, change to the directory containing the files for this assignment, start SML, and run CM.make(). This will compile all of the source files. If you edit your files and want to re-compile, run CM.make() again. Before you submit your files, run CM.make() to make sure that all of your code compile without errors.

There are 3 separate problems to this assignment. The first two problems require writing code and specifications; each involves a different abstraction, and each has several subparts. The last part is the written problem.

Part 1: Multivariate Polynomials (30 pts)

A multivariate polynomial is a polynomial with multiple variables. For instance, P(x,y) = x²y+ 3xy³ - 2y + 1 is a polynomial with two variables. Since the actual names of variables are not relevant, we can use canonical names: x₁ for the first variable, x₂ for the second, and so on. For instance, the polynomial P becomes: P(x₁,x₂) = x₁²x₂ + 3x₁x₂³ - 2x₂ + 1.

A polynomial is a sum of terms, where each term is the product between an non-zero integer coefficient and some non-negative, integer powers of the coefficients. That is, each term is of the form c₁ x₁^p1... x_n^pn. In the example above, x₁²x₂,  3x₁x₂³, -2x₂, and 1 are the four terms of polynomial P.

1) Polynomial Specification (10 pts)

Before beginning work on implementation, you need to complete the specifications. Take a look at poly.sig. The existing specs may be missing, incomplete, or even incorrect. Examine each function and decide what needs to be properly specified. You are not allowed to add new exceptions to the interface. In case of errors, the functions will raise Fail.

To do: submit a correct and complete poly.sig.

2) Polynomial Implementation (20 pts)

For this section you will modify poly.sml. You will implement a structure Poly which matches the signature POLY; You will implement each term c*x₁^p1*...*x_n^pn  using a record that contains the coefficient c and powers p1, ..., pn: {coeff=c, powers=[p1, .., pn]}. Terms with coefficients equal to zero are omitted. A polynomial is a record that holds the number of variables and a sorted list of terms. Polynomial zero has no terms.

type term = {coeff:int, powers:int list}
type poly = {nvars:int, terms:term list}

For instance, the above polynomial P is represented as:

{ nvars=2,
  terms=[{coeff=1, powers=[2,1]}, {coeff=3, powers=[1,3]},  
         {coeff= ~2, powers=[0,1]}, {coeff=1, powers=[0,0]}] }

The list of powers in each term must have length equal to the number of variables in the polynomial. This is also the case for terms where some, or all the powers are zero. For instance, {coeff=~2, powers=[0,1]} or {coeff=1, powers=[0,0]}. The list of terms is sorted by the lexicographic ordering of the powers in each term, in decreasing order. In the example polynomial P, term x₁²x₂ must occur before term 3x₁x₂³ (because power of x₁ decreases), and -2x₂ must occur before term 1 (because power of x₁ is the same, but the power of x₂ decreases). The provided function comparePowers yields the lexicographic ordering of two lists of powers. Finally, no duplicate terms are allowed in a polynomial, i.e., 2xy + 4x + 3xy should be 5xy + 4x.

Work to be done:

1. Document your implementation with a description of the abstraction function.
     
2. Write a repOK function that checks if a polynomial satisfies the representation invariant. If it does, then the same polynomial is returned, otherwise Fail is raised. Document your repOk function with the representation invariant that this function checks.
   
   val repOK : poly -> poly
     
3. Implement the following two functions that construct polynomials. Function zero builds a polynomial with value zero; its argument represents the number of variables. Function singleton builds a polynomial representing a single term. Given a coefficient c and a list [p₁,...,p_n], singleton builds the polynomial c *x₁^p1*... *x_n^pn.
    
   val zero : int -> poly
val singleton : int * int list -> poly
 
4. Write the following functions: numVars is the number of variables of a polynomial, numTerms is the number of terms, and coeffOf is the coefficient of a certain term, specified by its list of powers.
   
   val numVars : poly -> int
val numTerms : poly -> int
val coeffOf : int list * poly -> int
    
5. Write a function that evaluates a polynomial for given values of its variables. The values of variables are provided as a list of integers:
    
   val eval : int list * poly -> int
 
6. Write a function that  performs the addition of polynomials:
    
val plus : poly * poly -> poly
 
7. We have provided an incomplete function that generates a string representation of a polynomial, with variable names starting from 'a' and going up to 'z'. Hence, it requires that the polynomial has at most 26 variables. Improve this function in the following ways. First, do not print variables with zero powers. Second, do not print powers of 1. Third, do not print the coefficient 1, except for the constant term 1. For instance the result for the above polynomial should be: "a^2b + 3ab^3 - 2b + 1"
  
val toString : poly -> string
 

To do: Submit the implementation documentation; the functions repOK, zero, singleton, eval, plus; and the improved toString function in the  poly.sml file.

Part 2: A multiset Data Structure (50 pts)

A multiset (or bag) is a set that may contain more than one occurrence of a particular element. An ordinary set (e.g., {1,2,3}) cannot contain duplicate elements; a multiset (e.g. {1,1,2,2,2,3}) can. Ordering of elements is not important in multisets (as in the case of sets). For instance, the multisets {3,1,2,1} and {2,1,1,3} are the same. However, {3,1,2,1} is not equal to {1,2,3} because they do not contain the same number of 1's. multisets are useful for a variety of purposes; for example, keeping track of histograms during experimental measurements.

In this problem set you will finish defining a multiset data abstraction, implement a module that satisfies this abstraction, and test your module. The main goal for this problem set is to write correct code with clear specifications, and to do a good job of testing this implementation. We will be looking for code that is easy to understand and maintain. We expect your implementation to be reasonably efficient, especially for multisets with many occurrences of the same element; the run-time efficiency will carry some weight but will be a secondary consideration.  

1) Multiset specification (10 pts)

Before you begin implementing, you need to finish the specification. The existing specifications may be incomplete, incorrect, or nonexistent. An exception is declared in the current interface; do not add other exceptions to the interface. If you specify that an operation raises an exception under some condition, it should be this exception, or Fail.

To do: Correct and complete the specifications in the file multiset.sig.

2) Multiset implementation (25 pts)

1. Representation. Your first task is to decide how you will represent multisets. You should consider what functions are likely the most important and select a representation that will result in simple and reasonably efficient code. Add a design justification explaining your reasoning.

   type 'a multiset = your implementation here 
 

2. Along with the representation type, include a comment describing the abstraction function and representation invariant.
    
3. In addition you should implement the function repOK. This function is an identity for any multiset that satisfies the representation invariant; for representations that do not satisfy the invariant, repOK raises Fail.
   
   val repOK : 'a multiset -> 'a multiset
    
4. Implement the empty function, which creates a new, empty multiset. It takes in a comparison function as argument. This will help you if you want to keep your internal representation sorted, because comparisons (e.g. < or >) are not defined for many types and datatypes. 
   
   val empty : ('a * 'a -> order) -> 'a multiset
  
5. Implement functions that allow items to be added and removed from a multiset. delete removes only one element. Remember that this is a functional implementation, so both operations produce a new multiset.
   
   val add : 'a * 'a multiset -> 'a multiset
val delete : 'a * 'a multiset -> 'a multiset

   Examples: add(42,{3,42}) = {3,42,42}, delete(42,{3,42,42}) = {3,42}
    
6. Implement functions that inspect the contents of multisets. The function frequency returns the number of occurrences of a given element in the multiset. isEmpty returns true if there are no elements in the multiset and false otherwise.
   
   val frequency : 'a * 'a multiset -> int
val isEmpty : 'a multiset -> bool
 
Examples: frequency({1,2,3,3},3) = 2, frequency({1,2,3,3},42) = 0, isEmpty({}) = true.
    
7. The union and intersection operations:
   
   val union : 'a multiset * 'a multiset -> 'a multiset
val intersect : 'a multiset * 'a multiset -> 'a multiset

   Examples: union({3,1,2},{4,2})={1,2,2,3,4},  intersect({2,2,3,4},{1,2,2,2,3})={2,2,3}
    
8. Converters to and from a list representation. The fromList operation creates a multiset from a list, and toList creates a list from a multiset. The list should have one element for each element in the multiset.
   
   val fromList : 'a list * ('a * 'a -> order) -> 'a multiset
val toList : 'a multiset -> 'a list

   Examples: fromList([1,2,3,2], Int.compare) = {1,2,2,3}, fromList([], Int.compare) = {}, toList({1,2,2,3}) = [1,2,2,3], toList({}) = []
    
9. Higher-order operations. Function fold applies the argument function to each element to produce an accumulated value. If an element occurs more than once in the input list, the function is applied once for each occurrence of the the element. Function exists returns true if the multiset contains an element for which the argument function evaluates to true.
   
   val fold : ('a * 'b -> 'b) -> 'b -> 'a multiset -> 'b
val exists : ('a -> bool) -> 'a multiset -> bool

To do: select and document a representation for multisets and implement repOk, empty, add, delete, frequency, isEmpty, union, intersect, fromList, toList, map, and exists in the file multiset.sml.

3) Black-box testing (15 pts)

For this problem, you will be creating test cases that test the functionality of multisets. The signature testms.sig looks as follows: 

signature TESTMS = sig

  datatype fn_tests = EmptyMS | AddMS | DeleteMS | FrequencyMS | IsEmptyMS | 
                      UnionMS | IntersectMS | FromListMS | ToListMS |
                      FoldMS | ExistsMS

  datatype test_result = PASS of fn_tests | FAIL of (fn_tests * string)

  type test = unit -> test_result
  type test_generator = unit -> test list

  (* Returns: at least 15 tests *)
  val allTests : test_generator

  (* Effects: Prints out the results from all tests in the list. *)
  val printTests : test_result list -> unit

  (* Performs unit testing on the multiset ADT and returns a list of
   * results from the tests returned by the test_generator. *)
  val runTests : test_generator -> test_result list
end

In testms.sml, add functions of the type unit->test_result. Each function should test a different aspect of a multiset operation. You may find it useful to use toList and fromList in your testing. Each testing function should invoke the tested function and return a test_result that indicates whether the test passed or failed; which function it was testing; and, if the test failed, a message describing the reason.

We have already implemented printTests, so you can view the results of your test cases by executing printTests(runTests allTests).

While you should be testing all of your functions (and note that we will test all of your functions ourselves), you should only submit test cases for isEmpty, add, del, union, and intersect. You should test both basic functionality and corner cases. We will also use your test cases against buggy implementations of multisets, to check that your tests provide good coverage. You may find it useful to define additional identifiers in the structure, and bind them to multiset constants that your test functions use. Remember that you can only interact with multisets through the signature. You cannot assume anything about the underlying implementation; therefore, you should write black-box tests. 

To do: create at least 15 test cases that test isEmpty, add, del, union, and intersect, and implement allTests() in testms.sml that returns all of them. 

Part 3: Written Part (20 pts)

Include your answers to this problem in the file written.txt.

1) Specifications (10 pts)

Consider the following six possible specifications for a function

val f: int * int ->int

1. f(x,y) >= x 
2. f(x,y) = max (x, y).
3. f(x,y) = max (x, y). Requires: x >= 0 and y >= 0
4. f(x,y) >= 0.
5. f(x,y) >= 0. Requires: x >= 0 and y >= 0
6. f(x,y) >= 7. Requires: x >= 7 and y >= 7

Draw a diagram that describes the refinement relation among these specifications. The diagram should contain the names A through F. If specification 1 is a refinement of specification 2, draw a line between the two corresponding letters, and make sure that the name of specification 2 is higher in the diagram than that of Spec 1. For example, the diagram should contain at least the following arc:

     A 
     |
     B 

A line between specification 1 and specification 2 may be omitted if there is some other specification 3 in the diagram such that 2 refines 3, and 3 refines 1. 

2) Program Evaluation using Substitutions (10 pts)

Given the following datatype definition: