Idiomatic way to have constructor methods required by interfaces

Question

I'm trying to initialize generic types in generic methods. I've since learned you can't require constructors in interfaces, so I figured out how to use generics to roughly fake the same behavior:

interface Stack<V, T>{
    public V getEmptyStack();  //V is supposed to be the subclass
    public V copy(V s);
    public void push(T e);
    public T pop();
    public boolean isEmpty();
}

class ArrayStack<T> implements Stack<ArrayStack<T>, T>{ //Have to pass subclass

    public ArrayStack<T> getEmptyStack(){ //Constructor returns type of the class.
        return new ArrayStack<T>();
    }
...

With the above defined, I can define a generic method "reverse":

public static <V, S extends Stack<S,V> > S reverse(S s){
    s = s.copy();
    S out = s.getEmptyStack(); //Trying to initialize out as simply as possible.
    while(!s.isEmpty()){
        out.push(s.pop());
    }
    return out;
}

I want the interface to require constructor methods which return the subtype implementing the interface. The current interface does this if it's implemented correctly; however it is a bit complicated.

If Java can't do this in a simpler way, I'd like to know the idiomatic patterns for initializing generic types. Would folks generally be less confused by getDeclaredConstructor and newInstance than what I wrote above? Or is what I wrote above fine?

Answer 1

Reflection is just the wrong bet. In general treating a Class<?> reference as a place for 'type-wide operations' is wrong.

It sounds enticing, though, doesn't it? Let's cover why it feels like the right answer, so that we know what alternative we need to find, because I'll follow this up why it's wrong.

Why Class<?> / static methods feels right

The class itself is the place where such things should live (operations that make sense on arraylist should live in the arraylist type - that's a statement that would get very broad agreement).

In java terminology, there are 2 different things that both serve as 'class-global' functions: Constructors, and static methods. At a more pragmatic level there is effectively zero difference between those two constructs: They both do not require a receiver (x.foo() - x is the receiver), and they both completely operate outside the type hierarchy. static methods cannot be inherited. The language makes it look like you do, but this is fake - they don't engage in dynamic dispatch, any call to a static method is 'linked' by javac and isn't going to change at runtime (vs. any call to an instance method, where the JVM will apply dynamic dispatch and call the most specific override). Constructors also cannot be.

Nevertheless, for an operation that doesn't make sense to call on any specific ArrayStack, but does make sense to call on the concept of 'array stacks', all our textbooks say: That should be a static method inside ArrayStack. And if the specific operation we want to perform results in the creation of a new one, we'd want a constructor (which is just a weird static method).

But, as I mentioned, static methods just do not 'do' inheritance or a type hierarchy - you cannot define static methods (or constructors) in an interface, period. So when you want the power of generics and type hierarchy, you just have to look elsewhere.

In theory you can indeed just pass Class<?> instances around and use .getConstructor().newInstance() as ersatz 'type hierarchy-engaging, generified constructors' and even use e.g. .getDeclaredMethod().invoke(null, params-go-here) to declare static methods.

But we've now left the typing system behind completely. It is not possible to use the type system to enforce a no-args constructor, or the existence of a static method. And reflection is very hard to work with (all sorts of exceptions that fall out, for example, and things are now 'stringly typed' - if you typo that static method the docs decree you must have, the compiler won't tell you. In constrast to fat-fingering the name of a method you must implement because you implements some interface, in which case javac will tell you immediately you did it wrong. The tooling also helps: I can just type the fist few letters of a method defined in an interface I implements, hit CMD+SPACE in eclipse, and eclipse instantly fills in all the blanks (the full name, public, the argument types and sensible names, even a throws clause if relevant and an @Override annotation). None of that is available if you attempt to use reflection to call into static methods or constructors.

Class<?> is also 'broken generics' - they can only go one level deep. You can have a Class<String>, and its .getConstructor().newInstance() method will have type String. But you simply cannot have a Class<List<String>> - there is only one class object for all strings, it cannot be generified. That's quite a deleterious downside of even trying.

So what do you do?

FACTORIES!

I know, I know. It's a meme. Oh, those crazy java programmers and their BeanFactoryCreatorMachineDoohickeyFactory craziness.

But, that's just, I guess, misleading. At least, don't let that deter you from using the concept, because it is precisely what you want here: It's type-system-engaged, generics-capable class-wide operations.

The idea is simple. Let's take this stack notion and decree that any implementation of the concept Stack must provide some type-wide operations, which includes making a new empty one, but may also include more operations. For example, consider a generalized number system (where you have some Number concept, and you have 'complex number', 'vector number', 'real number', 'number stored as divisor and dividend', and so on. You may want type-wide 'construct me a new instance of you, with this int value' but also a 'construct me a multiplicative unit value of yourself, e.g. 0 for real numbers, 0+0i for complex, an all-zeroes-except-for-a-diagonal-with-ones matrix, and so on' operation.

Factory is how you do that. You create a second type hierarchy that represents instances (generally, only one instance per type) that represents that object that is capable of doing these operations:

interface StackFactory {
  <T> Stack<T> create();
  boolean isRandomAccess();
}

// and an example implementation:

public class ArrayStackFactory implements StackFactory {
  <T> public ArrayStack<T> create() {
    return new ArrayStack<T>();
  }

  public boolean isRandomAccess() {
    return true;
  }
}

public interface Stack<T> { ... }
public class ArrayStack<T> implements Stack<T> { ... }

This does some of what you want:

Given 'some sort of StackFactory', you can just call create() on it and get a Stack<T> back. That's perfect. However, if you know the specific type of the stackfactory you get a more specific type back. This works:

ArrayStackFactory asf = ....;
ArrayStack<String> = asf.create();

One downside is here is that java doesn't let you 'program' your type vars. You therefore can't have a typevar representing the stack type (say, ArrayStack), and then have a method that combines that typevar with an element typevar and thus produce the type ArrayStack<String> from separate typevars ArrayStack and String. e.g. your reverse method can't quite get the job done.

This would have been very neat:

interface StackFactory<S extends Stack> {
  <T> S<T> create();
}

But that's a java limitation that you can't work around, other than by 'casting' to generics (which does nothing, other than make the compiler stop complaining. It doesn't actually type test), and @SuppressWarnings the warning the compiler throws at you when you do that.

---

EDIT: Upon request, how reverse would work. Also, as a bonus, when your 'factory' only needs to expose one thing (e.g. the interface would have just the one method), instead you can just use Supplier<X> (or Function<K, V> if the operation takes an argument, and so on - something from the java.util.function package). This is in fact exactly what Collection.toArray() takes (its signature is public <T> T[] toArray(IntFunction<T[]> arrayMaker) - where arraymaker turns a requested size into an array of that size, and can be as simple as String[]::new which is an IntFunction<String[]>):

public static <T> Stack<T> reverse(Stack<T> in) {
  Stack<T> out = in.factory().create();
  while (!in.isEmpty()) out.push(in.pop());
  return out;
}

This assumes the Stack interface is updated to require that all stacks are capable of returning their factory. Alternatively, you can instead require that the factory is part of the argument. This is how toArray works (you pass the factory in, in the form of an IntFunction<T[]>).

We can do that 'in one go', so to speak, and get rid of our 'util' class entirely (util classes are kinda ugly, they really shouldn't exist). Java has default methods now:

public interface Stack<T> {
  StackFactory factory();
  T pop();
  void push(T elem);
  boolean isEmpty();

  default Stack<T> reverse() {
    Stack<T> out = this.factory().create();
    while (!this.isEmpty()) out.push(this.pop());
    return out;
  }
}

Or even, using a pass-in factory:

public interface Stack<T> {
  T pop();
  void push(T elem);
  boolean isEmpty();

  default <S extends Stack<T>> S reverse(Supplier<S> supplier) {
    S out = supplier.get();
    while (!this.isEmpty()) out.push(this.pop());
    return out;
  }
}

to use that last one:

ArrayStack<String> myStack = ...;
ArrayStack<String> reversed = someArrayStack.reverse(ArrayStack::new);

Which is neat in that it even lets us assign to a variable of type ArrayStack which the rest of these options can't manage.

Answer 2

For starters, Stack doesn't need a 2nd generic type parameter declared on the type.

interface Stack<V, T> {
    public V getEmptyStack();

can become

interface Stack<T> {
    public <V> Stack<V> getEmptyStack();

That should simplify things quite a lot.

With the above defined, I can define a generic method "reverse":

You can do that without that weird method by choosing a different implementation. You're already modifying the input stack. You may as well reuse that instance.

public static <T, U extends Stack<T>> U reverse(U s){
    List<T> items = new ArrayList<>();
    while (!s.isEmpty()){
        items.add(s.pop());
    }
    for (int i = items.size() - 1; i >= 0; i--) {
        s.push(items.get(i));
    }
    return s;
}

Would folks generally be less confused by getDeclaredConstructor and newInstance than what I wrote above?

Yes, probably.

I want the interface to require constructor methods which return the subtype implementing the interface

If I had a real need for this - and I have in the past - then I'd just put a JavaDoc on the interface stating that requirement.