Notations for Collections

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?

From Lancaster to Portland

So this is a belated message about the Grace meetings in Lancaster. Early during the week (Tuesday evening) we held a BOF – mostly hosted by Kim – with a good group of people attending to hear about Grace. There were good discussions and questions, mostly about where we plan to go next. I wish I could have stayed for the whole thing!

Then on the Saturday, after the conference – while most people were heading home – Gary Leavens (University of Central Florida), Erik Ernst & Johan Winther (Aarhus Universitet), and Kim & James met for a “good, intense, and productive” time to talk over the next stages in the design – primarily the type system. Main choices so far include:

  • A primarily gradual, parametric, structural type system
  • Classes, Types, and Methods may all take generic parameters
  • Generic types written as Array[T], following Eiffel and Ada.
  • Constraints on type parameters expressed via where clauses, following CLU & C#
  • Explicit union types e.g. (ListNode[T] | None) designed to work well with Grace’s pattern matching. These are inspired more directly by ML-style languages (& Ceylon) as an alternative to Scala’s case classes; although (as in general in Grace) they will remain primarily structural types
  • No need for variance annotations — an ad-hoc structural interface can always be defined where necessary
  • MyType and exact types at the top language level

Over the next few weeks – now we’re over the jetlag! – we hope to post on more details of this design, and eventually a 0.2 version of the language spec.


And although we’re just back from Lancaster, we also need to look forwards to the next time we’ll meet about Grace, which we’re planning at the SPLASH conference in Portland (Oregon) at the end of October. Our current thoughts are a general BOF early in the week (perhaps Monday evening) with a day-long design working session perhaps the Friday after the main conference ends.

We still have a little time to confirm these plans – if you’re thinking about going to SPLASH, we’d love to hear from you, so let us know when you’d be able to come along.

Types vs Classes

Like many object-oriented languages, Grace will have classes. Like some object-oriented languages, Grace will have types. Like a few
object-oriented languages, Grace programmers have the option to ignore classes and use only objects, or to ignore static types and use only dynamic types.

The relationships between objects and classes, and static and dynamic types, are well known. So, then, what’s the relationship between
classes and types in Grace? Or rather, what should be the relationship between classes and (static types?

Here’s the problem. Let’s take a simple Grace class:

This class creates a factory object that supports the creation of new Cat instances in response to the method request “new(aColour,aName)” (cognoscenti will notice we’re trying “def x =” syntax to define constants rather than “const x :=”. Sorry Niklaus).

What type does the variable “fergus” have? As in C#, local type inference gives it whatever type the “Cat.new” method returns. What if we want to declare that type explicitly, say for a variable?

Here the name “Cat” is being used as a type, rather than a factory. The key question is: where did that type come from? There seem to be two options in the design here:

  1. The Cat class declaration implicitly creates a Cat type.
  2. The Cat type must be declared explicitly, separate from the class
    declaration:

The first option, a class implicitly creating a type, is what most typed object-oriented languaes do: a class declaration also creates a type (technically the cone type rooted at the class). Implicit class-types lead to more concise programs, and allow “static typing early” courses to have students write and use their own classes without requiring an explicit concept or separate declaration of a static type.

On the other hand, the second option, explicit type declarations, make static types much more explicit. Under this option, Grace programmers couldn’t declare an explicitly typed variable (or more likely, any method, as method arguments are not inferred) without an explicit declaration of the Cat type. But this clarity comes at a price: simple programs are longer, requiring apparently redundant type declarations, declarations that are close to class declarations, but duplicated some information with some mandatory tweaks.

Grace programmers can avoid the price of a separate declaration in a couple of ways. First they can use dynamic types or local type inference — omitting types from variable and constant definitions will find types via local inference (if the type-checker is run) while omitting types from method arguments and results are interpreted as type dynamic. So the costs of declarations (presumably) would only be required whenever a type is to be written explicitly. Still, this is another case where a ”better” program (with explicit types) is longer and more redundant than a ”worse” program (without them). Most Grace programmers may choose to omit the declarations, so the language would fall into being dynamically typed by default.

In fact, the real situation is worse than this: there are about five or six kinds of “class-like” or “type-like” objects in Grace: a good solution here should address all these roles:

  • ”’Factory”’ object that creates new instances of a class

  • ”’Type”’ with which variables, arguments, and methods are declared

  • ”’Reified Type Parameter”’ Since Grace will have “reified”
    generics, what value or object should the reified value be?

    Note that inside the Collection, the reified type argument will have to be bound to the formal type parameter.

  • ”’Pattern”’ object used to match objects of that type in
    match/case statements

  • ”’Mirrors”’ used to reflect on instances of the class

If these are played by different objects — how many different namespaces will Grace need to name them all? If they are accessible in a shared namespace, how are names resolved?

Finally, following C#, Grace will provide constructs to reify the declared static type of an expression (perhaps “decltype(e)”) and the exact dynamic type of an object (“o.dyntype”, or perhaps alternatively “reflect(o).dyntype” via a mirror). The aim here is to let programmers write programs that interrogate the static and dynamic types in their programs. And, whatever the relationship we end up with, do we need better names for static type and dynamic type?

Learning Edge Momentum

Like many computer science or software engineering departments, at VUW we seem cursed with a “bimodal” distribution of marks in first year programming courses. While some students do very well and collect A or A+ grades, about as many do very poorly, taking away only Ds and Es — and with relatively few students in the
middle. This profile is very different from most other courses at the university — and generally from our second and third year courses — which have much more normal distributions.

A number of hypotheses have been proposed for the bimodal distribution — most commonly, that a large proportion of the population are congenitally unable to learn programming, and that our advertising fails to dissuade them from enrollment.

Recently, Anthony Robins, a colleague from Otago University in NZ (the southern-most university in the world, and oldest university in the NZ) has developed a novel rationale to explain these distributions. His paper, “Learning Edge Momentum” , hypothesizes that introductory programming is unlike many other disciplines, in particular, that “success in acquiring one concept makes learning other closely linked concepts easier (whereas failure makes it harder).”

What’s this to do with Grace? Well, one of our main aims in the design of Grace is to reduce the accidental difficulties of learning to program. In Robins’ terms, I think this could be described as “uncoupling the concepts” within the language — partly removing concepts, but mostly trying to make concepts less
closely linked.

Here’s a simple example. In Java 1.0:

To me, this needs a whole collection of tightly-linked concepts:

  • For loop
  • Integers, and “int” type
  • Variables and assignment
  • Length of a collection and that “col.length()” gets the length
  • Less than, and that “< " is less-than
  • ++ increment operator…
  • “col.at(i)” to get i’th member of a collection.
  • System.out.println to print things.

But the “new for loop” in Java 5.0 needs far fewer concepts:

In particular:

  • For loop
  • Variable declaration
  • System.out.println to print things.

Hopefully Grace’s “for” loop:

will be closer to the Java 5.0 loop rather than Java 1.0!

I look forwards to seeing how Robin’s hypothesis is developed and tested over time. I also look forwards to see how much we can ensure a clear and loosely coupled conceptual model under Grace.

Grace Workshop Lancaster – Saturday 30 July

The next Grace Workshop will take place on Saturday 30 July, after the ECOOP 2011 conference.

The Workshop will be held at Lancaster University, in the Computer Science Department (Infolab21 building) in room C60a. Here is a map of the campus (Infolab21 is building 62 on South Drive).

We’ll aim to start around 10am.

These workshops are to report progress on the design, to discuss challenges, and hopefully to involve others in the project. At this workshop, we also hope to show some very early prototypes that we are building to test the specification.

So, if you’re interested, and are able to come to this workshop, please let us know by emailing James, kjx@ecs.vuw.ac.nz so we have some idea who’s coming.