Page History

...

Now change the javadoc Access level in the javadoc Preferences to private and generate javadoc again. What is the difference?

From Scheme To Java

Has the world really changed as we transition from Scheme to Java?  Well, yes and no.   Yes, because we now look at the world as a collection of objects rather than as a collection of funcitons.   No, because CS principles still hold and so the same concepts must be still hold true no matter what language we express them in.

In particular, let's look at what happens to the list template from Scheme:

 (define (listFunc aList)
    (cond
       [(empty? aList) ...]
       [(cons? aList) ... (first aList)... (listFunc (rest aList))...])) 

 First, let's review what the template is saying to us:

• The template is a statement of an invariant properties of lists and the functions that process them.   That is, the template tells us things that are true for all lists.
• A function on a list is fundamentally separable into two parts:
  • The base case: The empty list is processed separately from the non-empty list.
  • The inductive case: The non-empty list (cons) is processed separately from the empty list and involves the two pieces of the non-empty list, namely first and rest.
• A recursive algorithm involves processing the rest of the list.

 Now, the Java viewpoint on lists:

• Objects "know" what they are.   An empty list knows that it is an empty list and does not need to be told such and likewise, non-empty (cons) lists know that they are non-empty and thus have a first and rest. 
  • Objects have behaviors, i.e. objects contain functions ("methods").    That is, the functions to process an object, e.g. a list, are built into the list.  (at least for now).
  • Never ask an object what it is.   The object already knows.   Let the object do what it already knows how to do.   Delegate to the object, don't query its type!
• Objects are part of an inheritance hierarchy, which in part, determines their type. 
  • Empty lists and cons (non-empty) lists are lists and thus are sub-types of ("extend") the abstract superclass, IntList, which represents *all* lists, i.e. the "union" of all empty and non-empty lists.

More List Exercises

Recall our object model (common known in the Scheme world as "data definition") for lists of int.

• IntList is an abstract list of int .
• EmptyIntList is an IntList
• ConsIntList(first, rest) is an !IntList, where first is an int and rest is an IntList .

The above can be implemented in Java using the composite design pattern as follows.

/** Abstract list structure. */
abstract class IntList {
}

/* Concrete empty list structure containing nothing. */
class EmptyIntList extends IntList {
}

/** Concrete non-empty list structure containing an int, called first, and a rest,
  * which is a list structure. */
class ConsIntList extends IntList {
    int first;
    IntList rest;
}

The above composite design for IntList gives rise to the interpreter design pattern for coding list methods. Here is the coding template.

Lists and List Algorithms

Recall our object model (common known in the Scheme world as "data definition") for lists of int.

• IntList is an abstract list of int .
• EmptyIntList is an IntList
• ConsIntList(first, rest) is an !IntList, where first is an int and rest is an IntList .

The above can be implemented in Java using the composite design pattern as follows.

/** Abstract list structure. */
abstract class IntList {
}

/* Concrete empty list structure containing nothing. */
class EmptyIntList extends IntList {
   static EmptyIntList ONLY = new EmptyIntList();  // Singleton
   private EmptyIntList {}
}

/** Concrete non-empty list structure containing an int, called first, and a rest,
  * which is a list structure. */
class ConsIntList extends IntList {
    int first;
    IntList rest;
}

The above composite design for IntList gives rise to the interpreter design pattern for coding list methods. Here is the coding template.

abstract class IntList {
    abstract returnType methodName(parameter_list); // returnType may be Void
}

class EmptyIntList extends IntList {
    static EmptyIntList ONLY = new EmptyIntList(); // Singleton
    private EmptyIntList {}
 
    returnType methodName(parameter_list) {
        // base case code
    }
}

class ConsIntList extends IntList {
    int first;
    IntList rest;
    returnType methodName(parameter_list) {
        // ... first ...
        // ... rest.methodName(parameter_list)...
    }

}

From Scheme To Java

Has the world really changed as we transition from Scheme to Java?  Well, yes and no.   Yes, because we now look at the world as a collection of objects rather than as a collection of funcitons.   No, because CS principles still hold and so the same concepts must be still hold true no matter what language we express them in.

In particular, let's look at what happens to the list template from Scheme:

 (define (listFunc aList)
    (cond
       [(empty? aList) ...]
       [(cons? aList) ... (first aList)... (listFunc (rest aList))...])) 

 First, let's review what the template is saying to us:

• The template is a statement of an invariant properties of lists and the functions that process them.   That is, the template tells us things that are true for all lists.
• A function on a list is fundamentally separable into two parts:
  • The base case: The empty list is processed separately from the non-empty list.
  • The inductive case: The non-empty list (cons) is processed separately from the empty list and involves the two pieces of the non-empty list, namely first and rest.
• A recursive algorithm involves processing the rest of the list.

 Now, the Java viewpoint on lists:

• Objects "know" what they are.   An empty list knows that it is an empty list and does not need to be told such and likewise, non-empty (cons) lists know that they are non-empty and thus have a first and rest. 
  • Objects have behaviors, i.e. objects contain functions ("methods").    That is, the functions to process an object, e.g. a list, are built into the list.  (at least for now).
  • Never ask an object what it is.   The object already knows.   Let the object do what it already knows how to do.   Delegate to the object, don't query its type!
• Objects are part of an inheritance hierarchy, which in part, determines their type. 
  • Empty lists and cons (non-empty) lists are lists and thus are sub-types of ("extend") the abstract superclass, IntList, which represents *all* lists, i.e. the "union" of all empty and non-empty lists.

A Simple Reverse Accumulation (Natural Recursion) Algorithm

Let's look at how this plays out as we compare a simple algorithm to sum the integers in a list:

First, in Scheme, using the above template:

;; sum:  list-of-int --> int
;; returns the sum the elements in a list of integers
(define (sum anIntList)
   (cond
     [(empty? anIntList) 0]
     [(cons? anIntList) (+ (first anIntList) (sum (rest anIntList)))])) 

In addition to everything that the template tells us, the algorithm tells us some specific (variant) issues about summing:

• The sum of an empty list is zero
• The sum of a non-empty list is the addition of first to the sum of the rest of the list.

 The biggest change that we will see when we switch to Java is due to the fact that objects "know" who they are and that we will use delegation to take advantage of that fact.   Thus, the "cond" statement in the Scheme function, whose sole purpose is to diffrentiate between the base and inductive cases, is no longer needed!   Instead, we will make the sum function a part of the list, and simply ask the list to sum itself.   Since any list object already knows whether it is empty or non-empty, it does not need to have a conditional for that purpose--the question is already answered and thus does not need to be asked!

On the other hand, summing a list is summing a list, no matter what language we are writing in.   The key elements of the algorithm are independent of language and thus remain:

• The sum of an empty list is zero.
• The sum of a non-empty list is first plus the sum of the rest of the list.

abstract class IntList {
    abstract int sum(); // all IntLists know how to sum themselves!
}

class EmptyIntList extends IntList {
    static EmptyIntList ONLY = new EmptyIntList(); // Singleton
    private EmptyIntList {}
 
   /**
    * The sum of an empty list
    * @return zero always
    */
    int sum() {
        return 0; // base case code
    }
}

class ConsIntList extends

abstract class IntList {
    abstract returnType methodName(parameter_list); // returnType may be Void
}

class EmptyIntList extends IntList {int first;
    IntList rest;

   /**
    returnType methodName(parameter_list) {
    * The sum of a non-empty list
    //* base@return casefirst code
plus the sum of }rest
}

class ConsIntList extends IntList {*/
    int first; sum() {
    IntList rest;
   return returnType methodName(parameter_list) {
        // ... first ...
        // ... rest.methodName(parameter_list)...
    }

}
first + rest.sum()  ; // inductive case code
    }
}

 Notice that, to within syntactical differences, the bodies of the base and inductive cases are identical between Scheme and Java implementations?

Where Did The Cond Go? 

 The Java implemenation enables us to clearly focus on and differentiate between the base and inductive cases by separating them into different sub-classes.  But where, you might ask, did the cond statement in the Scheme implementation go into the Java implementation?  

Remember that the sole function of the cond statement was to differentiate between the base and inductive cases.  What we did was to move that differentiation from a functional, operational process to a structural, architectural implementation.  The base and inductive cases are differentiated not at run-time, but at design-time, when we define the EmptyIntList and ConsIntList sub-classes of IntList.   The differentiation is not a process that is executed but a fundamental relationship between the classes in our system.

This should not be surprising in that the cond statement was part of the invariant function template for all lists.    This tells us that differentiation between base and inductive cases is fundamental to the nature of lists.    Scheme is unable to express this fact in its structural representations of data, i.e. structs, so we were forced to represent it in terms of an invariant function template.    Java, however, has the ability to express this relationship in terms of its inheritance hierarchy and thus we use delegation to leverage this "polymorphic" behavior of the IntList sub-classes to let them differentiate themselves.

NO COND!!

More List Exercises

A Scheme-like String representation of lists.

Suppose we want to display an empty list as () and the list containing 1, 2, 3 as (1, 2, 3) . How do we do this? We need to add a method to the InList hierarchy of classes to perform this computation. Let's call this method listString() and let's proceed together.

...