Note: Some of the code used in the following reading differ from that used in class!
The Java Development Kit (JDK) comes with a tool called JavaDoc.This tool will generate documentation for Java source code with comments written in accordance with the Java documentation style. The following links show more examples. You do need to spend time outside of the lab to study them.
The following is a very short summary of the Javadoc conventions.
/** * Represents a person who knows how to compute the number of months till his/her * next birthday. * @author DXN * @since Copyright 2009 by DXN - All rights reserved */ class Person { /** * birth month */ int bm; /** * Computes the number of month until the next birthday given the current month. * @param cm an integer between 1 and 12 as the current month. * @return an integer between 0 and 11. */ int nMonthTillBD (int cm) { return (bm - cm + 12) % 12; } } /** * JUnit test class to test all methods in class Person. * @author DXN * @since 02/20/2009 */ class TestPerson extends TestCase { /** * Tests nMonthTillBD by covering three cases: * the current month is less than the birth month * the current month is equal to the birth month * the current month is greater than the birth month. */ void test_nMonthTillBD() { Person peter = new Person(9); // a person born in September. assertEquals("Calling nMonthTillBD(2).", 7, peter.nMonthTillBD(2)); assertEquals("Calling nMonthTillBD(9).", 0, peter.nMonthTillBD(9)); assertEquals("Calling nMonthTillBD(12).", 9, peter.nMonthTillBD(12)); } } |
DrJavahas incorporated the javadoc utility into its IDE. Since javadoc does not know anything about language levels, we will delay running the javadoc utility on our code until we switch to the Full Java language.
For the "daring", you can try the following steps at your own risk!
Now change the javadoc Access level in the javadoc Preferences to private and generate javadoc again. What is the difference?
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 IntListConsIntList(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)... } } |
Let's take a look at what this means in light of what we'v learned from Scheme...
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:
cond
statement:
Now, the Java viewpoint on lists:
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 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:
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 IntList { int first; IntList rest; /** * The sum of a non-empty list * @return first plus the sum of rest */ int sum() { return 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?
Why don't we need to know the exact type of rest
?
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
!!
Integer.MAX_VALUE
and Integer.MIN_VALUE
are static fields of the Integer
class that will give you the largest and smallest possible integer values in Java.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.
Step 1: Instantiate the interpreter code template given above by replacing returnType
with String
, the methodName
with listString
and the parameter_list
with nothing. Be sure to create one file for each class. The code will not compile. Why?
Step 1.5: Add syntactically correct code to the template so that the whole thing compile.
Step 2: Write appropriate JUnit test classes. Because of lack of time, we will not do this step in class.
Step 3: Write the code for listString
in EmptyInstList
. This is trivial! Make sure it passes the JUnit test though!
Step 4: Write the code for listString
in ConsIntList
. You can try the structural recursive code given in the template and see that it will not work. This is because by the time you reach the end of the list (i.e. when rest
is the empty list), you need to do something different from what EmptyIntList
. listString()
is programmed to do. You will need to call on rest to perform an auxiliary ("helper") method to get the job done. Let's call this helper method listStringHelp
.
What does listStringHelp
need to know? You can pass to it what you (as the current list) know and ask rest to complete the job. What does the current list know? It knows it can build the string "(" + first
(meaning "(" concatenate with the default String representation of =first=) and it can pass this string to the helper method. So in effect the helper takes as parameter the accumulated string representation of the list so far and delegates the job for completing the final string representation to rest.
The code for ConsInList.listString()
is thus something like:
return rest.listStringHelp("(" + first); |
The code will not compile because we have yet to add the method listStringHelp
to the IntList
hierarchy.
Step 5: Add the method String listStringHelp(String acc)
to the IntList
hierarchy; add stub template code so that the whole thing compile. Unless you accidentally write the correct code, the JUnit test for ConsIntList
will not pass still.
Step 6: Write JUnit test code for listStringHelp
. Again, due to lack of time, we will not do that here in the lab. Actually, more than often, writing the test code will help write the code for the method in question.
Step 7: Write the code for EmptyIntList.listStringHelp(String acc)
What should the empty do here? It knows it has the accumulated string representation of the whole list so far and that all it needs is the closing parenthesis. So all it has to do is to add the closing parenthesis to the accumulated string and return: return acc + ")";
(And make sure it passes the JUnit test).
Step 8: Write the code for ConsIntList.listStringHelp
(and make sure that it passes the JUnit test). What can a non-empty list do here? All it needs to do is to concatenate a comma and its first to the accumulated string representation so far and pass it on to rest to complete the job: return rest.listStringHelp(acc + ", " + first);
(And make sure it passes the JUnit test).
Note that the code for listStringHelp
is tail-recursive.
Step 9: Run the complete JUnit test suite and the whole thing should pass!
Here is the solution code.
abstract class IntList { /** Computes a String representation of this list wiht matching parentheses * as in Scheme. For example, the list containing 1, 2 and 3 should return * (1, 2, 3) and the empty list should return (). * @return a non empty String consisting of elements in this list enclosed * in a pair of matching parenthesis, separated by commas. */ abstract String listString(); /** Accumulator helper method for listString to compute the String * required representation of this list given the accumulated * String representation of the preceding list. * @param acc the accumulated String representation of the list that * precedes this list. * @return a non empty String consisting of elements in this list enclosed * in a pair of matching parenthesis, separated by commas. */ abstract String listStringHelp(String acc); } class EmptyIntList extends IntList { /** @return "()"*/ String listString() { return "()"; } /** @param acc the accumulated String representation of the list that * precedes this list. For example "(5, 3" * @return a non empty String consisting of elements in this list enclosed * in a pair of matching parenthesis, separated by commas. For example, * "(5, 3)" */ String listStringHelp(String acc) { return acc + ")"; } } class ConsIntList extends IntList { int first; IntList rest; /** Calls on rest to perform the helper method listStringHelp passing it * the accumulated String representation so far, which is "(" + first. * @return a non empty String consisting of elements in this list enclosed * in a pair of matching parenthesis, separated by commas. */ String listString() { return rest.listStringHelp("(" + first); } /** @param acc the accumulated String representation of the list that * precedes this. For example "(5, 3" * @return a non empty String consisting of elements in this list enclosed * in a pair of matching parenthesis, separated by commas. For example, * "(5, 3)" */ String listStringHelp(String acc) { return rest.listStringHelp(acc + ", " + first); } } /** Testing empty lists. */ class TestEmptyIntList extends TestCase { void test_listString() { EmptyIntList mt = new EmptyIntList(); assertEquals(mt + ".listString()", "()", mt.listString()); } } |
prodNums
that returns the product of the number in the list, using a tail recursive helper method.makePalindrome
that returns a list consisting of the input list and its mirror around the last element, using a (non tail-recursive) helper with an accumulator. For example, (1, 2, 3).makePalindrome ()
returns the list (1, 2, 3, 2, 1)
.reverse
that reverses the list using a tail-recursive helper.listString
. Call it listString2
. How many different ways of writing this method can you come up with? Are some tail recursive and some not?