SOBs

A lurid headline is a proven way of grabbing attention. SOBs are Serviced Objects, objects that can be downloaded to your machine from a server, and thereafter serviced by it. Any modifications you make to the SOB get saved on the server, and any updates to the SOB by the service provider get delivered to you automatically. The former provides the SOB (and you) with backup, audit trail, and sharing across multiple users or devices. The latter provides for bug fixes and feature updates to the SOB on an ongoing basis.

All of this sounds suspiciously like a web app, except the fact that the SOB gets downloaded - which means it is available off line, can use all the features of your machine and in general doesn’t suffer the limitations of web apps. Another important distinction is that the core underlying technology is hotswapping, so the applications don’t need to be restarted when updated.

I’ve given a number of talks about this over the past few years; the latest was at Google earlier this month. Since that talk is available via Google Video, I thought I’d bring up the topic here.

The term I usually use for this idea is Objects as Software Services. It is more descriptive than SOB, but could be confused with generic stuff like SOAs and conventional web apps. Another descriptive name would be Live Network-Serviced Applications (LNSA). The “live” distinguishes them from most existing NSAs, which typically need to be taken down before being updated.

This leads to us to NSOOP, Network-Serviced Object Oriented Programming, and its support via NSOOPLs (NSOOP Languages). Though I just made these terms up, that is a big part of what the talk is about: language and platform features that enable LNSAs.

If this interests you, please see the talk. There are also earlier slides, and a brief write up.

Tuples

Tuples are a handy construct found in many programming languages. Oddly enough, they are lacking in mainstream languages like Java, C#, C++ etc.

Java was actually designed to have tuples from the start, but they never quite got in. At one point, I tried to add a tuple-like construct as part of JSR-65. We wanted to extend array initializers to full blown expressions. Eventually, that effort got quashed; I didn’t really resist, since the extension was painful, as such things always are in Java. We should have just done straight tuples as a separate construct - but at the time, that was frowned upon too.

Tuples are useful for a variety of reasons. If you need to package several objects together, but don’t want to define a class just for that purpose,you can use a tuple. This subsumes features like “multiple-value returns” which people have been seeking in Java for many years (without success). It also pretty much covers the need for variable-arity methods. Java went with a special sugar for these instead, a decision I initially opposed; I was eventually convinced to cave in on this, which I really regret (the responsible parties know who they are).

Anyway, that’s all water (well, coffee actually) under the bridge. Back to the main point.

Once you have tuples, handy uses crop up frequently, and you wonder how you ever got along without them.
Smalltalk doesn’t quite have tuples. Instead it has array literals, which are compile time constants and so rather limiting. Squeak does have tuples, though they are not very often used. It would be best to forego array literals entirely and replace them with tuples.

There are subtleties. Literal tuples are best defined as read only.
One reason for this is that readonly tuples are more polymorphic. Long tuples are subtypes of short ones:

{S. T. U. V } <= {S. T. U} <= {S. T} <= {S}

Read only tuples are covariant:

T1 <= T2, S1 <= S2 ==> {S1. T1} <= {S2. T2}

And a read-only literal tuple can be viewed as a list:

S <= U, T <= U, s: S , t : T ==> {s. t} : List[U]

where List[E] is a generic (note I'm using square brackets for type parameters) readonly type for lists (such as SeqCltn[E] in Strongtalk). It should be clear that it is very important to relate tuples to the general collection hierarchy.
Note that it is unsound to assume that

S <= U, T <= U ==> {S. T} <= List[U]

since

{S. T. V} <= {S.T} for all V, but if V <= U does not hold, {S. T. V} <= List[U] does not hold either.

Now if you want writable tuples, you can use an idiom like
{e1. e2. e3} asWritableTuple, which should create a copy of the literal that is writable (don’t worry about the cost of the copy; let the system figure it out).

So, to summarize: tuples are great. Every language should have them.

Representation Independent Code

In most object oriented languages, replacing a field with a method requires you to track down the uses of that field and changing them from field accesses to method invocations. The canonical example is a class of points. You decided to change your representation from cartesian to polar coordinates, and now all the places you wrote ‘x’ have to be rewritten as ‘x()’.


This example isn’t so bad, because the odds are you already had an x() method, and you probably had the sense to avoid making the x field public. But maybe you made it protected (perhaps your language is smart enough to disallow public fields, but simple-minded enough to force them to always make them protected, like Smalltalk). If x is protected, you’ll need to find all the subclasses. Maybe you don’t have access to all of them, and you can never get rid of the field x.


Or maybe you make a stupid mistake, and made x public, perhaps in the mad rush toward a release. Won’t happen to you? Take a look at Java’s System.out and ask yourself how it got to be there. Now go find all the uses of x and change them. Even if you can, it’s pretty tiresome.


The fact is, given the ability to publicize a field, programmers will do so. Once that’s happened, tracking down the uses may be impossible, and in any case is a huge amount of work.


It would be nice if you didn’t have to worry about this sort of thing. If everyone using your object went through a procedural interface, for example. Smalltalk makes all uses outside of an object do that - but uses within the object, in its class and subclasses, are exempt. As for mainstream languages like Java and C# - they allow you to declare public fields; it’s your funeral.


About 20 years ago, Dave Ungar and Randy Smith introduced Self, which fixed this problem. All communication is through method calls (or synchronous message sends, if you will) - even the object’s own code works exclusively by sending messages to itself and other objects. Fields (slots in Selfish) are defined declaratively, and automatically define access methods. The only way to get or set a field is by invoking a method. So if you get rid of the field and replace it with a method that computes the value instead, no source code anywhere can tell the difference. The code is representation independent. Self’s syntax makes it very easy and natural to send a message/call a method - there is no overhead compared to accessing a field in other languages.


In C# they have a thing called properties, which is similar. Except that C# also has fields, and so it requires careful attention by the programmer to ensure representation independence. In other words, it cannot be relied upon to happen. I don’t know why the designers of C# chose to support both fields and properties. I should ask my friends at Microsoft (yes, I have a few; I’m very non-judgmental). In complex languages, there are always all kinds of strange gotchas and constraints.


There are of course other ways that languages can undermine representation independence. In particular, the type system can support class types that make code dependent on which class you use, rather than on what interface is supported. I don’t want to dive into that right now.


The point of this post is to draw attention to the importance of representation independence. If you are using C# or something else with such a construct, I’d suggest you make the best of it and use properties or their equivalent religiously. And future languages should follow Self’s lead and ensure representation independence.

Parser Combinators

Many excellent ideas from functional programming apply to object oriented programming (functions are objects too, you know). Parser combinators in particular are a technique with a long history in the functional programming community.


This is a blog post, so I’m not going to give a proper bibliography of the idea; suffice to say that it goes back decades, and that Phil Wadler, and Erik Meijer, among others, have done important work in this area. I myself was inspired to look into the topic by Martin Odersky’s
Scala tutorial.


I’ve built a simple parser combinator library in Smalltalk, and it seems to work out very nicely. I thought it would be good to write about it here, coming at the topic from an OO perspective.


So, what are parser combinators exactly? The basic idea is to view the operators of BNF (or regular expressions for that matter) as methods that operate on objects representing productions of a grammar. Each such object is a parser that accepts the language specified by a particular production. The results of the method invocations are also such parsers. The operations are called combinators for rather esoteric technical reasons (and to intimidate unwashed illiterates wherever they might lurk).


To make this concrete, lets look at a fairly standard rule for identifiers:

id -> letter (letter | digit)*

using my combinator library in Smalltalk, one defines a subclass of CombinatorialParser, and inside it one writes

id := self letter, [(self letter | [self digit]) star]

Here, letter is a a parser that accepts a single letter; digit is a parser that accepts a single digit. Both are obtained by invoking a method on self ( this, for those unfortunates who don’t program in Smalltalk). The subexpression self letter | [self digit] invokes the method | on the parser that accepts a letter, with an argument that accepts a digit (ignore the square brackets for a moment). The result will be a parser that accepts either a letter or a digit.

tangent: No Virginia, Smalltalk does not have operator overloading. It simply allows method names using non-alphanumeric characters. These are always infix and all have the same fixed precedence. How can it be so simple? It’s called minimalism, and it’s not for everyone. Like Mies van der Rohe vs. Rococo.

The only detail I’ve glossed over is the brackets. The brackets denote closures, so that [self digit] is a closure that when applied, will yield a parser that accepts a digit. Why do I do this? Because grammar rules are often mutually recursive. If a production A is used in a production B and vice versa, one of them needs to be defined first (say, A), at which point the other (B) is not yet defined and yet must be referenced. Wrapping the reference to the other production in a closure delays its evaluation and gets round this problem. In a lazy language like Haskell this is not an issue - which is one key reason Haskell is very good at defining DSLs. However, Smalltalk’s closure syntax is very lightweight (lighter than lambdas in most functional languages!) so this is not a big deal. And Smalltalk’s infix binary methods and postfix unary methods give a very pleasing result overall.


We then invoke the method star on the result

(self letter | [self digit]) star

which yields a parser that accepts zero or more occurrences of either a letter or a digit.

In a syntax more people understand, this would look something like:


(1) letter().or( new DelayedParser(){ public Parser value(){ return digit();} }).star()


If Java had closures, it might look like this:


(2) letter().or({=> digit()}).star()


This is better, but either way, the goal of writing an executable grammar tends to get lost in the noise. Nevertheless, it seems most people prefer (1), and the vast majority of the rest prefer (2) over the “bizarre” Smalltalk syntax. Who knows what darkness lies in the hearts of men.

We pass this parser as an argument to the method , which we invoke on letter. The “,” method is the sequencing combinator (which is implicit in BNF). It returns a parser that first accepts the language of the receiver (target, in Javanese) and then accepts the language of its argument. In this case, this means the result accepts a single letter, followed by zero or more occurrences of either a letter or a digit, just as we’d expect. Finally, we assign this result to id, which will now represent the production for identifiers. Other rules can use it by invoking its accessor (i.e., self id).


The example also shows that this approach to parsing covers both lexers and parsers.


The lack of distinction between lexing and parsing is a bit of a problem. Traditionally, we rely on a lexer to tokenize the input. As it does that, it does away with whitespace (ignoring languages that make whitespace significant) and comments. This is easily dealt with by defining a new operator, tokenFor:, that takes a parser p and returns a new parser that skips any leading whitespace and comments and then accepts whatever p accepts. This parser can also attach start and end source indices to the result, which is very handy when integrating a parser into an IDE. From the point of view of higher level grammar productions, its useful to refer to a production identifier that produces such tokenized results:

identifier := self tokenFor: self id.

We would naturally do this for all the tokens in our language, and then define the syntactical grammar without concern for whitespace or comments, just as we would in traditional BNF. As an example, here’s the rule for the return statement in Smalltalk

returnStatement := self hat, [self expression].

Ok, so you can define a parser pretty much by writing down the grammar. However, just accepting a language isn’t all that useful. Typically, you need to produce an AST as a result. To address this, we introduce a new operator, wrapper: . The result of this operator is a parser that accepts the same language as the receiver. However, the result it produces from parsing differs. Instead of returning the tokens parsed, it processes these tokens using a closure which it takes as its sole parameter. The closure accepts the output of the parse as input, and yields some result - typically an abstract syntax tree.

returnStatement := self hat,  [self expression]

     wrapper:[:r :e  | ReturnStatAST new expr:e; start: r start; end: e end].  

The grammar production is still clearly separated, with the AST generation on a separate line. However, I would prefer to leave the grammar pristine. That’s easy - put all the AST generation code in a subclass, where the grammar production accessors are overridden, so:

returnStatement

^super returnStatement

    wrapper:[:r :e  | ReturnStatAST new expr:e; start: r start; end: e end].    

This is nice, for example, if you want to parse the same language and feed it to different back ends that each accept their own AST; or if you need to use the parser for a different purpose, like syntax coloring, but want to share the grammar. Another nice thing about this approach is that one can factor out language extensions very cleanly (especially if you can use mixins). It's one of the benefits of embedding a DSL in a general purpose language - your DSL inherits all the features of the host language. In this case, it inherits inheritance.


So what’s not to like? Well, one could imagine more efficient approaches to parsing. In Smalltalk, one usually parses one method at a time, and methods tend to be short. Even though I'm using Squeak, which isn't all that fast, and parses a method on every keystroke to do syntax coloring, it's perfectly acceptable. For large methods, the delay can be noticeable though. However, there are ways to tune things to improve performance. We have our methods ...


Another problem is left recursion, as in:

expr -> expr + expr | expr * expr | id

In such cases one has to refactor the grammar. I don’t see this as a big deal, and in principle, the parser could refactor itself dynamically to solve the problem; this is one of things that one can do relatively easily in Smalltalk, that tends to be harder in other languages.


In summary, parser combinators are really cool. They work out beautifully in Smalltalk. I had a blast implementing them and using them. Most important, they are a great example of how object orientation and functional programming synergize. If you want to learn more, there’s a lot of literature out there, mainly in the Haskell world.

Foozle Wars

I saw this piece about Foozles on Phil Wadler’s blog. It’s been there for a while, but I missed it until now. It’s great satire, covering many, er, infirmities of our field, from Aspectitis through Theorititis.


Since Foozles are a category theoretic dual of Aspects, I might as well mention that one of the most interesting things at OOPSLA was the debate over aspects. For the record, I have never believed in AOP. Not that there aren’t real problems that the AOP community highlights; my problem is with the alleged solution.


In particular, colleagues I respect, like Mira Mezini, have told me that AOP is in large part about modularity. And yet, it’s become quite clear that AOP has serious problems with modularity. I’d encourage everyone to read Friedrich Steimann’s excellent essay on the topic.


Kevin Sullivan has done a great job of pinpointing the modularity problem with AOP, and to propose fixes. There’s fascinating work out of Harvard Business School that informs his approach. See his OOPSLA tutorial for starters.


The modularity problems with aspects are related to those with inheritance, but more severe. Let’s look at inheritance. If one simply copies a class (textually) and modifies it, the copy is independent of the original. We can change the original without considering repercussions on the validity of the copy. With inheritance, we have a linguistic mechanism that performs the derivation for us, recognizes the dependency and maintains it. The advantages are well know - changes to the original automatically propagate to the subclass, type systems understand the relationship between the two etc. And there is a benefit - the delta defined by the subclass is defined separately. The disadvantage is that we are much more restricted in what changes we can make to the original without causing breakage in subclasses.


The situation with aspects is not dissimilar. Aspects, like inheritance, are a linguistic mechanism that automatically derive a variant of the original base code, and maintains a dependency from the base code to the aspects. The aspect is also textually separated - this is what makes people think it helps modularity. If the base code changes, the aspect can still apply - as long as the changes are restricted enough; on the downside, if the base code changes something the aspect relies on, the aspect will break, and so we are limited in what we can change in the base code.


Over time, we’ve recognized what the interface between superclasses and subclasses is, made much of it explicit, and understood what limitations that places on superclasses (and superinterfaces).


For example, widely distributed interfaces cannot have methods added to them, which is a pretty harsh restriction. Incidentally, while the common wisdom is that you can add concrete methods to abstract classes,the truth is that these may conflict with subclasses and in principle should be avoided as well.


With aspects, this interface remains implicit, and without an interface, there is no modularity. The base code does not commit to any interface that the aspects can rely on; they can be undermined at any time. The problem is compounded because the coupling with the base is very tight. Resolving this requires giving up on obliviousness - the idea that the base code is unaware of the aspects. Instead, base code will have to declare itself as being an aspect-base in some way. The restrictions on its evolution in that situation are likely to be pretty limiting.


Interestingly, the cloning solution - making a copy of the original and applying the aspects changes to it - is more viable if you take the view that aspects are a reflective change to the base program. We can achieve the effect of an aspect using a suitable reflective API, that can quantify over and modify base code from the outside. Using reflection, the base code need not be edited, and the aspect remains textually separate. Unlike real aspects, no dependency is maintained between the base code and the changes to it. Our “aspects” are independent of changes to the original. Of course, we do have a maintenance problem, which may be eased by tools that track and warn about changes to the base - but do not enforce any dependency. One can even take a similar tack with respect to inheritance.


Given how onerous the restrictions on base code are likely to be if they commit to supporting aspects (or how weak the aspects will be if the commitments by base code are not onerous), I doubt modular aspects will be worth supporting at the language level; I’d put my money on reflection and tool support instead - but time will tell.

And the Winner is ... Self

I just got back from OOPSLA.  Far too much going on to report all of it here. One thing I will mention was the awards session.

I was very pleased to see Dave Ungar recognized twice - once as an ACM Distinguished Engineer, and once more, with Randy Smith, for the original Self paper,(if you have some difficulties with ACM's digital library, here's the journal version), which was chosen as one of the three most influential OOPSLA papers published in the years 1986-1996.

David Bacon got an ACM Distinguished Scientist award as well.

It was also great to see Bill Harrison and Harold Ossher get an award for their paper on Subjectivity.  It’s especially nice when the winners are such nice people.

I don’t personally know Pattie Maes, the author of the other (not the third - there was no ranking among the winning papers) award winning paper, but it is a classic and truly deserving of recognition.

I hope these awards get people to go back and read those papers again. They are all great idea papers. As Dave said when accepting the award, the Self paper had no proofs, no discussion of implementation, and was not an extension of anything. This is in sharp contrast to most of the work that gets published today, which is largely incremental. It’s almost impossible to get a paper accepted that doesn’t have a fairly complete implementation, or a lot of formalism.  This is perhaps inevitable in a maturing field, but it isn’t nearly as much fun, as interesting, as inspiring or as important.

It would be very good if more people understood the ideas rather than the details of particular manifestations we see today. Comparing Self with some of the languages that are popular right now would be a very good exercise for anyone interested in programming language design.  It helps gauge the quality of the designs and the implementations, and gives a perspective that most people are missing.

Why is this blog named this way?

Well, there's the obvious reasons of course. Apart from those, in a previous life I was required to attend JavaOne. I noticed that the room where they handed out goodies to speakers was numbered 101.

Apparently, no one found this disturbing. I guess they haven't come out with "The complete idiot's guide to Orwell for dummies in 21 days" yet.
In any event, I hope to find time to occasionally post thoughts about programming languages and platforms.