Java Reference Types

Strong Reference

In Java, a variable always creates a strong reference to an object (which created in the Java memory heap space) by keeping the memory address of this object. Examples of the strongly referenced object can be as simple as object assignment to a variable or method invocation by passing an object as a method argument. Furthermore, an object can also have member variables which are referencing to other objects. All these references between objects form a strong references chain. A references chain must have a root reference to start with. Normally the root reference is held by the local variable or method argument which is stored in the stack. A static class member variable, on the other hand, holds the root reference in the heap space. Below is an example of reference chain.

List<BigDecimal> list = new ArrayList<>();
list.add(new BigDecimal(1));

Strong References Chain

The references chain can be used for object reachability analysis. An object which can be reached via this references chain indicates that this object is strongly reachable by the running thread. The garbage collector always considers a strongly reachable object as an in-used object and never reclaim this object. This behavior is guaranteed regardless that a so-called in-used object is apparently an unused object in the Java application or the application is running out of memory. The JVM ends up throws the OutOfMemoryError to bring down the application when there is no enough memory space for creating a new object. However, the garbage collector will reclaim the object which becomes unreachable when all the references to this object are gone (unreferenced) or it is still being referenced but resides in an unreachable references chunk of the chain.

Given the following program,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public static void main(String[] args) { // Allocate 1M ByteBuffer strongRefOnTheRoot = ByteBuffer.allocate(1000000); // Reachable root reference. // Allocate 3M List<ByteBuffer> strongRefInTheChain = new ArrayList<>(); for (int i = 1; i <= 3; i++) { strongRefInTheChain.add(ByteBuffer.allocate(1000000)); // Reachable references in the chain. } ByteBuffer.allocate(1000000); // Unreachable after object creation. Eligible for garbage collection. for (int i = 0; i < 50; i++) { ByteBuffer outOfScopeRef = ByteBuffer.allocate(1000000); // Unreachable after go out from every iteration scope. Eligible for garbage collection. } // Allocate last 1M ByteBuffer strongRefOnTheRoot2 = ByteBuffer.allocate(1000000); // Reachable root reference. // OutOfMemoryError ByteBuffer strongRefOnTheRoot3 = ByteBuffer.allocate(1000000); // Reachable root reference. }

Running this program with heap size -Xmx5M and we will definitely hit the OutOfMemoryError at line #22. Some other important points to take away.

• #12: An object is created and initialized but becomes unreachable immediately is possible but not practical because it is wasting effort and resources for object creation, memory allocation, and garbage collection. This probably is a sign of code smell.
• #15: A strongly referenced object become unreachable as soon as it is out of its effective scopes such as method scope, iteration scope, condition scope and etc.
• #22: In order for strongRefOnTheRoot3 to be created successfully, either strongRefOnTheRoot1 or strongRefOnTheRoot2 has to be cleared by assigning null to them.

New References New Reachabilities

In Java, the memory de-allocation process is handled automatically by the garbage collector. This is a great relieve to the Java programmer. However, this does not mean we can totally hand off of it. In some circumstance, the garbage collector just can't help. For example, a cache which limitless to keep un-used strong referenced objects in the application scope is actually putting the application at the risk of memory leak. In this case, we can't blame the strong reference or garbage collector. Instead, we should have aware of this risk and implement a memory de-allocation mechanism (cache eviction) to prevent the memory leak. One simple way to resolve this is by making use of Reference types introduced by Java.

Started from Java version 1.2, Java has introduced new reference types for us to have a limited degree of interaction with the garbage collector. Besides strong reference, an object now can have other reference types at the same time. There is 3 type of these new references, SoftReference, WeakReference and PhatomReference. Each weaker than the last and each corresponds to the different level of reachability. Unlike strong reference, these reference objects do not prevent their referent object to be reclaimed by the garbage collector when certain conditions are met. We will go into detail of each reference in the later sections.

In generally, we put an object as a referent into a reference object in order to create new reference type other than the strong reference. The referent object can be retrieved via Reference.get() method. The returned value could be null if the referent object has been collected. Therefore, we have to do a null check every time we retrieve our object from the reference objects. Below is the general usage of a WeakReference.

byte[] var = new byte[]{}; // byte[]{} object is strongly referenced by "var" variable.

Reference<byte[]> weakRef = new WeakReference<byte[]>(var); // byte[]{} object is weakly referenced by "weakRef" variable.

/**
 * At this point, byte[]{} object has strong and weak reference at the same time.
 * Stronger reference effect always supersede weaker reference effect.
 */

System.gc();
System.out.println(weakRef.get() == null); // result: false. Not null because strong reference still intact.

var = null; // Strong reference to the byte[]{} gone. The weak reference effect now can takes over.

System.out.println(weakRef.get() == null); // result: false. Not null because garbage collection not happen.
// We can create new strong reference by assigning the return value to a variable.

System.gc();
System.out.println(weakRmf.get() == null); // result: true. The byte[]{} object has been(collected.

Soft Reference

We can create a soft reference to an object by wrapping the object as a referent into a SoftReference object. An object is softly reachable if it is not strongly reachable and it can be reached by traversing the SoftReference object. In the following diagram, the BigDecimal object becomes softly reachable right after the strong reference (highlighted in red) of referent object is removed.

Soft reachability

When an object is softly reachable and the memory is sufficient, the garbage collector has the freedom to decide whether or not to reclaim the object during garbage collection cycles. However, it guarantees to reclaim softly reachable objects before the OutOfMemoryError is thrown. Execute the following program with heap size -Xmx5m.

List<Reference<ByteBuffer>> list = new ArrayList<>();
for (int i = 1; i <= 6; i++) {

    System.gc(); // trigger garbage collection

    // create soft reference to 1M big object
    list.add(new SoftReference<>(ByteBuffer.allocate(1000000)));

    System.out.println("----------------- Round " + i + " -----------------");
    list.forEach((ref) -> {
        System.out.println(ref + ": " + ref.get()); 
    });
}

As you can see from the result below, even though the garbage collection is triggered in every loop but the objects only be reclaimed when there is not enough memory to create a new object.

----------------- Round 1 -----------------
java.lang.ref.SoftReference@548c4f57: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
----------------- Round 2 -----------------
java.lang.ref.SoftReference@548c4f57: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
java.lang.ref.SoftReference@1218025c: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
----------------- Round 3 -----------------
java.lang.ref.SoftReference@548c4f57: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
java.lang.ref.SoftReference@1218025c: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
java.lang.ref.SoftReference@816f27d: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
----------------- Round 4 -----------------
java.lang.ref.SoftReference@548c4f57: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
java.lang.ref.SoftReference@1218025c: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
java.lang.ref.SoftReference@816f27d: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
java.lang.ref.SoftReference@87aac27: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
----------------- Round 5 -----------------
java.lang.ref.SoftReference@548c4f57: null
java.lang.ref.SoftReference@1218025c: null
java.lang.ref.SoftReference@816f27d: null
java.lang.ref.SoftReference@87aac27: null
java.lang.ref.SoftReference@3e3abc88: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
----------------- Round 6 -----------------
java.lang.ref.SoftReference@548c4f57: null
java.lang.ref.SoftReference@1218025c: null
java.lang.ref.SoftReference@816f27d: null
java.lang.ref.SoftReference@87aac27: null
java.lang.ref.SoftReference@3e3abc88: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
java.lang.ref.SoftReference@6ce253f1: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]

Given the characteristic of the soft reference, it can be used to implement memory sensitive cache. However, this is not the perfect solution (as per stated in SoftReference JavaDoc) as we should prevent garbage collector to reclaim recent created and recently used objects.

Weak Reference

WeakReference works similarly like SoftReference. An object is weakly reachable if it is neither strongly nor softly reachable and it can be reached by traversing the WeakReference object. As I've mentioned before, an object could have multiple references at the same time. However, the stronger reference effect always supersedes the weaker one. A weakly reachable object always be reclaimed during garbage collection cycle regardless the memory is sufficient or not. Execute the same program in the Soft Reference section with heap size -Xmx5M but this time change the reference type of big object to WeakReference.

The result shows that every newly created weakly reachable object was always reclaimed during garbage collection cycle in every loop.

----------------- Round 1 -----------------
java.lang.ref.WeakReference@548c4f57: null
----------------- Round 2 -----------------
java.lang.ref.WeakReference@548c4f57: null
java.lang.ref.WeakReference@1218025c: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
----------------- Round 3 -----------------
java.lang.ref.WeakReference@548c4f57: null
java.lang.ref.WeakReference@1218025c: null
java.lang.ref.WeakReference@816f27d: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
----------------- Round 4 -----------------
java.lang.ref.WeakReference@548c4f57: null
java.lang.ref.WeakReference@1218025c: null
java.lang.ref.WeakReference@816f27d: null
java.lang.ref.WeakReference@87aac27: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
----------------- Round 5 -----------------
java.lang.ref.WeakReference@548c4f57: null
java.lang.ref.WeakReference@1218025c: null
java.lang.ref.WeakReference@816f27d: null
java.lang.ref.WeakReference@87aac27: null
java.lang.ref.WeakReference@3e3abc88: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]
----------------- Round 6 -----------------
java.lang.ref.WeakReference@548c4f57: null
java.lang.ref.WeakReference@1218025c: null
java.lang.ref.WeakReference@816f27d: null
java.lang.ref.WeakReference@87aac27: null
java.lang.ref.WeakReference@3e3abc88: null
java.lang.ref.WeakReference@6ce253f1: java.nio.HeapByteBuffer[pos=0 lim=1000000 cap=1000000]

The weak reference can be used to prevent the memory leak of a program written in listener or observer pattern. When the Subject has a life span longer than the Observer we need a way to remove the out of scope observers. The appropriate approach is to explicitly unregister (unreference) the observers when they go out of scope. However, this requires the programmer awareness to do so. Failure of unregistering the out of scope observers will not cause any immediate error impact and the program still can run successfully as long as the memory is sufficient. However, in long run, the subject keeps accumulating (strongly referenced) un-used observers and could end up one day exhaust the memory and hit the OutOfMemoryError.

Given the TaskAgent class as Subject.

// TaskAgent as Subject
public class TaskAgent {

    private List<ITaskListener> taskListeners = new ArrayList<>();

    public void registerTaskListener(ITaskListener taskListener) {
        taskListeners.add(taskListener);
    }

    public void acceptTask(String task) {
        taskListeners.forEach((taskListener -> taskListener.doWork(task)));
    }

    public void unregisterTaskListener(ITaskListener taskListener) {
        taskListeners.remove(taskListener);
    }
}

The Worker class as Obverser to react when TaskAgent accepts new task. Noted that a 1M ByteBuffer object is added to the worker object in order to simulate the OutOfMemoryError if worker objects failed to be reclaimed.

public interface ITaskListener {
    void doWork(String task);
}

// Worker as Observer
public class Worker implements ITaskListener {

    private String name;

    // to simulate OutOfMemoryError
    private ByteBuffer bb = ByteBuffer.allocate(1000000);

    public Worker(final String name) {
        this.name = name;
    }

    @Override
    public void doWork(final String task) {
        System.out.println(name + " is working on " + task);
    }
}

The App class for execution.

public class App {

    public static void main(String[] args) {

        TaskAgent agent = new TaskAgent();

        int i = 1;
        while (true) {
            System.gc();
            Worker worker = new Worker("worker" + i);
            agent.registerTaskListener(worker);
            agent.acceptTask("task" + i);
            System.out.println("-------");
            agent.unregisterTaskListener(worker);
            i++;
        }
    }
}

In the App above, task agent has a long life span but each worker only live within a while-loop iteration scope. When the worker goes out of scope it becomes un-used and should be cleared by the garbage collector in the beginning of next iteration. Execute the App with -Xmx3M, the App can run endlessly. However, if we comment the unregisterTaskListener() method, we will hit the OutOfMemoryError in a couple of iterations as below.

worker1 is working on task1
-------
worker1 is working on task2
worker2 is working on task2
-------
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

To achieve the same result as per explicitly unregisterTaskListener(), we can make use of weak reference in TaskAgent as below.

public class TaskAgent {
    
    private List<WeakReference<ITaskListener>> weakRefTaskListeners = new ArrayList<>();

    public void registerTaskListener(ITaskListener taskListener) {
        weakRefTaskListeners.add(new WeakReference<ITaskListener>(taskListener));
    }

    public void acceptTask(String task) {
        for (Iterator<WeakReference<ITaskListener>> iter = weakRefTaskListeners.iterator(); iter.hasNext();) {
            WeakReference<ITaskListener> weakRef = iter.next();
            ITaskListener taskListener = weakRef.get();
            if (taskListener != null) {
                taskListener.doWork(task);
            } else {
                iter.remove();
            }
        }
    }

    // remain this method for explicitly unregister worker
    public void unregisterTaskListener(ITaskListener taskListener) {
        for (Iterator<WeakReference<ITaskListener>> iter = weakRefTaskListeners.iterator(); iter.hasNext(); ) {
            WeakReference<ITaskListener> weakRef =  iter.next();
            if (taskListener == weakRef.get()) {
                iter.remove();
                break;
            }
        }
    }
}

In this case, if the programmer forgets or not aware of explicit call the unregisterTaskListener(), the App still can run endlessly.

Another usage of WeakReference is to associate two objects where one object's lifespan is tightly coupled with another object's lifespan. The reason probably because of the relationship of these 2 objects is rare and temporary hence not worth to introduce and maintain a new class just to bind them together. We can do this by using WeakHashMap, a map with weak keys which do not prevent themselves to be reclaimed when their referent objects become weakly reachable. When keys are discarded by the garbage collector, the corresponding map entries will also be cleared automatically. Below is an example of mapping of Animal object and Image object.

public class App {

    public static void main(String[] args) {

        Animal cow = new Animal("cow");

        Map<Animal, Image> map = new WeakHashMap<>();
        map.put(cow, new BufferedImage(10, 10, 10));

        System.out.println(map.get(cow) != null); // true

        System.gc();
        System.out.println(map.get(cow) != null); // true

        cow = null; // "cow" object goes out of scope
        System.gc();
        for (Map.Entry<Animal, Image> entry : map.entrySet()) {
            System.out.println("never reach this point");
        }
    }
}

class Animal {

    String name;

    public Animal(final String name) {
        this.name = name;
    }

    @Override
    public boolean equals(final Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Animal animal = (Animal) o;

        return name.equals(animal.name);
    }

    @Override
    public int hashCode() {
        return name.hashCode();
    }
}

Phantom Reference and Reference Queue

It is confusing if we try to understand phantom reference by making a analogy of how we make use of soft and weak reference. While the phantom reference belong to the Reference family, but its function is quite different than the soft and weak reference. An object is phantom reachable if it is neither strongly, softly nor weakly reachable, it has been finalized and there is a phantom reference refers to it. When an object becomes phantom reachable, that's mean it has been finalized and we has no chance to get back the same object again. In fact, PhantomReference implementation always return null when we invoke get() method even though the referent object is currently being strongly referenced. So, what the phantom reference can do in this case? Working in conjunction with ReferenceQueue, phantom reference can be a better choice of scheduling cleanup action instead of using Java finalization mechanism.

A phantom reference object need to be registered to a reference queue. When its referent object is finalized, the garbage collector will append the phantom reference object onto the reference queue. The ReferenceQueue provides methods such as poll() (non-blocking) and remove() (blocking) which allow the caller to examine if the referent object has been finalized. If yes, then proceed with the cleanup action. By doing this, it is the caller thread responsibility to make sure the cleanup action take place. This is more flexible, reliable, and predictive compare to relying on Finalizer daemon thread to do the same thing.

The reference queue is not particularly used for phantom reference only. It can be used with soft and weak reference as well. However, the timing when the garbage collector enqueues the soft/weak reference objects and phantom reference objects are different. The timing when phantom references objects are enqueued is after the referent object is finalized. But the timing when soft and weak reference objects are enqueued is when the referent objects are marked as finalizable. Technically, that is mean we still can obtain or even "resurrect" the dying referent objects by creating new strong references to them at the finalization stage. This will never happen in using phantom references because the referent objects has passed the finalization stage. Moreover, you will never able to get the referent object from a phantom reference object.

Timing to enqueue reference objects into reference queue

The phantom reference has a special behavior that we need to pay attention with. As per stated in JavaDoc,

"Unlike soft and weak references, phantom references are not automatically cleared by the garbage collector as they are enqueued. An object that is reachable via phantom references will remain so until all such references are cleared or themselves become unreachable."

Meaning we must explicitly clear the phantom reference objects as well as the reference queue object in order for the garbage collector to fully reclaim the referent objects. In the following program (which run with -Xmx5M), I try to load a new 4M big object only after the previous big object is totally gone.

public class App {
    public static void main(String[] args) {

        ByteBuffer bb = ByteBuffer.allocate(2000000);
        ReferenceQueue queue = new ReferenceQueue();
        PhantomReference<ByteBuffer> pr = new PhantomReference<>(bb, queue);

        bb = null; // remove strong reference of big object
        System.gc(); // reclaim the big object

        try {
            Reference ref = queue.remove(2000);
            if (ref == pr) {
//                ref = null;
//                pr = null;
                System.out.println("Finalized...");
            } else {
                System.err.println("Cannot be finalized..");
            }
        } catch (InterruptedException e) {
        }

        ByteBuffer.allocate(2000000); // create new big object
    }
}

The program hits out of memory error when reach the line of creating new big object. There are 2 ways to resolve this.

First is to explicitly de-reference the phantom reference object and reference queue object by assigning null to them. The program can run successfully by un-commeting the commented null assignment lines.

Second is to change the reference type to weak reference. However, we have to make sure we don't implement object finalizer which could eventually prevent the object from being reclaimed. I am not sure why there is no auto clearing in phantom reference. According to the answer in this stackoverflow, auto clearing for phantom reference will be in place in Java 9.


References:
https://docs.oracle.com/javase/7/docs/api/java/lang/ref/package-summary.html
http://stackoverflow.com/questions/41396051/phantomreference-with-null-queue
https://community.oracle.com/blogs/enicholas/2006/05/04/understanding-weak-references
http://www.kdgregory.com/?page=java.refobj

Java Concurrency in Practice - Chapter 2 - Thread Safety

What is thread safety?

A class is thread-safe if it behaves correctly when accessed from multiple threads, regardless of the scheduling or interleaving of the execution of those threads by the runtime environment, and with no additional synchronization or other coordination on the part of the calling code.

Thread-safe classes encapsulate any needed synchronization so that clients need not provide their own.

Stateless objects are always thread-safe.

Atomicity

A race condition occurs when the correctness of a computation depends on the relative timing or interleaving of multiple threads by the runtime; in other words, when getting the right answer relies on lucky timing.

Race condition due to common compound actions below:

• read-modify-write: e.g. hit count incrementing
• check-then-act: e.g. lazy initialization

To avoid race condition, compound actions need to be atomic. Operations A and B are atomic with respect to each other if, from the perspective of a thread executing A, when another thread executes B, either all of B has executed or none of it has. An atomic operation is one that is atomic with respect to all operations, including itself, that operate on the same state.

Locking

When multiple variables participate in an invariant, they are not independent: the value of one constrains the allowed value(s) of the others. Even if they are atomic references which individually thread-safe, they can't avoid the race condition. To preserve state consistency, update related state variables in a single atomic operation.

Intrinsic locks

Java built-in locking mechanism for enforcing atomicity. synchronized block.

A synchronized block has 2 parts:

• a reference to an object that will serve as the lock; once a thread acquire this lock, other threads must wait, until the thread releases the lock.
• a block of code to be guarded by that lock; appear to execute as a single, indivisible unit.

Every Java object can implicitly act as a lock for purposes of synchronization; these built-in locks are called intrinsic locks or monitor locks. Intrinsic locks in Java act as mutexes (or mutual exclusion locks)

The synchronized block can easily make a class thread-safe. Using it carelessly, such as synchronizing the entire method can cause threads congestion which leads to another serious problem, which is the performance problem.

Intrinsic locks are reentrant. If a thread tries to acquire a lock that already holds, the request succeeds. Reentrancy saves us from the deadlock in the situation where a subclass overrides the synchronized method (e.g. doSomething()) of its parent class, then in overridden method subclass calls super.doSomething() method.

Guarding state with locks

For each mutable state variable that may be accessed by multiple threads, all accesses to that variable must be performed with the same lock held. In this case, we say that the variable is guarded by that lock.

Every shared, mutable variable should be guarded by exactly one lock. Make it clear to maintainers which lock that is. The fact is any Java object can be the lock object besides the intrinsic lock which is just a convenience so that you need not explicitly create lock objects.

For every invariant that involves more than one variable, all the variables involved in that invariant must be guarded by the same lock.

Liveness and performance

Too much of synchronization can lead to liveness or performance problems such as poor concurrency and poor responsiveness.

Improve concurrency while maintaining thread safety by narrowing the scope of the synchronized block. Not too small; you would not want to divide an operation that should be atomic into more than one synchronized block. But it is reasonable to try to exclude from synchronized blocks long-running operations that do not affect shared states, so that other threads are not prevented from accessing the shared state while the long-running operation is in progress.

Deciding how big or small to make synchronized blocks may require tradeoffs among competing design forces, including safety (which must not be compromised), simplicity, and performance. Resist the temptation to prematurely sacrifice simplicity (potentially compromising safety) for the sake of performance. A reasonable balance can usually be found.

Avoid holding locks during lengthy computations or operations at risk of not completing quickly such as the network or console I/O.

Java Concurrency in Practice - Chapter 1 - Introduction

Benefits of threads:

• Exploiting multiple processors.

• When properly designed, multithreaded programs can improve throughput by utilizing available processor resources more effectively.
• On single processor systems, while one thread is blocked/wait for a synchronous event such as I/O operation to complete, the another thread can still run, allow the application make progress.

• Simplicity of modeling.

• A program that processes one type of task sequentially is simpler to write, less error-prone, and easier to test than one managing multiple different types of tasks at once. With multi threads available, a complicated, asynchronous workflow can be decomposed into a number of simpler, synchronous workflows each running in a separate thread.

• Simplified handling of asynchronous events.

• In a single-threaded application, an I/O block could stall the whole processing. To avoid this problem, single-threaded applications are forced to use non-blocking I/O, which is far more complicated and error-prone than synchronous I/O.

• More responsive user interfaces.

• If the code called from the main event loop takes too long to execute, the user interface appears to "freeze" until that code finishes, because subsequent user interface events cannot be processed until control is returned to the main event thread. By assigning the long-running task to a separate thread, the main event thread remains free to process UI events, making UI more responsive.

Risks of threads

• Safety hazards

• Safety = nothing bad ever happens.
• Example: race condition.
• In the absence of sufficient synchronization, the ordering of operations in multiple threads is unpredictable and sometimes surprising. 

• Liveness hazards

• Liveness = something good eventually happens.
• Example: deadlock, starvation, livelock.
• A liveness failure occurs when an activity gets into a state such that it is permanently unable to make forward progress.

• Performance hazards

• Performance = good thing to happen quickly.
• Example: poor service time, responsiveness, throughput, resource consumption, scalability.
• Context switches: when the scheduler suspends the active thread temporarily so another thread can run. The higher number of threads, the higher significant costs for saving and restoring execution context, loss of locality, and CPU time spent scheduling threads instead of running them.
• The synchronization of shared data can inhibit compiler optimizations, flush or invalidate memory caches, and create synchronization traffic on the shared memory bus.

Java 8 Lambda Expression

What is Lambda Expression?

Lambda expression is also known as Anonymous Function. A function without the name nor bounded to an identifier.

It is First-class Function. That's mean we can pass the anonymous function as an argument to other functions, return it as a value from other functions, assign it to variables or store it into a data structure.

It models code as data which can be passed around and invoked in the later stage in the other functions.

Why does Java need Lambda?

• To eliminate the boilerplate code (of using anonymous inner class) in modeling the "code as data" so that it become lightweight, shorter and straight to the point. This is handy when working with libraries and frameworks that are designed to accept callback object which provides nothing but just a function. The typical example is to provide a sole purpose ActionListener to a JButton in Swing framework. 
  
  

  button.addActionListener(new ActionListener() {
     @Override
     public void actionPerformed(ActionEvent e) {
        label.setText(e.getActionCommand() + " is clicked");
     }
  });
  

  
  Using lambda expression, we can do the same thing in just one line as below.
  
  

  button.addActionListener(e -> label.setText(e.getActionCommand() + " is clicked"));
  

  
  
• To gain the advantage of declarative programming. "Declarative Programming - A style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow" - Wikipedia. In short, it is a programming style that describes the what to be achieved and hides the how to accomplish it. For example, prior to Java 8, iteration on a Java Collection has to be done explicitly and each element has to be processed in sequence.
  
  

  // for each of the increment of the integer i, start from 0 until we reach the size of list
  for (int i=0; i<list.size(); i++) {
      String e = list.get(i); // get the element from the list
      System.out.println(e); // print the element
  }
  

  
  Using lambda expression in Java 8, the iteration can be abstracted and done internally by the library.
  
  

  // for each element in the list, print the element
  list.forEach((e) -> System.out.println(e));
  

  
  As you can see, this abstraction makes the code easier to read. No more grandmother's tales. Besides, this abstraction also provides the opportunity to the Java Collections library to manage the control flow more efficiently and better performance by using of reordering of the data, parallelism, short-circuiting, or laziness. All these implementations detail are hidden from the programmer.


• To be friendly with functional programming. The programmer now has another choice of approach/design to resolve a problem beside object-oriented pattern. The Java Collections framework had adopted the functional design pattern and provides the Streams API which is a good place for the programmer to getting start with functional programming. Furthermore, the idea of stateless and immutable data in functional programming make the program run safely and predictable in the multi-threaded environment. You can find more examples in "Functional programming in Java" section. 

Lambda expression in Java

The lambda expression appears in the form of function. In general, a function is a piece of calculation that takes the input and return an output. The arrow token -> is used to separate the parameter (on the left) and expression body that might return value (on the right). Below are examples of lambda expression in Java. Note, the first four examples are doing the same thing.

// parameter -> expression body
(int x) -> { return x * x; };

// without explicit type information
(x) -> { return x * x; };

// without return syntax and curly bracket
(x) -> x * x;

// without bracket for parameter
x -> x * x;

// without parameter and return value
() -> System.out.println("x");

Lexical Scope

Unlike the inner class, lambda expression does not create a new level of scoping. It is lexically scoped which mean the names (and this) in the lambda expression body are interpreted just as they are in its enclosing environment. Refer to the code example below, see the different and get the idea.

public class HelloWorld {
    
    Runnable inner1 = new Runnable() { // New scope is created
        @Override
        public void run() {
            // "this" refers to inner1 instance itself
            System.out.println(this);
        }
    };
    
    Runnable inner2 = new Runnable() { // New scope is created
        @Override
        public void run() {
            // "toString()" of inner class has shadowed the "HelloWorld.toString()"
            System.out.println(toString());
        }
    };

    // "this" refers to this HelloWorld instance
    Runnable lambda1 = () -> System.out.println(this); 

    // "HelloWorld.toString()"
    Runnable lambda2 = () -> System.out.println(toString());  
    
    public String toString() {
        return "Hello, world!";
    }

    public static void main(String... args) {
        new HelloWorld().inner1.run(); // HelloWorld$1@548c4f57
        new HelloWorld().inner2.run(); // HelloWorld$2@1218025c
        new HelloWorld().lambda1.run(); // Hello, world!
        new HelloWorld().lambda2.run(); // Hello, world!
    }
}

How does Java promote Function to First-Class Citizen?

A programming language supports "first-class function" if it treats the function as the first class citizen. Java is primary object-oriented programming language where a function must reside in an object/class. In order to support the first-class function, Java requires Functional Interface as the type for lambda expression and perform Target Typing to fade out the existence of an object while at the same time only highlight the function of this object.

Functional Interface

Every instance in Java must have a type. Java does not introduce new type such as Function Type for lambda expression due to the challenges of complexities and incompatibility with Java typing system. Instead, Java converts lambda expression to a functional interface type, an interface which only has the single abstract method.

The functional interface is best fit into Java typing system and compatible with all common existing libraries. The existing Java libraries can have benefited from lambda expression without radical change or rewrite.

We can create our own functional interface. By marking the interface class with @FunctionalInterface, the compiler will make sure it fits the requirement of being a functional interface.

We can also make use of the common functional interfaces provided by Java.

• Function<T, R>: Represents a function that accepts one argument and produces a result.
  e.g. (Integer x) -> x.toString();
• Consumer<T>: Represents an operation that accepts a single input argument and returns no result.
  e.g. (String x) -> System.out.println(x);
• Supplier<T>: Represents a supplier of results.
  e.g. () -> "Hello";
• Predicate<T>: Represents a predicate (boolean-valued function) of one argument.
  e.g. (String x) -> x.equals("X");
• UnaryOperator<T>: Represents an operation on a single operand that produces a result of the same type as its operand.
  e.g. (Integer x) -> x + 2;
• BinaryOperator<T>: Represents an operation upon two operands of the same type, producing a result of the same type as the operands.
  e.g. (Integer x, Integer y) -> x + y; 

Besides the basic functiona interfaces above, Java also provides common function interfaces for

• Primitive specification such as IntFunction<R> that accepts an int-valued argument and produces a result.
  e.g. (int x) -> x.toString(); 
• Multi arities specification such as BiFunction<T, U, R> that accepts two arguments and produces a result.
  e.g. (String x, Integer y) -> x + y;

Target Typing

The functional interface does not appear in the lambda expression as per the following example. 

() -> "Hello";

Both the Callable and PrivilegedAction are the valid type for lambda expression above, but which one to choose? The answer depends on the expected type in the context (target type) where the lambda expression appears. The lambda expression must appear in the context whose target type is a functional interface. The Java compiler responsible for inferring the target type gives any compilation error if it can't find the target type for a lambda expression. Below are lambda expressions in the different context and the target types are highlighted in yellow.

// Assignment
Consumer<String> c = x -> System.out.println(x);

// Array initializer
IntConsumer[] cc = new IntConsumer[] {
    x -> System.out.println(x + 1),
    x -> System.out.println(x + 2),
    x -> System.out.println(x + 3)
};

// Lambda expression body
Supplier<Consumer<String>> s = () -> (x) -> System.out.println(x);

// Conditional expression
IntFunction<Integer> f = true ? x -> 1 : x -> 2;

// Cast expression
Consumer<String> ccast = (Consumer<String>) (x) -> System.out.println(x);

// Return statement
public Consumer<String> todoLater() {
    return x -> System.out.println(x);
}

The target types for the contexts above are obvious. However, this is not the case for Method argument context. Given the overloaded methods below.

public static void doSomething(Callable r) {
}

public static void doSomething(PrivilegedAction t) {
}

// Method argument - Method overloading
doSomething(() -> "Hello"); // Compilation error: reference to doSomething is ambiguous

Passing a lambda expression into doSomething() method causes compilation error due to the overloaded methods which lead to ambiguous target type; Java compiler does not know exactly which the method is referencing to. The similar case happens to the Generic method. Given the generic method in Example class below.

public static <T> void process(UnaryOperator<T> c) {
}

// Method argument - Type argument inference
Example.process(x -> x + 1); // Compilation error

In this case, the data type for x is ambiguous. It could be String or Integer. Whenever the Java compiler can't figure out the target type, we can help by providing the explicit type information.

// Method argument - Method overloading
doSomething((Callable)() -> "Hello");

// Method argument - Type argument inference
Example.<String>process(x -> x + 1);

What are the Method References?

Method references expression has the same characteristics as the lambda expression. It is encoded in a functional interface instance and requires a target type. However, instead of providing a function body, it just refers to an existing method. In other words, we can promote an existing method to become the first-class function. 

The following code examples are a different kind of method references expression. I put the lambda expression together with the corresponding method reference expression, so you can see the difference and get the idea. Both of them will give the same result.

A static method (ClassName::methodName)

BiFunction<Integer, Integer, Integer> operation = (x, y) -> Integer.sum(x, y); // lambda
BiFunction<Integer, Integer, Integer> operation = Integer::sum; // method reference
operation.apply(1, 2); // 3

An instance method of a particular object (instanceRef::methodName)

List<String> list = Arrays.asList("a", "b");
Predicate<String> condition = (x) -> list.contains(x); // lambda
Predicate<String> condition = list::contains; // method reference
condition.test("a"); // true

A super method of a particular object (super::methodName)

class Person {
    public void print() { System.out.println("Person"); }
}

class Worker extends Person {

    private String name;
    
    public Worker(String name) { this.name = name; }
    
    @Override
    public void print() { System.out.println(name); }
    
    public Runnable parentPrint() {
        return () -> super.print(); // lambda
        return super::print; // method reference
    }
}

Worker worker = new Worker("HauChee");
worker.parentPrint().run(); // "Person"

An instance method of an arbitrary object of a particular type (ClassName::methodName)

Worker worker = new Worker("HauChee");
Consumer<Worker> consume = (w) -> w.print(); // lambda
Consumer<Worker> consume = Worker::print; // method reference
consume.accept(worker); // "HauChee"

A class constructor reference (ClassName::new)

Function<String, Worker> makeWorker = (x) -> new Worker(x); // lambda
Function<String, Worker> makeWorker = Worker::new; // method reference
makeWorker.apply("Lew"); // create worker with name "Lew"

An array constructor reference (TypeName[]::new)

IntFunction<int[]> makeIntArray = (i) -> new int[i]; // lambda
IntFunction<int[]> makeIntArray = int[]::new; // method reference
makeIntArray.apply(10);  // creates an int[10]

Functional programming in Java

Java 8 lambda expression makes functional programming in Java much easier. It gives us another choice of programming style in resolving our problem. Therefore, why not get to know what is it and get a taste of it?

"Functional programming - A style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state (stateless) and mutable data (immutable)." - Wikipedia. 

High Order Function

A function that takes one or more other functions as its input arguments or returns a function as the result. In the code example below, negate is a high order function that takes a function argument and returns a new function which will negate the function argument result.

Function<Integer, Boolean> isZero = x -> x == 0;
isZero.apply(0); // true

Function<Integer, Boolean> isNegative = x -> x < 0;
isNegative.apply(-1); // true

// High order function
Function<Function<Integer, Boolean>, Function<Integer, Boolean>> negate = (func) -> (x) -> !func.apply(x);

Function<Integer, Boolean> isNotZero = negate.apply(isZero);
isNotZero.apply(0); // false

Function<Integer, Boolean> isPositive = negate.apply(isNegative);
isPositive.apply(-1); // false

In the next section, there are 3 different functional programming techniques are demonstrated in order to resolve the following simple formula.

x * y + z where x = 4, y = 10, z = 3

Function Composition

A technique to composites multiple functions into a function When this function is invoked the complete formula is evaluated and return the result.

Function<Integer, Integer> times10 = x -> x * 10;
Function<Integer, Integer> plus3 = x -> x + 3;

BinaryOperator<Function<Integer, Integer>> compose = (before, after) -> x -> after.apply(before.apply(x));

Function<Integer, Integer> times10plus3 = compose.apply(times10, plus3);
// a function that composites times10 and plus3
times10plus3.apply(4); // 43

// composition API provided by Java
times10.andThen(plus3).apply(4); // 43

Partial Function Application

A technique that partially resolves a portion of the formula and return a new function which carrying the resolved data. When this function is invoked then the rest of the formula portion is evaluated together with the resolved data.

BiFunction<Integer, Integer, Function<Integer, Integer>> partial = (x, y) -> z -> x * y + z;
// 4 * 10 is resolved to 40 first then only plus 3
partial.apply(4, 10).apply(3); // 43

Currying

A technique that takes multiple arguments into evaluating a sequence of functions, each with a single argument. It is like replacing the arguments into the formula one by one and evaluation only happen in the final stage.

Function<Integer, Function<Integer, Function<Integer, Integer>>> curry = x -> y -> z -> x * y + z;
r = curry.apply(4).apply(10).apply(3); // 43

Conclusion

The lambda expression might look weird especially for those who only practice object-oriented programming all the time. However, once we understand the concepts behind, get our hands dirty by trying it out, it can also become one of the useful tool for us in our coding life.

References:
http://www.oracle.com/technetwork/articles/java/architect-lambdas-part1-2080972.html
http://www.oracle.com/technetwork/articles/java/architect-lambdas-part2-2081439.html
http://www.oracle.com/webfolder/technetwork/tutorials/obe/java/Lambda-QuickStart/index.html#overview
http://cr.openjdk.java.net/~briangoetz/lambda/lambda-state-4.html
http://cr.openjdk.java.net/~briangoetz/lambda/lambda-state-final.html
http://cr.openjdk.java.net/~briangoetz/lambda/sotc3.html
https://dzone.com/articles/java-lambda-expressions-vs
https://dzone.com/articles/why-we-need-lambda-expressions
https://www.smashingmagazine.com/2014/07/dont-be-scared-of-functional-programming/
https://dzone.com/articles/functional-programming-java-8
https://en.wikipedia.org/wiki/Anonymous_function
https://en.wikipedia.org/wiki/First-class_function
https://en.wikipedia.org/wiki/Higher-order_function
https://en.wikipedia.org/wiki/Currying