Generics in Java

Could we talk about generics and what problems they are meant to solve? The idea of them seems simple enough but when I try to use them a lot of strange things happen:

  1. I can’t use primitives as type parameters and have to box them.
  2. I can’t do something like T t = new T(), i.e. I can’t call a default constructor. (Probably related to type erasure)
  3. As an extension of the second point: How can I ensure that I only allow types which have the required functions I need for my code to work?

A bit of googling reveals that 3. is apparently a feature of C++ called concepts but a search for java generics concepts yields no results. I guess I could create an interface that all the classes I want to allow as type parameters have to implement but this is not flexible and ultimately it also has the problem that I still can not instantiate a single thing of generic type. For example I want to have a matrix class which has coefficients in something that provides ring operations:

// Ring.java
public interface Ring {
    Ring getInteger(int n); // the intent here is to create the element n * 1_R
    Ring add(Ring r, Ring r);
    Ring mult(Ring r, Ring r);
}

// Matrix.java
import java.util.ArrayList;
import java.util.List;

public class Matrix<T extends Ring> {

    private List<T> coefficients;
    private int rows, columns;

    public Matrix(int dimension) {
        this.rows = dimension;
        this.columns = dimension;
        this.coefficients = new ArrayList<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                this.coefficients.add(i == j ? /* what now? */));
            }
        }
    }
}

The constructor is supposed to output an n times n identity matrix and this is where it all breaks down:

  1. I can’t use arrays here because just like in the second point above the expression new T[rows * columns] causes IntelliJ to complain. So I guess I have to use lists.
  2. I can’t use the getInteger method of Ring to fill the coefficient list because I need an instance of type Ring to invoke them.
  3. I can’t make those methods static because it is impossible for an interface to have a factory method for itself.

As I think about this I realize that you can’t actually instantiate a stream, list or anything else generic that is in the standard library. The usual course of action is that you either build a generic object by taking another generic object and re-storing it (= changing the packaging) or essentially cheat and wait for the user to create an instance of a concrete class and then repackage that into your generic object. (= transferring the burden of instantiation onto the user)
The “standard library” solution to my code above would be to create a matrix factory which takes a List<T> in the constructor and then assign that to this.coefficients. Thus I will have to duplicate boilerplate code for generating the identity matrix in every class implementing Ring which is exactly the type of thing generics are supposed to eliminate.

But the fun doesn’t end: If I actually built a class IntegerPolynomials which implemented Ring and I used the constructor in Matrix<IntegerPolynomial> the interface methods of Ring would return something of type Ring as opposed to something of type IntegerPolynomial and I can’t return that to the user who expects T to be IntegerPolynomial.

So in conclusion:

  1. Is what I am trying to do even possible with generics? (= does this tool fit my problem?)
  2. If not, what is the point of generics? (= which problem is the tool supposed to solve?)
  3. Can an interface specify that a return value or argument of a method is of the type of the implementing class?

Great questions. I doubt you can fill a kNobel tutorial talking about weird generics things, so here’s an answer.

First of all, read The Java Collections Framework

In Java, Generics are a “compile-time” feature. At runtime, your code works with Objects instead, because type erasure happens during compile time. This means that all generic type variables are replaced by Object, and sufficient synthetic bridge methods and casts are inserted.

Primitive types unfortunately are not Objects, so they need to be boxed. Java tries to make this painless, and it usually works, but basically what happens is that instead of an int, you have a heap-allocated const int*. The Java designers know that this is unfortunate and hope to eventually resolve this: JEP draft: Universal Generics (Preview)

T t = new T() is impossible for the reasons above (at runtime, you don’t know what the type of T is), but also because not every type has a no-arg constructor. For example, Void is a class which can not really be constructed (since the constructor is private). Otherwise, you require that every type has a non-null inhabitant, which is not what you want.

Related to your Ring example, the important question is: what is a Ring. Concretely, is Ring the class of elements of the Ring, or the class representing the abstract datatype itself?

If the latter, your Ring (or a field, IDK) instance would look like this:

interface Ring<T> {
  T zero();
  T one();
  T add(T, T);
  T mul(T, T);
}

where T is the class representing members of the ring. You can then create a Ring<Integer> or a Ring<Polynomial<T>> from a Ring<T>. These constructions then mirror the mathematical constructions (i.e. by acting pointwise).

In general, creating instances of generic types is not supported. You can cheat and create a Supplier<T> that gives you new instances, but I don’t think that this is what you want here.

It’s not, really. Generics are just Java’s internal version of System F, where a \forall-typed identity function looks like this: <T> T id(T) – yes you can actually declare such a function in any class. It also allows you to declare higher-order types, which also is a very useful feature you would not have otherwise.

They do not really represent more advanced higher-order type class inference, which is the tool you are looking for here (i.e. where you can register a Ring<Integer> and by registring alone, certain functions become available on instances of Integer).

No.

Hope this answers your questions,
Johannes

1 Like

Thanks for this great answer!

Via the openJDK site you linked I found this very helpful explanation of how Java and C++ handle generics and why Java chose erasure. The JEP draft for Universal Generics linked above is part of a project to enhance generics in Java but I don’t understand enough about the inner workings of the JVM to get what exactly they want to change. But since a ctrl + f didn’t yield a result for heterogeneous translation I am afraid that we won’t be getting anything resembling concepts anytime soon.

If I understand your proposal for ring correctly you say that Ring should be parametrized so that the parameter T represents the underlying set of the ring and an implementation of Ring is nothing but putting a structure on T. That should work out in enforcing structure on the parameter. It is not as straightforward as I would want it to be but I guess I have to live with it.

Note that Java’s philosophy is to be explicit and in particular to always name things.

What you are likely looking for is something like impl Ring for i64. This has large non-local effects: Adding this impl somewhere suddenly makes code at a completely different place legal. In Java, your implementation needs to be specified at the use side, and be given a name.

Further, you can only have one instance of Ring for i64. While not that large of an issue for rings, there are many different monoids carried by \mathbb N, like (\mathbb N, +, 0) or (\mathbb N, *, 1) or (\mathbb N, \max, 0). In Java, this is easy since you can tell your different implementations apart, since they have names, and because “dynamic dispatch” (i.e. overriding) exists.

I didn’t think the the impl ... for ... was an actual snippet from a language, so I just thought of it as a vague idea. :smile: And now I found out that this is actual code:
https://doc.rust-lang.org/book/ch10-02-traits.html

This seems to do what I want (wrong language though) with the caveat you provided. Also Rust seems to support method definitions which accept and/or return something called self, i.e. the other thing I asked for earlier.

1 Like