Never Design a Language is the current post on Bertrand Meyer’s blog, and you’d expect Bertrand to be someone who knows what he’s talking about on this subject. Although, I don’t think it’s too unkind to point out that he didn’t take his own advice at least once.

Bertrand’s main point (and it’s a good one) is that the API is more important than the concrete syntax for invoking any operations. Perhaps I’d say “conceptual model” rather than API, but once an API has pre & post conditions & invariants then you’re pretty much talking about the same thing. But the API – indeed the concrete syntax – are also important: the real difficulties (perhaps the real reason why never to design a language) is that the devil is in the details of the feature interactions.

For example: Grace objects are self-sufficient (they’re not defined by a class or metaobjects). The object constructor expressions that create single objects support inheritance to abbreviate descriptions. Grace class declarations can be seen as creating a “factory” object that creates other objects (the class’s instances). So how should inheritance work between classes? If classes inherit, there is a clear (subtyping) relationship between their instances — but should the subclass’s factory likewise be a subtype of its superclass’s factory? Sounds good — but it turns out that requires a Family Polymorphic type system. Oops. Isn’t Grace supposed to be simple, easy to learn, easy to teach?

The real point of this post is to say that we’re not dead yet: in fact, below the surface, we’re making good progress: we have outlines of a module system for Grace, a solid design for pattern matching (we think), parser combinators, a specification of the concrete syntax (done in Grace via the parser combinators), and progress on prototype implementations. We’re working towards a consolidated spec that will include much of this and perhaps be worth some scrutiny – and once that is done, we’ll be able to blog about the motivation and design of each of these in detail.

But we’d like to get the spec out first. So, watch this space…

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!