CS 2510 Spring 2012: Lab 8 - Abstracting over Datatypes; Understanding Javadocs

copyright 2012 Felleisen, Proulx, et. al.

Goals

The goal of this lab is to understand how we can design more general (generic) programs by defining/designing structured data parametrized over the type of objects the data structure contains with the common behavior encoded as parametrized methods. We illustrate these ideas on recursively built lists, but the techniques apply equally well to other data structures, such as binary trees and other data structures we will see soon.


1  Parametrized Datatypes.

Begin by downloading Lab8.zip and building a project that contains all the files. Your project should have the following files:

The last two files will be used in parts 2 and 3 of the lab - you can ignore them at the beginning.

s

Run the project and make sure all tests pass, then work through the following exercises.

  1. The file ExamplesLists.java contains tests for the method totalValue in the classes that represent lists of items of the type T.

    If you un-comment the testTotalValue method in the ExamplesLists class then the program breaks. Modify the Book, Song, and Image classes so that the method totalValue works correctly for the list classes with items of the type Book, Song, and Image, and all the tests pass.

  2. Now design a method makeString for the list classes that produces readable String representations of the elements of type T in the list.

  3. Warning: The examples you have seen are bad. They force us to design a new interface for every method that processes the items in the list, an require that every class that wants to use it implement this interface. We want to design a more general solution where we do not have to change either the classes and interfaces that represent the list, nor the classes that represent the items in the list. We also want to avoid casting the data within the method, as this could lead to runtime errors not detected by the type checker.

    The next two exercises and the last problem show you two different better ways of doing this.

    Think of the Racket function map. It consumes a list of X, a function of the type X -> Y, and produces a result of the type Y by applying the given function to a each item in the list.

    map: [Listof X] (X -> Y) -> [Listof Y]
    (map (list x1 x2 ... xn) f) -> (list (f x1) (f x2) ... (f xn))
    

    So, our makeStrings method is a map from lists of the type T (we used Songs, Books, and Images) to lists of items of the type String.

  4. We would like to generalize the method filter we have seen previously so that it works for arbitrary lists of items. The method produces a list of all items that satisfy some predicate. We modify the ISelect interface so it can be applied to any type of data:

       // a method to decide whether this item 
       // has the desired property
       interface ISelect< T>{
          // does this data item have the desired property?
          public boolean select(T data);
       }
    

    Design the method filter that produces a list of all items in the list (parametrized by the type T) that satisfy the given predicate (an instance of a class that implements the ISelect interface). Test it by selecting all books that cost less than $25, all songs that play for more than 180 seconds, and all images with the "jpeg" file type.

  5. You will finish this last problem as a part of your next homework.

2  User-Defined Exceptions.

We will learn how to design our own exception classes, and how the program can recover after an exception has been thrown during the program execution. After all, you would not want a long running program that processes thousands of transactions stop every time it encounters some incorrect input data. You will define your own NoSuchElementException class, a method that throws this kind of exception, another method that invokes it and catches the exception and allows us to continue running the program.

The class NoSuchElementException included in the Lab8.zip files is a user-defined class that extends the Exception class defined in the Java libraries. The template for the exception classes is always the same - for the standard cases the programmer just decides on the name of the exception class.

The class RuntimeException we have seen in the earlier labs also extends the Java Exception class. When the method throws the RuntimeException, (or an exception from any of the classes that extend the RuntimeException) the programmer does not have to note that the method may fail. The faults that trigger throwing the RuntimeException are typically such that testing for their occurrence would be too time-consuming and these faults should not occur in well-designed programs. However, if the method throws an exception that is not a subclass of the RuntimeException, the programmer must make this seen in the method header, and any program that invokes this method must include the code that specifies what the method should do if the exception is thrown. Here is an example:

The following method indicated that it may throw an exception:

// produce the author of this book
// throw an exception if no name is known
public String authorName() throws NoSuchElementException{
  if (this.author.equals(""))
    throw new NoSuchElementException(
              "No author for the book " + this.title);
  else
    return this.author;
}

and when invoked, the programmer must include the try - catch clause as follows:

// test for the method that throws an exception
// using the try-catch clause
void testAuthorName(Tester t){
  Book noAuthor = new Book("The Bible", "", 20);
  try{
    t.checkExpect(noAuthor.authorName(), "");
  }
  catch(NoSuchElementException e){
    t.checkExpect(e.getMessage(), "No author for the book The Bible");
  }
}

As you can see, the catch part looks like a method invocation that consumes an instance tt>e of the desired Exception class. This instance can then invoke the method e.getMessage() to extract the message that the program produced when the exception was thrown.

Design the method findItem that produces the first item in this list that satisfies the given predicate. If there is no such item, throw an NoSuchElementException as follows:

You will finish this problem as a part of your next homework.

3  Visitors.

We often do not know what kinds of methods the programmers need to define for their lists of objects. Furthermore, they may have to define one specific method for their list that is not applicable to any other list of objects. Here is an example:

We may want to use these classes for our circularly defined data. So we may want to add the method addBook to the classes that represent the list of authors (or addRole to the classes that represent the list of movie actors).

To make the library extensible, the designers need to provide ways for adding new methods at the time the programmer wants to use it.

One way to make the self-referential union of classes extensible is by defining a visitor interface and add to the union a method that invokes the methods of the visitor interface supplying its own internal data as arguments. This sounds very complicated. We will illustrate this on an example.

Here is an example of a visitor interface for the classes that define a list of objects:

// A visitor for the ILo classes that 
// and produces the result of the type R
interface ILoVisitor{
  // method for the empty list
  public R forMt(); 
  
  // method for the nonempty list
  public R forCons(T first, ILo rest);
}

The visitor for a union of data types contains one method for every class in the union, and has the name that indicates the class it targets. The arguments for each method are the fields in the target class that are needed to perform any operations on an object in this field. So, here, the method forMt takes no arguments, as there are no relevant fields in the class MtLo< T>. On the other hand, the method forCons consumes the first and the rest, where the first is of the type < T> and the rest is of the type ConsLo< T>.

We now add to the classes MtLo< T> and ConsLo< T> the hooks, the methods that accept the instance of the visitor class and invoke the appropriate methods defined there:

// in the interface ILo< T>:
// accept the visitor that produces a result of the type R
public < R> R accept(ILoVisitor< R, T> ilov);

// in the class MtLo< T>:
// accept the visitor that produces a result of the type R
public < R> R accept(ILoVisitor< R, T> ilov){
  return ilov.forMtLo();
}

// in the class MtLo< T>:
// accept the visitor that produces a result of the type R
public < R> R accept(ILoVisitor< R, T> ilov){
  return ilov.forConsLo(this.first, this.rest);
}

The example included in the Lab8.zip files defines a visitor that represents a method that computes the total download time for all files in the list of image files

The visitor class is defined as follows:

// A visitor that computes the total download time for all files 
// in the list of image files
class ILoImageDownloadTimeVisitor 
  implements ILoVisitor{
  
  int speed;
  ILoImageDownloadTimeVisitor(int speed){
    this.speed = speed;
  }

  // method for the empty list
  public Integer forMt(){
    return 0;
  }
  
  // method for the nonempty list
  public Integer forCons(Image first, ILo rest){
    return 
        first.fileSize / speed + rest.accept(this);
  }
}

The following examples show how we can use this method with our lists of data:

ILoVisitor imageDownloads = 
        new ILoImageDownloadTimeVisitor(200);
    
// test the use of the ILoMakeStringVisitor
void testILoMakeStringVisitor(Tester t){
  t.checkExpect(this.mtloi.accept(this.imageDownloads), 0);
  t.checkExpect(this.ilist2.accept(this.imageDownloads), 287);      
}

We see that the methods defined in the class that implements the visitor have the same structure as those originally defined inside of the MtLo... and ConsLo... classes. The instance of the list then invokes the new method by applying the accept method with the appropriate visitor as its argument.

  1. Make another example of the use of the ILoImageDownloadTimeVisitor that computes the download time with the download speed 100 for the list ilist3.

  2. Design a visitor that implements the method that produces a list of titles of all songs in a list of songs. Of course, you need to make sure that your solution works.

  3. Design a visitor that implements the method that produces one long String that contains the titles of all books, separating the titles with the new line String that is encoded as "\n". Of course, you need to make sure that your solution works.

We could now rewrite the solution to the circularly referential problem af books and authors (or actors with movie roles) using the generic list of objects and adding the appropriate visitor to the list of authors (or actors). Work this out on your own as a practice problem - it is not a required part.

You will finish this problem as a part of your next homework.

4  Reading/Using Java Documentation.

Until now, our purpose statements were sufficient for someone trying to understand how our program works and where to make changes, even if another person wanted to improve the program we have written. However, if we design a program that represents a reusable datatype, such as lists or binary search trees parametrized over the type of data they contain, a client of our code may not be interested in the implementation details, only the fields, constructors, and methods that can be used, called, or overridden.

Most modern general-purpose programming languages come with a special (embedded) language for writing purpose statements that can then be translated into documentation. Typically the documentation is generated as cross-referenced web pages, which allow the client programmer to understand and use the library without looking at actual code.

JavaDoc Basics

  1. Go to the javalib web site: http://www.ccs.neu.edu/javalib

    Go to theTester link on the left, then look at JavaDocs tab and open the documentation for the latest version of the tester library. The web site you see has the documentation for all public fields and methods in the library. Click on the Tester tab in the left pane and you will see a description of the Tester class.

  2. Scroll through the descriptions of the methods until you find the documentation for checkInexact. Click on the method and you will see a detailed description of the method - its purpose, its parameters, and the return value it produces.

  3. Now look at the method checkRange in the Method Summary section. You can see that there is a number of methods with this name: some that consume an argument of the type java.lang.Comparable< T> and some that consume an argument of the type java.util.Comparator< T>.

    These are two interfaces defined in standard Java libraries. The first is a part of the Java language package (java.lang). The classes and interfaces defined there are automatically imported for every Java program. For example, the class String is specified in the documentation as java.lang.String; we have been using it all along without the need for specific import statements.

    The interface java.util.Comparator< T> is a part of the java.util package in the Java Collections Framework: a library of classes and interfaces for dealing with collections of data.


Last modified: Mon Feb 27 22:05:14 EST 2012