| 6.170 | Laboratory in Software Engineering Spring 2004 Quiz Review 2: From Object Modeling to Design Patterns Sunday, April 4th, 2004, 3pm-5pm in 34-101 |
Contents:
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:
ConcurrentModificationException's
in the Java Collections API is an example of fail-fast defensive
programming. It is better that an operation fail quickly than
returning meaningless results to the client, which the client assumes
are the result of a correct program execution.
Java 1.4 provides assert statements that cause the
program to fail if the given predicate is false at runtime.
assert (x >= 0); // program fails if x < 0
assert statements also document assumptions the code is
making at any given time. Unlike comments, these statements are
executable so they enforce the assumption at runtime. Assertions can
normally be turned off when the code is shipped, but they are often invaluable
during program debugging.
Assertions should be used in code to test important assumptions that the program relies on. The following are some important invariants that can be asserted:
Many assertion mechanisms, including Java's, are built so that assertions are executed only during the testing and debugging phase. However, disabling assertions causes a program to often have far less error-checking when it needs it most. Most assertions are cheap and should not be disabled in the final release.
Since assertions may be disabled, the correctness of the program should never depend on whether or not the assertion expressions are evaluated. Particularly, the expressions should have no side-effects.
Assertions can clutter code and so must be used judiciously. They
should not be used: to test conditions guaranteed by the compiler
(e.g. assert ((new String()) instanceof String));
external conditions (the state of the network, existence of a file);
or the correctness of user input. Assertions test the internal state
of your program to see if it is within the bounds of the intended
specifications.
When an exception is thrown (e.g. an assertion fails, or explicitly
using the throw statement) control is passed to the
nearest enclosing exception handler--the catch clause of a try-catch
block. An exception can cause control to pass out of the current
method, to a procedure higher on the call stack. Exceptions are passed
upward through the call stack until either a handler is found or the
top level is reached, in which case the thread terminates and
a stack trace is printed out.
try {
// code that throws an exception
} catch (IOException ioe) { System.out.println("I/O exception");
} catch (Exception e) {
System.out.println("general exception");
}
The first matching exception handler is selected to be
executed, given the runtime type of the thrown exception. For
instance, if an IOException, or a subclass, was thrown in
the try above the first handler will be executed, for
other Exception subclasses, the second handler will be
executed. If we reverse the order of the catch clauses, the compiler
will complain that the exception handler code for IOException
will never be reached.
requires clauses make a method partial, undefined
for some inputs. Whenever possible, it is better to make the method a
total function by using exceptions. A requires clause can
be replaced by a throws clause; an exception is thrown
(e.g. IllegalArgumentException) whenever some
precondition is violated. The client can now depend on some specific
behaviour when something unexpected happens.
Many methods may have special results that occur under some
circumstances. For instance a find() method that searches
an array and returns the (integer) index of the desired element may
need to notify the client about when the element is not present. Also,
a quadratic solver that returns a double might need to
handle the special case when the solution is a complex number.
It is possible to handle these cases by using special return values
(-1 for find or Double.NaN for
the quadratic solver), but one could also use specialized
Exception subclasses to handle these special cases
(e.g. NoSuchElementException,
ComplexResultException). Exceptions are generally far less
efficient than special return values, but before using the later
approach, the following two questions are important:
HashTable's return null when a
get for a non-existent element is called, but also allow
the storage of null elements. This is a problem.Throwable in Java can be
thrown (using throw) and caught using the Java exception
mechanisms. Depending on its parents in the class hierarchy, an
exception class is either a checked exception or an
unchecked exception. Both behave the same at compile time, but
the compiler enforces some additional constraints for code that uses
checked exceptions.
For any checked exceptions thrown, the Java compiler requires that a
throws clause be present in the method signature. The
compiler also makes sure you have a catch clause for that
exception, surrounding any such method call. So, if a method calls
another method that throws a checked exception, the caller must either
handle that exception or declare that exception in its own method
signature. This can be tedious, but is extremely useful because it
ensures that any exceptions that are expected to occur
(e.g. FileNotFoundException) will be handled.
Unchecked exceptions are not enforced by the compiler, and may not be
listed in the method signature. Examples are
IllegalArgumentException,
NullPointerException, and
ClassCastException. Even though Java method signatures do not
require the inclusion of unchecked exceptions, they should be documented in
the specifications.
Exception classes that derive from Error (reserved for
JVM errors) or RuntimeException are unchecked. All other classes
derived from Throwable are checked exceptions.
One simple rule is to always use unchecked exceptions for program
failures (e.g. broken rep-invariants) and checked exceptions for
special case results (e.g. FileNotFoundException).
Black-box testing involves testing a module through its specifications alone. One way of doing this is by checking to see if the input-output relationship embodied by the specifications holds for all possible inputs to the procedure. However, it is usually infeasible to test on the set of all possible inputs and as a result, we need to try and focus our tests on the most likely problem spots. We do this by:
static void appendVector(ArrayList v1, ArrayList v2) {
if (v1 == null || v2 == null)
throw new NullPointerException("input arraylists cannot be null");
while (v2.size() > 0) {
v1.add(v2.get(v2.size() - 1));
v2.remove(v2.size() - 1);
}
}
Test-driven development: Procedural black-box tests depend only on the specifications for a procedure and are completely independent of implementation-level details. For this reason it is a good idea to write these tests before the implementation is concrete so as to preserve any bias arising from knowledge of the internal workings of the procedure.
Glass-box testing involves testing a module's internal program structure exhaustively. Black-box testing may not exercise all lines of code by virtue of the fact that it ignores the internals of procedures and focuses only on the specifications. Glass-box testing remedies this by using knowledge of the program structure to provide maximum coverage of the code.
Ideally, glass-box testing should be path-complete, i.e., it should run all possible paths through a program. Since there are often an infinite number of paths through a program, we must settle for testing path boundary conditions:
Invalid inputs: A program should also be tested on inputs outside its expected input space. A number of bugs involve callers accidentally (or intentionally, in the case of hackers) failing to obey a "requires" clause and thus causing an error. For this reason, it is important to test the behaviour of the code in response to incorrect inputs. The worst way to deal with such inputs is to do nothing and return a wrong answer. Ideally, when tested, the program should check the "requires" clause and signal some kind of an error.
In order to test the type hierarchy for any given subtype, we must test:
It is important to note that although the supertype should have its own glass-box test suite for testing its correctness, this is not needed to test the type hierarchy for its subtypes.
To test an abstract supertype class itself, one should provide a stub implementation of a subtype: one that provides trivial implementations of the supertype's abstract methods. This stub can then be used to test the supertype's non-abstract methods. Full subtype implementations should also test their behavior through the supertype's spec.
Unit tests serve to test a single module in isolation. While testing large programs, unit tests should be written for each class and every static procedure in the system. Initially, black-box tests should be written as soon as the specification for a module exists. Once the implementation of the module is complete, additional glass-box tests should be written to test its implementation-specific behaviour.
Integration tests serve to test a group of modules interfacing to one another. Integration tests help isolate problems related to the interconnection of various modules. These problems primarily arise from vague specifications leading to assumptions between modules that are not shared universally.
Integration tests can be done recursively upwards, as larger modules make use of more and more smaller ones. At the top-level, this is called a system test and should be run automatically and regularly in any software engineering environment.
Regression tests involve testing every component after each build or bug-fix. These are necessary to ensure changes made to one module do not cause something that was previously working to break down. Regression tests are especially useful since whatever changes were made are fresh on the engineer's mind, so bugs can be tracked down more quickly.
Automatic testing systems are vital to make regression testing easy and fast. When a bug is found, tests should be written immediately that fail with the bug and pass once the bug is fixed.
Subtyping in Java can be achieved by using the extends
keyword to extend a superclass and the implements keyword
when extending an interface. True subtyping is not enforced by Java
language mechanisms, particularly because Java only enforces method
signatures, not specifications.
Subtypes in Java can override a superclass/interface's methods,
providing their own implementation. Regardless of the declared type of
a variable there is no way for an external client to invoke any other
version of an overridden method other than that associated with the
run-time type of that object. So, for instance, if an object is of
type ArrayList, invoking the equals() method
always transfers control to the implementation of
equals() in the ArrayList class. Never to
the equals() defined in Object, regardless
of the type of the reference used to make the invocation.
The super keyword can be used within a subclass's code
to invoke a parent's method. Since Java does not allow multiple
superclasses, super always refers to method
implementations in the parent class. ArrayList code can
use super.equals(x) to call Object's
equals() method implementation.
Subtypes can also change the specifications for overridden methods. However, if the intent is to produce a true subtype, the new specification must be stronger than the supertype's specification (relaxing the requirements or promising more in the effects). The substitution principle is key in establishing the true subtype relationship.
Subclassing in Java has a number of advantages in the realm of code reuse: subclasses need not reimplement unchanged fields and methods; clients don't need to change code when new subclasses are added; resulting designs can have better modularity and reduced complexity.
It is important to realize that subtyping is subtle, but subclassing without subtyping is dangerous.
Subtyping relationships can be used to reduce module dependencies. For
example, code that depends on equals() only depends on
Object and not on every class whose equals()
method implementation it actually invokes.
abstract
classes and interfaces. The difference between the two is
that an interface contains only specifications for
methods, never any member fields or method implementations; while
abstract classes can contain implementations for some methods and
definitions of fields. In an abstract class some methods may be left
without implementations, a subclass must provide an
implementation for those methods. A class implementing an interface
must provide implementations for all methods specified in that
interface.
The new keyword can never be used
to create an object using an interface or abstract class as the type
argument.
Java allows a class to implement multiple interfaces, but
each class can only extend a single superclass. So
existing classes can be retrofitted to implement interfaces but not,
in general, a new abstract class. The advantage of using an abstract
class is the ability to provide implementations for some methods,
facilitating code reuse.
As in the Java collections API, one can provide skeletal
implementations of each non-trivial interface
(e.g. AbstractList) to combine
the virtues of both interfaces and abstract classes.
For top-level classes, only public and package-private modifiers are valid. The rule of thumb is to make each class or member as inaccessible as possible.
If a method overrides a superclass method, the subclass cannot
redefine it to have a reduced accessibility (trying to define a method
that is public in the superclass as being
private will result in a compile-time error if the rest
of the signature is unchanged)
When using composition instead of inheritance, the new class may want
to provide access to some methods of the older
class. Forwarding methods can be provided which invoke methods
on the internal object in response to external calls. For instance, a
class that composes a HashSet may also define a
size() method which is implemented simply by forwarding
control, by calling the internal HashSet's
size() method.
Stack extends
Vector; Properties extends
HashTable).
Inheritance is a powerful tool for code reuse, but isn't always appropriate. It is safe to use within a package when both superclass and subclass are under the control of the same programmer. The danger is that inheritance breaks encapsulation: a subclass depends on the implementation details of the superclass. If these details change, the subclass implementation may break too. Sometimes classes that are intended to be extended can be designed appropriately, but this requires careful design and documentation.
If A is not a true subtype of B, but B is merely a detail of A's implementation, composition and forwarding should be used in A instead of inheritance.
A design pattern is:
The third point above is worth stressing. You may feel that some of the design patterns seem obvious or simple and also that you have used design patterns without realizing you were doing so. That is the whole point! Design patterns are nice when they are simple and most people can think of them on their own if needed. It is still important to study design patterns so that you have a common vocabulary that you can use to quickly convey your ideas to other engineers when discussing software design.
Design patterns are not free: a design with a pattern is not necessarily better than a design without a pattern. Usually a pattern can solve one nagging problem but sacrifices some other convenience. A static factory method allows interning, but then makes subclassing more difficult! A singleton may seem nice and cool, but what if you really could use more than one instance of the object? A visitor may allow double-dispatch, but sometimes operations are context-sensitive and makes writing each visitor much more difficult.
Design patterns should only be introduced into your design or implementation after you have noticed a problem. After you have determined that there is a problem, and investigated the source of the problem, looking at a design patterns reference will often help you to solve your problem without having to reinvent the wheel.
Premature inclusion of design patterns into the program design should be avoided much like premature program optimization.
The Singleton pattern ensures that a class has at most one instance. The Singleton provides a global point of access to the class. There is at most one instance rather than exactly one because the instance can be created lazily, when it is first requested. An IDE, for example, may want to ensure that at most one instance of the debugger exists at any time. A debugger object may actually be an expensive object and allocated only when it is first requested.
Some other advantages of the singleton pattern are:
getInstance()
method and return subtypes.
new operator always returns an object of
the type passed in as the argument to it; this behaviour may not
always be appropriate. Returning a subtype would still be type-correct
and may be more appropriate.
Sometimes when constructing an object, one might want the input
parameters to determine the runtime type of the object returned. For
instance, suppose one wanted to create a new Image from a
file. One might want the returned object to be of a type corresponding
to the file format of that image (e.g. JpegImage,
GIFImage). One could define a factory method
loadImageFromFile() with the declared return type of
Image but with a runtime return type that depended on the
actual format of the file being loaded from.
Another intent of the factory pattern is to define an interface for creating an object which lets subclasses decide which classes to instantiate. See the lecture 17 notes and recitation 7 notes for further examples of this usage of the factory design pattern.
If there are many objects to construct, including factory methods in each class can bloat the code and make it hard to change. Sibling subclasses cannot easily share the same factory method. A factory object class is a class that encapsulates factory methods. Since this class can be subclassed to vary the behaviour of the various factory methods, this is probably the most flexible creational design pattern around.
Another restriction of Java constructors the factory pattern overcomes
is that the new operator always creates a new instance of
the class, never returning an older one. Factory methods can reuse existing
objects, which can be particularly helpful with costly immutable classes.
BipartiteGraphTestDriver class
from the problem sets.
Adaptor: adaptors change the interface of a class without changing its basic functionality. For example, one use might be to provide interoperability between two geometry packages, one measuring angles in radians and the other in degrees.
Decorator: a decorator extends functionality while
maintaining the same interface. Typically a decorator does not change
existing functionality, but only adds to it, so that objects of the
resulting class behave exactly like the original ones, but do
something extra. Sounds like subclassing, but not every instance of
subclassing is a decoration---decorators don't usually provide
different implementations for superclass methods, they reuse the
superclass method, wrapping it with extra functionality. An example is
a BorderedWindow decorator for a Window,
with the decorator just adding the functionality of drawing a border
around the window after Window's drawing code finishes.
Proxy: is a wrapper pattern that has the same interface and functionality as the class it wraps. This can be useful if the object being wrapped needs to be accessed in a stylized or complicated way. Proxy capabilities are particularly useful if the client does not know that the underlying object being manipulated has special properties. For instance, a proxy can access a remote object by converting local method invocations into remote procedure calls over the network; in multi-threaded programs, proxies can be used to lock objects; etc.
Consider a spreadsheet system that includes embedded graphs that view the data contained in the cells. In this system, as a user changes the data in the cells, the graphs should be notified of the changes and they should update their diagrams appropriately. The subject is the data model and the observers are the embedded graphs. The model generates events whenever a cell is edited.
The benefit of the Observer pattern is that it decouples the observer from the subject. The subject doesn't need to know anything special about its observers. Instead, the subject simply allows observers to subscribe. When the subject generates an event, it simply passes the event to each of its observers.
The subject can generate events which contain information about what changed (the push model; e.g. "cell E1's contents changed to 10.0") or the subject can just produce a generic update message (the pull model; e.g. "some cell changed") and the observers must call methods on the subject to find out what changed.
A blackboard is a pool of messages which is readable and writable by all processes. When an event occurs that might be of interest to someone else, some process knowledgeable about that event's occurrence adds a message announcing that event to the blackboard. Other processes can read the blackboard, filter out the events based on their content, reacting only to those events they are interested in.
The Interpreter design pattern is being used if the operation that needs to traverse the composite hierarchy is declared as a method in the composite base class. Composite nodes recursively call the operation an their parts and leaves terminate the recursion.
The trouble with the interpreter pattern arises when we need to add a new operation to the hierarchy. All the classes in the hierarchy must be updated to include the new operation. An alternative is procedural traversal or the visitor design pattern.
The Visitor pattern encodes traversal over a composite
hierarchy. Each operation is represented by a class (e.g. class
CalculateWeight implements BicycleVistor), called a visitor. Composite
classes assume responsible for traversal of the visitor object through
the hierarchy:
composite.accept(visitor)).
part.accept(visitor)).
Wheel,
visitor.forWheel(this) would be called; when it reached a
Frame, the visitor.forFrame(this) method
would be called; and so on. There would be a different
Visitor interface for each composite type hierarchy that
would define the appropriate methods.
In building UI's with high usability, it to try to understand users using the Model Human Processor (MHP) abstraction. It is a high-level look at the cognitive abilities of a human being. The MHP abstraction has several different kinds of processors and memories:
MHP processors have cycle times, the time to accept one input and produce one output. Cycle times in the MHP model are derived from psychological studies. The following are some important results from the MHP model:
Perceptual Fusion: Two stimuli within the same perceptual processor cycle (typically around 100ms, but may be as low as 50ms or as high as 200ms) appear fused. Perceptual fusion is responsible for the way we perceive a sequence of movie frames as a moving picture. Sometimes when the delay is long enough between two UI events, and the perceptual fusion is broken, users can become annoyed on a subconscious or conscious level, and might just think their computer is running slow.
Fitt's Law: The time T to move your hand to a target of
size S at distance D away is T = a + log (D/S + .5). In
general terms, it means as the target gets smaller and/or farther
away, the time to hit it with a mouse pointer takes longer, and the
probability of overshooting it increases. One implication is that
targets at screen edges are easy to hit, since the you can't overshoot
them. Another is that hierarchal menus are hard to hit, since it is
relatively easy to overshoot them and in many UI's those menus close
quickly when the mouse pointer moves away.
Color: A significant fraction of human beings are affected by color blindness, so it is essential to take into account when you are deciding what color to use in a user interface. Don't depend on color distinctions to convey information (e.g. a red wavy underline under a word is a spelling mistake, a green one is grammatical error). Chromatic aberrations can occur because of the structure of human eyes. For example, edges between widely separated wavelengths, e.g. blue and red, simply cannot be focused.
The following heuristics or Usability guidelines can be used to drive UI design:
User UI Testing: Starting with a UI prototype, write up some representative tasks (short but not trivial, e.g. "add this meeting to the calendar"), then find some representative users (3 is often enough) and watch them try to do the tasks with the given prototype. Developers know too much about the underlying system, so they're not good representative users. The following are some things to keep in mind during user testing:
Waterfall Model: This model puts a lot of discipline on developers to think first and code second. This design process stipulates a sequence of stages in the program's development:
Spiral Model: The waterfall model runs into trouble when the requirements are not well defined (e.g. a missing requirement may not be discovered till the acceptance test). For risky projects, the spiral model works better, using an iterative approach to improve the design and incorporate missing requirements. The spiral model has a cycle of phases:
Test-Driven Development: In test-driven development, coding is preceded by the generation of black-box tests from the specifications, so that the code can be validated as it is developed.
Last modified: Sun Apr 4 1:09:10 EST 2004 by asfand