13/02/2012

CS/ENGRD 2110
Object-Oriented Programming
and Data Structures
Spring 2012
Thorsten Joachims

Lecture 7: Software Design

Software Engineering
The art by which we start with a problem
statement and gradually evolve a solution.
There are whole books on this topic and most
companies try to use a fairly uniform
approach that all employees are expected to
follow.
The IDE can help by standardizing the steps.

Top-Down Design
Building a Search Engine:

Bottom-Up Design
Just the opposite: start with parts:

Search Engine

Crawler
Queue

HTTP
Client

Search Engine

Indexer
Database

Hashmap

Inverted
Index
List

Ranking
Function
Pagerank

User
Interface
Spelling
Correction

Crawler
HTTP
Server

Term
Weighting

Refine the design at each step

Decomposition / Divide and Conquer

Top-Down vs. Bottom-Up

Is one of these ways better? Not really!
Its sometimes good to alternate
By coming to a problem from multiple angles you might
notice something you had previously overlooked
Not the only ways to go about it

With Top-Down its harder to test early because

parts needed may not have been designed yet
With Bottom-Up, you may end up needing
things different from how you built them

Queue

HTTP
Client

User
Interface

Indexer
Database

Hashmap

Inverted
Index

Ranking
Function

List

Pagerank

Spelling
Correction

HTTP
Server

Term
Weighting

Composition
Build-It-Yourself (e.g. IKEA furniture)

Software Process
For simple programs, a simple process
Waterfall

But to use this process, you need to be sure that

the requirements are fixed and well understood!
Many software problems are not like that
Often customer refines the requirements when you try to
deliver the initial solution!

13/02/2012

Incremental & Iterative

Deliver versions of the system in several small cycles:

TESTING AND
TEST-DRIVEN DEVELOPMENT

Recognizes that for some settings, software

development is like gardening.
You plant seeds see what does well then replace the
plants that did poorly.

The Importance of Testing

Famous last words
Its all done, I just have not tested it yet.

Many people
Write code without being sure it will work
Press run and pray
If it fails, they change something random
Never work, and ruins weekend social plans.

The Example
A collection class SmallSet
containing up to N objects (hence small)
typical operations:
add

adds item

contains

is item in the set?

size

# items

well implement add(), size()

Test-Driven Development!

Test Driven Development

Well go about in small iterations
1.add a test
2.run all tests and watch the new one fail
3.make a small change
4.run all tests and see them all succeed
5.refactor (as needed)

Well use JUnit

JUnit
What do JUnit tests look like?
SmallSet.java
package edu.cornell.cs.cs2110;

SmallSetTest.java
package edu.cornell.cs.cs2110;

public class SmallSet {

...
}

import org.junit.Test;
import static org.junit.Assert.*;
public class SmallSetTest {
@Test public void testFoo() {
SmallSet s = new SmallSet();
...
assertTrue(...);
}
@Test public void testBar() {
...
}
}

13/02/2012

A List of Tests
We start by thinking about how to test,
not how to implement

size=0 on empty set

size=N after adding N distinct elements
adding element already in set doesnt change size
throw exception if adding too many
...

Each test verifies a certain feature

A First Test
We pick a feature and test it:
SmallSet
class SmallSet {}
SmallSetTest
class SmallSetTest {
@Test public void testEmptySetSize() {
SmallSet s = new SmallSet();
assertEquals(0, s.size());
}
}

This doesnt compile: size()is undefined

But thats all right: weve started designing the
interface by using it

Red Bar
A test can be defined before the code is written

Green Bar
Whats the simplest way to make a test pass?
SmallSet
class SmallSet {
public int size() {
return 0;
}
}

SmallSet
class SmallSet {
public int size() {
return 42;
}
}

Running the test

yields a red bar
indicating failure:

Fake it till you make it

Re-running yields the legendary JUnit Green
Bar:

If we add the size function and re-run the the

test, it works!

Move on with the next feature

Adding Items
To implement adding items, we first test for it:
SmallSetTest
class SmallSetTest {
@Test public void testEmptySetSize() ...
@Test public void testAddOne() {
SmallSet s = new SmallSet();
s.add(new Object());
assertEquals(1, s.size());
}
}

add() is undefined, so to run the test we

define it: SmallSet
public int size() ...

Adding Items
The test now fails as expected:
It seems obvious we need to count the number
of items: SmallSet
private int _size = 0;
public int size() {
return 0;
return _size;
}
public void add(Object o) {
++_size;
}

And we get a green bar:

public void add(Object o) {}

13/02/2012

Adding Something Again

So what if we added an item already in the set?
SmallSetTest
class SmallSetTest {
@Test public void testEmptySetSize() ...
@Test public void testAddOne() ...
@Test public void testAddAlreadyInSet() {
SmallSet s = new SmallSet();
Object o = new Object();
s.add(o);
s.add(o);
assertEquals(1, s.size());
}
}

As expected, the test fails...

Remember that Item?...

We need to remember which items are in the
set... SmallSet
private int _size = 0;
public static final int MAX = 10;
private Object _items[] = new Object[MAX];
...
public void add(Object o) {
for (int i=0; i < MAX; i++) {
if (_items[i] == o) {
return;
}
}
_items[_size] = o;
++_size;
}

All tests pass, so we can refactor that loop...

Refactoring

Too Many

FOR-loop doesnt speak to us as it could...

What if we try to add more than SmallSet can hold?

SmallSet (before)
public void add(Object o) {
for (int i=0; i < MAX; i++) {
if (_items[i] == o) {
return;
}
}
_items[_size] = o;
++_size;
}

SmallSet (after)
private boolean inSet(Object o) {
for (int i=0; i < MAX; i++) {
if (_items[i] == o) {
return true;
}
}
return false;
}
public void add(Object o) {
if (!inSet(o)) {
_items[_size] = o;
++_size;
}
}

All tests still pass, so we didnt break it!

Size Matters
We first have add() check the size,
SmallSet

public void add(Object o) {

if (!inSet(o) && _size < MAX) {
_items[_size] = o;
++_size;
}
}

... re-run the tests, check for green,

define our own exception...
SmallSetFullException
public class SmallSetFullException extends Error {}

... re-run the tests, check for green,

and...

SmallSetTest
...
@Test public void testAddTooMany() {
SmallSet s = new SmallSet();
for (int i=0; i < SmallSet.MAX; i++) {
s.add(new Object());
}
s.add(new Object());
}

The test fails with an error:

ArrayIndexOutOfBoundsException

We know why this occurred, but it should bother

us: ArrayIndex isnt a sensible error for a set

Testing for Exceptions

... finally test for our exception:
SmallSetTest
@Test public void testAddTooMany() {
SmallSet s = new SmallSet();
for (int i=0; i < SmallSet.MAX; i++) {
s.add(new Object());
}
try {
s.add(new Object());
fail(SmallSetFullException expected);
}
catch (SmallSetFullException e) {}
}

The test fails as expected,

so now we fix it...

13/02/2012

Testing for Exceptions

... so now we modify add() to throw:

After all Tests are Passed

Is the code is correct?
Yes, if we wrote the right tests.

Is the code efficient?

SmallSet

public void add(Object o) {

if (!inSet(o) && _size < MAX) {
if (_size >= MAX) {
throw new SmallSetFullException();
}
_items[_size] = o;
++_size;
}
}

Probably used simplest solution first.

Replace simple data structures with better data structures.
New ideas on how to compute the same while doing less work.

Is the code readable, elegant, and easy to maintain?

It is very common to find some chunk of working code, make a replica, and
then edit the replica.
But this makes your software fragile
Later changes have to be done on all instances, or
some become inconsistent

Duplication can arise in many ways:

All tests now pass, so were done:

constants (repeated magic numbers)

code vs. comment
within an objects state
...

DRY Principle
Dont Repeat Yourself
A nice goal is to have each piece of
knowledge live in one place
But dont go crazy over it
DRYing up at any cost can increase dependencies
between code
3 strikes and you refactor (i.e., clean up)

Simple Refactoring
Renaming variables, methods, classes for readability.
Explicitly defining constants:
public double weight(double mass) {
return mass * 9.80665;
}

public double totalArea() {

...
// now add the circle
area += PI * pow(radius,2);
...
}

public double totalArea() {

...
area += circleArea(radius);
...
}

public double weight(double mass) {

return mass * GRAVITY;
}

If your application later gets used as part of a Nasa mission

to Mars, it wont make mistakes
Every place that the gravitational constant shows up in your
program a reader will realize that this is what she is looking
at
The compiler may actually produce better code

Extract Method
A comment explaining what is being done
usually indicates the need to extract a method

static final double GRAVITY = 9.80665;

Extract Method
Simplifying conditionals with Extract
Method
before
if (date.before(SUMMER_START) || date.after(SUMMER_END)) {
charge = quantity * _winterRate + _winterServiceCharge;
}
else {
charge = quantity * _summerRate;
}

private double circleArea(double radius) {

return PI * pow(radius, 2);
}

after

One of the most common refactorings

if (isSummer(date)) {
charge = summerCharge(quantity);
}
else {
charge = winterCharge(quantity);
}

13/02/2012

Review
Started with a to do list of tests / features
could have been expanded
as we thought of more tests / features

Added features in small iterations

Is testing obligatory?
When you write code in professional settings
with teammates, definitely!
In such settings, failing to test your code just means
you are inflicting errors you could have caught on
teammates!
People get fired for this sort of thing!
So in industry test or perish!

But what if code is just for yourself?

a feature without a test doesnt exist

Fixing a Bug
What if after releasing we found a bug?

Testing can still help you debug, and if you go to the

trouble of doing the test, JUnit helps you keep it for
re-use later.
I have never written a program that was correct
before I tested and debugged it. Prof. Joachims

A bug can reveal a missing test

but can also reveal that the specification was
faulty in the first place, or incomplete
Code evolves and some changing conditions can
trigger buggy behavior
This isnt your fault or the clients fault but finger
pointing is common

Great testing dramatically reduces bug rates

And can make fixing bugs way easier
But cant solve everything: Paradise isnt attainable in
the software industry
Famous last words: It works!

Reasons for TDD

By writing the tests first, we

test the tests

design the interface by using it
ensure the code is testable
ensure good test coverage

By looking for the simplest way to make

tests pass,
the code becomes as simple as possible, but no
simpler
may be simpler than you thought!

Not the Whole Story

Theres a lot more worth knowing about TDD
What to test / not to test
e.g.: external libraries?

How to refactor tests

Fixtures
Mock Objects
Crash Test Dummies
...
Beck, Kent: Test-Driven Development: By Example

13/02/2012

How people write really big programs

When applications are small, you can understand
every element of the system
But as systems get very large and complex, you
increasingly need to think in terms of interfaces,
documentation that defines how modules work,
and your code is more fragmented
This forces you into a more experimental style

Junit testing isnt enough

For example, many systems suffer from leaks
Such as adding more and more objects to an ArrayList
The amount of memory just grows and grows

Some systems have issues triggered only in big

deployments, like cloud computing settings
Sometimes the application specification was flawed, and
a correct implementation of the specification will look
erroneous to the end user
But a thorough test plan can reveal all such problems

Why is Q/A a cycle?

Each new revision may fix bugs but could also
break things that were previously working
Moreover, during the lifetime of a complex
application, new features will often be added and
those can also require Q/A
Thus companies think of software as having a very
long life cycle. Developing the first version is
only the beginning of a long road!

Testing is a part of that style!

Once you no longer know how big parts of the
system even work (or if they work), you instead
begin to think in terms of
Code youve written yourself. You tested it and know
that it works!
Modules you make use of. You wrote experiments to
confirm that they work the way you need them to
work
Tests of the entire complete system, to detect issues
visible only when the whole thing is running or only
under heavy load

The Q/A cycle

Real companies have quality assurance teams
They take the code and refuse to listen to all the
long-winded explanations of why it works
Then they do their own, independent, testing
And then they send back the broken code with a long
list of known bugs!
Separating development from Q/A really helps

Even with fantastic Q/A

The best code written by professionals will still have
some rate of bugs
They reflect design oversights, or bugs that Q/A somehow
didnt catch
Evolutionary change in requirements
Incompatibilities between modules developed by different
people, or enhancements made by people who didnt fully
understand the original logic

So never believe that software will be flawless

Our goal in cs2110 is to do as well as possible
In later CS courses well study fault tolerance!