Skip to main content

Existential Types are the flip side of generics

Generic types, as can now be seen in all the major programming languages have a flip side that has yet to be widely appreciated: existential types.

Variables whose types are generic may not be modified within a generic function (or class): they can be kept in variables, they can be passed to other functions (provided they too have been supplied to the generic function), but other than that they are opaque. Again, when a generic function (or class) is used, then the actual type binding for the generic must be provided – although that type may also be generic, in which case the enclosing entity must also be generic.

Existential types are often motivated by modules. A module can be seen to be equivalent to a record with its included functions: except that modules also typically encapsulate types too. Abstract data types are a closely related topic that also naturally connect to existential types (there is an old but still very relevant and readable article on the topic Abstract types have existential type)

One way that I like to visualize existential types is that of a box with a type inside it. As a programmer using the box, you know there is a type in there, it has a name and it has a set of functions that reference the type but you know nothing about its actual realization.

Existsbox

Inside the box, you know what type foo is, and it can be any type so long as the other functions in the contract are implemented appropriately.

Outside the box you know nothing about the foo type. What this means is that any program text that uses the type from the box is strictly limited in what it can do: it is limited essentially to passing foo values around and to invoking other functions from the same box.

Thus, existentials and universals have a complementary role in programming: generics are used when the entity being defined must be general purpose. Existentials should be used when the use of the entity should be generic.

An excellent example of where this might be useful is in frameworks such as testing frameworks.

Existstest

Most test frameworks are pretty lame: you define a bunch of void functions with embedded assertions. A full test framework with existentials could be designed to test arbitrary functions and/or classes. All that the programmer would need to do to use such a framework to test her programs would be to invoke it!

A final note about existentials: they represent a neat way of characterizing system or built-in types. For example, the string type can be viewed as an existentially quantified type whose implementation belongs to the compiler. The difference here is that there is typically only one privileged instantiation of string; however, it would be very convenient for a language system to be able to support multiple kinds of string with different implementation characteristics.

Popular posts from this blog

Comments Should be Meaningless

This is something of a counterintuitive idea: Comments should be meaningless What, I hear you ask, are you talking about? Comments should communicate to the reader! At least that is the received conventional wisdom handed does over the last few centuries (decades at least). Well, certainly, if you are programming in Assembler, or C, then yes, comments should convey meaning because the programming language cannot So, conversely, as a comment on the programming language itself, anytime the programmer feels the imperative to write a meaningful comment it is because the language is not able to convey the intent of the programmer. I have already noticed that I write far fewer comments in my Java programs than in my C programs.  That is because Java is able to capture more of my meaning and comments would be superfluous. So, if a language were able to capture all of my intentions, I would never need to write a comment. Hence the title of this blog.

Safe and effective software

Someone recently asked me why I was working on the particular topics that I was interested in. I am afraid that in the heat of the moment I had a reasonable but ultimately lame answer (something about reducing friction in the marketplace). In fact, the true answer is simpler and much more powerful. I want to be part of a 'professional' industry, and I believe that we are not really there yet. It is a constant source of amazement to me that there have not been any class action lawsuits against certain high profile software companies. I like the phrase safe and effective , which describes the basic requirements for medicines of course, but should be equally applicable to software. What would the benefits of being able to label a system safe and effective? Primarily it means that someone using the system has some assurance that the software will do what it is supposed to do, and that it wont lead you into trouble. Of course, if you take too many aspirin, or if you misuse a softwar

Concept Oriented Markup

I have long been frustrated with all the different text mark up languages and word processors that I have used. There are many reasons for this; but the biggest issue is that markups (including very powerful ones like TeX) are not targeted at the kind of stuff I write. Nowadays, it seems archaic to still be thinking in terms of sections and chapters. The world is linked and that applies to the kind of technical writing that I do. I believe that the issue is fundamental. A concept like "section" is inherently about the structure of a document. But, what I want to focus on are concepts like "example", "definition", and "function type". A second problem is that, in a complex environment, the range of documentation that is available to an individual reader is actually composed of multiple sources. Javadoc exemplifies this: an individual library may be documented using Javadoc into a single HTML tree. However, most programmers require access to multip