Date: Thu, 28 Mar 2024 13:49:25 -0500 (CDT) Message-ID: <441735814.1017.1711651765296@wiki-n2.rice.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_1016_760277542.1711651765289" ------=_Part_1016_760277542.1711651765289 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html
Note: Some of the code used in the following reading differ from that us= ed in class!
The Java Development Kit (JDK) comes with a tool called JavaDoc.This too= l will generate documentation for Java source code with comments written in= accordance with the Java documentation style. The following links show mor= e 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 h= is/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 curre= nt 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 =3D 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 d= oes not know anything about language levels, we will delay running the java= doc 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 privat= e and generate javadoc again. What is the difference?
Recall our object model (common known in the Scheme world as "data defin= ition") 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.
/** Abs= tract list structure. */ abstract class IntList { } /* Concrete empty list structure containing nothing. */ class EmptyIntList extends IntList { static EmptyIntList ONLY =3D 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 des= ign pattern for coding list methods. Here is the coding template.
abstrac= t class IntList { abstract returnType methodName(parameter_list); // returnType may be Vo= id } class EmptyIntList extends IntList { static EmptyIntList ONLY =3D 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 c= ollection 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:
(defin= e (listFunc aList) (cond [(empty? aList) ...] [(cons? aList) ... (first aList)... (listFunc (rest aList))...])) = pre>
First, let's review what the template is saying to us:
con=
d
statement:=20
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 tell= s 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 delegatio=
n to take advantage of that fact. Thus, the
On the other hand, summing a list is summing a list, no matter what lang= uage we are writing in. The key elements of the algorithm are i= ndependent of language and thus remain:
abstrac= t class IntList { abstract int sum(); // all IntLists know how to sum themselves! } class EmptyIntList extends IntList { static EmptyIntList ONLY =3D 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 implementati= ons?
Why don't we need to know the exact type of rest
?
cond
Go? The Java implemenation enables us to clearly focus on and dif=
ferentiate between the base and inductive cases by separating them into dif=
ferent sub-classes. But where, you might ask, did the cond statement in the Scheme implementation go into the Java implementat=
ion?
Remember that the sole function of the cond
statement was t=
o differentiate between the base and inductive cases. What we did was=
to move that differentiation from a functional, operational process to a <=
em>structural, architectural implementation. The base =
and inductive cases are differentiated not at run-time, but at design-time, when we de=
fine the EmptyIntList and ConsIntList sub-classes of IntList. &nb=
sp; The differentiation is not a process that is executed but a fundame=
ntal relationship between the classes in our system.
This should not be surprising in that the cond
statement wa=
s part of the invariant function template for all lists. =
This tells us that differentiation between base and inductive cases is fund=
amental to the nature of lists. Scheme is unable to expre=
ss this fact in its structural representations of data, i.e. structs, =
so we were forced to represent it in terms of an invariant function templat=
e. Java, however, has the ability to express this relatio=
nship in terms of its inheritance hierarchy and thus we use delegation to l=
everage this "polymorphic" behavior of the IntList sub-classes to let them =
differentiate themselves.
NO COND
Integer.MAX_VALUE
and Integer.MIN_VALUE
are s=
tatic fields of the Integer
class that will give you the large=
st 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 meth=
od to the InList
hierarchy of classes to perform this computat=
ion. Let's call this method listString()
and let's proceed tog=
ether.
Step 1: Instantiate t=
he interpreter code template given above by replacing returnType with
String
, the methodName
with listSt=
ring
and the parameter_list
with nothing. Be sure to cr=
eate one file for each class. The code will not compile. Why?
Step 1.5: Add syntact= ically correct code to the template so that the whole thing compile.
Step 2: Write appropr= iate JUnit test classes. Because of lack of time, we will not do this step = in class.
Step 3: Write the cod=
e for listString
in EmptyInstList
. This is trivi=
al! Make sure it passes the JUnit test though!
Step 4: Write the cod=
e for listString
in ConsIntList
. You can try the=
structural recursive code given in the template and see that it will not w=
ork. This is because by the time you reach the end of the list (i.e. when <=
code>rest is the empty list), you need to do something different fro=
m what EmptyIntList
. listString()
is programmed =
to do. You will need to call on rest to perform an auxiliary ("helper") met=
hod to get the job done. Let's call this helper method listStringHelp=
.
What does listStringHelp
need to know? You can pass to it w=
hat you (as the current list) know and ask rest to complete the job. What d=
oes the current list know? It knows it can build the string "(" + fir=
st
(meaning "(" concatenate with the default String representation o=
f =3Dfirst=3D) and it can pass this string to the helper method. So in effe=
ct the helper takes as parameter the accumulated string representation of t=
he list so far and delegates the job for completing the final string repres=
entation 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 li=
stStringHelp
to the IntList
hierarchy.
Step 5: Add the metho=
d 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 ConsIntL=
ist
will not pass still.
Step 6: Write JUnit t=
est code for listStringHelp
. Again, due to lack of time, we w=
ill not do that here in the lab. Actually, more than often, writing the tes=
t code will help write the code for the method in question.
Step 7: Write the cod=
e 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 a=
nd return: return acc + ")";
(And make sure it passes the JUni=
t test).
Step 8: Write the cod=
e 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 representati=
on so far and pass it on to rest to complete the job: return rest.lis=
tStringHelp(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 pas= s!
Here is the solution code.
abstrac= t class IntList { /** Computes a String representation of this list wiht matching parenth= eses * as in Scheme. For example, the list containing 1, 2 and 3 should r= eturn * (1, 2, 3) and the empty list should return (). * @return a non empty String consisting of elements in this list encl= osed * 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 encl= osed * 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 encl= osed * in a pair of matching parenthesis, separated by commas. For exampl= e, * "(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 i= t * the accumulated String representation so far, which is "(" + firs= t. * @return a non empty String consisting of elements in this list encl= osed * 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 encl= osed * in a pair of matching parenthesis, separated by commas. For exam= ple, * "(5, 3)" */ String listStringHelp(String acc) { return rest.listStringHelp(acc + ", " + first); } } /** Testing empty lists. */ class TestEmptyIntList extends TestCase { void test_listString() { EmptyIntList mt =3D 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 c=
onsisting 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 meth=
od can you come up with? Are some tail recursive and some not?<=
/li>