Recitation 8
Data Abstraction Example: Polynomials

Suppose we want to develop a data abstraction for univariate polynomials; that is, expressions of the form a+bx+cx2+dx3+...+ zxn. We'd like to be able to create polynomials and to add, subtract, and multiply them. The name of the variable is not important, so we only need to track of is the coefficients corresponding to each exponent. 

For many data abstractions, the capabilities offered by signatures (or other interface specification techniques in other languages) still do not provide enough expressive power.  For instance, for univariate polynomials, we would like to ensure not only that the degree of an exponent is an integer but also that it is non-negative.  We note such additional specifications as being required in the comments.

Interface

The following signature POLYNOMIAL is an interface to a data abstraction for polynomials:

signature POLYNOMIAL =
  sig

    (* A poly is a univariate polynomial with integer
     * coefficients. For example, 2 + 3x + x^3. *)
    type poly

    (* zero is the polynomial 0 *)
    val zero: poly

    (* singleton(c,d) is the polynomial c*x^d.
     * Requires: d >= 0 *)
    val singleton: int*int -> poly

    (* degree(p) is the degree of the polynomial:
     * the largest exponent of the polynomial with
     * a nonzero coefficient *)
    val degree: poly -> int

    (* evaluate(p,x) is p evaluated at x *)
    val evaluate: poly*int -> int

    (* coeff(p,n) is the coefficient c of the term
     * of form c*x^n, or zero if there is no such term.
     * Requires: d >= 0 *)
    val coeff: poly*int -> int

    (* plus, minus, times are +, -, * on polynomials,
     * respectively *)
    val plus: poly * poly -> poly
    val minus: poly * poly -> poly
    val times: poly * poly -> poly

    (* toString converts a poly to a nicely readable string *)
    val toString: poly -> string

  end

The type poly is an abstract type that may be implemented in different ways by different structures that implement this signature. Again by looking at the signature, we can tell what poly does but not what it is. The signature prevents clients from depending on the module in inappropriate ways, by hiding all the things they're not supposed to know about. The signature also acts like a defensive perimeter that prevents clients from constructing values of a declared types except through the operations provided. Thus, the signature is a contract between the implementer of the module and the clients of the module. As long as both sides abide by the contract -- the implementer by providing all of the operations that the signature defines, and the client, by only using the module in accordance with the signature -- the two sides can work without stepping on one another's toes. The client doesn't need to see or think about the code that the implementer is writing, and the implementer doesn't have to think about the details of how clients are using the code.

This signature provides not only the types of the operations but also their specifications. As discussed earlier, the signature is the right place to put these specifications. There are two views of an data abstraction: the abstract view, which is the view from the standpoint of the user of the data abstraction, and the concrete view, which is the view of the implementer. The abstract view is presented by the module interface; the concrete view by the module implementation. A well-designed data abstraction can be used entirely from the abstract view, without knowing the concrete type that represents the abstract values, or the actual algorithm being used to implement the operations. Thus, the specifications that appear in the signature should always be from the abstract view, not the concrete view, which would violate the abstraction barrier.

The singleton and coeff operations are both partial functions because they are not defined for negative exponents, and hence have "requires" in the comments. In the specifications for plus, minus, times, we rely on the reader's understanding of polynomials to avoid writing tedious specifications of the form, "plus(p,q) is p+q", etc. It is acceptable and even a good idea to rely on the reader's likely knowledge to avoid long specifications. However, as with all writing tasks, this requires a judgment about your likely reader. If that reader is yourself (perhaps at some time in the future), it is relatively easy to assess what will be comprehensible! But when writing code for a larger organization more care must be taken.

The right way to develop modules is to figure out the signature (interface) first, then write the structure (module implementation) to match the interface. This approach has two big advantages. First, a lot of design problems become evident when the signature is being written. It's much lower cost in terms of development time to get the design right before trying to implement the module. Another advantage is that code can be written using the interface even before the implementation is complete; the module client and module implementer can work in parallel, speeding up development. And because the interface is known by both parties, it is more likely that when they finish their work, the complete program will work as intended.

Implementation

Choosing the right representation for a data abstraction is the first step in any implementation. The following is a simple representation of polynomials:

type poly = int list

The first item in the list will be the coefficient a for x, the second one b for x2, and so on. The number of items in the list will tell us the degree of the polynomial. In addition, we will need to make sure that the list never ends in a trailing sequence of zeros, because that would might mislead us about the degree of the polynomial. The empty list will represent the polynomial 0.

Note that this is just one of many possible ways to represent a polynomial, all of which can meet the signature but which can lead to very different implementations (structures).

Now we can start to implement the operations specified in the signature POLYNOMIAL. For example, the function degree:

fun degree(p: poly):int =  

   case p of 

      [] => 0

      | _ => length(p) - 1

How about polynomial addition?

fun plus(p: poly, q: poly): poly =
  case (p, q) of
      (nil, q) => q
    | (p, nil) => p
    | (a::p2, b::q2) =>
        (a+b)::plus(p2,q2)

Actually this doesn't quite work. Why? Because the result might have trailing zeros if the two polynomials cancel each other out, causing the degree function to return the wrong result.

- plus([1,2], [1,~2]);
val it = [2,0]: poly
- degree(it)
val it = 1: int

We can avoid this by checking as follows:

fun plus(p: poly, q: poly): poly =
  case (p,q) of
      (nil,q) => q
    | (p, nil) => p
    | (a::p2, b::q2) =>
        case (a+b)::plus(p2,q2) of
            [0] => []
          | r => r
- plus([1,2], [1,~2]);
val it = [2]: poly

Here is more of the implementation:

structure Polynomial :> POLYNOMIAL =
  struct
    (* Univariate polynomials represented using a list of coefficients.
     * Degree of each term is based on its position in the list. *)
    type poly = int list
    val zero: poly = []

    (* A singleton cx^d is a list of length d, where the first d-1
     * elements are 0 and the last element is c *)
    fun singleton(coeff: int, degree: int):poly =
      case (coeff, degree) of
        (0, _) => zero
      | (c, 0) => [c]
      | (c, d) => if (d<0)
                    then raise Fail "negative degree"
                    else 0::singleton(c, d-1)

    fun degree(p:poly):int =       
      case p of
        [] => 0
      | _ => length(p)-1

    fun coeff(p: poly, n: int):int =
        case p of
          nil => 0
        | h::t => if n = 0 then h else coeff(t, n-1)

    (* plus and minus both operate term by term, so this function
     * abstracts out the common pattern *)
    fun termapply (f:int*int->int,p:poly,q:poly):poly =
      case (p,q) of
        (nil,q) => q
      | (p, nil) => p
      | (a::p2, b::q2) =>
        case f(a,b)::termapply(f,p2,q2) of
          [0] => []
        | r => r

    fun plus(p:poly, q:poly):poly =
      termapply(op+, p, q)

    fun minus(p:poly, q:poly):poly =
      termapply(op-, p, q)

    fun times(p:poly, q:poly):poly =
      raise Fail "Not implemented"

    fun evaluate(p:poly, x:int): int =
      case p of
        nil => 0
      | a::q => a + x*evaluate(q, x)

    fun toString (p: poly): string =
      let fun pp_ndegree(deg: int, p: poly): string =
        case p of
          nil => ""
        | h::t =>
          if h = 0 then 
            pp_ndegree(deg+1,t)
          else 
            Int.toString(h) ^
            ( if deg > 0 then 
                "x" ^ (if deg > 1 then "^"^Int.toString(deg) else "")
              else 
                "" ) ^
                ( case t of
                    nil => ""
                  | _ => " + " ^ pp_ndegree(deg+1, t))
        in 
          case pp_ndegree(0, p) of
            "" => "0"
          | s => s
        end 

  end

We can provide this module to other programmers and they can then create polynomials using Polynomial.zero and Polynomial.singleton and manipulate them with Polynomial.degree and Polynomial.plus. they don't have to know that polynomials are really lists of integers (and with only the signature they won't know).

The abstraction barrier

The abstraction barrier prevents the clients of the Polynomial module from using their knowledge of what poly is. In fact, the SML interpreter will not even print out values of a type like poly. Without the signature, we can see what poly's really are:

- Polynomial.zero;
val it = []: Polynomial.poly

Once the module is protected by its signature, values of the type poly are printed only as a dash:

- Polynomial.zero;
val it = - : Polynomial.poly

Without the abstraction barrier, users might get into trouble. For example, a client using the Polynomial structure might see that  polynomials are really lists and write code like this:

let z: Polynomial.poly = [2,3,4] in ... end

It looks convenient; what's wrong with it? Two things: this code depends on the actual type used to represent polynomials. An implementer cannot change between int list and another representation of polynomials without breaking this code; therefore we've lost loose coupling. Second, there is nothing that prevents the client from constructing lists that violate our no-trailing-zeros condition. The operations defined on polynomials will not work properly if polynomials are constructed out of such lists. In general, a misbehaving client could cause the program to give wrong answers or even crash with an exception in a module that another programmer wrote! This is bad because it makes it hard to assign blame for bugs.

The abstraction barrier gives the implementer has the freedom to change what the poly type is bound to and correspondingly change the implementation of degree, plus, zero, etc. to match.For example, the implementer might decide to use the SML vector type instead of list, resulting in a more efficient implementation of polynomials.