The Last Five Years

Sometimes it’s easy to forget how much Grace has changed over the last five years. Most of the major language design decisions were made early, and since then … what?

Quite a lot, actually! I just had cause to re-visit some binary tree code that I wrote in the summer of 2015 as an example for a data structures class. It’s nothing special, but does illustrate the power of Grace’s λ-expressions, which, unlike those in Java, let you close over variables, not just constants. We can therefore use a λ-expressions to abstract over the command that is required to update a field in a parent node to refer to a new child. I described this “trick” in a previous post on this blog.

Of course, the original code no longer compiled; too much has changed. What exactly? Comparing the two versions in git gives us a good summary:

  • The “math” module has been removed. Mathematical operations are now methods on numbers.
  • The “random” module has been added, to give access to various random number generators.
  • factory method has been replaced by class.
  • Type parameters are now enclosed in double square brackets, rather than in angle brackets.
  • Interfaces are defined with the reserved word interface, rather than with type
  • inherits has been changed to inherit
  • The standard dialect now defines Proceduren and Functionn instead of Blockn
  • Traits have been added to Grace, and the standard dialect redefined using them. This makes it possible to combine and re-combine dialects, and pieces of dialects.
  • The == operator is no longer defined on graceObject and inherited by all other objects. Instead, graceObject defines isMe(_) and myIdentityHash, and a trait identityEquality is available for reuse to define the ==, and hashmethods.
  • Patterns and types are somewhat less confused than formerly. Arbitrary patterns can be used in match statements, but not in type declarations.
  • We have rigorously defined Grace’s indentation rules, and minigrace is a bit pickier about correct indentation that it used to be.
  • Square brackets now denote Sequence constructors. ”Lineups”, are gone, collections now understand >> and << for pipelining.
  • Variable-arity methods are no longer part of Grace. Instead, the programmer can define independent methods with the same name and different numbers of arguments—so sequence, sequence(_), and sequence(_,_) can co-exist.

There are probably some other language changes too, and certainly additions to the libraries, but these are the changes that made it necessary to modify formerly-correct code from 2015 so that it compiles and runs in 2020.

The last change—eliminating variable-arity methods—although small in itself, is probably the change with the biggest consequences, because it necessitated changing the interface for constructing collections.

All of these changes have a rationale. In some cases, the change was made for consistency, in others, to make Grace easier to teach. In the case of trait use, it was to make reuse simpler and more powerful than was possible with inheritance alone. Grace continues to evolve, but I feel that we are converging on a language that is pleasant to use, communicates well, and has as much expressiveness (in its target space) as its competitors.

Uniform Referents

Back in 1969, at the first “Software Engineering” conference, Doug Ross presented a paper entitled “Uniform Referents: An Essential Property for a Software Engineering Language” [Ross 1970].  Ross’s idea was that the way that you access an attribute should be independent of an implementation. In his language, he used the notation A(B) to always mean “Property A of thing B”. If A were an array, then B would be an index; if A were a component, then B would be a pointer; if A were a function, then B would be an argument.

The reason that Ross though this was an essential property for a Software Engineering Language is that the implementation of a software artifact changes as its design evolves. Indeed, when you  start the design process, there is no implementation: you are just defining an interface, keeping all implementation options open. Ross argued that one ought to be able to slide different implementations under the same interface and not have to change the code.

Bertrand Meyer, in his 1998 book Object Oriented Software Construction, called what appears to be the same idea the “Uniform Access Principle”. We have it in Grace, at least where the “thing” is an object: we write b.a for attribute a of object b, regardless of whether the implementation of b chooses to store a in memory, or compute it on demand.

Uniform Referents in Grace: accessing object attributes

When we announced this decision during the early design of Grace, someone on the mailing list complained that, when reading a client program, they wouldn’t be able to distinguish field access from method invocation. That, indeed, was the whole point: we didn’t think that you ought to be able to distinguish.

Over the last few days I’ve been augmenting the Grace parse tree to enable more accurate highlighting of errors. The idea, which is hardly novel, is that the IDE should do something like this:

In this screenshot, the user accidentally typed dow instead of do; in addition to getting the message

in the grasscatcher, I wanted to highlight the location of the error.

The parse tree records the starting position (line and column) of each construct, so this ought to have been pretty simple. The problem was that it did not record the ending position. So I set out to fix this, by adding a method end to every node in the parse tree.

It turns out that there are about 30 different kinds of parse tress nodes. For most of them, figuring the end position is pretty trivial. For something like an identifier, it’s just the start position plus the size of the identifier (- 1). For a comment node, it’s the end of the line (because comments always go to the end of the line in Grace); the source code is available, so with a small amount of grubbing around, the end method can come up with the right answer.  Many nodes just inherit from baseNode the following method:

For most composite nodes, the end of the node is the end of the final component, and so on. In many nodes, the code for the end method was one line long.

For a few kinds of node, however, the answer isn’t so simple. The end of a string is not just string.size + 2 - 1  (+ 2 for the quotes) characters away from the start, because it might contain embedded escapes like \" or \t. So, in these cases, I simply added a field end to the node, and set that field in the parser when the parse node is created. There was only one place where string nodes were created, so this wasn’t very onerous.

Because end is a public field, it overrides the inherited end method. The clients of a parse node didn’t care — indeed, they couldn’t tell — whether end was implemented by a field or a method. Voilà! The Uniform Referent Principle at work!

A fly in the ointment

Fairly quickly, I had something working:

But not quite:

Notice that the closing parenthesis is not highlighted. The problem here is that the node that represents a method request is calculating its end position as the end of its last argument list. The argument list, in turn, is calculating the position as the end of the last argument in that list. At this point, no-one knows any longer whether that argument list was parenthesized. Scanning the input for closing parentheses won’t work, because we can’t tell if they belong to this request or some enclosing expression. What to do?

I though of a number of hacks, but it became clear that the right thing to do was simply to store the end position of the request in the parse node when the request is parsed — after all, the parser knows where it is in the input. The only issue was that there are lots of places where request nodes are created (some of them because of internal rewritings, which don’t correspond to any place in the input). Did I have to find (and fix) them all? After all, my heuristic that approximated the end of a request by the end of its last argument worked well enough most of the time.

My solution relied on Grace’s ability to override not just the field end by a method end, but also the setting of that field with end := newPosition. Instead of just replacing the end method with an end field, I made the method smart:

This code overrides not just end (lines 2–12) but also end:=(_) (on line 13): in Grace, we have not just uniform access to an attribute (as an r-value), but a true uniform referent mechanism that deals with l-values too.  In the code above I declare a field, called endPos , as well as the two methods.  A request on the method  end:=(_) is redirected to set  endPos. I hope that the logic of the end method is fairly clear. If  endPos still has its initial value of noPosition , we approximate the answer using the old heuristic; however, if  endPos has been set, we return its value.

Extending the principle

I was quite pleased with the way that Grace helped me handle this problem — it really is quite graceful. The Uniform Referent Principle is so useful, though, that I started to wonder why we didn’t adopt it elsewhere. Why do we make the programmer write


thus forcing them to distinguish between implementing a function by calculation and implementing it with a table? Why not write both

I wonder …

A Graceful Summer

I (Andrew Black) have spent a large part of the summer teaching an introductory programming course to a small-ish group of post-bacc students. This was part of PSU’s “New Beginnings” program, which is designed to prepare students who have a bachelor’s degree in some other subject (history, accounting, chemistry, soil science, music …) to enter into our MS program. New Beginnings is intended to be very intensive: students spend 16 hours a week in the classroom, split between two subjects (discrete math and programming, in the case of this summer), plus another 8 hours in labs, plus homework.

My goal for the summer was to lead the students to roughly to the point that an undergraduate would reach after our three-course introductory programming sequence. This turned out to be a stretch goal for those who had never programmed before, but quite reasonable for those students who had a little background.

I never cease to be amazed at the variety of learning styles, even in a cohort of just 11 students. Some are happy to experiment, while others would have really benefited from a Graceful Data Structures book for the latter part of the course. We used Kalicharan’s excellent “Data Structures in C”, and my original plan was to just re-write the programs in Grace. That didn’t actually work out, because a C-based text has to emphasize things that are irrelevant in Grace, and a Grace text will need to talk about stuff that is irrelevant in C — primarily object structure. Still, the basic programs are parallel; I invite you to take a look at binary trees.

Grace is getting Smaller!

In my last blog post, I told you that Grace was growing, and talked a little about GUnit. It’s also growing in other ways: a type checker is under development, and the Graphics libraries now run in the Javascript (Web -based) implementation, as well as in the C implementation.

But notice that all of these developments have been in the libraries. The core of the language has actually shrunk, in at least one way.

We took private fields out of objects.

Before you get too excited, and start calling us up and asking how we expect you to teach about encapsulation if objects can’t have private fields, let me tell you that Grace still does have confidential fields and methods. Confidential attributes are those that can be accessed by an object and by those objects that inherit from it, and confidential is the default for fields (as it is, for example, in Smalltalk).

As originally proposed, private was a bit odd, because it applied only to fields: there were no private methods. Private meant just that: accessible only to the object that contained it, and to no others. It added complexity: three levels of protection are certainly more to explain than two. Moreover, we realized, that because of Grace’s lexical scope, it didn’t really add any power. This is because the effect of a private field can be obtained by removing the field from the object entirely, and putting it in an enclosing scope.

The best way to illustrate this is with an example. Here is a simple one, inspired by a problem in Mark Miller’s dissertation. The problem is to create a counter, and two objects that access it: one object can be used only to increment the counter, and the other only to decrement it.

method counterPair {
    var counter:Number := 0
    def countUp = object {
        method inc { counter := counter + 1 }
        method value { counter }
    def countDown = object {
        method dec { counter := counter - 1 }
        method value { counter }
    object { method up { countUp }; method down { countDown } }

def c1 = counterPair
def c2 = counterPair
print "counter 1 has value {c1.up.value}"
print "counter 2 has value {c2.up.value}"
print "counter 1 has value {c1.up.value}"
print "counter 2 has value {c2.up.value}"

counterPair makes the two objects, one for incrementing and one for decrementing counter. Because we don’t have tuples built-in, counterPair returns an object with two attributes, up and down, which are the increment and decrement objects. The example code creates two counters, and the output shows that they are independent.

You can run this code yourself here.

The default protection for methods is public, because that is what one wants most of the time; a method can be made confidential by adding the “is confidential” annotation. The default protection for fields is confidential, but a field can be made readable, and, in the case of a variable field, writeable, with the is readable and is writable annotations. To the requestor, accessing a readable or writable field looks exactly like reading from or assigning to a variable, as it always has. So, the line of code above that constructs the result of counterPair could have been written

object { def up is readable = countUp; def down is readable = countDown }

in both cases the client object can request the up and down attributes of the newly-created object.