Java – How do existential types differ from interfaces

interfacesjavatype-systems

Given the existential type

T = ∃X.{op₁:X, op₂:X→boolean}

and this generic Java interface:

interface T<X> {
    X op₁();
    boolean op₂(X something);
}

What are the fundamental differences between the existential type and the Java interface?

Obviously there are syntactical differences, and Java's object-orientation (which also includes details such as hidden this parameters etc.). I'm not so much interested in these as in conceptual and semantic differences — though if someone would like to shed light on some finer points (such as the notational difference between T vs. T<X>), that would be appreciated too.

Best Answer

Hmm... That definition looks very similar to some haskell sample I've seen long time ago.

{-# LANGUAGE ExistentialQuantification #-}
data X = forall a . X { value :: a, viewValue :: a -> String }
instance Show X where show (X { value = x, viewValue = f}) = f x
sample :: [X]
sample = [X 3 show, X "abc" show, X 3.14 show]

When constructor X is applied ∀ actually becomes ∃. Note that when you take out value you don't know the type and have empty set of operation over it. But since viewValue is kinda coherent with value it can be applied to it.

I guess the main difference of Java interface you proposed is the fact that you have to know intermediate type for passing result of op₁ to op₂. I.e. proper system for existential type should select the right type which is guaranteed to exist by condition. I.e. you should be able to write function with type: ∀X. X→(X→boolean)→T. In prev sample such function is X constructor used in X 3 show (show is function which takes argument of any type that implements Show and returns String)

Updated: I just re-read your question and I think I've got proper construction for Java:

interface T {
    boolean op₂();
}
...
T x = new T() {
    private final int op₁ = ...;
    public boolean op₂() { return ((op₁ % 2) == 0); }
};
T y = new T() {
    private final char op₁ = ...;
    public boolean op₂() { return ('0' <= op₁ && op₁ <= '9'); }
};
if (x.op₂() && y.op₂()) ...

You are right about mentioning this - it's actually your op₁.

So I guess I understood now that classical OOP languages (Java, C#, C++ etc) always implement existential type with single value this and a functions over it called "methods" which implicitly called with that value :)

P.S. Sorry, I'm not very familiar with Java, but I hope you've got the idea.

Related Solutions

Functional Programming, Haskell – Why Existential Types Are Considered Bad Practice

Existential types are not really considered bad practice in functional programming. I think what's tripping you up is that one of the most commonly cited uses for existentials is the existential typeclass antipattern, which many people do believe is bad practice.

This pattern is often trotted out as a response to the question of how to have a list of heterogeneously typed elements that all implement the same typeclass. For example, you may want to have a list of values that have Show instances:

{-# LANGUAGE ExistentialTypes #-}

class Shape s where
   area :: s -> Double

newtype Circle = Circle { radius :: Double }
instance Shape Circle where
   area (Circle r) = pi * r^2

newtype Square = Square { side :: Double }
    area (Square s) = s^2

data AnyShape = forall x. Shape x => AnyShape x
instance Shape AnyShape where
    area (AnyShape x) = area x

example :: [AnyShape]
example = [AnyShape (Circle 1.0), AnyShape (Square 1.0)]

The problem with code like this is this:

The only useful operation you can perform on an AnyShape is to get its area.
You still need to use the AnyShape constructor to bring one of the shape types into the AnyShape type.

So as it turns out, that piece of code doesn't really get you anything that this shorter one doesn't:

class Shape s where
   area :: s -> Double

newtype Circle = Circle { radius :: Double }
instance Shape Circle where
   area (Circle r) = pi * r^2

newtype Square = Square { side :: Double }
    area (Square s) = s^2

example :: [Double]
example = [area (Circle 1.0), area (Square 1.0)]

In the case of multi-method classes, the same effect can be generally accomplished more simply by using a "record of methods" encoding—instead of using a typeclass like Shape, you define a record type whose fields are the "methods" of the Shape type, and you write functions to convert your circles and squares into Shapes.

But that doesn't mean that existential types are a problem! For example, in Rust they have a feature called trait objects that people often describe as an existential type over a trait (Rust's versions of type classes). If existential typeclasses are an antipattern in Haskell, does that mean that Rust picked a bad solution? No! The motivation in the Haskell world is about syntax and convenience, not really about principle.

A more mathematical way of putting this is pointing out that the AnyShape type from above and Double are isomorphic—there is a "lossless conversion" between them (well, save for floating point precision):

forward :: AnyShape -> Double
forward = area

backward :: Double -> AnyShape
backward x = AnyShape (Square (sqrt x))

So strictly speaking, you're not gaining or losing any power by choosing one vs. the other. Which means the choice should be based on other factors like ease of use or performance.

And keep in mind that existential types have other uses outside of this heterogeneous lists example, so it's good to have them. For example, Haskell's ST type, which allows us to write functions that are externally pure but internally use memory mutation operations, uses a technique based on existential types in order to guarantee safety at compilation-time.

So the general answer is that there's no general answer. Uses of existential types can only be judged in context—and the answers may be different depending on what features and syntax are provided by different languages.

C# Collection Interfaces – Transitioning from Java

IEnumerable<T> is the interface to use. It is the most basic interface available for collection type objects. IEnumerable<T> is able to be used in foreach loops. It also contains a number of quite useful extension methods, which allow you to do anything from convert it to a list by calling ToList(), filtering results by calling Where(x => { //filtering functionality } and all sorts of other things.

The other interface to use is IDictionary<U, V>, which is the interface to use for dictionaries. ConcurrentDictionary<TKey, TValue> is probably the most useful of the standard concrete dictionary types as it is designed (funnily enough) for concurrency.

Whatever you do, avoid using List<T> outside of local variables.

The other thing to note is that LinkedList<T> does not implement the IList<T> interface.

Best Answer

Related Solutions

Functional Programming, Haskell – Why Existential Types Are Considered Bad Practice

C# Collection Interfaces – Transitioning from Java

Related Topic