Following from comments on the variance post, here’s an attempt at explaining the rules for type conformance in Grace.

In Grace, we say “type B conforms to another type A” when every object of type B can be supplied whenever an object of type A is expected. B conforms to A is written B <: A; or we may say B is a subtype of A or A is a supertype of B. I’ll try and stick to “conforms to” because hopefully it is the least confusing.

Now – what does “B conforms to A” mean? In other words, given two types A and B, when can we say that we know that “B conforms to A”?

In Grace there are three rules, and only the last one is sometimes difficult. The key idea is that if B conforms to A, or B can be supplied whenever an A is required, then every request for a method that is valid on an A must also be acceptable on a B. The rules are:

1. B must respond to every method request that A responds to
2. The types of the results returned by B’s messages must conform to the types of the results returned by A’s messages
3. The types of the formal parameters expected by A’s messages must conform to the types of the formal parameters expected by B’s messages

If you’ve survived this far, the first rule is, I hope, noncontroversial. If A responds to some method “m”, then B must also respond to that method. The second rule, too, hopefully makes sense: if calling “m” on A returns some other type C, then calling “m” on B must return a C, or rather something that is acceptable when C is required — something that conforms to C.

The third rule is the tricky case: what it says is that if method m on A expects a formal parameter of type D, method m on B must also work if a D is supplied or it can accept more objects than A — methods on B can be less selective than A, but they cannot be more selective. This rule seems backwards to the other two rules, which is where the “contra” comes from.

Let’s try a more concrete example. Say I have a Pet type like this:

type Pet = {
sleeps -> Boolean
eats(f : PetFood) -> Unit // doesn’t return anything
}

I want to make a Cat class that conforms to the Pet type — what does that say about the Cat class’s interface? Well by rule 1, the Cat class has to have to have all the methods included in the Pet type — “sleeps” and “eats” — although it may have more — “purrs” say. I say by rule 1, but really it will be required by the design: if part of the program needs an object meeting the Pet interface, then presumably the sleeps and eats methods will be requested on that object.

Considering rule two, the methods can return the same or more specific types – if my cat sleeps all the time, I could make a “sleeps’ method that returns “true” and it would still conform to the Pet type. Again this comes from the design of the program — some code presumably calls the sleeps method and expects to get a Boolean in return.

Then finally rule three: argument types: the Cat class has to have an “eats” method that accepts PetFood. Again presumably this is because a program that uses the Pet type will feed that Pet some PetFood. What this means is that we can’t make our Cat class fussier than any other kind of Pet. A Cat that insisted on CatFood rather than PetFood, or GourmetCatExtreme rather than anything else, wouldn’t conform to the Pet interface. On the other hand, a Cat that is less choosy, a Cat that is happy to eat DogFood, or Chicken, or any kind of Food, will conform to the Pet interface.

So the type of a Cat would look alike this:

type CatType = {
sleeps -> Boolean
eats(f : PetFood) -> Unit //Doesn’t return anything
purrs -> Unit //Doesn’t return anything either
}

and we would be able to say Cat <: Pet.

Variance is a sticky topic in programming language design. Here’s why variance is a problem, and how Grace will address it.

Consider a generic Sequence interface:

type Sequence<E> = {
   get(Number) -> E
   count -> Number
}

We can instantiate this sequence to make a list of objects (Sequence<Object>) or a list of books (Sequence<Book>). Assuming the Book type conforms to the Object type (Book <: Object) what is the relationship between these the two types of list?

In Grace, typing is structural, that is, we look at the structure of the types to decide, not (just) their declarations. The type Sequence<Object> expands to:

type Sequence<Object> = {
   get(Number) -> Object
   count -> Number
}

by replacing the parameter E with Object. Similarly a Sequence<Book> has the interface:

type Sequence<Book> = {
   get(Number) -> Book
   count -> Number
}

Now consider the method requests in both interfaces. The count request is the easiest — it’s exactly the same in both. The get method returns an Object in Sequence<Object> and a Book in Sequence<Book> — hopefully as we’d expect. Because the return types the book sequence requests are equal to or conform to the return types of the object sequence requests, Grace’s type system allows a sequence of books to be provided whenever sequence of objects is required: that is

Sequence<Book> <: Sequence<Object>.

So far so good. The trouble is, the Sequence type only lets you get things out of the list, not put them in. For that, we need an interface like the actual List interface:

type List<E;> = {
   get(Number) -> E
   add(Number, E)
   count -> Number
}

By comparing their expansions, Grace can show that, for any E, every List<E> <: Sequence<E> — whenever Grace needs a Sequence of something, you can give it a List of the same things. Fair enough, because any method requiring a Sequence isn’t going to use the add method, or they’d have to require a List instead.

The tricky question is: what’s the relationship between List<Book> and List<Object>? The expansion starts the same as for Sequence, but now we have “{ add(Number, Object) } ” in List<Object> and “{ add(Number, Book) }” in List<Book> — we can add anything to a List of Objects, but can only add Books to a list of Books. Considering the types of just the add methods, we must have this relationship:

{ add(Number, Object) } <: { add(Number, Book) }

a method requiring an Object argument is a subtype of a message requireing a Book argument! This is called contravariance because the methods vary in the opposite order to the types of their arguments.
In fact, the situation for Lists is even worse, because the get method is covariant — this is what lets the Sequence of Books be a subtype of the Sequence of Objects. So there is no subtype relationship in either direction between List<Book> and List<Object>.

All this Co/Contra/Bi/In/variance is quite confusing, which is why Eiffel and Dart use a covariant rule for everything, and insert dynamic checks that can fail at runtime. Java, Scala, C# provide wildcards and variance annotations to handle: the methods you are permitted to call depend on how the argument types are used.

Grace’s structrural types don’t need variance annotations, and we don’t plan to add them. (O’CAML also uses structural types, I’m not sure why it also has variannce annotations). In Grace, you can always write down whatever type you need when you need it, and you can use partially or completely dynamic types if you want to reply on dyanmic checking. If you don’t care, you can write

def listOfBooks : Dynamic := List<Object>.new

to say you explicitly don’t care about the type of this list. (Of course, this means that listOfBooks could now hold anything). If you at least want to be sure you have a list, but don’t mind what goes in or out, you can write:

def listOfBooks : List<Dynamic> := List<Object>.new

and that’s what you get: Eiffel or Dart style dynamic checking on what goes in or out of the list, and static checking of the list operations themselves.

If you’re sure you only want to read things out of a list of books, (or perhaps a list of some other things) then make the type a Sequence of objects: any kind of list can go in here, but you can’t add things to the box — because random objects won’t fit into a list of Books.

def listOfBooks : Sequence<Object> := List<Book>.new

But say (if you’re packing up your house) and you want a list you can put books (in to) perhaps just a list of books, perhaps a list of anything else, you can write a structural type that says just what you want:

def listOfBooks : { add(Book) } := List<Object>.new

And any list (or anyting else) to which a book can be added to will be compatible with that type.

---

Java variance is one of the things I’ve always found hard to teach: tangling together the underlying mathematical regularities (you can put a book into a box of anything, but you can only put books into a box of books) and the language features. It’s been interesting trying to explain this in Grace. Hopefully the types capture the underlying regularities, and the language offers engineering tradeoffs for programmers to make.

The basic principles of Grace’s type system — that types describe the structure of objects’ interfaces; that programmers can always write any type at any time; that type Dynamic gives run-time typing when and where you want it — hopefully add up to an understandable system that’s not too hard to learn and to use.

Structural types seem to be the key here: if a type isn’t in a library, structural typing means you can always write it down. Java and Scala’s nominal type systems need wildcards to say “which methods to leave out” of an existing type: programmers can’t usefully define new interfaces because, even if they do, the library classes won’t implement them.

The examples also show my current thinking about Collections for Grace. Following Clu the library will have both read-only (covariant) and read-write (invariant) interfaces for the main collection classes. Generally the read-only interface will have a more “mathematical” name (Bag; Set; Sequence; Map) and the read-write interface a more “pragmatic: name (Collection; List; Dictionary). I’m assuming the contravarint (write only) interface will be rarely used: programmers can write it as necessary — or perhaps even construct it by type subtraction or type division. And yes, I’d like to abbreviate “Sequence” to “Seq” or find another good three letter name!

While the following is not central to the design of Grace, we do expect that users will frequently be working with collection classes like lists, sets, etc.

The first question, is how do you create one of these objects. In Java you would create a linked list of three integers as follows:

List lst = new LinkedList()
lst.add(1)
lst.add(2)
lst.add(3)

Note that Java does introduce a compact notation for declaring arrays:
Integer[] arr = {1,2,3}
but there is nothing equivalent to that for other collection classes.

Scala makes it easy:
var lst = List(1,2,3)

With Grace’s vararg feature (allowing a variable number of parameters at the end of the actual argument list), we could write:

var lst: List[Integer] := LinkedList[Integer].new(1,2,3)

or, with a small amount of type inference

var lst := LinkedList[Integer].new(1,2,3)

Python, as well as functional languages like ML and Haskell, allow programmers to create lists with a more compact notation: [1,2,3]

We expect to encourage a more listful style of programming with the use of higher-order functions like map, foreach, etc. Do we need to introduce a more compact notation for lists, like that in Python, or is the above fine?  What is the right answer given our target audience of first and second year students in CS.

As well as creating these collection classes, we also need to access elements. For linear sequences, we would like to access and update the ith element.

For Java arrays, we would write arr[i], while for lists we would write lst.get(i). The notation arr[i] can also be used on the left side of an assignment, while lst.set(i,newVal) results in replacing the ith element by newVal for a list.

In Scala, the access to the ith element is defined in an apply method, whose name can be omitted in a call. Thus, lst.apply(i) is the same as lst(i). An update method is used to provide a new value for the ith element (in a mutable collection).

Python accesses the ith element of a list with square brackets: lst[i], which can also be used on the left side of an assignment.

In Grace our current plans are to access elements using regular message sends where the message has a name like “at” or “get”. Another alternative might be to use an operator like “@” or use the [] notation like Python.

What do you think of these ideas? What choices are the simplest, most consistent, and/or most acceptable to our target oudience?