2911, the tl;dr

Software Design Principles

Structured v OO-Design

  • Structured design focuses on top-down development
    • what is the function of the system
    • decomposed into different levels of detail
    • each function is broken into sub-functions
    • dataflow models focus on message passing between different functions at the same level
  • OO design focuses on dependencies between software abstractions
    • class-based design models a system as a collection of interacting objects
    • overall system is a collection of services provided by the objects
    • not a single top-level function

Abstraction

Abstraction is inherent in all modelling/design; we can't describe all aspects, and users only need to know interfaces (not internals).

We use ADTs to provide a collection of operations; an abstraction of a real-world entity into update/query/creation operations (data representation irrelevant).

Known as dependency inversion:

  • In structured design top-level functions are decomposed into lower level functions, and the meaning of them is hence defined in terms of lower components.
  • Hence top-level depends on lower-level.
  • Lower-level is more likely to change, hence why we abstract away the details, making high-level less likely to change.

Modularity

Managing software dependencies is done through modularity. A software module groups related functionality (high cohesion) - strongly related services should be together so as to reduce dependencies, but unrelated services should be separated out to make it as clean as possible.

Keeping interfaces small and simple helps achieve weak coupling

  • Weak/Low Coupling implies few dependencies between different modules
    • allows one module to use services of another (or many many others)

Encapsulation

Encapsulation are techniques for achieving modularity and abstraction

By hiding information, utilising private/public (so clients only see public) and ensuring data is only accessed via methods we can make code cleaner.

Ideally all objects are accessed via an Interface, rather than a Class.

Interfaces

  • are ADTs
  • do not declare fields or implement code

Classes

  • implement ADTs (or don't and are just objects)
  • define various features of objects, such as
    • properties and accessor methods
    • update methods
  • classes are defined as distinct by distinguishing features
  • if the features of one class of objects are a subset of the features of a second class of objects then the second class is a subclass of the first
  • classes are immutable
    • can't change an object into a new object (e.g. boy class into man class)
    • perhaps don't need a new class for boy, just an age feature in a man class? (male v female classes fix gender though)

OO-Modelling

  • is-a = partial ordering
  • is how we do subtyping (e.g. man is a person)
  • has-a = associations
  • is how we do attributes (e.g. man has a name)

Implements v Extends

The point of implements and extends (and abstract - later) is to provide modularity and optimal code re-use, and implicit organisation/hierarchy within the types and subtypes.

  • Classes implement 0+ interfaces
  • Classes extend 0 or 1 other classes (e.g. class black cat extends class cat)
  • Interfaces extend 0+ interfaces

Subtype polymorphism

The type of an object being determined by the relationships between all the things it inherits, is called subtype polymorphism.

Override

Subclasses can override superclass methods (not fields) with their own code.

Super

Calling super() inside a function calls the superclass's version of that function and returns that, allowing it to be built upon (e.g. if you want to use that information, rather than directly replacing it).

Super is also often used in subclass constructors, where a new supertype is all that is needed.

Dynamic v Static Binding

  • If the compiler can locate what code a method call refers to at compile-time it is statically bound
  • If the compiler cannot locate it until run-time it is dynamically bound
    • For instance if a function takes in X x and calls x.method(), if there are subclasses of x we do not know exactly which code will be used for x.method(), as it is not fixed exactly what object type X is.
    • This allows code reuse (flexibility of type - used in diff. circumstances)

Abstract Classes

To extract out common code, create an abstract class. For an interface that will have 50% of its methods implemented in the same way always, and the other 50% implemented differently depending on the implementation chosen, create an abstract class with the first 50%.

  • Is a class/method modifier (public abstract class)
  • Methods can be abstract; they have no code and must be implemented in a sub-class
  • Non-abstract methods in abstract classes are implemented

Example

Screen%20Shot%202012-10-29%20at%207.37.02%20PM.png

OO Design Techniques

  • Using the following introductory methods to address typical problems and use a standard way of designing classes
  • Designing for Reuse
    • Extensible designs
    • Design to interfaces, not classes
    • Liskov substitutability principle
      • subtype behaviours should be consistent with the inherited behaviours
      • often we just extend inherited code with additional behaviour
    • Open-Closed Principle
      • classes should be closed to clients (private)
      • classes should be open for extension and customisation (via subclasses)
      • clients can rely on the specification, implementation is encapsulated
      • inheritance gives access to internals of an implementation (subclasses may need to be able to edit/override info (protected))
  • Refactoring Designs
    • When they get too complex, separate them out

CRC Cards

  • Class
    • Objects in a system
  • Responsibility
    • Roles and features of each object
  • Collaboration
    • Identify interactions between classes
  • quick first-cut design technique
  • classes are drawn in boxes
  • class associations are drawn with lines that connect the class boxes

Screen%20Shot%202012-10-29%20at%207.51.25%20PM.png

Object Diagrams

  • objects are vertices (or nodes) of graph
  • references are edges of graph (changes as objects link to other objects)
  • provide a dynamic view
    • useful for understanding possible structures
    • not useful for specifying allowed structures

Class Diagrams

  • focus on modelling relationships between different objects
  • directed edges with open triangular arrowheads indicate a sub/superclass relationship
  • italics denote interfaces or abstract classes, they have no direct object instances

Screen%20Shot%202012-10-29%20at%207.12.36%20PM.png

Design by Contract

Using Java Modelling Language we can place restraints on allowable states of objects; e.g. a 'day' field must be from 1 to 31, for instance.

Writing these in notation is good for standards, but we also need to implement these with asserts or exceptions in our code.

int /*@spec_public@*/ day;
/*@invariant 1 <= day && day <= 31; @*/ //class invariant
  • state-based specification of objects
  • invariant constraints allowable states
  • preconditions specify applicability of operations
    • @ requires 0 < amount && amount + balance < MAX_BALANCE;
  • postconditions specify effect of operations
    • @ ensures balance == \old(balance) + amount;

Design Patterns

  • identify specific design choices and implementation issues
  • GOF “Gang of Four” design patterns

Good Design Choices

  • simpler architecture
  • more modular design
  • fewer dependencies

Constructors

Constructors initialise a class, and allow the use of new Object():

Blah x = new Blah();
 
public class Blah {
   int x;
   int y = 5;
 
   public Blah (int x) {
      this.x = x;
   }
}

Classes take no modifiers (abstract, static, etc) and have no return type (they're returning a new object).

If no constructor is created then the default initialisation happens, with each field being initialised to its pre-set value, or defaults (e.g. 0, null).

Types of Constructors

Classes in java can have as many constructors as you like, as long as they take different arguments. Different kinds of constructors include:

  • No arguments - Blah()
    • The default constructor if no constructor is declared
  • All arguments Blah(int x, int y)
    • Pass all arguments in and set them (similar to above example)
  • Copied Object Blah(Blah c)
    • Initialise this object by copying values from another object
    • Essentially the same as clone

Subclass Constructors

Each class needs its own constructor (or defaults to null) - it does not inherit from a superclass.

It can call this(args) to reference another of its own constructors, or super(args) to reference its superclass's (but only if these are called as the first line of the constructor).

Object Initialisation

  1. Object memory is allocated on heap (or exception thrown)
  2. Fields given default values
  3. Call stack frame set up with constructor args
  4. If this() is called, do a new constructor call. Else call the super constructor (this is called implicitly if no constructor, or if a constructor doesn't explicitly call super).
  5. Execute field initialisers (super fields done with super call)
  6. Execute rest of constructor

Iterators

  • abstract data representation
  • standardise traversing elements of a collection (array, list, set, etc)
  • constructed and implemented within the collection

Called like

LinkedListAtLast l = new LinkedListAtLast();
java.util.Iterator<Object> i = l.iterator();
while(i.hasNext()) {
    System.out.print((Link) i.next() + " ");
}

Object (the class)

  • Every interface and class extends Object; all are subtypes
  • There are methods of Object that are hence callable on any class (most classes should override these):
    • equals()
      • (tested as being identical - not necessarily relevant, hence override)
      • should maintain equivalence relation (reflexive, symmetric and transitive)
    • hashCode()
      • if a.equals(b) then a.hashCode() == b.hashCode()
    • toString()
    • clone()
    • finalize()
      • All objects are reachable (live), or finalizer-reachable (unusable but not garbage yet), or unreachable (garbage collected)

Static

Static means that it cannot directly refer to a "this" instance of the surrounding class.

The only real use of static member types is to reduce the number of top-level type names:

public class Outer { public static class C { ... }}

From outside of Outer, the class C is named as Outer.C - compile to O.class and O$C.class

Inner Classes

Inner classes (a class declared within another class) are associated with an instance of the surrounding class Outer (can access fields and methods of surrounding class Outer directly, or by referring to the associated instance of Outer - Outer.this).

Within Inner the variable this just refers to the current instance of Inner.

They allow classes to locally define their own implementations, and are often used for special implementations of standard interfaces e.g. iterator)

They have three forms:

Non-Static Class Members

public class Outer {
   public class Inner { ... }}
}

Anonymous Classes

  • An inner class with no name - no need to name a class if its type is only used once
    • as part of a new instance creation, blend new Constructor syntax with class definition
    public Iterator<Object> iterator() { 
        // TODO Auto-generated method stub
        return new Iterator<Object>(){
            private Link current = first;
            public Link next() {Link prev = current; if (current != null) { current = current.getNext();}  return prev; }
            public boolean hasNext() {if (current != null) {return true;} else { return false;}}
            public void remove() {throw new UnsupportedOperationException(); };
        };
 
    }

Local Classes

are seldom used in Java

Immutable Objects

"Immutable" means does not change - once initialised, the state (field data) of an immutable object never changes.

  • immutable objects can be shared safely with multiple clients no unexpected state changes
  • it's safe to use an immutable state as keys in hash tables
  • computational results dependent (only) on immutable objects can be cached

Making an object immutable

  • Avoid any mutator methods in the class
  • All fields should be initialised in the constructor or in an initialisation expression
  • Declare fields final
  • BUT subclasses may extend a class with mutable data
  • it's not so easy to guarantee immutability given subclassing
  • classes can be declared final - this prevents them from being extended

Errors

Kinds of run-time errors

  • abnormal conditions
  • out of memory - stack overflow
  • class loading problems
  • program errors
    • divide by zero errors
    • calling a method on a null target
    • array index out of bounds
    • unsupported operation
    • method declared by class, but not implemented
    • etc

Defensive Programming

  • test for all possible error conditions
  • code becomes bloated and unintelligible
  • leads to redundant error handling
  • robustness of code vs performance vs clarity

Structured Exception Handling

  • an exception is thrown when an error occurs
  • execution resumes where it is caught
  • exceptions are just objects that extend class java.lang.Exception
  • throw new UnsupportedOperationException("message");

Catching Exceptions

Surround code with a block:

try {
//code here
} catch (exception1 e) {
   throw new Exception(e.getMessage());
} catch (exception2 e) {
   throw new Exception(e.getMessage());
}
  • Each catch clause declares a variable with the type of exception that it handles
  • The finally clause provides a place for cleanup after the block

Runtime Hooks into Source Code

Java provides a number of techniques for accessing source code information at runtime

  • instanceof
  • typecasts
  • reflection (self-knowledge) and runtime type information
    • Class and Method objects -getClass() - getDeclaredMethods() etc.

Type Rules

Type Rule for Assignment

Binding of object references;
LHS x;
RHS y;
x = y;
The above is only legal iff RHS is a subtype of LHS.

Screen%20Shot%202012-10-29%20at%2010.50.11%20PM.png

Persistent Objects

Persistent objects live beyond the lifetime of a particular execution of an application (a session). This can be done through writing to a file and loading in later

Object Serialisation

Helps in the process of persistence.

  • objects are marshalled into a linear byte-based representation and written to an object stream
  • objects can be read back from an object stream
  • automatically keeps track of multiple objects and inter-object references

To tell the compiler that serialisation support is needed for a particular class

  • implement java.io.Serializable
  • introduce a magic number into the class - this is saved to the persistent object stream and checked for consistency when the stream is reloaded

Also used for

Distributed object applications, where objects need to be transmitted to remote applications or devices

Generics

Generic definitions have types as formal parameters (often called parametric polymorphism). They allow for type abstraction. E.g.

class Box<E>

General purpose algorithms are also called "generic"

Most Common Type Names

  • E - Element (used extensively by the Java Collections Framework)
  • K - Key
  • V - Value
  • N - Number
  • T - Type
  • S,U,V etc. - 2nd, 3rd, 4th types

Generic Classes/Interfaces

generic classes and interfaces

  • Introduce formal type parameters in a class definition
  • Different uses of the class or interface may use different actual types for the parameter

Generics allows us to do things without typecasting. E.g.

Apple[] array = { new Apple(), ... };
List apples = Arrays.asList(array); 
 
Apple a = array[2];              // OK 
 
Apple b = apples.get(2);         // NOT OK - just gets an object
Apple c = (Apple) apples.get(2); // OK with cast
Object d = apples.get(2);        // OK
 
List<Apple> apples = ...
Apple a = apples.get(2);         // OK without type cast

Constraining Generics

Within a generic class, we can use the formal type parameters as variable actual types:

class Zoo<E> { 
  List<E> animals(); 
  int legs() { 
    int sum = 0; 
    for (E animal : animals()) 
      sum += animal.legs();  // BAD TYPE - type E does not have a legs method
    return sum ; 
  } 
}

We can correct the above error by putting constraints on E;
E must be constrained to a type that declares int legs() e.g. WithLegs:
interface WithLegs { 
   int legs(); 
} 
class Zoo<E extends WithLegs> {
..
}

Generic Methods

  • Introduce formal type parameters in a method definition
  • Different method calls may use different actual types

Declaration & Calls

public static <X, Y>
Pair <X, Y> pair (X x, Y y) { 
    new Pair <X, Y> (x, y); 
}
 
// Call implicitly
Pair.pair (42, "life");
 
// Call explicitly
Pair.pair <Numeric, String> (42, "life");

Wildcard

Wildcards are anonymous type parameters, only used inside <>.
Used in cases like:

void x(Collection<?>) {
 
}

Wildcards can be constrained, e.g. the following must be a comparator that must be defined for elements of type E or some supertype of E

Comparator<? super E> comparator();

Collections

Rather than reinvent the wheel, java has inbuilt ways of storing elements (references to objects, not copies).

Screen%20Shot%202012-10-29%20at%2011.24.57%20PM.png

Design Patterns/Frameworks

A framework is a collection of related interfaces and classes. Frameworks provide a reusable architecture for typical application problems.

Design patterns capture reusable design components and often focus on relationships between interfaces and their possible implementations, solving some design problem.

Factory Method

  • Problem
    • How can you defer the selection of concrete class?
  • Context
    • Client code wants to construct instances but does not know what the concrete types are
  • Solution
  • Defer calling of a constructor by providing an interface to a factory method
  • Different implementation classes construct different concrete types of objects

Class Diagram

Screen%20Shot%202012-10-29%20at%2011.38.54%20PM.png

Abstract Factory

  • Problem
    • How do we construct a variety of different types of objects ( = a product line!)
  • Context
    • We have different implementations of the product line
    • Such as, platform specific variants: XP vs Vista vs Mac vs Linux
    • (Or singles vs doubles tennis matches)
  • Forces
    • We wish to preserve consistency within a product line (e.g. all blue objects or all Nike rather than Adidas)
    • Clients should not be able to create products from more than one product line

The Abstract Factory interface declares n factory methods

  • product1() … productn()
  • each concrete Factory class implements these to provide a related family of products
  • client code need not know about the concrete details of the product line

Wikipedia Example

"An example of this would be an abstract factory class DocumentCreator that provides interfaces to create a number of products (e.g. createLetter() and createResume()). The system would have any number of derived concrete versions of the DocumentCreator class like FancyDocumentCreator or ModernDocumentCreator, each with a different implementation of createLetter() and createResume() that would create a corresponding object like FancyLetter or ModernResume. Each of these products is derived from a simple abstract class like Letter or Resume of which the client is aware. The client code would get an appropriate instance of the DocumentCreator and call its factory methods. Each of the resulting objects would be created from the same DocumentCreator implementation and would share a common theme (they would all be fancy or modern objects). The client would need to know how to handle only the abstract Letter or Resume class, not the specific version that it got from the concrete factory"

Iterator

  • Problem
    • How can you traverse the elements in a container without exposing the container implementation
  • Context
    • different containers have different implementations
  • Solution
    • define an Iterator interface with methods for traversing the container
    • define a Container interface with a factory method for making iterator objects
    • implement specific types of iterators for specific types of containers

Template Method

  • The basic design pattern for OO frameworks
  • defines outline of algorithm in an abstract class
  • subclasses specialise steps of algorithm
  • In abstract class:
    • define primitive operations - abstract or default (hook) code used to implement the template method
  • In concrete subclasses:
    • implement abstract operations
    • specialise hook operations if required

Screen%20Shot%202012-10-30%20at%209.24.08%20AM.png

Decorator

  • Problem
    • how to extend existing functionality of an object's methods?
  • Solution 1: use inheritance (Non-Decorator)
    • override inherited methods
    • reuse code by calls back to super
    • a class-based solution
    • this is NOT the Decorator-based solution
  • Solution 2: use a decorator
    • “wrap” an existing object with a decorator
    • the decorator object implements the same interface
    • adds its own functionality to any of the methods
    • passes calls on (i.e. delegates) to the existing (or backing object)
    • an object-based solution

Explanation

Essentially we create a new abstract class that implements the interface. It contains a protected field of type Interface, and its constructor sets this to be the 'backing' object it is passed in.

Each method then merely returns backingObject.method(). Essentially the Abstract Decorator Class defines all of this forwarding behaviour to the backing object in one place.

Other concrete classes may extend this abstract class, calling super() to get the base method call and then altering it themselves.

Class Diagram

Screen%20Shot%202012-10-30%20at%209.33.46%20AM.png

Composite

  • Problem
    • how can you model whole-part hierarchies?
  • Forces
    • clients want to treat individual objects and compositions of objects uniformly
  • Solution
    • make a recursive tree of Composite objects
  • Consequences
    • client interface is simplified
    • but designing that interface is important
  • Known uses
    • window systems, syntax trees in language processing

Explanation

If we want to group a whole lot of objects and operate on them as one thing (e.g. be able to move one square or fifty, together, on a graphics simulation) then we can treat them as a 'composite' and do just that.

Requires:

  • All elements have same Interface
  • Composites have a child list of all leaf/composite components

Example

interface Animal { 
  int legs(); 
} 
abstract class CompositeAnimal<E extends Animal> 
implements Animal { 
  List<E> animals(); 
  int legs() { 
    int sum = 0; 
    for (E animal : animals()) 
      sum += animal.legs(); 
    return sum 
  } 
}

Class Diagram

Screen%20Shot%202012-10-30%20at%209.51.07%20AM.png

Strategy

  • Some context where there are:
    • A variety of possible algorithms
    • We make them interchangeable
    • Encapsulates each algorithm independently of the Context
    • Lets the algorithm vary independently from clients that use it
  • Provides common interface for all algorithms
  • Context uses this interface to call the algorithm defined by a ConcreteStrategy

Consequences:

  • clients must be aware of different Strategies
  • communication overhead between Context and Strategy
  • increased number of objects

Class Diagram

Screen%20Shot%202012-10-30%20at%209.56.13%20AM.png

Screen%20Shot%202012-10-30%20at%209.57.02%20AM.png

Observer

  • An object is aware of all its dependencies and relations, and informs these whenever there is a change of state (usually through a method call).
  • support for broadcast communication and unexpected updates
  • Problems
    • how can you update an object's dependents?
  • Forces
    • a subject needs to update its dependents
    • reduce coupling between subjects and dependents
  • Solution
    • subject keeps a list of dependents
    • dependents subscribe to the subject (join a list)
    • subject publishes notifications to all dependents
  • Known uses
    • MVC (model-view-controller) in GUI

Class Diagram

Screen%20Shot%202012-10-30%20at%2010.00.59%20AM.png

Basic Code

public class Observable extends Object { 
   public void addObserver(Observer o); 
   public void deleteObserver(Observer o);  
   protected void setChanged();   
   public void notifyObservers();  
   public void notifyObservers(Object arg);  
   ...  
} 
public interface Observer { 
   public void update(Observable o, Object arg); 
}

Memoisation

Memoisation is essentially caching results; if a method is 'pure' (stateless - same arg = same result, so its internals do not affect the result) then we can store its results for various args, rather than recompute multiple times.

Complexity Fibonacci Example

Let T(n) = number of additions for computing fib(n)
T(n) = T(n-2) + T(n-1) + 1, if n > 1 = 1, otherwise

  • so T(n) > fib(n)
  • but fib(n) grows exponentially, hence T(n) = HUGE for large n

With Memoisation (caching), it becomes more like O(n) + n2

Game-Playing

Min-Max

Minimax is a game-play algorithm designed to simulate both players making optimal moves. A game-tree is created, and a 'value' of each leaf-node state is calculated. The value for each level is calculate as either taking the maximum or minimum of its descendants (max if you, min if other player).

  • Having a simple state-reward evaluation implies faster, but may not be accurate
    • Tradeoff: better scoring function vs deeper look ahead
  • Repeated states
    • reach same game state by different move sequences
    • may be worth storing states
    • use hash of board state
    • watch out for excessive memory usage

Alpha-Beta

Alpha beta is minimax with pruning. Branches of a minimax tree can be pruned when it is guaranteed that they will be less optimal.

If α is ever >= β, at a you-turn, or β <= α at a them-turn, we prune.

Complexity

If branching factor is b then for minmax to depth level d, number of states = bd

Alphabeta has the same worst case as for minmax, in best case, number of states = bd/2 = sqrt of complexity - we can double the depth! (best case arises when best moves are evaluated first, achieves earlier pruning).

Graph Search

Depth First

Breadth First

Shortest Path

Iterated Depth First

A*

Iterated A*

Exhaustive Search

Backtracking

Greedy

Dijkstra

Kruskal

Huffman

Divide and Conquer

Chip and Conquer

Dynamic Programming

Formulating Recurrence Relations