CS2030S Notes

Compiled vs Interpreted Programs

Dynamic Typing vs Static Typing

Dynamic Typing

i = 4   # i is an integer
i = "5" # i is now a string

Static Typing

int i;   // declaring a variable
i = 4;   // ok
i = "5"; // error, cannot assign a string to an `int`

The type that a variable is assigned with is called the compile-time type.

Compiler will throw an error if there is a type mismatch.

Strong Typing vs Weak Typing

int i; // declare a variable
i = 4; // ok
i = (int)"5";

Line 3 is ok for weak typing, but will throw an error for strong typing.

| incompatible types: java.lang.String cannot be converted to int (Java example)

Types in Java

Primitive Types

Integral values

• byte -- 8-bit signed integers
• short -- 16-bit signed integers
• int -- 32-bit signed integers
• long -- 64-bit signed integers
• char -- 16-bit unsigned integers representing UTF-16 Unicode characters

Floating-point values

• float -- 16-bit floating-point numbers
• double -- 32-bit floating-point numbers

Boolean values

• true
• false

Primitive type variables never share their value with each other.

int i = 1000;
int j = i; // j is 1000
i = i + 1; // i is updated

i; // 1001
j; // 1000 (unchanged)

Subtypes

Let S and T be two types. We say that T is a subtype of S if a piece of code written for variables of type S can also safely be used on variables of type T.

T <: S or S :> T to denote T is subtype of S.

* both transitive and reflexive (clearly not symmetric)

For Java: byte <: short <: int <: long <: float <: double char <: int

Right to left is narrowing (requires explicit type casting). Left to right is widening (always ok).

double d = 5.0;
int i = 5;
d = i; // ok
i = d; // error (incompatible types: possible lossy conversion from double to int)

Heap and Stack

JVM will partition memory into several regions.

method area for storing the code for the methods metaspace for storing meta information (metadata) about classes, like static fields which are shared amongst all class objects heap for storing dynamically allocated objects stack for storing local variables (including primitive types and object references) and call frames

Heap and stack are common to all execution environments.

Abstraction: Composite Data Type

• Groups primitive types together

(in C)

typedef struct {
  double x, y; // (x,y) coordinate of the center.
  double r; // radius
} circle;

// functions that operate on a circle
double circle_area(circle c) { ... };
bool   circle_contains_point(circle c, double x, double y) { ... };
  :

Abstraction: Class and Object (Encapsulation)

• using classes

(in Java)

// Circle v0.1
class Circle {
  double x;
  double y;
  double r;

  double getArea() {
    return 3.141592653589793 * r * r;
  }
}

Circle c = new Circle(); // c is now a Circle object
c.r = 10; // set the radius to 10
c.getArea(); // returns 314.1592653589793

To model a problem in an object-oriented manner, we typically model the nouns as classes and objects, the properties or relationships among the classes as fields, and the verbs or actions of the corresponding objects as methods.

Circle class is a reference type.

Circle c1 = new Circle();
Circle c2 = c1;
System.out.println(c2.r); // print 0
c1.r = 10.0;
System.out.println(c2.r); // print 10.0

// c1 and c2 both refer to the same object because Circle is a reference type.

Special Reference Value: null

Circle c1;
c1.r = 10.0;  // error
|  Exception java.lang.NullPointerException

Remember to always instantiate a reference variable before using it.

Data Hiding

// Circle v0.2
class Circle {
  private double x;
  private double y;
  private double r;

  public double getArea() {
    return 3.141592653589793 * r * r;
  }
}

If access modifier is not speciifed, it defaults to the default modifier.

• Private modifier
  • not accessible and not modifiable outside of the class Circle
• Public modifier
  • accessible and modifiable outside of the class Circle

Constructor

// Circle v0.3
class Circle {
  private double x;
  private double y;
  private double r;

  public Circle(double x, double y, double r) {
    // constructor method
    this.x = x;
    this.y = y;
    this.r = r;
  }

  public double getArea() {
    return 3.141592653589793 * this.r * this.r;
  }
}

Circle c = new Circle(0.0, 0.5, 10.0); // creates a Circle object

Constructor method

• has the same name as the class
• has no return type

The this keyword

Refers to the class variable, rather than a local variable or parameter.

Main Method

public final static void main(String[] args) {
}

Every Java program has a class method called main.

Main method takes in command-line arguments as parameter args.

Sharing References (Aliasing)

Point p = new Point(0, 0);
Circle c1 = new Circle(p, 1);
Circle c2 = new Circle(p, 4);

p.moveTo(1, 1); // mutator method for Point

// now, c1 and c2 are both centered around (1, 1) instead of (0, 0)

If moveTo is instead a Circle method instead of Point method, doing c1.moveTo(p2) will mutate c1 but not c2.

The toString Method

toString is invoked implicitly by Java, by default to convert a reference object to a String object during string concatenation using the operator +.

Circle c = new Circle(new Point(0, 0), 4.0);
String s = "Circle c is " + c; // Circle c is Circle@1ce92674

The 92674 behind the Circle@ is the reference to the object (and can change based on different runs).

Overriding toString method for a class

// version 0.6
class Circle {
  private Point c;   // the center
  private double r;  // the length of the radius
  :
  :
  /**
   * Return the string representation of this circle.
   */
  @Override
  public String toString() {
      return "{ center: " + this.c + ", radius: " + this.r + " }";
  }
}

Point p = new Point(0.0, 0.0);
Circle c = new Circle(p, 4.0);
c.toString(); // { center: (0.0, 0.0), radius: 4.0 }

This is known as method overriding, to alter the behaviour of an existing class.

Circle::toString has overriden Object::toString.

Annotation

@Override is an annotation.

It is not part of the program and does not affect the bytecode generated. It is merely a hint to the compiler.

But, recommended and expected to do this (in CS2030S).

Overriding Method that Throws Exception

The overriding method must throw only the same, or a more specific checked exception, than the overridden method. This follows Liskov Substitution Principle.

Dynamic Binding

The toString methods called are different.

Whichever method is invoked is decided during the run-time based on the run-time type of the obj. This is called dynamic binding or late binding or dynamic dispatch.

Applied to only instance method invocations.

The most specific method will be called.

Run-time type of target and compile-time type of arguments are used to determine the method that is called during execution of the program.

The compile-time return type is used to a certain extent as well (as a sanity check) to make sure that the required method actually exists.

The equals method

Circle c0 = new Circle(new Point(0, 0), 10);
Circle c1 = new Circle(new Point(0, 0), 10);
Circle c2 = c1;

c0.equals(c1); // false
c2.equals(c1); // true

Because c0 and c1 refer to different objects but c1 and c2 refer to the same object.

Overriding Object::equals

/**
 * Return true the object is the same circle (i.e., same center, same radius).
 */
@Override
public boolean equals(Object obj) {
    if (obj instanceof Circle) {
        Circle circle = (Circle) obj;
        return (circle.c.equals(this.c) && circle.r == this.r);
    }
    return false;
}

• equals takes in a parameter of compile-time type Object. It only makes sense if we compare (during run-time) a circle with another circle. So, we first check if the run-time type of obj is a subtype of Circle. This is done using the instanceof operator. The operator returns true if obj has a run-time type that is a subtype of Circle.
• To compare this circle with the given circle, we have to access the center c and radius r. But if we access obj.c or obj.r, the compiler will complain. As far as the compiler is concerned, obj has the compile-time type Object, and there is no such fields c and r in the class Object! This is why, after assuring that the run-time type of obj is a subtype of Circle, we assign obj to another variable circle that has the compile-time type Circle. We finally check if the two centers are equal (again, Point::equals is left as an exercise) and the two radii are equal2.
• The statement that assigns obj to circle involves type casting. We mentioned before that Java is strongly typed and so it is very strict about type conversion. Here, Java allows type casting from type $T$ to $S$ if $S<:T$. This is called narrowing type conversion. Unlike widening type conversion, which is always allowed and always correct, a narrowing type conversion requires explicit typecasting and validation during run-time. If we do not ensure that obj has the correct run-time type, casting can lead to a run-time error (which if you recall, is bad).

Overriding Circle::equals MUCH better!

class Circle {
     :
  /**
   * Return true the object is the same circle (i.e., same center, same radius).
   */
  @Override
  public boolean equals(Circle circle) {
      return (circle.c.equals(this.c) && circle.r == this.r);
  }
}

Does not override Object::equals.

Example of Violation of LSP

void displayGrade(Module m, double marks) {
    char grade = m.marksToGrade(marks);
    if (grade == 'A')) {
        System.out.println("well done");
    else if (grade == 'B') {
        System.out.println("good");
    else if (grade == 'C') {
        System.out.println("ok");
    } else {
        System.out.println("retake again");
    }
}

Module::marksToGrade returns 'A', 'B', 'C', 'F' (char)

Suppose CSCUModule where CSCUModule <: Module and CSCUModule::marksToGrade only returns 'S', 'U' (char).

This will cause displayGrade to fail to work properly because CSCUModule::marksToGrade violates LSP.

Abstract Class

Good to make functions that take in more general classes. Abstract classes should contain at least 1 abstract method, otherwise, it does not make sense to be abstract.

// version 0.3
double findLargest(Shape[] array) {
  // as opposed to Circle[] array
  double maxArea = 0;
  for (Shape curr : array) {
    double area = curr.getArea();
    if (area > maxArea) {
      maxArea = area;
    }
  }
  return maxShape;
}

This function can work for an array containing different shapes too.

abstract class Shape {
    private int numOfAxesOfSymmetry ;

    public boolean isSymmetric() {
        return numOfAxesOfSymmetry > 0;
    }

    abstract public double getArea();
}

Shape s = new Shape(); // error, abstract class cannot be instantiated

An abstract class in Java is a class that has been made into something so general that it cannot and should not (cannot) be instantiated.

As long as one of the class methods is abstract, the class becomes abstract. Abstract classes can include "default" non-abstract methods that will be used if not overridden.

Shape::isSymmetric is a concrete method but Shape::getArea is abstract.

Concrete Class

A concrete class is a class that has no abstract methods.

Pure vs Impure Interfaces

Interfaces can have default methods. However, this is considered impure and used mostly for backwards compatibility reasons.

Don't implement default methods for CS2030S!

Auto-boxing and Unboxing

Integer i = 4; // auto-boxing
int j = i;     // unboxing

Treat the wrapper as a box.

Java automatically converts a wrapper class to its primitive type and vice versa auto-magically.

However, wrapper classes are much slower as they are immutable. (about 2 times slower)

Throwing Exceptions

  :
  public Circle(Point c, double r) throws IllegalArgumentException {
    if (r < 0) {
      throw new IllegalArgumentException("radius cannot be negative.");
    }
    this.c = c;
    this.r = r;
  }
}

throws and throw keywords!

throw new SomeException("Optional Message");

Throwing an exception will cause the method to immediately return.

Checked vs Unchecked Exceptions

Unchecked Exceptions Generally indicates that there is something wrong with the program and might cause run-time errors. Some examples: IllegalArgumentException, NullPointerException, ClassCastException.

Can mean some cases of input are not handled properly (if at all).

An unchecked exception, if not caught, will propagate automatically down the stack until either, it is caught or if it is not caught at all, resulting in an error message displayed to the user.

Checked Exceptions Exceptions that a programmer has no control over. For example, when attempting to open a file, in some cases, it cannot be opened.

In Java, unchecked exceptions are subclasses of RuntimeException.

Checked exceptions must be handled otherwise, will not compile.

// version 0.2 (handle where exception occur)
class Toy {
  static FileReader openFile(String filename) {
    try {
      return new FileReader(filename);
    } catch (FileNotFoundException e) {
      System.err.println("Unable to open " + filename + " " + e);
    }
  }
  public static void main(String[] args) {
    openFile();
  }
}

// version 0.3 (passing exception to caller)
class Toy {
  static FileReader openFile(String filename) throws FileNotFoundException {
    return new FileReader(filename);
  }
  public static void main(String[] args) {
    try {
      openFile();
    } catch (FileNotFoundException e) {
      // warn user and pop up dialog box to select another file.
    }
  }
}

A method has to either catch the exception or throws the exception onto the caller of that function.

Custom Exceptions

class IllegalCircleException extends IllegalArgumentException {
  Point center;
  IllegalCircleException(String message) {
    super(message);
  }
  IllegalCircleException(Point c, String message) {
    super(message);
    this.center = c;
  }
  @Override
    public String toString() {
      return "The circle centered at " + this.center + " cannot be created:" + getMessage();
    }
}

Should only create own exceptions if there is a good reason to do so, for example: to provide additional useful information to the exception handler.

Good Practices for Exception Handling

If exception occurs before some important deallocating process, need to think about how to circumvent this. e.g. Deallocate those resources in the finally block.

Bad Practices for Exception Handling

Do not use "catch-all"

catch (Exception e) { ... }

Do not exit a program just beacuse of an exception. This prevents the calling function from cleaning up the resources. Do not exit a program silently.

try {
  // your code
}
catch (Exception e) {
  System.exit(0);
}

Do not break abstraction barrier Try to handle the implementation-specific exceptions within the abstraction barrier.

Do not use exceptions as control flow mechanism (if/else)

Error

Java has an Error class for situations where the program should terminate as it is hard to recover from. OutOfMemoryError StackOverflowError Typically, do not need to create or handle these errors.

Generic Type

class Pair<S,T> {
  private S first;
  private T second;

  public Pair(S first, T second) {
      this.first = first;
      this.second = second;
  }

  S getFirst() {
      return this.first;
  }

  T getSecond() {
      return this.second;
  }
}

Pair<String,Integer> foo() {
  return new Pair<String,Integer>("hello", 4);
}

Pair<String,Integer> p = foo();
Integer i = (Integer) p.getFirst(); // compile-time error

Method that returns a pair with String, Integer.

Must use Integer, since only reference types can be used as type arguments.

The types are bound during compile time.

Once a generic type is instantiated, it is called a parameterised type.

class DictEntry<T> extends Pair<String,T> {
     :
}

Can pass the type parameter of a generic type to another.

Generic Method

class A {
    // version 0.4 (with generics)
    public static <T> boolean contains(T[] array, T obj) {
      for (T curr : array) {
        if (curr.equals(obj)) {
          return true;
        }
      }
      return false;
    }
}

String[] strArray = new String[] { "hello", "world" };
A.<String>contains(strArray, 123); // type mismatch error
// second argument must be a string

class A {
    // version 0.5
    public static <T extends GetAreable> T findLargest(T[] array) {
        double maxArea = 0;
        T maxObj = null;
        for (T curr : array) {
            double area = curr.getArea();
            if (area > maxArea) {
                maxArea = area;
                maxObj = curr;
            }
        }
        return maxObj;
    }
}

Specifying that T must be a subtype of GetAreable. Uses extends even though GetAreable is an interface.

class Pair<S extends Comparable<S>,T> implements Comparable<Pair<S,T>> {
  private S first;
  private T second;

  public Pair(S first, T second) {
      this.first = first;
      this.second = second;
  }

  S getFirst() {
      return this.first;
  }

  T getSecond() {
      return this.second;
  }

  @Override
  public int compareTo(Pair<S,T> s1) {
      return this.first.compareTo(s1.first);
  }

  @Override
  public String toString() {
    return this.first + " " + this.second;
  }
}

Enabling Pair class to be compared by extending Comparable.

So, java.util.Arrays.sort will work.

Can use multiple bounds with Something<T extends A & B & C>.

a.compareTo(b) => a - b

Arrays and Generics Can't Mix

Will cause heap pollution.

Arrays are reifiable type -- a type where full type information is available during run-time.

But Java generics are not reifiable due to type erasure.

Illegal Java syntax

Pair<String,Integer>[] pairArray = new Pair<String,Integer>[2];
new Pair<S,T>[2];
new T[2];

Raw Types

A raw type is a generic type but used without type arguments.

Compiler will give a warning when using raw types because it can't do any type checking.

Array a = new Array(4);

Raw types only exists for backwards compatibility.

ArrayList<String> as = new ArrayList<String>();
as instanceof ArrayList // true
as instanceof ArrayList<String> // does not compile

PECS

"Producer Extends, Consumer Super."

Upper Bounded Wildcard

? extends T

public void copyFrom(Array<? extends T> src) {
  int len = Math.min(this.array.length, src.array.length);
  for (int i = 0; i < len; i++) {
      this.set(i, src.get(i));
  }
}

Only matches for classes that are child classes of T.

Use extends because src is the producer.

A<S> <: A<? extends S>

Covariant.

Lower Bounded Wildcard

? super T.

public void copyTo(Array<? super T> dest) {
  int len = Math.min(this.array.length, dest.array.length);
  for (int i = 0; i < len; i++) {
      dest.set(i, this.get(i));
  }
}

Only matches for classes that are superclasses of T.

Uses super because dest is the consumer.

A<S> <: A<? super S>

Contravariant.

Unbounded Wildcard

Array<?> will accept any type of Array<>.

Array<?> a1 = new Array<String>(0);       // Does compile
Array<?> a2 = new Array<Integer>(0);      // Does compile

Array<Object> a1 = new Array<String>(0);  // Does not compile
Array<Object> a2 = new Array<Integer>(0); // Does not compile

// this is because generics in Java are invariant.

For any type S: A<S> <: A<?> A<? super S> <: A<?> A<? extends S> <: A<?>

Diamond Operator

Pair<String,Integer> p = new Pair<>();
Pair<String,Integer> p = new Pair<String,Integer>();
// are both equivalent!

Target Typing

public static <T extends GetAreable> T findLargest(Array<? extends T> array);

Can also specify the type of parameter T.

Advantages of Immutability

• Ease of understanding

• Enabling safe sharing of objects

  • Example: ORIGIN Point, EMPTY_BOX Box
  • No problem of aliasing

• Enabling safe sharing of internals

• Enabling safe concurrent execution

• can be used to represent same object at different stages

• can "revert" objects to a previous state

Variadic Arguments

// @SafeVarargs ise used here because compiler would throw unchecked warning as generics and arrays do not mix well
@SafeVarargs
public static <T> ImmutableArray<T> of (T... items) {
  return new ImmutableArray(items, 0, items.length - 1);
}

Nested Non-Static Classes

Also known as inner class.

Inner classes cannot have static fields because they themselves belong to an instance (hence does not make sense to have static fields). (unless they're constants written and known at compile time, e.g. int literals, string literals)

Nested Static Classes

class A {
  private int x;
  static int y;

  class B {
    void foo() {
      this.x = 1;   // error
      A.this.x = 1; // this is preferred
      y = 1; // accessing y from A is OK
    }
  }

  // the definition of static nested classes are stored in the metaspace
  static class C {
    void bar() {
      x = 1; // accessing x from A is not OK since C is static
      y = 1; // accessing y (static field) is OK
    }
  }
}

Local Classes

Classes inside a method. Scoped only inside the method.

// Comparator is a common use case for local classes
void sortNames(List<String> names) {

  class NameComparator implements Comparator<String> {
    public int compare(String s1, String s2) {
      return s1.length() - s2.length();
    }
  }

  names.sort(new NameComparator());
}

Variable Capture

class G {
  void doTask() {
    int x = 0;
    class H {
      int inc() {
        return x + 1;
      }
    }
    x = 1; // removing this statement will lead to this compiling

    H h = new H();
    h.inc();
  }
}

Local variables (including primitives) referenced from an inner class must be final or effectively final (only assigned once even though not explicitly final)!

Usually, when a method returns, all local variables of the method are removed from the stack. BUT an instance of a local class can still exist. Thus, local classes make a copy of (captures) local variables inside itself (even if unused as a failsafe).

Anonymous Class

names.sort(new Comparator<String>() {
  @Override
  public int compare(String s1, String s2) {
    return s1.length() - s2.length();
 }
});

Essentially instantiating an anonymous class that implements Comparator<String>.

No Side Effects

Violated through:

• print to screen
• write to files
• throw exceptions
  • be careful of division by zero, FileNotFoundException and other errors
• change other variables
• modifying values of arguments (of reference types)

Referential Transparency

No internal state

Violated through:

• using instance variables (that are not final)

Functional Interface

@FunctionalInterface annotation

An interface in Java with only one abstract method is called a functional interface.

Comparator<T> is a functional interface.

Lambda Expressions

Functions can be first-class citizens (using anonymous classes) BUT very verbose, so use lambda expressions instead to achieve the same thing.

Can use lambda expression to replace anonymous class (only in functional interfaces!)

Note: Lambda expressions do not have to be lazy.

(x, y) -> x + y i -> i + 1

(x, y) -> {}

Don't have to specify the type of the arguments because of type inferencing. (because already declared in interface, and only got 1 method there)

Comparator<Integer> cmp = (x, y) -> x - y;

Only used variables are captured.

Currying Functions

Chaining functions to avoid issue of being allowed only one argument

// Transformer::transform only takes in 1 value
Transformer<Integer, Transformer<Integer, Integer>> add = x -> y -> (x + y);

add.transform(4).transform(5);
// 9

Lambda as Closure

Value of origin is captured by the lambda expression dist.

// origin has to be final or effectively final
Point origin = new Point(0,0);
Transformer<Point, Double> dist = p -> origin.distanceTo(p);
Transformer<Point, Double> dist = origin::distanceTo;
// above 2 are equivalent

Cross-Barrier State Manipulator

Lambda expressions allow you (as the client) to "customise" some implementation into the Implementor's methods (including modifying Implementor's internal states).

Maybe

This is so that we can have different behaviour for "having value" and "null" yet not having to create a special Null class for every type of object.

Lazy/Delayed Evaluation

Lazy = opposite of Eager. Done using lambda expressions.

@FunctionalInterface
interface Task {
  void run();
}

Task t = () -> { System.out.println("Execute"); };
Task t = () -> System.out.println("Execute");
// above 2 are equivalent

t.run(); // Execute printed from this

Memoize

Only makes sense when function is deterministic.

class Lazy<T> {
  private T value;
  private boolean evaluated;
  private Producer<T> producer;

  public Lazy(Producer<T> producer) {
    this.producer = producer;
    this.value = null;
    this.evaluated = false;
  }

  public T get() {
    // only evaluates the first time you get()
    if (!evaluated) {
      this.value = this.producer.get();
      this.evaluated = true;
    }
    return this.value;
  }
}

Terminal Operations

Terminal operation is an operation on the stream that triggers the evaluation of the stream. A typical way of writing code that operates on streams is to chain a series of intermediate operations together, ending with a terminal operation.

forEach, reduce etc count() returns the count of the stream as a long

Stream.of(1, 2, 3).forEach(System.out::println);
Stream.generate(() -> 1).forEach(System.out::println); // infinite loop

Intermediate Stream Operations

An intermediate operation on a stream that returns another stream. They are lazy and do not cause the stream to be evaluated. Thus, order does not matter.

map, filter, flatMap etc

flatMap takes in a lambda expression that transforms every element in the stream into another stream. After which, the resulting streams are then flattened and concatenated together.

Stream.of("hello\nworld", "ciao\nmondo", "Bonjour\nle monde", "Hai\ndunia")
    .map(x -> x.lines()) // returns a stream of streams

Stream.of("hello\nworld", "ciao\nmondo", "Bonjour\nle monde", "Hai\ndunia")
    .flatMap(x -> x.lines()) // return a stream of strings

Stateful and Bounded Operations

Stateful intermediate operations need to keep track of some internal state.

sorted, distinct etc

sorted returns a stream with the elements sorted. Can also pass in a Comparator to tell sorted how to sort.

distinct returns a stream with only distinct elements.

Truncating Infinite Lists

limit takes in an int $n$ that returns a stream containing only the first $n$ elements of the stream.

takeWhile takes in a predicate and returns a stream containing the elements of the stream, until the predicate becomes false. Note: can potentially still be infinite if predicate never becomes false.

Peeking with a Consumer

Stream.iterate(0, x -> x + 1).peek(System.out::println).takeWhile(x -> x < 5).forEach(x -> {});

Reducing a Stream

reduce(init, (acc, x) -> ??)

reduce(BinaryOperator<T> accumulator) reduce(U identity, BiFunction<U,? super T,U> accumulator, BinaryOperator<U> combiner)

Also known as fold, accumulate in other languages. Repeatedly applies a lambda on elements of the stream to reduce it into a single value.

Stream.of(1, 2, 3).reduce(0, (x, y) -> x + y);
// returns the sum of all elements in a list.

Element Matching

noneMatch -> true if none of the elements pass the given predicate allMatch -> true if all the elements pass the given predicate anyMatch -> true if at least 1 element passes the given predicate

Prime Generating Example

private boolean isPrime(int n) {
  return n > 1 && IntStream
    .range(2, n)
    .noneMatch(x -> n % x == 0);
}

IntStream.iterate(2, x -> x + 1)
    .filter(x -> isPrime(x))
    .limit(500)
    .forEach(System.out::println);

Prints out first 500 primes.

Streams lead to code into becoming more declarative, allowing the code to be more succinct and less bug-prone. However, overusing streams instead of loops can become very messy if multiple nested components are required.

Identity Law

Factory method should not do anything extra to the value and side information.

Left identity law says: Monad.of(x).flatMap(y -> f(y)) must be equivalent to f(x)

Right identity law says: monad.flatMap(x -> Monad.of(x)) must be equivalent to monad

Associative Law

monad.flatMap(x -> f(x)).flatMap(y -> g(y)) must be the same as monad.flatMap(x -> f(x).flatMap(y -> g(y))) (NOTE: The location of the closing brackets)

Preserving Identity

functor.map(x -> x) must be the same as functor

Preserving Composition

functor.map(x -> f(x)).map(x -> g(x)) must be the same as functor.map(x -> g(f(x)))

Concurrency

Concurrency gives the illusion of subtasks running at the same time.

Parallelism

Parallel computing refers to when multiple subtasks are actually running at the same time.

Parallel Streams

Stream in Java allows for parallel operations on the elements of the stream.

parallel is a lazy intermediate operation. sequential will force the stream to be processed sequentially instead. Note that if multiple parallel and sequential are used on the last stream, the last one used will override.

parallelStream() instead of stream() also exists to be used on a collection.

IntStream.range(2_030_000, 2_040_000)
    .filter(x -> isPrime(x))
    .parallel()
    .forEach(System.out::println);

Output produced will not be in the correct order because there is no coordination among the parallel tasks on the order of printing. Thus, whichever task that completes first will output to the screen first.

forEachOrdered(...) will force the output to be ordered BUT will lose some benefits of parallelisation.

IntStream.range(2_030_000, 2_040_000)
    .filter(x -> isPrime(x))
    .parallel()
    .count();

Order does not matter for count(). Thus, it is a perfect use case for parallelisation.

List<String> list = new ArrayList<>(List.of("Luke", "Leia", "Han"));
list.stream()
    .peek(name -> {
         if (name.equals("Han")) {
           list.add("Chewie"); // they belong together
         }
      })
    .forEach(i -> {});

Stateful vs Stateless

Stateful lambda is one where the result depends on any state that might change during the evaluation of the stream.

Stream.generate(scanner::nextInt)
	.map(i -> i + scanner.nextInt())
	.forEach(System.out::println)

// stateful because relies on the stdin

To ensure that the output is correct, need to also ensure that state updates are visible to all parallel subtasks

Side Effects

List<Integer> list = new ArrayList<>(
    Arrays.asList(1,3,5,7,9,11,13,15,17,19));
List<Integer> result = new ArrayList<>();
list.parallelStream()
    .filter(x -> isPrime(x))
    .forEach(x -> result.add(x));

The forEach above has a side effect of modifying result.

ArrayList is a non-thread-safe data structure. Thus, if 2 threads manipulate it at the same time, may lead to incorrect result.

list.parallelStream()
    .filter(x -> isPrime(x))
	.collect(Collectors.toList())

List<Integer> result = new CopyOnWriteArrayList<>();
list.parallelStream()
    .filter(x -> isPrime(x))
    .forEach(x -> result.add(x));

Associativity

reduce operation is parallelisable but have to abide by some rules: reduce(identity, accumulator) reduce(identity, accumulator, combiner)

Accumulator: First parameter is the accumulated value, second parameter is the current value of the stream. Combiner: Used to combine the results of all the parallel sub-streams.

1. combiner.apply(identity, i) must be the same as i
2. combiner and accumulator must be associative

• Parameters for the combiner and accumulator must be able to be swapped.

3. combiner and accumulator must be compatible

• combiner.apply(u, accumulator.apply(identity, t)) must be equal to accumulator.apply(u, t)

Multiplication is a valid operation that abides by these 3 rules.

If not following all these rules, you still might get the correct output sometimes but not consistent in different runs.

Performance of Parallel Stream

Parallelising streams does not always improve performance. Creating a thread to run a task incurs overhead. Overhead of creating too many threads can outweigh the benefits of parallelisation!

Ordered vs Unordered Source

Streams created from iterate and ordered collections (List, arrays) are ordered Streams created from generate and unordered collections (Set) are unordered

Stable Operations Stable operations preserve the original ordering of the elements.

distinct, sorted

Parallel versions of findFirst, limit, skip can be expensive on an ordered stream, since it needs to coordinate between streams to maintain order.

Thread Names

Every thread in Java has a name. Thread.currentThread() gets the reference of the current running thread. Thread.currentThread().getName() gets the name of the current running thread.

The main thread automatically created when the main method is invoked.

Thread Sleep

Thread.sleep(x) sleeps the thread for x milliseconds.

Is Alive

thread.isAlive() checks if a thread is running.

Note: The program exits only after all threads created run to their completion, including the main thread.

Creating a CompletableFuture

CompleteableFuture<U> completedFuture(U value) is equivalent to creating a task that is already completed and returns a value.

CompletableFuture<Void> runAsync(Runnable runnable) CompletableFuture<T> supplyAsync(Supplier<T> supplier) runAsync and supplyAsync Returned CompletableFuture completes when the given lambda expression finishes.

allOf and anyOf methods take in a variable number of other CompletableFuture instances. allOf is completed only when all given CompletableFuture completes. anyOf is completed when any given CompletableFuture completes.

runAfterBoth(CF other, Runnable r), runAfterEither(CF other, Runnable r) do what their names suggest.

Chaining CompletableFuture

thenApply analogous to map thenCompose analogous to flatMap thenCombine analogous to combine

The methods above run the given lambda expression in the same thread as the caller.

There are also asynchronous versions: thenApplyAsync, thenComposeAsync, thenCombineAsync which may cause the given lambda expression to run in a different thread (more concurrency).

Getting Result

get() is a synchronous call so it will block until CompletableFuture completes. Thus, we should only call it at the final step in the code.

CompletableFuture::get throws InterruptedException and ExceutionException. InterruptedException is thrown when the thread has been interrupted. ExecutionException is thrown when there are errors/exceptions during execution.

join() is an alternative to get() that is exactly the same except it does not throw checked exceptions.

thenRun, runAsync (both take in a Runnable), thenAccept (takes in a Consumer) also exist.

When using runAsync, the Java program may terminate before the Runnable is completed!

Examples

// findIthPrime returns the ith prime
private boolean isPrime(int n) {
  return n > 1 && IntStream
    .range(2, n)
    .noneMatch(x -> n % x == 0);
}
int findIthPrime(int i) {
    return Stream
        .iterate(2, x -> x + 1)
        .filter(x -> isPrime(x))
        .limit(i)
        .reduce((x, y) -> y)
        .orElse(0);
}

int i = 9999;
int j = 999;

CompletableFuture<Integer> ith = CompletableFuture.supplyAsync(() -> findIthPrime(i));
CompletableFuture<Integer> jth = CompletableFuture.supplyAsync(() -> findIthPrime(j));

CompletableFuture<Integer> diff = ith.thenCombine(jth, (x, y) -> x - y);

Integer result = diff.join();

CompletableFuture: Handling Exceptions

Exception handling is troublesome when doing asynchronous programming because often times you still want some of the output and not crash the entire program.

CompletableFuture<T> handles exceptions unlike Thread.

exceptionally, whenComplete, handle are methods that deal with exceptions.

CompletableFuture<T> stores exceptions thrown by a computation and passes it down the chain of calls until join is called which will then dump all the exceptions in a CompletionException.

handle method takes in a BiFunction (similar to cs2030s.fp.Combiner), first parameter is the value, second is the exception.

cf.thenApply(x -> x + 1)
  // Java uses null to indicate no exception thrown
  .handle((t, e) -> (e == null) ? t : 0)
  .join();

// can check for either
// if exception, t == null
// if no exception, e == null

https://mincong.io/2020/05/30/exception-handling-in-completable-future/ handle is used for transforming the data depending on if there is a exception. whenComplete is used for logging information. exceptionally is used exclusively for exception handling (and has no access to the data).

Recursive Task

Abstract class RecursiveTask<T> supports fork() and join() and has an abstract method compute() which we will use to specify the computation.

RecursiveAction is a result-less version of Recursive Task.

class Summer extends RecursiveTask<Integer> {
    private static final int FORK_THRESHOLD = 2;
    private int low;
    private int high;
    private int[] array;

    public Summer(int low, int high, int[] array) {
      this.low = low;
      this.high = high;
      this.array = array;
    }

    @Override
    protected Integer compute() {
      // stop splitting into subtask if array is already small.
      if (high - low < FORK_THRESHOLD) {
        int sum = 0;
        for (int i = low; i < high; i++) {
          sum += array[i];
        }
        return sum;
      }

      int middle = (low + high) / 2;
      Summer left = new Summer(low, middle, array);
      Summer right = new Summer(middle, high, array);
      // !!
      // many ways to do next 2 lines
      // but using 1.fork(), 2.compute(), 1.join() is the best way
      left.fork();
      return right.compute() + left.join();
    }
  }

    Summer task = new Summer(0, array.length, array);
    int sum = task.compute();

1.fork(), 2.compute(), 1.join() is the most optimal compute() is likely faster than fork() then join() because this reduces the overhead of interacting with the ForkJoinPool

ForkJoinPool

Java manages the thread pool with fork-join tasks internally but the details are out of scope of CS2030S.

1. Each thread has a deque of tasks
2. When a thread is idle, it checks its queue of tasks.
3. If queue is not empty, it picks up a task at the head of the queue to execute (invokes its compute() method)
4. Otherwise, it picks up a task from the tail of the queue of another thread to run. This is known as work stealing. Picking up from the tail to minimise conflicts.
5. When fork() is called, the caller adds itself to the head of the queue of the executing thread. This is similar to recursion stack.
6. When join() is called, several different cases
7. If the subtask to be joined hasn't been executed, its compute() method is called and the subtask is executed.
8. If the subtask to be joined has been completed (other thread stole it), then the result is read and done.
9. If the subtask to be joined has been stolen and is still being executed, current thread works on another task (in local queue or steals another task)

The threads are always looking for something to do and cooperate to maximise work done! Minimise the time each thread is spent idling.

Similar to .NET and Rust implementation.

Ordering of Fork and Join

Since the most recently forked task is likely to be executed next, we should join() the most recent fork() first.

Order of forking should be the reverse of the order of joining. ABCDDCBA

left.fork();
right.fork();
return right.join() + left.join();

is efficient.

Doing this order is better because its added to the queue from the front, thus the second fork will be the new head of the queue.

Join and Fork comes together so must be used in tandem.