Abstractions 
------------

- as a motivation for Java language features
- 
and for understanding program design - the design of reusable code

Design Recipe for Abstractions
------------------------------

Start with two or three pieces of code that look very similar.

Identify the places where they are different: highlight the differences.

Turn each set of differences into a parameter. Rewrite the original code
with parameters. Then rewrite each of the original pieces of code as an
application of the abstracted code by supplying the correct values for
the parameters.

Run the original test cases.
------------------------------------------------------------------------


Examples where abstraction introduces new language features - and a new
way of thinking about program design
------------------------------------------------------------------------


Abstracting over common components:
-----------------------------------

Several classes in the union have the same fields. 
Several classes in the union implement the common method in the same way.

We introduce 'abstract class' that extends the common interface
and defines the common fields
and contains concrete implementations of the common methods.

If only one of the several classes implements the common method differently,
we show them how the new definition within that class overrides the 
original one in the super class.


Abstracting over the data type:
-------------------------------

We see several programs that use a list of books, a list of shapes, a
list of shots in the UFO program

-- we replace each of the lists with a LoObject/MTObject/ConsObject
   or with AList<E> MTList<E> ConsList<E>



Abstracting over the behavior:
------------------------------

When designing programs that produce lists of only those items that are
'the cheap toys' 'the shots that are out of bounds' 'the books published
before the given date' 'the books by a given author'

All programs are the same except for the way we select the ones to keep.

... if (this.first.cheapToy()) ...
... if (this.first.goodShot()) ...
... if (this.first.beforeDate(1950) ...
... if (this.first.writtenBy("Hemingway") ...

We introduce lambda.
Simple in Scheme - complicated in Java.

interface Selector<E>{
  boolean select(E object);
}

class GoodShots implements Selector<Shot>{
  boolean select(Shot s){
    return true --- if shot is within bounds;
  }
}

Your parameter is then 'Selector choose = new GoodShots()'
and the method invocation becomes:

... if (choose.select(this.first)) ...

Note: This technique looks complex and convoluted - but is used in Java daily
in the Comparator in the Collections Framework, and to implement the actions
attached to the GUI buttons. 

I intentionally start with Selector - to make sure they think of the abstraction,
if they have heard about Comparator already. They should see this as a universal
technique - not as some special way just to do comparison.



Abstracting over datatype manipulation (ADT)
--------------------------------------------

We have examples of dealing with lists and binary search trees or priority queues
where we do the same operations on each:

interface Dataset<E>{
  Datatype<E> add(E obj);
  boolean contains(E obj);
  int count();
  getFirst();
  DataType<E> getRest();
}

We can design an interface that represents these operations, have our program use
them, and repalce the implementation with the dataset that is most suitable for
our type of data manipulation.

Another example I use here is 'Key-Value' pair.

interface KeyData<K, V>{
  Datatype<K, V> add(K key, V value);
  V find(K key);
  boolean contains(K key);
  Datatype<K, V> remove(K key);
}



Abstracting over the traversal
------------------------------

This is a special case of abstracting over datatype manipulation. We use only the
following three operations:

interface traversal<E>{
  boolean isEmpty();
  e getFirst();
  DataType<E> getRest();
}

Before, every time we needed to design a new methods that manipulated a list (or a 
binary search tree) we had to add new methods to existing classes. If these classes
are already in a library - this becomes difficult - as we need to extend three classes
in the hierarchy in a 'synchronized' way.

With these operations the new method is defined in an Algorithms class:

boolean contains(Traversal tr, Selector choose){
  if (tr.isEmpty())
    return false;
  else
    return choose.select(tr.getFirst()) ||
           contains(tr.getRest(), choose):
}

This is back to the Scheme programs.

Note: I start with this version of iterator - it makes it clear that the Java Iterator
is not the only solution and highlights the connection to what we have already seen 
in Scheme.

Shriram's and Kathi's  loop lecture then shows how to think about this without details of
the loop travesal. (




Why do we do this?
------------------

By the time students have seen all of these abstractions they are ready to learn how to 
read Javadocs for the Java Collections Framework and use the classes and algorithms 
defined there.

We now show them how to write the documentation, how to read it, and give them an overview
of the Java Collections Framework design. We explain why we have both:
 
interface Collection
abstract class AbstractCollection

and talk about the algorithm complexity to explain why we need to organize data in different
ways. 



ArrayList is introduced as a way to access the data directly. it allows us to do the binary 
search. Searching motivates the three ways of organizing data:

sequential - lists, stacks, queues, where we can access only the first element and need 
             to advance to the next to know more about the data structure

direct access - where we can access any element by supplying the location information
                knowing only the size of the data structure

key-value access - where we access every data element by supplying its key
                   This includes binary search trees, tree map, hash map, and table lookup
------------------------------------------------------------------------------------------


Testing and Equality
--------------------

ProfessorJ provides us with test harness for evaluating our results.
Notice that we compare the values we produce with the values of the expected results.
This is not 'Java equals' method!!!

In functional approach every method produces a result (not void) and to verify that we
produced a correct result we cannot use the 'intensional' equality - as the new object
does not exist prior to the method invocation.

ProfessorJ provides a test harness that compares the two objects by their deep 
'extensional equality':

Book b = new Book("Old Man and the Sea", new Author("Hemingway", 1899), 1951);
Author h = new new Author("Hemingway", 1899);
Book b1 = new Book("Old Man and the Sea", h, 1951); 

When comparing b and b1 it will compare the titles of the two books (using the built-in
Java String equals), compare the two years of publications, and compare the author fields
again looking at the values of their fields: same name, same year of birth.

This is hard to do once we move to real Java. In the past, students had to write their 
own comparison methods - implementing 'ISame' interface:

interface ISame<E>{
  boolean same(E obj1, E obj2);
}

For every class they defined - as well as their own 'toString()' method, so they can
display the values of their objects. This detracts from the topics that are relevant.
JUnit is no help in this situation.

Our new test harness provides for a smooth transition to full Java once the students
move beyond ProfessorJ:

-- it provides complete extensional equality comparison for all data: primitive types, 
   wrapper classes, user-defined classes, any library classes - by comparing the values 
   of the fields that have been declared 'public'

-- for datasets that implement the 'Traversal' interface, the Java 'Iterator" interface,
   and for Java Arrays, the datasets are compared by first checking that thy both represent
   the same type of data and are of the same size, and then each pair of data elements
   is compared for equality using the same test harness

-- if the user implements their own version of the ISame interface for a given class, the 
   data in that class is compared by invoking their 'same' method - allowing the comparison 
   of protected and private fields

-- user can also supply a different method to be used to produce the boolean value - in that
   case the user supplies the object that invokes the method, the method name, and the
   list of arguments to be used in method invocation - as well as the expected result

-- finally, user may supply the object that invokes a method, the method name, and the list
   of arguments, and provide the expected Exception instead of the expected result -- here
   the test harness verifies that the specified method invocation throws the expected
   Exception - with the specified message.

The final report either provides only the list of failed tests or the complete list of test 
that were done, with the count of the number of test that were run and how many failed.

Additionally, the test harness allows the user to display all data well formatted, with each
field on a new line, properly indented, with field name followed by the field value -- and 
displaying the data elements for the Traversal-s Iterator-s and Array-s.

This allows us to postpone the discussion of the equality till later - while providing a
rich set of examples where different levels of equality can be demonstrated. Students then
transition confidently to writing their tests using JUnit.