[type hierarchy] Need for semi-sealed interfaces

[danieldietrich]

I'm not sure if this is worth the effort or if it makes completely sense. It is subject to think about before starting to implement it...

I think it might be better to add a clear specification to the API docs than introducing new types, blowing up the hierarchy and so on. Simplicity wins.

With #1801, we should instead update the API for the case the underlying collection is empty. Here for example: empty.prependAll(list) will return list if list is instanceof List.

---

Some of our collections are final classes, like Queue:

public final class Queue<T> {
    Queue<T> prependAll(Iterable<T> elements) {
        if (isEmpty() && elements instanceof Queue) {
            return (Queue<T>) elements; // <-- OK
        } else {
            ...
        }
    }
    ...
}

But other collections are interfaces, like List:

public interface List<T> {
    List<T> prependAll(Iterable<T> elements) {
        if (isEmpty() && elements instanceof List) {
            return (List<T>) elements; // <-- PROBLEMATIC
        } else {
            ...
        }
    }
    ...


    final class Nil<T> extends List<T> {
        ...
    }

    final class Cons<T> extends List<T> {
        ...
    }
}

The PROBLEMATIC line may be a security issue, if someone else implemented List and passed an instance to prependAll().

We are able to ensure that we return only own implementations by introducing a hidden, tagging type:

public interface List<T> {
    List<T> prependAll(Iterable<T> elements) {
        if (isEmpty() && elements instanceof SealedList) {
            return (List<T>) elements; // <-- OK (by convention)
        } else {
            ...
        }
    }
    ...

    final class Nil<T> extends SealedList<T> {
        ...
    }

    final class Cons<T> extends SealedList<T> {
        ...
    }
}

// tagging interface, not visible to the outside
interface SealedList<T> extends List<T> {
}

Note: We can't prevent users from implementing List. But we can prevent to return a user-implemented type when operating on user implementations. Therefore I call SealedList a 'semi-sealed' interface.

[Kreinoee]

Why not make List an abstract class instead of an interface. By giving the abstract List class an private constructor, we can ensure that only inner classes can extend it, and thereby guaranty that all instances of the List class is immutable.

Currently I consider List as not being immutable, because when I create a method that takes a List, client could just as well pass in there own mutable implementation. This is fine on the generel interfaces, but the concrete implementations (as List is one of), should be able to completely guaranty immutability.

[danieldietrich]

@Kreinoee You are right. To the time we initially designed the interfaces the future direction wasn't clear, e.g. adding mutable counterparts, parallel collection views, ...

But from the user-site viewpoint it makes absolutely sense to have abstract classes instead of interfaces. I will consider this change for the next major release 3.0.0.

Thank you!

[ruslansennov]

I will consider this change for the next major release 3.0.0.

yeaaaah

[danieldietrich]

yeaaaah

finally... it took some years to align my synapses to that idea :-)
but wait, I like these interfaces... just kidding ;)

[nfekete]

I see the List interface as a contract. While making it impossible for other classes to implement that contract might be a way to exclude the possibility that a non-conforming implementation will be passed to client code that expects a conforming implementation, that would come with a cost: no-one will be able to provide alternative (conforming) implementations. That would exclude legitimate use-cases no API designer can foresee. I think this kind of lock-in is counter-productive and risky, besides making the javaslang implementation more complicated.

And there's the other side of the story: why would I have to accept to be denied to implement a contract?

[danieldietrich]

@nfekete @Kreinoee true, that's what the (polymorphic) open/closed principle is all about.

Interface specifications can be reused through inheritance but implementation need not be. The existing interface is closed to modifications and new implementations must, at a minimum, implement that interface.

If an interface is not implemented as described by 'the contract' then it should be considered as a bug, not as a security hole. The same applies to java.util.List. I'm able to implement j.u.List.add(int, T) in a way that contradicts the API spec.

Our collections are defined to be immutable/persistent. I also question if we should deny the possibility of extension. In an object-oriented world the are numerous, unforeseeable requirements to change the behavior of a type (e.g. proxying, ...).

[danieldietrich]

With this issue we will focus to make the shortcuts safe (see above // <-- PROBLEMATIC) by introducing internal, sealed interfaces.

[Kreinoee]

But List is not the contract LinearSeq and Seq is. What does list add to the contract that these to interfaces is not?

List is an concreate implementation of linearSeq just as Queue is it, and Queue is a concrete class that cannot be extended. Also comparing List from javaslang with List from java.util is wrong, as List is more on the same level as java.util.LinkedList, where Seq and java.util.List is more alike.

Having interfaces defining the contract, and then concrete not extendable classes providing standard implementations that can guaranty either immutability or a certain performance behaviour is in my opinion really good practice. Then your can freely chose when implemting code, if your want to work on contract level, or instead needs the concrete implementations.

My quess is that the javaslang collection library is inspired by the scala collection framework, and if we look there, its actually done in this way. There are interfaces providing the contract, allowing for extendability, but the concrete implementations does not.

Another reason is that implementing a class, so it actually can be extended can complicate stuff a bit, so its often better to disallow concrete classes being extended, and instead define the functionality in an interface. We can look at the guidelines for implementing custom collections in java, they say to extend AbstractCollection, AbstractSet, AbstractMap and so on, instead of extending the conrete classes like ArrayList, even though this is possibly. I would guess that if they could make ArrayList and the similar classes final they would do so, as extending these has turned out to be problematic. However they cannot due to backward compability.

And finnally when the collections is used as fields in a class that needs to be fully immutable, then List is not an option as long as its an interface as illustrated her (assuming Person is an Immutable class) :

public final class Department {
    private final List<Person> employes;

    public Department(List<Person> employes) {
        this.employes = employes
    }

    public boolean containsAllTheseEmployes(Seq<Person> ) { ... }
}

However if I change the List to a Vector the class can guaranty immutability, as Vector is an concrete class that cannot be extended. I think that this both demonstrates a problem with List in it self, but also that it's confusing that there is such a fundamental difference on two classes, that is actually on the same level of the hierarchy, of the same collection library.

[danieldietrich]

@Kreinoee good discussion! you are absolutely right. Several Javaslang types need to be adjusted.

These are our real interfaces (white background):

These changes need to be performed:

• We remove Tuple and λ from the public API. Additionally we rename λ to Lambda because of several encoding problems of 3rd party libs in the past.
• This implies that we remove λ.Memoized from the public API
• We remove Kind1 from Kind2 (delete)
• Either, Option, Try and Validation need to be abstract classes with private constructor
• We remove Foldable from the public API, maybe we remove it completely
• BitSet, Iterator, List, Stream and Tree need to be abstract classes with private constructor
• We remove the Stack interface from the lib. It is just a name and not part of the collection hierarchy. List is a stack by itself.

Furthermore there are more types that should not be extended, i.e. they shouldn't be interfaces:

• API.Match.Case, API.Match.Pattern

I'm not sure if these types should or should not be interfaces. In Scala they are traits:

• Future, Promise

Note: We still need the Ordered interface to indicate that a collection has a Comparator for the underlying elements.

---

We need to be careful with internal (package-private/protected) abstract classes. These exists a bug the hinders us from using method references (see #1326 (comment), http://bugs.java.com/bugdatabase/view_bug.do?bug_id=8141122, http://bugs.java.com/bugdatabase/view_bug.do?bug_id=8068254)

[Kreinoee]

I must admit that I am not aware of the reasons for Future and Promise being traits in Scala, but my best guess would be, that they have no characteristics that forces them to be none extendable:

• They are mutable by nature.
• They promice no specific performance characteristics.

[danieldietrich]

See these tweets:

[danieldietrich]

We already do this in Vavr 1.0.

[danieldietrich]

Reopening it because I need to port this from the 2.0.0 branch to master.

Jean-Baptiste pointed this out already in the early days of Javaslang: #252