The following is a common definition of a list.
We rephrase the above classic list definition as follows.
We model the above abstract formulation of a list using three interfaces: IList, IEmptyList, and INEList. The table below shows the differences between the object-oriented formulation in Java and the "data-directed" formulation in Scheme (a la Comp 210).
| OO Design in Java | Data-directed Design in Scheme |
/**
* Represents the abstract notion of a list.
* At this point, it has no behavior, i.e. no method.
* We shall add behaviors later.
*/
public interface IList {
}
/**
* Represents the immutable empty list, which is a list.
* At this point, the empty list has no behavior.
* Note that in contrast with the non-empty list, since it has
* no first and no rest, there is no getFirst()
* nor getRest() method.
*/
public interface IEmptyList extends IList {
}
/**
* Represents the immutable non-empty list, which is a list.
* A non-empty list has a data object called first, and an
* isomorphic subcomponent called rest. Its structural behavior
* provides access to its internal data (first) and
* substructure (rest).
*/
public interface INEList extends IList {
/**
* "Gettor" method for the list's first.
* @return this INElist's first element.
*/
public Object getFirst();
/**
* "Gettor" method for the list's rest.
* @return this INElist's rest.
*/
public IList getRest();
}
|
;; A
list
is either ;; (make-Empty) , the empty list ;; or ;; (make-NonEmpty f r) where ;; f is a data object and r is a list |
|
The above is only an abstract specification of the (immutable) list structure. Note that the Scheme formulation is written as comments, whereas the Java formulation is written as actual Java code. The Java code specifies in effect a "contract" of what the list structure "looks like" and what it "behaves" like (i.e. what it is capable of doing). In order to create concrete IList objects and work with them, we need to define concrete classes to implement the above interfaces. Below is an example of concrete list implementations.
|
|
/**
* Concrete implementation of the empty list, IEmptyList.
* Since the empty list has no fields, there is no need to
* explicitly define any constructor for EmptyList.
* However, the compiler will generate the following constructor:
* public EmptyList() {};
* Note that there is no code inside the curly braces.
* The above constructor has no parameter. A constructor without
* any parameter is called a "default" constructor.
* To instantiate a concrete empty list, we simply call:
* new EmptyList();
*/
public class EmptyList implements IEmptyList {
}
|
(define-struct Empty()) ;; make-Empty is automatically generated |
| /** * Concrete implementation of the non-empty list, INEList. * Contains two pieces of data: * first: an Object representing the first data element * rest: an IList object representing the rest of this * non-empty list. * When a class contains other objects that are isomorphic to * itself, this class is called a composite. * Provides concrete code for a constructor * to initialize this NEList to a given first and rest, * the getFirst() method for accessing the first data element, * getRest() method for accesssing the rest of the list. */ public class NEList implements INEList { /** * The first data element of this NEList. */ private Object _first; /** * The rest or "tail" of this NEList. * Data Invariant: _rest != null; */ private IList _rest; /** * Initializes this NEList to a given first and rest. * @param first the first data element of this NEList. * @param tail != null, the rest of this NEList. */ public NEList(Object first, IList tail) { _first = first; _rest = tail; } /** * Returns the first data element of this NEList. */ public Object getFirst() { return _first; } /** * Returns the rest of this NEList. */ public IList getRest() { return _rest; } } |
(define-struct
NEList(first rest)) ;; make-NEList, NEList-first, NEList-rest ;; are automatically generated |
The following UML diagram illustrates the above object-oriented design (click on the diagram to see the full documentation).
The above design allows us to instantiate a list of any size.
IList list0 = new EmptyList(); // the list ()
IList list1 = new NEList("one", list0); // the list ("one")
IList list2 = new NEList("two", list1); // the list ("two" "one")
IList list3 = new NEList("a", new NEList("b", new NEList("c", new EmptyList()))); // the list ("a" "b" "c")
There are more than one way to express the list abstraction in Java code. Below is another formulation.
| Another OO List Design in Java |
| /** * A list is an abstract entity that intrinsically knows how to return * its first data element and its rest, which is another list. */ public interface IList2 { public Object getFirst(); public IList2 getRest(); } |
| /** * An empty list is a list. It has no first and no rest element. * It throws an exception when asked for first and rest. * What is an exception? What is its effect? */ public class EmptyList2 implements IList2 { public Object getFirst() { throw new IllegalArgumentException ("EmptyList has no first!"); } public IList2 getRest() { throw new IllegalArgumentException ("EmptyList has no rest!"); } } |
| /** * A non-empty list is a list. It has an element called first and an * element called rest, which is itself another list. */ public class NEList2 implements IList2 { private Object _first; private IList2 _rest; public NEList2(Object first, AList rest) { _first = first; _rest = rest; } public Object getFirst() { return _first; } public IList2 getRest() { return _rest; } } |
The above formulation allows us to program the list at the abstract
IList2 level and not knowing about its concrete implementations. However, this may lead to programming errors by incorrectly calling getFirst and getRest on the empty list. Such calls cannot be caught by the compiler and will cause the program to crash at run time. Because of that, we will not use this formulation in our course.In the above two formulations, a non-empty list object (e.g. NEList) "has a" an element, called rest, whose structure is isomorphic to the enclosing non-empty list itself. A non-empty defined as such is said to be a composite. Its structure is recursively constructed and terminates with the "base case", the empty list (e.g. EmptyList). The above taxonomy is an example of what is called the composite design pattern.
The composite pattern is a structural pattern that prescribes how to build a container object that is composed of other objects whose structure is isomorphic to that of the container itself. In this pattern, the container is called a composite. The composite pattern is the expression of "recursive decomposition," one of the most important ways in computing for breaking down a problem in order to solve it.
The composite pattern also prescribes a coding pattern for the container's methods. We shall study this coding pattern in the next lecture. In the mean time, let us take a look at a common way to program such lists without taking advantage polymorphism.
How do we write code to operate (i.e. perform algorithms) on the list (
IList)? For example, how do we compute the length of a list? The following table shows the Scheme code and a direct translation into Java. The Java translation is not object-oriented since it makes use of the instanceof operator to check for the type of the list instead of making use of the polymorphic nature of IList. (We show the object-oriented version later).| Java Code | Scheme Code |
/**
* A non object-oriented way of coding list operations.
* Scheme functions are translated into public static methods.
* The instanceof operator is used to check for the type of a
* given list.
*/
public class ListOps {
/**
* Computes the length of a list.
* @param L one of the two types of IList.
*/
public static int GetLength(IList L) {
if (L instanceof IEmptyList) {
return 0;
}
else {
return 1 + GetLength(((INEList)L).getRest());
// Note how type-casting is used here!
// Why do we need to type-cast?
}
}
}
|
;; Contract: ;; getLength: list -> number ;; Purpose: ;; (getLength alist) returns the number of elements in alist. (define (getLength alist) (cond [(Empty? alist) 0] [(NEList? alist) (+ 1 (getLength (NEList-rest alist)))])) |