The Draft Grace Language Specification 0.350 has been added to the documents page.
Changes from the previous released version 0.132 include:
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…
We’ve been discussing encapsulation controls in Grace. For teaching, a rather conventional “visibility system” that lets features of an object be accessible only to
(a) the object itself, or
(b) the object and the heirs of that object, or
(c) the object, heirs and clients of the object
is probably necessary and sufficient – although we’re not 100% sure we need to support each of these visibility levels. Necessary, because at least some instructors will want to teach students how to use such a system, and sufficient for our intended audience. (I still believe that an industrial-strength language in which reuse is a goal should put control of encapsulation in the hands of the client, as we did in the Schärli, Black & Ducasse OOPSLA 2004 paper. However, even with controllable encapsulation policies, there still needs to be a way to define default policies for heirs and clients. )
If once accepts that as a starting point, there are still a number of decision to be made. We need to pick names for each kind of visibility — so we can have this conversation — and then we need to decide how to apply the different levels to the features of an object — its methods, variables and constants. Another decision is whether the visibility declarations should be advisory, or whether there should be work-arounds, as there are in almost every industrial-strength language. (Even if you really want a feature to be private, you probably still want to be able to look at it in the debugger.)
The problem with names is that all of the good ones are taken. The best name that I can think of for (a) is private, but Java uses private to mean “accessible not only by me, but also by any object that happens to share the same class as me”, and Ruby uses private to say that the method can be used only with self as the receiver, which means that it can be used by heirs as well by an object itself. Still, private is the best name that we could think of for (a). For access level (c), public seems entirely appropriate, but level (b) is tricky. “Family access only” is the most descriptive phrase that I could come up with. “Confidential” is a possibility — less private than private, but not public. Other possibilities are “hidden”, but it’s not clear that hidden is more accessible than private, and “protected”, which has the same disadvantage, as well as being taken by Java to mean “more accessible than the default”. Can you suggest good terms?
Speaking of defaults, should we have default visibilities, or must they always be declared? The principles of clarity and readability tell us that we should tag each feature with its visibility explicitly. However, the principle of brevity tells us that the common case should require less characters on the screen. The common case, I believe — at least in the beginning — is that methods should be public and that constants and variables should be private, or perhaps confidential. But that gives rise to a complicated rule: the default depends on how the feature is implemented. A simpler rule — simpler to teach and simpler to remember — would be for every feature to have the same default visibility. So those of us who are enthusiasts for encapsulation would make all features default to private, and those of us who are enthusiasts for reuse would make everything default to confidential. However, in both cases, methods intended for clients would have to be declared to be public explicitly. Is this an undue burden, considering that, at least in the beginning, the only reason to declare a method is to provide public access?
Another issue is the syntax for these accessibility declarations. Should we use keywords public, private and confidential? Should we sigils, such as UML’s +, – and #? Should we use annotations (attributes), as we are considering for “overrides”? The argument for sigils is brevity, and lack of syntactic clutter, especially if every method, constant and variable needs to have its visibility made explicit; the argument against is that we want students to learn the right vocabulary, and refer to private methods as “private methods” and not as “- methods”. This is the rationale that has led us towards using more keywords in Grace than in many other languages (for example, labeling methods with method), and generally spelling keywords out in full (integer rather than int).
A final issue — and one that is often neglected — is to define the semantics of the visibility annotations. Private methods are not really methods at all: they are early bound and have lexical scope, and thus they should not be part of an object’s type. Public and Confidential methods are both real, late bound methods; the distinction is that confidential methods can be requested only from self. We think it’s reasonable to make that a syntactic restriction, so that
self.protectedMethod
is OK, but
o := self
o.protectedMethod
is an error.
Should Confidential methods appear in an object’s type? That rather depends on the rôle of types: do they exist to describe what clients can do, or what heirs can do? It’s actually quite reasonable to have two different type systems with those two different goals, but the type system for clients will be the more widely used, and probably the one that teachers will want to emphasize. We think that all of the checks required for the correct use of inheritance can be done statically in a whole-program analysis without burdening the programmer with a second type system.
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:
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!