For my current project I’m using Java 11 and, since I last used with version 8, I thought that would be interesting to check the latest features and get a better feel of where the language is going.

In the previous blog post I presented an exercise I sometimes use during interviews and I thought I would do it with Java 16 latest features.

The exercise is about representing a binary tree and then implementing an algorithm that adds a unique identifier to each node.

The examples I present in the previous blog post use a functional approach to implement the algorithm.

As Java includes more and more functional features, I thought that would be interesting to use a similar style with Java16 and see how close is the Java implementation to the Scala and Dotty ones.

Once implemented with Java16, I realized doing it again with major Java versions would be a good way to understand how Java has evolved.

Java 16

The data structure for the Tree is implemented using a type similar to an algebraic datatype using the new ‘record’ feature (JEPS-395) for the product type and a class inheritance for the sum type.

public interface INode<T> {
}

public record Branch<T>(T value, INode<T> left, INode<T> right) 
    implements INode<T> {
}

public record Leaf<T>() implements INode<T> {
}

This is quite concise and removes all the getter/setter/equals/hashcode/constructor boilerplate that makes Java classes so verbose.

One trick I really like with that implementation is to add the id by storing a tuple in the tree: in the newly created tree, the new nodes will contain an id and the value from the previous tree.

As there is no native tuple support in Java (yet ?), quite a lot of libraries add it (c.f. https://stackoverflow.com/questions/2670982/using-pairs-or-2-tuples-in-java).

Instead of using one of them, I decided to use the type AbstractMap.SimpleEntry() which is in java.util.

AbstractMap.SimpleEntry<Integer,INode<AbstractMap.SimpleEntry<Integer,T>>> 
    addId(INode<T> node, Integer start) {
    INode<AbstractMap.SimpleEntry<Integer,T>> l = new Leaf<>();
    var r = new AbstractMap.SimpleEntry<>(start, l);

    if (node instanceof Branch<T> b) {
        var newLeft = addId(b.left(), start);
        var newRight = addId(b.right(), newLeft.getKey());
        var newBranch = new Branch<>(
                new AbstractMap.SimpleEntry<>(newRight.getKey(), b.value()),
                newLeft.getValue(),
                newRight.getValue()
            );
            r = new AbstractMap.SimpleEntry<>(newRight.getKey() + 1, newBranch);
    }
    return r;
}

The recursion on either the branch or the leaf is implemented with an ‘if’ clause as matching on types is not yet implemented in the new switch expression introduced in java16 (JEPS-361). Still, it is nice to use the pattern matching with type (JEPS-394) as it removes the possibility of runtime error with a failed type cast.

Another addition that reduces boilerplate code is the ‘var’ keyword but it cannot be used as extensively as in Scala. Even Scala type interference has limitations as it does not have a Hindley-Milner type system like ML languages or Haskell.

The type inference for generic creation also helps keep the code readable.

The full implementation is here.

Java 8

I decided to use is Java 8 as it was a major milestone and is still widely used.The main change in this implementation is that I didn’t use an algebraic data type to store the tree but instead relied on the ‘Optional’ type which was one of the new features of Java 8.

The tuple is still stored in the AbstractMap.SimpleEntry() as it was added in Java6. The ‘var’ keyword is no longer available so types need to be explicitly declared for all variables which makes the declarations less readable.

private Node<AbstractMap.SimpleEntry<Integer,T>> addId(Integer start) {
    Optional<Node<AbstractMap.SimpleEntry<Integer,T>>> 
        newLeft = left.map((n) -> n.addId(start));
    Integer leftIndex = newLeft.map((n) -> n.value.getKey() + 1).orElse(start);
    Optional<Node<AbstractMap.SimpleEntry<Integer,T>>> 
        newRight = right.map((n) -> n.addId(leftIndex));
    Integer rightIndex = newRight.map((n) -> n.value.getKey() + 1).orElse(leftIndex);

    return new Node<>(
        new AbstractMap.SimpleEntry<>(rightIndex, value),
        newLeft,
        newRight);
}

Still, the functional approach allows to use ‘map’ to extract the value in the Optional which is more elegant than using a ‘if’. Also, it makes refactoring a lot easier.

For example, newLeft can be replaced by its value in the expression:

Integer leftIndex = left.map((n) -> n.addId(start)).map((n) -> n.value.getKey() + 1).orElse(start);

And then the two consecutive ‘map’ can be combined into one:

Integer rightIndex = newRight.map((n) -> n.value.getKey() + 1).orElse(leftIndex);

As we need the intermediary values ‘newLeft’ and ‘newRight’ I didn’t use that simplification but I think it shows well how functional programming constructs help build programs which are easier to maintain and refactor.

Using Objects methods, the implementation of the ‘hashCode’ and ‘equals’ methods are not overtly verbose but the records really shine in comparison for their simplicity.

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Node<?> node = (Node<?>) o;
    return Objects.equals(value, node.value) &&
            Objects.equals(left, node.left) &&
            Objects.equals(right, node.right);
}

@Override
public int hashCode() {
    return Objects.hash(value, left, right);
}

The full implementation is here.

Java 6

Java 6 was another milestone release and probably the one that had the most impact, it was released in December 2006 and stayed the standard for almost 10 years. As a side note, I have never seen Java7 being used in production.

As it didn’t have any functional features, I implemented the tree using inheritance.  When Java6 was widely used, quite a lot of libraries like Google Guava and Apache Commons tried to fill the gap by adding collections with functional features. Removing them from the legacy code base to use Java8 new stream library is likely to keep quite a lot of programmers busy ;-).

This time, to store the tuple, I defined a new type ‘Pair’.

public final class Pair<T1,T2> {
    final T1 v1;
    final T2 v2;

    ...
}

On top of having to implement the getters/equals/hashcode, a difference that really surprised me with that implementation is the number of files. As both ‘Node’ and ‘Leaf’ inherit from ‘Tree’ they have to be in their own files, they cannot be inner classes.

Also having to define the equal/hashCode methods for all these classes is really painful so I added a paired down version of ‘Objects’. Because of inheritance, the algorithm is split in multiple classes which makes understanding it more complicated. Another aspect of OO that I forgot ;-).

In Java 6, generics come of age so they are used extensively here but they come at a cost, they don’t support the primitive types (Scala generics do). As an interesting side note, Martin Odersky the creator of Scala wrote the code that added support for generics in Java (c.f. https://www.cs.purdue.edu/homes/hosking/352/generics.pdf)

The implementation of the ‘Leaf’ as a Singleton is interesting. making the constructor private ensures only one instance exists. Singleton is actually a very ‘OO’ design pattern. In FP, without state, it is not needed.

Another peculiar aspect of ‘Leaf’ is the implementation of addId:

protected Pair<Integer, Tree<Pair<Integer, T>>> addId(Integer start) 
{
    return new Pair(start, this); 
}

At first glance that looks correct but it is not:

• ‘this’ is of type ‘Leaf' (so also Tree)
• but the second parameter of ‘Pair’ constructor is Tree<Integer,T>.

Logically that should not work as is different from <Integer,T> but because of [Java type erasure](https://docs.oracle.com/javase/tutorial/java/generics/erasure.html) it does.

As the class does not contain any value of T it is not an issue. Type erasure can cause issues so C# which came after Java  does not include it. Clearly the team that designed it learnt from Java.

The full implementation is here.

Java 2

For the last part of this article, I decided to try Java1.2 as it was called when released.

I choose Java 2 for practical reason, it was the earliest Java version that I could compile to without having to find a SPARCstation.

For that, I used the jdk option that allows to generate bytecode for previous java version. By trial and error I found out the earliest bytecode version each of these java versions can generate:

With generics not yet present in Java 2, I had to store the value in the node using an Object reference. Also, instead of using a generic tuple I use an object that contains an integer for the id and an object for the value.

public class Node extends Tree {
    private final Object value;
    private final Tree left;
    private final Tree right;

    public Object getValue() {
        return value;
    }

    public Node(Object value, Tree left, Tree right) {
        this.left = left;
        this.right = right;
        this.value = value;
    }

    protected Indexed addId(int start) {
        Indexed newLeft = left.addId(start);
        Indexed newRight = right.addId(newLeft.getIndex());

        return new Indexed(newRight.getIndex() + 1,
            new Node(new Indexed(newRight.getIndex(), this.getValue()),
                (Tree) newLeft.getValue(),    // main drawback of using 'Object'
                (Tree) newRight.getValue())); // casting is needed, possible runtime error
    }
}

The solution is more elegant than I was expecting as it contains only two type casts. Still when we use the values on the nodes, runtime error are possible because of the type casts.

This solution may very well compile with Java 1.0 as it doesn’t use inner classes (introduced in 1.1) or any of the collections classes (introduced in 1.2). In Java 1.0, the library collection consisted of hasmaps and array of objects, no lists or sets ;-).

The full implementation is here.

Conclusion

This quick tour of the changes in Java shows that the language has evolved significantly in 25 years, reflecting the move of functional programming from academia to industry as well as OO slight fall of fashion.

It would be interesting to compare how other widely used languages have evolved.

As a light python user for 15 years I have not seen such a change in python, even the highly controversial move from python2 to python3 has not affected me greatly as the changes for small code bases are quite minor.

I did use C++ and C extensively when using the STL was the standard, but I did not really use it ‘in anger’ recently, so I missed on the boost library as well as the lambda extensions. So I do not really have a feel of how much the idiomatic C++ style has evolved.

Although talking to C/C++ users, I have a feeling some are still very slow to embrace the new features. That reminded of William Gibson’s quote, “The future is already here; it’s just unevenly distributed.” (or was it from Bruce Sterling ;-) ?)

Haskell would be another interesting example as it is will very well suited to extensions, which has led to its own ‘boomerang’ effect, Simple Haskell.

Would you know of any other language that have evolved as much as Java ? Feel free to add comments below !