Reasonable Deviations

a rational approach to complexity

© Robert Andrew Martin 2023. All rights reserved. Disclaimer.

Object Oriented Programming

Some images herein have been borrowed from the Course Handout

Introduction

1. Types, Objects, Classes

Most languages will have some primitive types to signify what is in the memory. A variable is a name used to refer to a specific instance of the type. In Java:

It is safe to perform widening conversions between types, but narrowing will not compile.

int x = 200;
long y = x;  // safe
byte z = x;  // will raise Incompatible types error 
byte z = (byte) x;  // will compile but z = -56.

Java is statically typed, meaning that every variable name must be bound to a type when it is first declared.

Object construction

Classes are used to represent concepts, grouping state and behaviour. To be precise, the state takes the form of fields and behaviour is described in methods.

Objects are instances of classes, and can be made using a call to the constructor method.

public class Vector2d {
    float x; float y;  // Fields
    
    Vector2d(float xi, float yi) {
        this.x = xi;  // 'this' can be used to disambiguate
        this.y = yi;
    }
}
    
// Creating an object by calling the constructor
Vector2d v1 = new Vector2d(3.0, 4.0);

The prototype of a function refers to the function name, arguments, and return types. Functions can be be overloaded to support different arguments (possibly with a different return type) – this also applies to the constructor. However, choosing between overloaded functions is static, i.e it happens at compile time. The JVM chooses the most specific method when resolving overloads.

When state is more logically associated with a class than an object, we can make a static field (same as class variable in python). These are most suited to class-related constants.

We can also have static methods, which do not require any instance-specific state. These can be called without instantiating the class, e.g. Math.sqrt(). Static methods tend to be easier to debug.

2. Designing classes

Classes should logically group state (nouns) and behaviour (verbs). We can visualise this using a UML Class diagram

In addition to classes, for added modularity we can use packages, i.e directories containing multiple class files. This allows us to develop, test and update functionality independently.

Encapsulation and access modifiers

Coupling is how much one class depends on another (bad). Cohesion is how strongly related everything in a class is (good).

Encapsulation refers to hiding some parts of the internal state using access modifiers, in order to reduce coupling. In general, all state should be private unless there is a good reason to the contrary.

We can interact with private fields from outside the class by using getters and setters. The advantage of a setter is that it can provide sanity checks for modification.

Immutable objects

If we have private fields and remove any setters, the class becomes immutable. The advantages of this are:

By default, arrays are not immutable, but strings are.

Parameterised types

Although java does not have full type inference, we can define polymorphic functions using generics, which defines classes with a placeholder type. This is implemented under the hood using type erasure.

public class Test<T> {
	private T t;
	
    public void set(T t){
        this.t = t;
    }
    public T get(){
        return this.t;
    }
}

There is then some limited type inference when instantiating a generic class:

LinkedList<Vector3D> ll = new LinkedList<>();

3. References and memory

All compilers map a variable name to a specific memory address – the type determines how many blocks the data tasks. Pointers are variables which contain memory addresses, which can then be manipulated.

A reference is an alias for some data – it is either assigned (and therefore valid) or unassigned. References are implemented using pointers, just that the compiler ensures memory safety.

In Java, everything is either a reference or a primitive.

Memory

Memory is represented by a grid of cells.

Only primitive types can be stored on the stack: everything else goes on the heap.

4. Inheritance

Inheritance is the mechanism by which new classes can take on the properties of existing classes – we can create a base class such that new classes inherit state, behaviour, and type. This reduces code duplication and allows us to represent conceptual hierarchies.

Java is a nominitive type language - things must have the right name. By contrast, structural typing (e.g. in Haskell) examines whether the internal structure is the same, so the below code would compile. Duck typing (e.g. in python) is a subset of structural typing but only checks at runtime.

class Foo {
  public void method(String input) { }
}
class Bar {
  public void method(String input) { }
}
Foo f = new Bar(); // ERROR!!

In contrast to the “has-a” relationship, inheritance is described by empty arrowheads that describe the “is-a” relationship.

Casting

By definition, any instance of the superclass could be replaced by an instance of the subclass. This means that widening casts/conversions are acceptable.

// Explicit 
Child c = new Child();
Parent p = (Parent) c;  // Redundant cast

// Implicit 
public void doStuff(Parent p) {...};
doStuff(new Child());

By contrast, narrowing conversions may fail. This is because the child may have some attributes that the parent doesn’t, so the parent class may not be able to represent the child.

Parent p = new Parent();
Child c = (Child) p; // Fails AT RUNTIME

Child c = new Child();
Parent p = (Parent) c; // Widening cast is fine
Child c2 = (Child) p; // Ok!

When an object is created, Java stores the information at a specific memory location (returning a reference). Casting just creates a new reference with a different type. If we try to cast a parent to a child, there won’t be the necessary information in memory, but this is not caught by the compiler and will lead to a runtime error.

Inheriting fields and methods

Abstract classes

5. Polymorphism and multiple inheritance

When a subclass overrides a parent method and we refer to the object by the parent type, which method should we run?

Multiple inheritance

Multiple inheritance allows classes to inherit from multiple parents. Java does not support this because of the diamond problem: if the two parents of a child class have the same method (which they have overridden from their common parent), which method should be inherited by the child class?

Java’s alternative is interfaces, which are like special classes which:

Interfaces should be used to represent types.

They are represented on UML with a <<interface>> label, and are generally named as adjectives. Interfaces can extend other interfaces.

interface Drivable {
    void turn();
    void brake();
}

interface Identifiable {
    void getIdentifier();
}

class Bicycle implements Drivable {
    public void turn() {...};
    public void brake() {...};
}

class Car implements Drivable, Identifiable {
    public void turn() {...};
    public void brake() {...};
    public void getIdentifier() {...};
}

6. Lifecycle of an object

When an object is created, Java goes through the following process:

  1. Load class (if not already loaded), allocate static fields, and run static initialisers.
  2. Allocate memory for object
  3. Run initialiser blocks
  4. Run constructor

When inheritance is involved:

Object Destruction

Deterministic destruction involves objects being deleted at predictable times, e.g. manual deletion or automatic deletion when out of scope. Objected oriented languages sometimes have a destructor, which frees resources when an object is destroyed. This supports RAII (resource acquisition is initialisation), in which access to a resource follows an object’s lifecycle.

Java does not do this. Java instead uses garbage collection to automatically delete objects. Though there are finalisers (deprecated), these are not guaranteed to run and are very unreliable. As an alternative to RAII, Java offers try-with-resources:

The garbage collector is a separate process that monitors the program. It will slow down a program but helps minimise memory leaks. The different philosophies are:

  1. Stop the world – pause the operation of the program to delete objects
  2. Incremental – garbage collect in multiple phases letting the program run in the meanwhile
  3. Concurrent – no pause. Ideal but hard to implement.

Garbage collection algorithms

The original Java garbage collector uses reference counting. It keeps track of how many references point to a given object; if there are none, the object is deleted.

Problems with reference counting:

An alternative is to use mark and sweep tracing:

  1. List all immediate references
  2. Follow each reference recursively, marking the object if visited.
  3. Delete all unmarked objects.

A potential improvement is the generational garbage collector, which classifies objects as short/long lived and collects the short ones more frequently. Objects can be promoted from short to long.

7. Java Collections and Object Comparison

Java is a platform that offers a large class library. The Collections Framework in particular offers the Iterable and Collection interfaces (Iterable is the parent). They define operations such as add(Object o), clear(), next(), isEmpty() – if a particular class doesn’t offer the operation, it will throw UnsupportedOperationException.

These operations only work on objects, not primitives. The workaround is autoboxing: for each primitive type, Java provides an object wrapper (e.g. Integer, Boolean). The compiler autoboxes and unboxes, replacing the primitive with its object wrapper and vice versa as needed.

List<Integer> li = new ArrayList<>();
for (int i = 1; i < 50; i++)
    li.add(i);  // int is autoboxed before insertion

Note on the LHS we used List rather than ArrayList – this is acceptable because ArrayList inherits from List (widening/upcasting).

Set interface

Inheriting from Collection, represents a collection of unique elements

List interface

A list is an ordered collection of elements that may contain duplicates.

Queue interface

An ordered collection that supports removal of elements from the head (poll) and addition to the back (offer). peek() can be used to look at the head without removal.

Map interface

The map interface provides dictionary functionality: mapping unique key objects to value objects. m.keySet() and m.values() get the keys and values respectively.

Iterators

Because Collection inherits from Iterable, we can iterate over a collection using a foreach loop:

for (Integer i : list) {
    System.out.println(i);
} 

for (Map.Entry<String, String> entry : map.entrySet())
{
    System.out.println(entry.getKey() + "/" + entry.getValue());
}

hash.forEach((key, tab) -> /* do something with key and tab */);

When iterating over a collection, it is dangerous to change the structure (e.g. by deleting). To do this we must use the Iterator class, which supports hasNext(), next() and remove(), but does not support forEach.

Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    it.remove(); // Safe with Iterator
}

Object comparison

Comparing primitives is straightforward. However, in many cases we will want to compare/sort objects.

By default java tests reference equality, i.e whether the two references point to the same chunk of memory. If we want to test whether the values of the objects are equal, we must override the equals() method in object (default is reference equality).

@Override
// Compare the current object to another object o 
public boolean equals(Object o) {
    return ((o.name == this.name) && (o.field == this.field))
}

Objects in Java have a hashCode() method which should return the same result if the objects are equal. Thus you should override hashCode() whenever you override equals().

In order to compare objects, their class should implement the Comparable<T> interface, overriding the int compareTo(T o) method.

Implementing Comparable defines a natural ordering for the class, which should be consistent with equals and define a total order:

However, we may want to be able to sort the same class in different ways. For this we use a Comparator. This is a class which implements the Comparator<T> interface:

class AgeComparator implements Comparator<Person> {
    public int compare (Person p1, Person p2) {
        return (p1.age - p2.age);
    }
}

Collections.sort(plist); // sort with compareTo
Collections.sort(plist, new AgeComparator()); // sort with comparator

Java does not support operator overloading.

8. Error handling

Errors fall broadly into three categories: syntactic, logical (bugs), external. Mostly we dicuss logical errors, which can be reduced by:

Traditional imperative languages deal with errors using return codes. But you have to constantly check what return values signify, and it means code can’t conveniently just use the result of a method.

Alternatively, we can use deferred error handling, in which an error sets some state, which can be later checked.

However, the most common form of error handling is to use exceptions, which are thrown by a method then caught later.

double divide(double x, double y) throws DivideByZeroException {
    if (y==0.0) throw new DivideByZeroException();
    else return x/y;
}

try {
    double z = divide(x,y);
    // more code
} catch (DivideByZeroException | NumericalException d ) {
    // handle error here
    // 'more code' does not run if there is an error.
} catch (OtherException e) {
    // handle
} finally {
    // ALWAYS CALLED
}

Creating exceptions

To create an exception, we can extend Exception and provide a custom constructor. Java offers exception chaining: if one exception causes another, we can include the first one as data in the second one by having a Throwable argument in the constructor:

public class ComputationFailed extends Exception {
    public ComputationFailed(String errorMsg, Throwable t) {
        super(errorMsg, t);
    }
}

try {
    // some code that may divide by zero
} catch (DivideByZeroException d) {
    throw new ComputationFailed("Other IOException", d);
}

Checked exceptions must be declared then either handled or passed up. A function with a checked exception must be wrapped in try-catch when called. Unchecked exceptions extend from RunTimeException and are used for programming errors, such as NullPointerException. Errors typically arise from the JVM and should not be caught.

Important points about exceptions:

Advantages of exceptions:

Disadvantages of exceptions:

Assertions

Type of error checking designed for debugging. If the statement being asserted is false, the program ends. They should not be used in production and are disabled by default. They can be enabled/disabled with the -ea and -da flags when running a program.

They are particularly useful for postconditions, i.e things that should be true at the end of your algorithm if it is working. They should only be used to test programmer error, and should not have side effects.

9. Copying Objects

All classes in Java have the Object class as their ancestor. Object provides a clone() method, but we can only call this if we implement the Cloneable interface. Cloneable is a marker interface that doesn’t have any code in it, but is used to label a class so that other functionality knows that it is cloneable.

By default this is set to a shallow copy, so all reference types will still point to the same data. After implementing Cloneable, we should override clone.

@Override
public Object clone() {
    // Copies primitives etc:
    MyClass cloned = (MyClass) super.clone(); 
    // Deep copy reference types
    cloned.attr = deepCopy(this.attr); 
    return cloned;  // this is of type MyClass... see below
}

The principle of substitution says that a reference to a superclass can always be replaced by references to its subclass, so rather than returning an Object we can return something more specific.

Although clone() is protected in Object, by overriding it we can weaken the access modifier.

An alternative to cloning is to use copy constructors, which accepts an object of the same type and manually copies data.

public class MyClass {
    int x; int y;
    public MyClass(MyClass m) {
        this.x = m.x; 
        this.y = m.y;
    }
}

Variance of return types

Loosely speaking:

Java arrays are covariant: an array of type T[] can contains elements of type T or any subtype S. Additionally, S[] itself is a subtype of T[].

10. Language evolution

When implementing new features, a key issue is backward compatibility. For example, java initially included Vector as an expandable array. It has since been completely replaced by ArrayList, but only remains for backwards compatibility.

Generics

Initially, Collections dealt with objects only. But this requires constant casting and can cause accidental type mixing in the collection.

In order to fix this while maintaining backwards-compatibility, Java uses type erasure, such that within a generic, the compiler deletes all instances of the generic type so that it is converted into the old code.

This explains why primitives cannot be passed directly, and must first be boxed.

Because of this type erasure, generics must be invariant. Unlike arrays, List<S> is not a subtype of List<T> even if S is a subtype of T.

ArrayList<String> strList = new ArrayList<>();
ArrayList<Object> superList = strList; // NOT OK

Anonymous functions

Java 8 added support for syntax reminiscent of functional programming, which can reduce the boilerplate. In many cases we will only want to use a function or object once, so it is unnecessary to define a method/class just for that purpose.

For example, consider a simple GUI with a clickable button. We thus need to register an ActionListener which increments a counter whenever the button is clicked. The obvious way to structure this is:

class ButtonCounter implements ActionListener {
    // Fields and constructor 
    
    @Override
    public void actionPerformed(ActionEvent e) {
        counter++;
        button.setText(String.valueOf(counter));
    }
}

public class Gui {
    // Fields
    
    Gui() {
        button = new JButton("mybutton");
        button.addActionListener(new ButtonCounter(button));
    }
    // Other GUI stuff
}

However, ButtonCounter is only needed as this specific part of the GUI. Thus we can improve using an inner class, in which we simply move ButtonCounter into Gui (its fields become Gui’s fields). This can increase encapsulation, because inner classes can be given access modifiers.

However, because we only need to register this listener once, we have wasted effort in creating a reusable class. An anonymous inner class defines one on the spot.

public class Gui {
    // Fields 
    
    Gui() {
        button = new JButton("mybutton");
        button.addActionListener(
                 new ActionListener() {
                     @Override
                     public void actionPerformed(ActionEvent e) {
                         button.setText(String.valueOf(counter++));
                     }
                 });
    }
    // Other GUI stuff 
}

But this whole class has been defined just to get the actionPerformed functionality! We can use a lambda function instead:

public class Gui {
    // Fields 
    
    Gui() {
        button = new JButton("mybutton");
        button.addActionListener(
                a -> button.setText(String.valueOf(counter++))
        );
    }
    // Other GUI stuff
}

This is only possible because addActionListener() implements a functional interface. Such an interface only has one abstract method – a lambda function is an instance of a functional interface.

List<String> list = new LinkedList<>();

// Expression lambda 
list.forEach(s -> System.out.println(s + s));

// Statement lambda 
list.forEach(s -> {s = s.toUpperCase();
                   System.out.println(s);});
                   
// Method reference
list.forEach(System.out::println);

Different functional interfaces allow functions to be treated as ‘values’, with different characteristics.

// No arguments, void return
Runnable r = () -> System.out.println("Some state change");
r.run()

// No arguments, non-void return 
Callable<Double> pi = () -> 3.141;
pi.call();

// One argument, non-void return
Function<String, Integer> f = s -> s.length();
f.apply("Some input string");

Streams

Collections can be made into streams, which we can then filter and map (though they get consumed in the process).

// 1. Create stream from collection
// 2. Element-wise operate
// 3. Aggregate
List<Integer> list = new ArrayList<>(List.of(1,2,3,4,5));
list.stream().map(x -> x*x).collect(Collectors.toList());

11. Design patterns

A design pattern is a general reusable solution to a commonly occurring problem in software design. Many of them follow the Open-Closed principle, that classes should be open for extension but closed for modification. There are three classes of design pattern:

Singleton

How can we ensure that only one instance of an object is created by developers using the code? e.g. database connections.

The Singleton pattern does this by having a private constructor and storing the only instance as a private static final field.

public class Singleton {
    private static final Singleton instance;
    
    public static getInstance() {
        if (instance == null ) {
            instance = new Singleton();
        }
        return instance;
    } 
    private Singleton() {} // private constr blocks creation
}

We can then call it with Singleton.getInstance(). This version of Singleton is lazy, because we initially set instance = null and only create it when getInstance() is called.

Decorator

How can we add state or methods at runtime? e.g. supporting gift-wrapped books in an online store.

This pattern describes how we can Decorate implementations of some Component interface.

Composite

How can we treat a group of Component objects as a single Composite object?

for (Component c: children) c.operation();

Observer

When an object changes state, how can other objects know? e.g. action on click in a GUI.

This pattern refers to how an observer can monitor changes in the state of a subject. It is straightforward conceptually:

State

How can we let a Context object alter its behaviour when its internal state changes? e.g. pressing the play button does something different depending on whether the music is on or off.

Strategy

How can we select an algorithm implementation at runtime?

The Strategy pattern is designed in the same way as State (with Context being used as a ‘switcher’), however its main purpose is to reduce code repetition during development:

12. The JVM and Bytecode

In order to build a distributable platform, we can use an interpreter, but this is not as efficient as a compiled language. Java uses a hybrid model:

The advantages of bytecode: