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

but

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 other 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
c1.up.inc
c1.up.inc
print "counter 1 has value {c1.up.value}"
print "counter 2 has value {c2.up.value}"
c2.down.dec
c2.down.dec
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.

Grace is growing!

You wouldn’t know it by reading this Blog, but this has been an active summer in Gracelang. In fact, we’ve been so busy coding and editing the specification — and having fun with Grace — that we haven’t posed anything here.

Amongst other things, I’ve been working on a usable, if simple, version of GUnit — the ubiquitous unit testing framework — for Grace. It basically does what xUnit does in any other language: it let’s you write a bunch of test methods that contain assertions, and then runs them all, notifying you only of errors and failures. Grace’s blocks and exception handling find their niche here. For example, here is a test for lists:


import "GUnit" as GU
import "collections" as coll
def aList = coll.aList

class aListTest.forMethod(m) {
    inherits GU.aTestCase.forMethod(m)

    def oneToFive = aList.with(1, 2, 3, 4, 5)
    def evens = aList.with(2, 4, 6, 8)
    def empty = aList.empty
    method testFirst {
        assert{empty.first} shouldRaise (coll.boundsError)
        assert(evens.first) shouldBe (2)
        assert(oneToFive.first) shouldBe (1)
    }
}

def listTests = GU.aTestSuite.fromTestMethodsInClass(aListTest)
listTests.runAndPrintResults

The boilerplate is pretty standard for any xUnit. The only thing that needs explanation is the inherits clause: as in most implementations of xUnit, tests must be methods of a class that inherits from a framework class, which in Grace is called aTestCase.

Anyway, the nice thing is the first assertion:

assert{empty.first} shouldRaise (coll.boundsError)

Notice that the first argument is a block: it is evaluated as part of the action of the assert method, which enables the assert method to trap any exception that is raised.
So we are able to test that asking for the first element of an empty list does indeed raise the right exception — and then go on to run more tests.

The above code, when run, outputs:

1 run, 0 failed, 0 errors

and nothing else: passing tests are quiet.

If you would like to see all of the code, just drop us an email, and we will give you access to our subversion repository.