What is an Existential Type?

I think briefly: existential types are interfaces, and universal types are generics.

I think briefly: existential types are interfaces, and universal types are generics. So for example, something like "ICollection" is effectively "there exists some concrete implementation type X where I can call . Length on X, but I don't know what type X it is".

That's ICollection when you don't know if it's an Array or a List or whatnot. When you upcast a concrete type to an interface, you "forget" it's real type, and just know that there exists some concrete type with these interface properties. Then something like "Stack" is like "for any known T I can create a stack of it and call s.

Push(T x)". For all T, I can stamp out a new instance of this thing. That's kinda simplistic and not well-written (sorry), but it's the gist.

1 This is wrong. The ICollection example is an example of a bounded type parameter, which applies equally well to existential types and universal types. Existential types have nothing to do with interfaces.

– Kannan Goundan Apr 21 '11 at 11:13.

When someone defines a universal type ∀X they're saying: You can plug in whatever type you want, I don't need to know anything about the type to do my job, I'll only refer to it opaquely as X. When someone defines an existential type ∃X they're saying: I'll use whatever type I want here; you won't know anything about the type, so you can only refer to it opaquely as X. Universal types let you write things like: void copy(List source, List dest) { ... } The copy function has no idea what T will actually be, but it doesn't need to.

Existential types would let you write things like: interface VirtualMachine { B compile(String source); void run(B bytecode); } // Now, if you had a list of VMs you wanted to run on the same input: void runAllCompilers(List vms, String source) { for (∃B:VirtualMachine vm : vms) { vm. Run(vm. Compile(source)); } } Each virtual machine implementation in the list can have a different bytecode type.

The runAllCompilers function has no idea what the bytecode type is, but it doesn't need to; all it does is relay the bytecode from VirtualMachine. Compile to VirtualMachine.run. Java type wildcards (ex: List) are a very limited form of existential types.

Update: Forgot to mention that you can sort of simulate existential types with universal types. First, wrap your universal type to hide the type parameter. Second, invert control (this effectively swaps the "you" and "I" part in the definitions above, which is the primary difference between existentials and universals).

// A wrapper that hides the type parameter 'B' interface VMWrapper { void unwrap(VMHandler handler); } // A callback (control inversion) interface VMHandler { void handle(VirtualMachine vm); } Now we can have the VMWrapper call our own VMHandler which has a universally typed handle function. The net effect is the same, our code has to treat B as opaque. Void runWithAll(List vms, final String input) { for (VMWrapper vm : vms) { vm.

Unwrap(new VMHandler() { public void handle(VirtualMachine vm) { B bytecode = vm. Compile(input); vm. Run(bytecode); } }); } } An example VM implementation: class MyVM implements VirtualMachine, VMWrapper { public byte compile(String input) { return null; // TODO: somehow compile the input } public void run(byte bytecode) { // TODO: Somehow evaluate 'bytecode' } public void unwrap(VMHandler handler) { handler.

Handle(this); } }.

Makes sense totally – Aswin Jun 24 '11 at 15:13 @Kannan, +1 for a very useful, but somewhat difficult-to-grasp answer: 1. I think it would help if you could be more explicit about the dual nature of existential & universal types. I only realised by accident how you've phrased the first two paragraphs very similarly; only later do you state explicitly that both definitions are basically the same, but with "I" and "you" reversed.

Also, I didn't immediately understand what "I" and "you" is supposed to refer to. – stakx 2 days ago (continued:) 2. I don't fully understand the meaning of the mathematical notation in List> vms or for (∃B:VirtualMachine vm : vms).(Since these are generic types, couldn't you have used Java's?

Wildcards instead of "self-made" syntax? ) I think it might help to have a code example where no generic types such as ∃B:VirtualMachine are involved, but instead a "straight" ∃B, because generic types are easily associated with universal types after your first code examples. – stakx 2 days ago.

An existential type is an opaque type. Think of a file handle in Unix. You know its type is int, so you can easily forge it.

You can, for instance, try to read from handle 43. If it so happens that the program has a file open with this particular handle, you'll read from it. Your code doesn't have to be malicious, just sloppy (e.g. , the handle could be an uninitialized variable).

An existential type is hidden from your program. If fopen returned an existential type, all you could do with it is to use it with some library functions that accept this existential type. For instance, the following pseudo-code would compile: let exfile = fopen("foo.

Txt"); // No type for exfile! Read(exfile, buf, size); The interface "read" is declared as: There exists a type T such that: size_t read(T exfile, char* buf, size_t size); The variable exfile is not an int, not a char*, not a struct File--nothing you can express in the type system. You can't declare a variable whose type is unknown and you cannot cast, say, a pointer into that unknown type.

The language won't let you.

4 This won't work. If the signature of read is ∃T. Read(T file, ...) then there is nothing you can pass in as the first parameter.

What would work is to have fopen return the file handle and a read function scoped by the same existential: ∃T.(T, read(T file, ...)) – Kannan Goundan Apr 2 '11 at 0:29 1 This seems to be just talking about ADTs. – kizzx2 Aug 27 '11 at 14:33.

Research into abstract datatypes and information hiding brought existential types into programming languages. Making a datatype abstract hides info about that type, so a client of that type cannot abuse it. Say you've got a reference to an object... some languages allow you to cast that reference to a reference to bytes and do anything you want to that piece of memory.

For purposes of guaranteeing behavior of a program, it's useful for a language to enforce that you only act on the reference to the object via the methods the designer of the object provides. You know the type exists, but nothing more. See: Abstract Types Have Existential Type, MITCHEL & PLOTKIN theory.stanford.edu/~jcm/papers/mitch-pl....

I think it makes sense to explain existential types together with universal types, since the two concepts are complementary, i.e. One is the "opposite" of the other. I cannot answer every detail about existential types (such as giving an exact definition, list all possible uses, their relation to abstract data types, etc.) because I'm simply not knowledgeable enough for that.

I'll demonstrate only (using Java) what this HaskellWiki article states to be the principal effect of existential types: Existential types can be used for several different purposes. But what they do is to 'hide' a type variable on the right-hand side. Normally, any type variable appearing on the right must also appear on the left … Example set-up: The following pseudo-code is not quite valid Java, even though it would be easy enough to fix that.

In fact, that's exactly what I'm going to do in this answer! Class Tree { α value; Tree left; Tree right; } int height(Tree t) { return (t! = null)?

1 + max( height(t. Left), height(t. Right) ) : 0; } Let me briefly spell this out for you.

We are defining… a recursive type Tree which represents a node in a binary tree. Each node stores a value of some type α and has references to optional left and right subtrees of the same type. A function height which returns the furthest distance from any leaf node to the root node t.

Now, let's turn the above pseudo-code for height into proper Java syntax! (I'll keep on omitting some boilerplate for brevity's sake, such as object-orientation and accessibility modifiers.) I'm going to show two possible solutions. 1.

Universal type solution: The most obvious fix is to simply make height generic by introducing the type parameter α into its signature: int height(Tree t) { return (t! = null)? 1 + max( height(t.

Left), height(t. Right) ) : 0; } This would allow you to declare variables and create expressions of type α inside that function, if you wanted to. But... 2.

Existential type solution: If you look at our method's body, you will notice that we're not actually accessing, or working with, anything of type α! There are no expressions having that type, nor any variables declared with that type... so, why do we have to make height generic at all? Why can't we simply forget about α?

As it turns out, we can: int height(Tree t) { return (t! = null)? 1 + max( height(t.

Left), height(t. Right) ) : 0; } As I wrote at the very beginning of this answer, existential and universal types are complementary / dual in nature. Thus, if the universal type solution was to make height more generic, then we should expect that existential types have the opposite effect: making it less generic, namely by hiding/removing the type parameter α.

As a consequence, you can no longer refer to the type of t. Value in this method nor manipulate any expressions of that type, because no identifier has been bound to it. (The?

Wildcard is a special token, not an identifier that "captures" a type.) t. Value has effectively become opaque; perhaps the only thing you can still do with it is type-cast it to Object.

As I understand it's a math way to describe interfaces/abstract class. As for T = ∃X { X a; int f(X); } For C# it would translate to a generic abstract type: abstract class MyType{ private T a; public abstract int f(T x); } "Existential" just means that there is some type that obey to the rules defined here.

4 I'm pretty sure that's a universal type. – Chris Conway Nov 15 '08 at 15:01.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.