Existential types provide a way of abstracting type information, such that (a) a provider can hide a concrete type ("pack"), and thus avoid any possibility of the client depending on it, and (b) a client can manipulate said type by only by giving it a name ("unpack") and making use of its bounds.

Existentials play a big role in our understanding of abstract data types and encapsulation. However, they have not been taken up in mainstream programming languages so far. Recently, Martin proposed to add existentials to Scala (in order to make Scala's nice and clean generics operate smoothly with Java's not-so-nice and not-so-clean generics). Here, I won't go too much into Java interop. I am more interested in pattern matching.

A small example

It's already high-time for an example. Take your typical generic OO types (I write T* for a list of Ts):

	T ::= C[T*] | X
	

A type is either a named type (with arguments) like List[String] or a type variable X. You use these things every day -- but there are some Scala programs where these are not enough. This one is maybe the simplest.

def headofany(x:Any) = x match {
  case xs: List[a] => xs.head 
  // it has type a... but what is a?
}

This program says, match on x, if its type is List[a]for some a, then return its head. Here, a is an existential type, we know it exists because List takes one type parameter. Due to JVM erasing types, we won't know if it was a list of strings or integers -- this may sometimes be annoying, we have come to live with it, and at least the programs are fast. Just one thing, what should the type of xs.head be?

When we don't know, we can always choose the easy way out and assign it type Any, which is Scala's most general type. Type Any is equivalent to a for_some { type a; } (a more mathematical notation would be \exists a.a). If there were not more useful examples, where bumping up the type in this manner is prohibitively imprecise, the story would end here.

def headof(x:Any) = x match {
  case ys: List[a] => { x => ys } 
  // result is a function
  // here, ys is List[a], what type has 
  // the function? Any => List[a]?
}

Here we take our ys and return a new function, which ignores its argument and then returns ys. However, the a only makes sense in this case clause branch, we could not use Nothing => List[a] as a return type, cause the a is a type variable, and we don't like typevars freely floating around. Also, if we decided to regard ys as an Any, this time we would really lose information (if we wanted to invoke length, for instance, we wouldn't need to know what a really is).

Still, Scala's definition-site variance comes to the rescue, and we can ignore existential types in this example... since is covariant in its type parameter (it is defined as List[+A]) there is a natural choice to express List[a] where a is not known. We can simply take List[Any] - this is an example of how types with existentials can be simplified to types without existentials.

However, I wanted to talk about existentials. So, let's assume some type Foo[A] that is invariant in A and repeat the example.

def headof(x:Any) = x match {
  case y: Foo[a] => { x => y } 
  // result is a function... what is its type?
  // Any => Foo[a] wouldn't work 
  // because a is "free".
}

Here, there is no way to communicate that we tested x and found it to be a Foo[a]... unless we use existentials. The proposed syntax, as hinted at earlier, is to say Foo[a] for_some {type a;}.

what is it good for, again?

Alas, existential types give you data abstraction, and data abstraction is a Good Thing. Enter a standard example for using existentials. In Cardelli and Wegner's words: "Hence, there are useful existential types which hide some of the structure of the objects they represent but show enough structure to allow manipulations of the objects through operations the objects themselves provide". In Scala, operations are typically grouped together in classes. Let me give another simplistic example.

class Archery[X,Y] { 
  def arrow: X; 
  def shoot(someArrow:X): Y 
}

def foo(a:Any) = a match {
  case arch:Archery[x,y] => arch.shoot(arch.arrow)
}

we can actually shoot our arrow without knowing of what type it is.

Existentials, GADTs and Extractors

What drives to write up all this stuff is that recently, we managed to provide Scala with a sort of user-definable pattern matching facility: the extractors. One thing we constantly kept in mind is that we would like the GADT examples to go throught, which are so en vogue in functional programming these days. It uses the dynamic type test done by the pattern match, like so:

class Term[X]
case class App[Y,Z](fun:Y=>Z, arg:Y) 
  extends Term[Z]

def foo[X](x:Term[X]) = x match {
  case app: App[y,z] => ... 
  // ok, some y,z exists, you know the deal.
}

Now... what happens, if the App pattern is an extractors? That is, a user-defined method that will test-and-deconstruct a Term[X] into the things that form an App

class Term[X]
object App { 
  // i'm hidden
  case class InternalApply[Y,Z](fun:Y=>Z, arg:Y) extends Term[Z]

  def apply[Y,Z](fun:Y=>Z, arg:Y): Term[Z] = 
    new InternalApply[Y,Z](fun,arg)
  def unapply[Y,Z](app:InternalApply[Y,Z]) = 
    Some(app.fun, app.arg)
}

What we see here is a pretty convenient hack: the unapply method takes type parameters, and has an argument type which is already the thing that we want to test for. In a pattern match term match { case App(fun,arg) => ... }, the compiler will first test whether term is really an InternalApply before calling the App.unapply method.

There's one thing where the perceived gain in extensibility (in contrast to having a case class Apply, you can change InternalApply at will) breaks down: If you compiled your program and then later decided, that InternalApply was not what you wanted, let's use FooApply[Y,Z] instead, then compiling the extractor alone will not work -- the type test for the InternalApply is still sitting in all the code that was compiled before, so you have to make sure that everything is recompiled.

With existentials, we could instead give a nicer type to the unapply, which does not even mention the internal thing in its signature

class Term[X]
object App { 
   // i'm hidden
   case class InternalApply[Y,Z](fun:Y=>Z, arg:Y) extends Term[Z]

   def apply[Y,Z](fun:Y=>Z, arg:Y): Term[Z] = 
     new InternalApply[Y,Z](fun,arg)

   def unapply[X](arg:Term[X]): // existential return type!
     Option[(Y=>Z,Y)] for_some {type Y, type Z} = 
       arg match {
         case i:InternalApply[y,z] => Some(i.fun, i.arg)
         case _                    => None
       }
}

This is a typical "pack" operation: we hide the types Y,Z. Actually, we hide them because we do not know them ourselves, since they resulted from an unpack operation %D, namely the pattern match.