42 basic OO assignments
Recently, I started to re-wire some mildly used parts of my brains to accommodate capabilities for a 1st year CS course on OO programming and modeling. Long before I joined the faculty in Koblenz, the course had been designed to get students going in (OO) “programming in the small” and “basics of (OO) modeling” as well as “related foundations of CS” (such as bits of PL theory and complexity theory) and the implied treatment of the “imperative heritage” including the whole range of Hoare semantics and structured programming. So this course may end up being a mix of Java, UML and the classical first CS course. To tell you a secret, I have a hidden agenda of the kind that students are potentially prepared for the post-Java 1.5 / UML 2.1 era. To this end, I subliminally detour into FP ground and touch upon some of the issues with current OO programming.
I should also mention that the course at hand in the curriculum at hand neither should produce “little OO programmers”, nor “UML junkies”, nor “recursion theoreticians”. That is, by far not every student in this class will end up as a software developer, and by the time these folks graduate, most programming will be reduced to model-driven development anyhow, right? Seriously, most of my students focus on “information management” as opposed to vanilla CS. This raises the question of how to make the course valuable for such students. My current take is to implant a good number of higher-level and timeless concepts into these young brains so that these students can think of programming and modeling and talk to technical folks and understand designs and honor technical problems. As a complement, the lecture also offers demo parts and the labs are pretty much hands-on. Again, programming-related courses can be extremely boring (ditto for examinations), and hence I have decided that a more intellectual (dis)course may be more fun; I can only speak for the lecturer.
There are these ways to consume this blog post: (i) my students may check out their understanding of all previous lectures to date, and they should not panic if a few questions are over their heads; (ii) other lecturers (e.g., those whose slide decks I have adopted for my course) may use some of the questions, if they ever run out of questions themselves; (iii) everyone else may find some riddles, admittedly nothing of Brian’s caliber, but then again, also without any risk of headache or brain damage. As the course continues over the next few months, I may publish another bag of questions, assuming that the course will not be abandoned or get stuck. If anyone wants to reply with clever solutions, this is more than appreciated.
Yours,
Ralf Lämmel
1. Encapsulation
a. Why is it a good idea to hide the state representation for the implementation of an object type for complex numbers? Yes, hiding representations is always a good idea, but what’s so special about complex numbers to provide a particular incentive?
b. Given a pair of setter and getter methods, what is a reasonable and general correctness criterion for these methods? To put it differently, how would you test setters and getters; how would incorrectness be revealed in a simple test?
c. Consider a class for a counter with an integer for the count as state; the count is initialized to 0 upon construction, it can be read by a getter, and it can be incremented by a corresponding method. Why may it be desirable to exclude the setter for the count?
d. Can you provide an example that fits the following scenario? (i) The initial state of an object is described by a parameterized constructor that lists all required components of the object. (ii) One required component is purposely read-only, i.e., there is a getter but no setter. (iii) All other components (required or optional) come with both a getter and a setter.
e. Can you come up with (and defend) some scenario of object modeling where information hiding may be irrelevant, where no proper encapsulation is needed? Again, the extreme OO follower may refuse to consider this option, but let’s try, just for the sake of it.
f. Consider the following legal Java class:
class C {
private C c;
public void setC(C c) { c.c = this.c; }
}
That is, the body of the setC method exercises access to “private” state of its argument. Here we note that the “private” modifier is the most restrictive access modifier in Java. Can you think of an even more restrictive mode that would illegalize the above program, but keep intact other permissions associated with “private”? Describe the language rules for this new “very-private” access modifier.
g. Consider the following legal Java class:
public class C {
private C() { }
}
This class shows that the default constructor can be effectively removed from the interface of a class. How can this capability be helpful in enforcing a useful, initial state of an object and in minimizing the number of setters to be exposed? Provide an example.
2. Class inheritance
a. Consider the following illegal attempt to privatize a method in Java:
public class C {
private boolean equals(Object o) {
return super.equals(o);
}
}
Can you defend this language rule?
b. A class with abstract methods is necessarily abstract. Can you provide a compelling scenario for a class that has only non-abstract methods, but is labeled abstract voluntarily by the programmer?
c. Does it make sense for a concrete class to have an abstract subclass?
d. Consider the following illegal Java classes:
public class C extends D { }
public class D extends C { }
Can you argue why cyclic class inheritance may be undesirable? Here is some elaboration of this question. It is a known fact that inheritance can be “designed away” by means of object composition. Suddenly, the following program is legal:
public class C { public D d; }
public class D { public C c; }
“How come” object composition works, but inheritance fails?
e. Consider the following two Java classes:
public class C {
protected int x;
}
public class D {
private C c;
public D() { c = new C(); }
public int getX() { return c.x; }
public void setX(int x) { c.x = x; }
}
Now assume that these classes are in different Java packages. In this case, the methods of class D cannot access the protected member x of class C. (Hence, the program turns out to be illegal.) Can you advice a solution to this access insufficiency? It is required that C and D remain in different packages, and class C is kept unchanged; ditto for the package of C. Hint: we may subclass C; a good name for the new class may be BreakEncapsulation.
f. Consider the following illegal Java class:
public abstract final class C { };
Why is it reasonable to disallow this sort of class?
g. One may think that the “super” construct for invoking methods of the superclass may not be strictly necessary, as far as expressiveness is concerned. That is, one may hope to “copy and paste” the superclass implementation to the derived class. Does this trick always work?
3. Interfaces
a. Java provides neither protected nor private interface members. Why is this reasonable?
b. Suppose you want to replace certain uses of Java arrays by different data structures, possibly even by database access. As a first step, provide an interface that captures the essential operations on Java arrays including indexed access. Another operation is construction parameterized by the number of elements in the array. Can you add a constructor to the Java interface? How could a constructor possibly make sense in an interface?
c. Describe a design scenario (in terms of concepts, attributes, behavior, generalizations, specializations) that clearly benefits from the use of an interface, when compared to class inheritance? What are the precise drawbacks that are encountered when trying to survive with class inheritance alone?
d. Describe a design scenario that clearly benefits from the use of class inheritance as opposed to solely using interfaces for generalization? What are the precise drawbacks that are encountered when trying to avoid class inheritance?
e. Argue why multiple interface inheritance is less bothersome than multiple class inheritance. Refer to the so-called diamond shape of inheritance where a given class inherits indirectly twice from the same base class.
f. Consider the following legal Java program:
public interface I { }
public class C implements I { }
public class D { }
In particular, one may have empty interfaces, and one may have classes (empty or nonempty) that implement such interfaces. In your wildest dreams, can you think of any usage scenario for empty interfaces in actual programming or modeling?
g. When you place a type bound on a type parameter (for generics in Java 1.5) then you use the “extends” keyword (such as “T extends Number”), no matter whether you mean to say that the actual type must be a class that “implements” the interface of the bound, or a class that indeed “extends” the class of the bound. Suppose you are part of the Java language team and someone complains to you that more clarity is desirable, i.e., programmers should be able to use both “implements” and “extends” for the sake of precision. Now suppose you don’t want to change Java. Can you come up with an argument such that the sole use of “extends” may be accepted by the petitioner?
4. Modeling versus programming
a. From an UML modeling perspective, what are Java enumeration types good for? That is, what sort of UML diagrams can benefit from enumeration types when implementing them in Java?
b. Consider the concepts of residences and residents. We assume a bi-directional association such that a resident may have multiple residences and a residence may be occupied by multiple residents. The classes for residents and residences will need to provide methods for registration and deregistration. What can possibly go wrong in a Java implementation of this association? That is, what programming errors are you prepared to avoid?
c. Suppose the abovementioned relationship is annotated with cardinality such that each resident has at least one residence. If we assume that this constraint is to be enforced stringently, then it will also affect the construction protocol for residents. How?
d. What sorts of generalizations/specializations are directly supported by UML but require encoding effort by contemporary Java? Identify a sample scenario and sketch a possible encoding.
e. Consider aggregation (or composition) in the sense of “part-of” relationships. Which form of cloning (shallow vs. deep) is appropriate for the compositor class (i.e., the class that represents the whole)? Defend your choice.
f. What rigor is needed in a UML sequence diagram so that it can be turned rather mechanically into a “test case” in the sense of a method body that exercises the scenario?
g. Can you sketch an object model (i.e., class diagram) of basic Nassi-Shneiderman diagrams? That is, devise classes and associations and relationships for the building blocks and the forms of composition in Nassi-Shneiderman diagrams. How is it apparent from the obtained object model that these diagrams are restricted, by definition, to structured programming without “spaghetti capability”? Argue in what sense an object model of flowcharts would fail to possess this desirable property.
5. Predefined types
a. Why is it reasonable that complex numbers are not defined as a primitive type in Java? Please go beyond the universal argument that complex numbers could be derived from existing primitive types, and the implementation could be wrapped up by a user-defined class.
b. Numeric functionality must carefully observe the precision of numeric types as well the out-of-range behavior and the associativity for numeric operations. Provide one test case that shows that associativity of say “*” for doubles matters, i.e., the result of a given computation differs when the default associativity of multiplication is overridden by parentheses.
c. Consider the following loop, which determines an approximation of the machine epsilon for Java’s floating-point arithmetic, i.e., (an approximation of) the difference between 1 and the smallest exactly representable number greater than one:
float machEps = 1.0f;
do {
machEps /= 2.0f;
}
while ((float)(1.0 + (machEps/2.0)) != 1.0);
System.out.println(machEps);
Can you identify a law that must hold for the involved division operation so that this loop terminates? (The fact that precision is finite does not imply termination just by itself.) How would you use the found (approximation of) the machine epsilon in a test that determines whether given floating-point numbers a, b, c, which are assumed to represent the length of the sides in a triangle, are related by the Pythagorean theorem, i.e., whether c2 = a2 + b2 (modulo permutation of a,b,c)? (Be pragmatic! A rigorous approach to limiting numerical errors is beyond the scope of this question.)
d. Built-in Java arrays provide a bounded collection type, i.e., the number of elements in the collection must be fixed at the time of constructing the collection object. Can you think of a way to provide an unbounded collection type (presumably a new class) whose implementation nevertheless leverages Java arrays for storing the elements of the collection? (In fact, collection classes like Vector and ArrayList exploit the idea that you need to recover.)
e. Why is the length of a Java string defined by a method as opposed to a constant? Why is the length of a Java array defined by a constant as opposed to a method?
f. The Java class Math defines a number of common operations for numeric types. For instance, there is an operation abs (for absolute value). Why are these operations defined as static methods (as opposed to regular methods)?
g. Consider the following Java code; the test case completes fine:
Integer i1 = new Integer(42);
Integer i2 = new Integer(42);
String s1 = new String("42");
String s2 = new String("42");
assertTrue(i1!=i2);
assertTrue(s1!=s2);
s1 = s1.intern();
s2 = s2.intern();
assertTrue(s1==s2);
This code basically illustrates that each construction of an Integer object (by wrapping an int) leads unsurprisingly to a new object that is different from any object that possibly wraps the same int. In fact, the situation seems to be very similar for the case of String objects, except that the intern method allows us to map strings to a canonical representation. Here are two questions: (i) What would it take to provide an intern method for Integer objects? (ii) Why is it arguably less beneficial to try working with canonical Integer objects (when compared to the string case)?
6. Implementation of algorithms
a. One corollary of the Böhm/Jacopini Theorem is that for any possible flowchart, it is sufficient to use sequential composition of statements, if-then-else selection and pre-test iteration in order to compose a functionally equivalent flowchart. In fact, one while loop is sufficient (as opposed to any number of loops). Transform the following program accordingly:
int k = 1;
while (k < 10) {
int p = 1;
while (p < 10) {
System.out.println("k:" + k + " p:" + p);
p++;
}
k++;
}
b. What property of “&&” is essential for the following program to work?
String[] x = {"0","1","2","3"};
int i;
for (i = 0; i < 4 && x[i] != null; i++) {}
if (i < 4) x[i] = "42";
c. Suppose “&&” would not be defined by the Java language. Would you be able to define this operator as a (static) method? Please make an attempt and report on your findings.
d. Transform the above program so that you do not rely on the property in question.
e. How would you implement an infinite precision type for natural numbers including simple arithmetic operations as well as conversions to and from int? Provide two solutions: (i) a solution that is strikingly simple in terms of conceptual clarity and thereby easy to prove correct; (ii) a solution that makes an effort to achieve a small memory footprint for huge natural numbers. Both solutions should share an interface.
f. Consider the following program for binary trees; nodes are labeled by strings; there is a left and a right subtree; the method member tests whether a given string occurs as a label in this. Thus:
public class BinTree
{
public String label;
public BinTree left;
public BinTree right;
public boolean member(String s) {
return
(label != null && label.equals(s))
|| (left != null && left.member(s))
|| (right != null && right.member(s));
}
}
Why are the non-null tests essential for the design at hand? Propose a revision of the BinTree class so that these non-null tests can be avoided. Hints: (i) you may want to introduce an extra class; (ii) you may need to make some assumptions (and possibly enforce them) regarding the non-null properties of method and constructor arguments.
g. The member method in the above BinTree class is recursively defined. How can you resort to iteration instead? It is too easy to see that you may want to use a stack object to keep track of nodes, as you are walking down the tree, so that you can return to these nodes later on. So let’s find a better question. Can you propose a modest revision of BinTree such that no object whatsoever needs to be created when the member method is executed? Several solutions come to mind; make sure to pick one that delivers a reentrant member method, i.e., a method that allows for concurrent executions of the method.
Comments
Anonymous
December 01, 2007
本期链接列表的主要内容有：ASP.NET MVC Framework, MVP, 设计模式, Python, 英语学习 :)Anonymous
December 01, 2007
本期链接列表的主要内容有：ASP.NET MVC Framework, MVP, 设计模式, Python, 英语学习 :)Anonymous
May 31, 2008
Recently, I started to re-wire some mildly used parts of my brains to accommodate capabilities for a 1 st year CS course on OO programming and modeling. Long before I joined the faculty in Koblenz, the course had been designed to get students going iAnonymous
June 04, 2008
Recently, I started to re-wire some mildly used parts of my brains to accommodate capabilities for a 1 st year CS course on OO programming and modeling. Long before I joined the faculty in Koblenz, the course had been designed to get students going iAnonymous
July 01, 2008
When I was doing my CS course we had a good curriculum for OO programming. i really loved it very much. Your agenda is very good. I had to read the article again to get more knowledge from it..