| 6.170 | Laboratory in Software Engineering Spring 2004 Quiz Review 1: From Java Syntax to Object Modeling Sunday, February 29, 2004, 7pm-9pm in 34-101 |
Contents:
In Java, every variable has a declaration that indicates its
type. Primitive types such as int, boolean, and
char, define sets of values. All other types defines sets
of objects. Therefore, variables of primitive types contain values,
while variables of all other types, including strings and arrays,
contain references to objects that reside on the heap. Objects can be
created with literals or with the new operator. The
keyword null denotes a value that can be taken on by an object
reference. It means that the reference does not in fact refer to any
object. There is no null object!
Example:
String a = "deeb"; String b = a.toUpperCase (); System.out.println (b);
We can draw the result of the first two statements as an object
diagram.
All objects are either mutable or immutable. The
state of an immutable object never changes, while the state of mutable
objects can change. Strings are immutable. The second statement does
not modify a but it creates a new string object.
When two variables contain references to the same object, they are
called aliases. To determine when two variables are aliases, we
test equality. The built-in == test tells you whether two
references are for the same object, so it is often called a test of
reference equality.
Immutable objects should not be compared to their literal
counterparts or other objects of the same type using ==
if what you want is to check whether they have the same value. You
should use their .equals() method instead.
String aStringLiteral = "abc";
String aStringObject = new String("abc");
String anotherStringObject = new String("abc");
What should be the output of the following statements?
1. aStringLiteral == "abc";
2. aStringLiteral.equals("abc");
3. aStringObject == "abc";
4. aStringObject.equals("abc");
5. aStringLiteral == aStringObject;
6. aStringObject == anotherStringObject;
7. aStringObject.equals(anotherStringObject);
AnswersIn addition to using built-in types, it is also possible
to create new types by declaring new classes. A class
declaration looks as follows:
public class MyClass {
// Fields (also called instance variables)
// Constructors (also called Creators)
// Methods
// - Producers
// - Observers
// - Mutators
}
By default, in Java, classes, fields, and methods are visible to all other classes in the same package. This visibility can be changed with access modifiers: public makes a class, method, or field visible from outside of the package; private constrains the access to the current class only.
One class can be defined as a subclass of another, and can override some of its methods. This is called subclassing or inheritance, and it is a central (although dangerous) feature of object oriented languages.
public class Curve {
private Point startingPoint;
private Point endingPoint;
private double length;
public Curve(Point startingPoint, Point endingPoint, double length) {
this.startingPoint = startingPoint;
this.endingPoint = endingPoint;
this.length = length;
}
}
public class ClosedCurve extends Curve {
protected double area;
public ClosedCurve(Point startingPoint, double length, double area) {
super(startingPoint, startingPoint, length);
this.area = area;
}
public double getArea() {
return area;
}
}
public class Circle extends ClosedCurve {
...
}
When a method operates on Curves, we can pass it in
parameter an instance of Curve or an instance of the
subtypes ClosedCurve or Circle. The method
is polymorphic: it will operate correctly on all these
different types.
Java is a typesafe language, meaning it checks (both at compile-time and at run-time) that all expressions are assigned to variables with valid types. The declared type of a variable is what it appears to be at compile-time. The runtime type of a variable is its actual type when code is executed. For object types, the runtime type must either be the same as the declared type T, one of its subclasses if T is a class, or an implementing class if T is an interface.
Assignment examples:
Object a = new Point(1,2); // safe based on declared type and runtime type Point b = new Point(3,4); // safe based on declared type and runtime type Point c = a; // unsafe based on declared type but safe at runtime Point d = (Point)a; // safe based on declared type and runtime type ClosedCurve d = (ClosedCurve)a; // safe based on declared type but not runtime type ClosedCurve e = new Circle(b,10); // unsafe based on both declared and runtime types
Dynamic dispatch defines how a call o.m() may
actually invoke the code of different methods, all with the same name
m, depending on the runtime type of the receiver object
o.
Tricky dispatching example:
class Parent {
void print() {
System.out.println("Root print");
print2();
}
void print2() { System.out.println("Root print2");}
}
class Child1 extends Parent {
void print2() { System.out.println("Child1 print2");}
}
class Child2 extends Parent {
void print() {
System.out.println("Child2 print");
super.print();
}
void print2() { System.out.println("Child2 print2");}
}
// *** What gets printed by the following ***
class TestDispatching {
public static void main(String[] args) {
Parent p1 = new Child1();
p1.print();
Parent p2 = new Child2();
p2.print();
}
}
Answer:
Root print Child1 print2 Child2 print Root print Child2 print2
A specification of a method consists of several clauses:
The precondition is an obligation on the client (i.e. the caller of the method). It is a condition over the state in which the method is invoked. If the precondition does not hold, the implementation of the method is free to do anything (including not terminating, throwing an exception, returning arbitrary results, making arbitrary modifications, etc.).
The postcondition is an obligation on the implementor of the method. If the precondition holds for the invoking state, the method is obliged to obey the postcondition, by returning appropriate values, throwing specified exceptions, modifying or not modifying objects, and so on. The frame condition is related to the postcondition. It explicitly identifies which objects may be modified. So in fact, the frame condition or modifies clause as it is sometimes called is really an assertion about the objects that are not mentioned. For the ones that are mentioned, a mutation is possible but not necessary; for the ones that are not mentioned, a mutation may not occur.
A postcondition that is weak enough to accept more than one valid output for a single input is called underdetermined or non-deterministic.
We have two conventions for writing specifications in this
course. One is from the Liskov text, and uses just the
requires/modifies/effects clauses described so far. The other
convention is called Javadoc6170, and combines the Liskov clauses with
a standard set of Javadoc tags used to document Java code. The
combined set of tags are:
| tag | argument(s) | Description |
| param | name_description | Describes input parameters, with one line per parameter |
| requires | condition | Declares that condition must hold when the method is called (6.170 extension) |
| modifies | object1, object2,... | Declares that nothing besides the objects mentioned will be modified by the method, as long as the requires clause holds when it is invoked (6.170 extension) |
| effects | condition | Declares that condition will hold at exit from the method, as long as the requires clause holds when it is invoked (6.170 extension). Describe the side-effects the method has on the objects in the modifies clause |
| throws | name_description | Describes exceptions the method may throw, with one clause per exception; this tag is also called exception |
| return | value | Declares that the method returns a value |
Example:
/** * This method takes a list, sorts it, and then performs * a search on it to find the required object, * returning the first index of the object, e, in the sorted * list such that (obj == null ? e == null : obj.equals(e)). * If no such object exists in the list, method returns -1. * * @param list the list to be sorted and searched * @param obj the object to be found in the list * @requires list is not null * @modifies list * @effects sorts list using its natural order * @throws NullPointerException if list is null * @throws ClassCastException if the type of the * specified element is incompatible with this list * @return the first index of the obj in the sorted list, * or -1 if it is not in the list */ public static int sortAndFind(ArrayList list, Object obj);
Suppose you want to substitute one method for another. How do you
compare their specifications? We say that specification A is
stronger than specification B if A is harder to satisfy than B
(that is, if the set of implementations that satisfy A is a subset of
the implementations that satisfy B). More formally, a specification A
is at least as strong as a specification B if:
As an example, let's consider a few possible specificatins for
the sortAndFind method:
These specifications can be ordered from strongest to weakest as: Spec E, Spec C, Spec D, Spec B, Spec A.
The goal of testing is to ensure that a module functions correctly, and fulfills its intended purpose. Testing cannot prove the absence of errors, only their presence. One approach to testing is black-box testing, where a module is tested based only on knowledge of its specification, and not its implementation
If we run the module on every possible input and check each output for correctness, then we are guaranteed that the module is correct. This technique, however, is infeasible in practice because the space of inputs may be infinite. We therefore must select a subset of all possible inputs on which we need to test our module.
Example: How should we test Spec F (returns largest result such that a[result] = val or -1 if no such result)
Answer: (1) Test with a list that contains the object. (2) Test with a list that does not contain the object. (3) Test with a list that contains the object twice. (4) Test with an empty list. (5) Test with a list equal to null. (6) Test with an object equal to null.
There are two main testing strategies. Testing can be performed either bottom-up, in which subpieces are verified before they are assembled into pieces, then those pieces are verified before being put together into even larger components, or top-down, in which the entire system is tested before the pieces are built, and the system is filled in from the root. A bottom-up approach requires a tester to write drivers for each module. A top-down approach requires a tester to write stubs.
Regression testing means re-testing your code after you make a change. This is crucial because it is very easy to introduce a new bug when you fix an old one, but many people don't bother to re-validate their implementation after making corrections, extensions, or other modifications. If tests are easy to run (for instance, you have written a test driver), then regression testing is very easy to do.
Another effective testing strategy is to use assertions. An assertion checks a property and raises an error if the property is not satisfied. These are useful for verifying preconditions, postconditions, and representation invariants.
Set) or it may be domain-specific (e.g.,
Deck) but it should not mix generic and domain-specific
features. Operations should be simple and they should have a
well-defined purpose (not a complex set of special cases). The set of
operations should also be sufficient to do the kinds of computations
clients are likely to want to do.
A good abstract data type should be representation independent. This means that the use of an abstract type is independent of its representation (the actual data structure or data fields used to implement it), so that changes in representation have no effect on code outside the abstract type itself.
Additionally, a good abstract data type should preserve its own invariants. An invariant is a property of a program that is always true. Immutability is an example of invariant. If the code outside of the class can modify the representation directly, we have a representation exposure. A rep exposure can break rep invariants but can also reveal the implementation and break representation independence.
Typical cases of representation exposure are:
public class Period {
private final Date start,end;
public Period(Date start, Date end) {
this.start = start; // WRONG!
this.end = end; // WRONG!
// CORRECT is
// this.start = new Date(start.getTime();
// this.end = new Date(end.getTime();
}
}
public class Period {
...
public Date start() {
return start; // WRONG!
// CORRECT is
// return new Data(start.getTime());
}
}
public class MyList {
private final elts = new List();
...
public Iterator getElements() {
return elts.iterator(); // WRONG!
// Correct: return Collections.unmodifiableCollection(elts).iterator();
When we choose how to implement a data type, we choose its
representation. We have in mind how this representation maps to the
specification. We communicate this information in the abstraction
function. An abstraction function AF maps the concrete representation
of an abstract data type to the abstract value space that the ADT
represents:
AF: R => A
where R is the set of rep values, and A is the set of abstract values. You can think of an element in R as the Java object. A, on the other hand, exists only in our imagination, and has no existence inside the computer.
For example, if we choose to use a string to represent a set of characters, we can show graphically how the space of all strings maps onto the space of character sets, with an arc from a rep value to the abstract value it represents:
Many rep values can map to the same abstract value. Not all rep values are mapped but every abstract value is mapped to. For a rep value r, RI(r) is true if and only if r is mapped by AF.
The abstract values of many abstract data types have a tuple structure at the top level. For example, a line is a pair of points; a mailing address is a number, a street, a city and a zipcode; a URL is a protocol, a host name, and a resource name. In these cases, one can specify a single function that maps representation objects to tuples. This is the approach followed by our textbook. But it s convenient, and perhaps more natural, to break the function into several separate functions, each viewed as defining a specification field.
The abstraction function is then written as:
// Abstraction function // specfield1 = some function of fields // specfield2 = some function of fields
Examples:
/**
* Cons model a stack of integers
* @specfield elts: sequence // the stack of integers
*/
class Cons {
int value;
Cons tail;
// Abstraction function
// elts = [] (if this is null)
= [value]:tail.elts (otherwise)
}
/**
* A IntQueue is a mutable queue of integers.
*
* @specfield elements: sequence // the integers in the queue
* @derivedfield size: int // the size of the queue
* @derivedfield first: int // the first int in the queue
* @derivedfield last: int // the last int in the queue
*/
public class IntQueue {
private Cons front;
private Cons back;
// Abstraction Function
// elements = front:reverse(back)
}
/**
* The Period class is an immutable ADT that represents
* a time interval between two points in time.
*
* @specfield start : date
* @specfield end : date
* @derivedfield duration : integer
*/
public class Period {
private final Date start;
private final Date end;
private final long duration;
// Abstraction Function
// A Period represents the time interval from start to end
A representation invariant, or rep invariant for short, is a constraint that characterizes whether an instance of an abstract data type is well formed, from a representation point of view. You can view it as a function that takes objects of the abstract type and returns true or false depending on whether they are well formed:
RI : Object -> boolean
To argue that every object of the type satisfies the rep invariant, we can use structural induction:
Of course, representation exposure can still cause the representation invariant to be violated.
The representation invariant function is implemented in the
checkRep() method. The latter throws a
RuntimeException when the rep invariant is violated. To
detect errors that would cause the rep invariant to be violated, we
place calls to checkRep at the exit of every public
constructor and at the entry and exit point of every public method.
With this approach, if some bit of code violates the rep invariant,
the error will pop up immediately in a predictable way, instead of at
some undetermined point in the future.
Examples
public class IntQueue {
private Cons front;
private Cons back;
// Representation Invariant
// true
}
public class Period {
private final Date start;
private final Date end;
private final long duration;
// Representation Invariant
// (end.getTime() >= start.getTime()) &&
// ((end.getTime() - start.getTime()) == duration)
In Java, every class extends Object and inherits all its
methods, namely:
public boolean equals(Object o);
public int hashCode();
For equals and hashcode,
the specification requires that the following holds:
equals must define an equivalence relation that
is reflexive, symmetric, and transitive
equals must be consistent: repeated calls to the
method must yield the same result unless the arguments are modified
in between.
x, x.equals(null) should
return false
hashCode must produce the same result for two
objects that are deemed equal by the equals method.
equals it must still meet the specification defined
above. For example:
class Point {
private final int x;
private final int y;
private final String name;
[...]
// WRONG. Breaks Symmetry!!!
public boolean equals(Object o) {
if (!(o instanceof Point))
return false;
Point p = (Point) o;
return (p.x == x) && (p.y == y) && name.startsWith(p.name);
}
// CORRECT
public boolean equals(Object o) {
if (!(o instanceof Point))
return false;
Point p = (Point) o;
return (p.x == x) && (p.y == y) && name.equals(p.name);
}
}
Inheritance can easily break these properties. It is a fundamental
flaw in inheritance. Remember the ColorPoint example:
public class ColorPoint extends Point {
...
// Preserves symmetry but not transitivity!
public boolean equals (Object o) {
if (!(o instanceof Point))
return false;
// if o is a normal Point, do a color-blind compare
if (!(o instanceof ColorPoint))
return super.equals (o);
ColorPoint cp = (ColorPoint) o;
return super.equals (o) && cp.color.equals (color);
}
}
We distinguish two types of equivalence:
With behavioral equivalence, if two objects are equal they remain equal forever. If two objects are not equal they remain unequal forever. There is nothing that can be done to make unequal objects become equal and vice versa. It is not the case with observational equivalence. It is worth noting that for immutable types, both observational and behavioral equivalence are the same, since there are no mutators. Consequently, only when we are implementing a mutable ADT do we have to choose between these two notions of equivalence.
Examples:
Set a,b;
String s1, s2;
[...]
string objects are immutable.
In Java, container classes use equality and hashcode information when they store and retrieve objects. For immutable objects and for mutable objects that implement behavioral equivalence, this works very well. For mutable objects that implement observational equivalence this may cause problems as illustrated by the following example:
Question: Can you guess what the following does?
Set set = new HashSet();
List list = new ArrayList();
list.add("6.170");
list.add("6.004");
list.add("6.003");
set.add(list);
set.contains(list); // what does this return?
list.add("6.033");
set.contains(list); // what does this return?
set.add(list);
System.out.println("set has " + set.size() + " elements");
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
Answer: The first contains() returns true,
the second returns false and the code prints out the following:
set has 2 elements [6.170 6.004 6.003 6.033] [6.170 6.004 6.003 6.004]
Obviously this is bad behavior: a set isn't supposed to have any
duplicates. What went wrong here? When the HashSet
first stored the list, it stored the list using its hash
code. Mutating the list changed that hash code (since lists use
observational equivalence), so that the set was now storing it under
the *wrong* hash code. So we broke the rep invariant of the
HashSet by mutating the list. This is an essential
danger of using observational equivalence for mutable types.
A central issue in designing software is how to decompose a program into parts : executable modules are parts but specifications are also parts. Some benefits of decomposition are: division of labor, reuse, modular analysis, and localized changes.
The decomposition should produce a set of parts all roughly at the same level of abstraction. The decomposition should be centered around data rather than around functions. Coupling measures the strength of bindings between modules (i.e., how much details modules know about each other, how complex their interfaces are, how many modules know about each other). Coupling between the parts should be minimized.
The most basic notion of relationship between parts is the uses relationship. We say that a part A uses a part B if A refers to B in such a way that the meaning of A depends on the meaning of B. When A and B are executable code, the meaning of A is its behavior when executed, so A uses B when the behavior of A depends on the behavior of B.
Uses is a transitive relationship. If A uses B and B uses C, then A depends on both B and C. To avoid the complexity of analyzing long paths of dependencies, we use specifications to block the dependence at one hop. A specification is a description that describes a behavior completely. It does not itself depend on other parts.
A specification cannot be executed so for each specification part, we need at least one implementation part that behaves according to the specification. A dependence diagram has therefore two kinds of arcs. An implementation part may depend on a specification part or it may fulfill or meet a specification part. A single implementation may depend and fulfill several distinct specification parts.
Breaking the uses relationships into "depends" and "meets" has several advantages: it weakens assumptions (a specification says explicitly which aspects of B matter to A), it limits the scope of changes, it simplifies communication between developers of different parts, and it makes it possible to provide multiple implementations of a part.
Because they are always present, we draw dependence diagrams omitting specification parts. We simply assume they are always there. We draw specifications only when we want to make explicit their presence.
Definition summary:
Notation summary and illustration (example taken from lecture notes)
A dependence is a liability. It expands the scope of what needs to be considered when a part is examined. We therefore try to minimize dependences: to decouple parts from one another. A good initial decomposition is a key to a low coupling between parts. Other techniques are: hiding the representation, facade design pattern, polymorphism, and callbacks.
Specifications for ADT's rely on the overview section, and other local specifications, to define a model for object state. Such models are typically relatively simple, and are based on a small set of mathematical concepts.
The situation is not so simple for an entire program, which may contain many classes. How can the state for an entire program be modeled? One way is to use an object model.
An object model consists of a graph and a textual description. The graph contains nodes and edges, the nodes representing the kinds of objects in the program, and the edges representing relations between them. Specifically, each node is a named set of instances. In the model, we draw a box for each node and a directed arrow for each edge.
Notation summary:
Example:
