More on Modules

My posts seem to raise more questions than they answer. This is as it should be, in accordance with the Computational Theologist Full Employment Act. In this post, I’ll try and answer some of the questions that arose from my last one.

How does one actually hook modules together and get something going? As I mentioned before, module definitions are top level classes - classes that are defined in a namespace, rather than in another class.

Defining a top level class makes its name available in the surrounding namespace. More precisely, it causes the compiler to define a getter method with the name of the class on the namespace; the method will return the class object.

Since a module definition is just a class, one needs to instantiate it, by calling a constructor - which is a class side method. Continuing with the example from the previous post:

MovieLister finderClass: ColonDelimitedMovieFinder

Now this isn’t quite realistic, since ColonDelimitedMovieFinder probably needs access to things like collections and files to do its job. So it’s probable that it takes at least one parameter itself. The typical situation is that a module definition takes a parameter representing the necessary parts of the platform libraries. It might look something like this:

ColonDelimitedMovieFinder usingLib: platform = (
|
OrderedCollection = platform Collections OrderedCollection.
FileStream = platform Streams FileStream.
|
)...


So we’d really create the application this way:

MovieLister finderClass: (ColonDelimitedMovieFinder usingLib: Platform new)

where Platform is a predefined module that provides access to the built-in libraries.

Bob Lee points out that if I change MovieLister so that it takes another parameter, I have to update all the creation sites for MovieLister, whereas using a good DIF I only declare what needs to be injected and where.

In many cases, I could address this issue by declaring a secondary constructor that feeds the second argument to the primary one.

Say we changed MovieLister because it too needed access to some platform library:

class MovieLister usingLib: platform finderClass: MovieFinder = ...


We might be able to define a secondary constructor

class MovieLister usingLib: platform finderClass: MovieFinder = (
...
): (
finderClass: MovieFinder = (
^usingLib: Platform new finderClass: MovieFinder
)
)

There are however two situations where this won’t work in Newspeak.

One is inheritance, because subclasses must call the primary constructor. I showed how to deal with that in one of my August 2007 posts - don’t change the primary constructor - change the superclass.

class MovieLister finderClass: MovieFinder = NewMovieLister usingLib: Platform new finderClass: MovieFinder
(...)

The other problematic case is for module definitions. In most cases, the solutions above won’t help; they won’t be able to provide a good default for the additional parameter, because they won’t have access to the surrounding scope. For this last situation I have no good answer yet. I will say that the public API of a top level module definition should be pretty stable, and the number of calls relatively few.

So overall, I think Bob makes an important point - DIFs give you a declarative way of specifying how objects are to be created. On the other had, it gets a bit complicated when different arguments are needed in different places, or if we don’t want to compute so many things up front at object creation time. Guice has mechanisms to help with that, but I find them a bit rich for my blood. In those cases, I really prefer to specify things naturally in my code.

Another advantage of abstracting freely over classes is that you can inherit from classes that are provided as parameters.

class MyCollections usingLib: platform = (
| ArrayList = platform ArrayList. |
)(
ExtendedArray List = ArrayList (...)
)

Now, depending what library you actually provide to MyCollections as an argument, you can obtain distinct subclasses (in fact, there’s an easier way to do this, but this post is once again getting too long). Correct me if I’m wrong, but I don’t think a DIF helps here.

You can also do class hierarchy inheritance: modify an entire library embedded within a module by subclassing it and changing only what’s needed. This is somewhat less modular (inheritance always causes problems) but the tradeoff is well worth it in my opinion.

I spoke about class hierarch inheritance at JAOO, and will likely speak about it again in one or more of my upcoming talks on Newspeak, at Google in Kirkland on January 8th, at FOOL on January 13th, or at Lang.Net 2008 in Redmond in late January.

I’m trying to make each of these talks somewhat different, but they will necessarily have some overlap. I hope that some of these talks will make it onto the net and make these ideas more accessible.

Lethal Injection

Some months ago, I wrote a couple of posts about object construction and initialization. I made the claim that so-called dependency-injection frameworks (DIFs) are completely unnecessary in a language like Newspeak, and promised to expand on that point in a later post. Four months should definitely qualify as “later”, so here is the promised explanation.

I won’t explain DIFs in detail here - read Martin Fowler’s excellent overview if you need an introduction. The salient information about DIFs is that they are used to write code that does not have undue references to concrete classes embedded in it. These references are usually calls to constructors or static methods. These concrete references create undue intermodule dependencies.

The root of the problem DIFs address is that mainstream languages provide inadequate mechanisms to abstract over classes.

Terminology rant: DIFs should more properly be called dependee-injection frameworks. A dependency is a relationships between a dependent (better called depender) and a dependee. The dependencies are what we do not want in our code; we certainly don’t want to inject more of them. Instead, DIFs inject instances of the dependees, so the dependers don’t have to create them.

DIFs require you write your code in a specific way, where you avoid creating instances of dependees. Instead, you make sure that there is a way to provide the dependee instance (in DIF terminology, to inject it) from outside the object. You then tell the framework where and what to inject. The reason injection traffics in instances rather than the classes themselves is because there’s no good way to abstract over the classes.

Having recapped DIFs, lets move on to Newspeak. Newspeak modules are defined in namespaces. Namespaces are simply objects that are required to be deeply immutable; they are stateless.

Tangent: This ensures that there is no global or static state in Newspeak, which gives us many nice properties.

Namespaces are organized like Java packages, as an inversion of the internet domain namespace. Unlike Java packages, sub-namespaces can see their enclosing namespace.

A module is a top-level class, that is, a class defined directly within a namespace. Newspeak classes can nest arbitrarily, so a module can contain an entire class library or framework, which can in turn be subdivided into subsystems to any depth. Nested classes can freely access the lexical scope of their enclosing class.

Modules, like all classes, are reified as objects that support constructor methods. Recall that in Newspeak, a constructor invocation is indistinguishable from an ordinary method invocation. Objects are constructed by sending messages to (invoking virtual methods on) another object. That object may or may not be a class; it makes no difference. Hence all the usual abstraction mechanisms in the language apply to classes - in particular, parameterization.

Here is a trivial top level class, modeled after the motivating example for DIFs given in Fowler’s article:

public class MovieLister = (
|
private movieDB = ColonDelimitedMovieFinder from:’movies.txt’.
|)
(
public moviesDirectedBy: directorName = (
^movieDB findAll select:[:m |
m director = directorName
].
)

The idea is that MovieLister supports one method, moviesDirectedBy:, which takes a string that contains the name of a director and returns a collection of movies directed by said director. The point of Fowler’s example is that there is an undesirable dependency on a class, ColonDelimitedMovieFinder, embedded in MovieLister. If we want to use a different database, we need to change the code.

However, this code won’t actually work in Newspeak. The reason is that the enclosing namespace is not visible inside a Newspeak module. Any external dependencies must be made explicit by passing them to the module as parameters to a constructor method. These parameters could be other modules, namespaces, or classes and instances of any kind.

In this specific case, ColonDelimitedMovieFinder cannot be referenced from MovieLister. If we try and create a MovieLister by writing: MovieLister new, creation will fail with a message not understood error on ColonDelimitedMovieFinder. We’d have to declare a constructor for MovieLister with the movie finder as a parameter:

public class MovieLister finderClass: MovieFinder = (
|
private movieDB = MovieFinder from:’movies.txt’.
|)
(
public moviesDirectedBy: directorName = (
^movieDB findAll select:[:m |
m director = directorName
].
)

At this point, we can immediately see that we can replace ColonDelimitedMovieFinder with any class that supports the same interface, which was the object of the entire exercise. Newspeak won’t let you create a module with concrete external dependencies, because that wouldn’t really be a module, would it?

In Newspeak code in a module doesn’t have any concrete external dependencies, and no dependees need to be injected. What’s more we can subclass or mix-in any class coming in as a parameter - something a DIF won’t handle.

What about a subsystem within a module? What if I don’t want it using the same name binding as the enclosing module? I can explicitly parameterize my subsystem, though that requires pre-planning.

I can also override any class binding in a subclass. Newspeak is message-based, so all names are late-bound. Hence any reference to the name of a class can be overridden in a subclass. Classes can be overridden by methods or slots or other classes in any combination. So even if you do not explicitly parameterize your code to allow for another class to be used to construct an object, you can still override the binding of the class name as necessary.

In summary, Newspeak is designed to support, even induce, loose coupling. That’s the point of message based programming languages. DIFs are an expedient technique to reduce code coupling in the sad world of mainstream development, but in a language like Newspeak, they are pointless.

Executable Grammars

Way back in January, I described a parser combinator library I’d built in Smalltalk. Since then, we’ve moved from Smalltalk to Newspeak, and refined the library in interesting ways.

The original parser combinator library has been a great success, but grammars built with it were still polluted by two solution-space artifacts. One is the need to use self sends, as in

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

In Newspeak, self sends can be implicit, and so this problem goes away. We could write

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

The other problem is the use of blocks. We’d much rather have written

id:: letter, (letter | digit) star

The solution is to have the framework pre-initialize all slots representing productions with a forward reference parser that acts as a stand-in for the real parser that will be computed later.

When the tree of parsers representing the grammar has been computed, it will contain stand-ins exactly in those places where forward references occurred due to mutual recursion. When such a parser gets invoked, it looks up the real parser (now stored in the corresponding slot) and forwards all parsing requests to it.

Our parsers are now entirely unpolluted by solution-space boilerplate, so I feel justified in calling them executable grammars. They really are executable specifications, that can be shared among all the tools that need access to a language’s grammar.

Below is a small but complete grammar in Newspeak:

class ExampleGrammar1 = ExecutableGrammar (
|
digit = self charBetween: $0 and: $9.
letter = (self charBetween: $a and: $z) | (self charBetween: $A and: $Z).
id = letter, (letter | digit) star.
identifier = tokenFor: id.
hat = tokenFromChar: $^.
expression = identifier.
returnStatement = hat, expression.
|
) ()

If you want to understand all the details, check out this paper; if you can, you might also look at my JAOO 2007 talk, which also speculates on how we can make things look even nicer, e.g.:

class ExampleGrammar3 = ExecutableGrammar (
|
digit = $0 - $9.
letter = ($a - $z) | ($A - $Z).
id = letter, (letter | digit) star.
identifier = tokenFor: id.
expression = identifier.
returnStatement = $^, expression.
|
)()

Object Initialization and Construction Revisited

In my last post, which discussed object initialization and construction, I had promised to come back to the topic and clarify it with concrete examples. I've finally found time to do that; hopefully I will dispel some of the misunderstandings that the last post engendered, no doubt replacing them with fresh, deeper misunderstandings.

Below is a standard example - a class representing points in the plane. What’s non-standard is that it is written in Newspeak, an experimental language in the style of Smalltalk, which I and some of my colleagues are working on right now. In cases where the syntax is non-obvious, I’ll use comments (Pascal style, like so: (* this is a comment *)) to show how a similar construct might be written in a more conventional (and less effective) notation.

class Point2D x: i y: j = ( 
(* Javanese version might look like this : 
   class Point2D setXY(i, j) { ...} *)
(*A class representing points in 2-space” *)
|
  public x ::= i.
  public y ::= j.
|
) (    (* instance side *)

  public printString = (
    ˆ ’ x = ’, x printString, ’ y = ’, y printString
  ) 
)

this declaration introduces the class Point2D. The class name is immediately followed by a message pattern (method signature for readers of Javanese) x: i y: j. This pattern describes the primary constructor message for the class. The pattern introduces two formal parameters, i and j, which are in scope in the class body. The result of sending this message to the class is a fresh instance, e.g.:

Point2D x: 42 y: 91 
(* In Javanese, you might write Point2D.setXY(42, 91);  
   But don’t even think of interpreting setXY as a static method!
*)

yields a new instance of Point2D with x = 42 and y = 91. The message causes a new instance to be allocated and executes the slot initializers for that instance, in this case

x ::= i.
y ::= j.

The slots are accessed only through automatically generated getters (x and y) and setters (x: and y:).

How is all this different from mainstream constructors?
Because an instance is created by sending a message to an object, and not by some special construct like a constructor invocation, we can replace the receiver of that message with any object that responds to that message. It can be another class (say, an implementation based on polar coordinates), or it can be a factory object that isn’t a class at all.

Here is a method that takes the class/factory as a parameter

makePoint: pointFactory = (
(* In Javanese: 
   makePoint(pointFactory) {
     return pointFactory.setXY(100, 200)
   } 
*)
  ^pointFactory x: 100 y: 200
)

We can invoke this so:

makePoint: Point2D

but also so:

makePoint: Polar2D

where Polar2D might be written as follows:

class Polar2D rho: r theta: t = (
(* A class representing points in 2-space”*)
|
  public rho ::= r.
  public theta ::= t.
|
) (   (* instance side *)
  public x = ( ^rho * theta cos) (* emulate x/y interface *)
  public y = (^rho * theta sin)
  ...
  public printString  = (
    ˆ ’ x = ’, x printString, ’ y = ’, y printString
  )
) : (  (* class side begins here*)
  public x: i y: j = (
    | r t |
    t := i arcCos.
    r := j/ t sin.
    ˆrho: r theta: t
  )
)

Here, Polar2D has a secondary constructor, a class method x:y:, which will be invoked by makePoint:.

You cannot do this with constructors or with static factories; you simply cannot abstract over them.

You could use reflection in Java, passing the Class object as a parameter and then searching for a constructor or static method matching the desired signature. Even then, you would have to commit to using a class. Here we can use any object that responds to the message x:y:.

Using Java core reflection in this case is awkward and verbose, and historically hasn’t been available on configurations like JavaME. And it doesn’t work well with proxy objects either (see the OOPSLA 2004 paper we wrote for details). What’s more, you may not have the right security permissions to do it. The situation is not much better with the VM from the makers of Zune (tm) either.

Zune is a trademark of Microsoft Corporation. Microsoft is also a trademark of Microsoft Corporation. But GNU’s not Unix

Alternatively, you could also define the necessary factory interface, implement it with factory classes, create factory objects and only pass those around. You’d have to do this for every class of course, whether you declared it or not. This is tedious, error prone, and very hard to enforce. The language should be doing this for you.

So far, we’ve shown how to manufacture instances of a class. What about subclassing? This is usually where things get sticky.

Here’s a class of 3D points

class Point3D x: i y: j z: k = Point2D x: i y: j (
(* A class representing points in 3-space *)
| public z ::= k. |
)  (* end class header *)
(  (*begin instance side *)
   public printString = (
    ˆsuper printString, ’ z = ’, z printString
  )
)

One detail that’s new here is the superclass clause: Point3D inherits from Point2D, and calls Point2D’s primary constructor. This is a requirement, enforced dynamically at instance creation time. It helps ensure that an object is always completely initialized.

Unlike Smalltalk, one cannot call a superclass’ constructors on a subclass. This prevents you from partially instantiating an object, say by writing:

Point3D x: 1 y: 2  (* illegal! *)

without initializing z as intended. Also, unlike Smalltalk, there’s no instance method that does the initialization on behalf of the class object. So you cannot initialize an object multiple times, unless the designer deliberately creates an API to allow it. The idea is to ensure every object is initialized once and only once, but without the downsides associated with constructors.

Preventing malicious subclasses from undermining the superclass initialization takes care. We’re still considering potential solutions. The situation is no worse than in Java, it seems, and we may be able to make it better.

A different concern is that the subclass must call the primary constructor of the superclass. So what happens when I want to change the primary constructor? Say I want to change Point2D to use polar representation. Can I make rho:theta: the primary constructor? How can I do this without breaking subclasses of Point2D, such as Point3D? We can't do it directly yet (though we should have a fix for that in not too long), but I can redefine Point2D
as

class Point2D x: i y: j =  Polar2D rho:  ... theta: ... = ()()
: ( “class side begins here”
(* secondary constructor *)
  public rho: r theta: t = (
    ˆx: r * t cos y: r * t sin
  )
)

Now anyone who uses a Point2D gets a point in polar representation, while preserving the existing interface. And anyone who wants to can of course create polar points using the secondary constructor. I can also arrange for that constructor to return instances of Polar2D directly:

public rho: r theta: t = (
  ˆPolar2D rho: r theta: t
)

If you find this interesting, you might want to read a short position paper I wrote for the Dynamic Languages Workshop at ECOOP. It only deals with one specific issue regarding the interaction of nested classes and inheritance, and it’s a just a position paper describing work in progress, but if you’ve gotten this far, you might take a look.

I still haven’t explained why I see no need for dependency inversion frameworks. The short answer is that because Newspeak classes nest arbitrarily, we can define a whole class library nested inside a class, and parameterize that class with respect to any external classes the library depends on. That probably needs more explanation; indeed, I think there’s a significant academic paper to be written on the subject. Given the length of this post, I won’t expand on the topic just yet.

Constructors Considered Harmful

In mainstream object oriented programming languages, objects are created by invoking constructors. This is rather ironic, since you can say a lot about constructors, but you cannot honestly say that they are object oriented. Ok, so what? Isn’t “object-oriented” just an old buzzword? If constructors work well, who cares?

Of course, the problem is that constructors don’t work very well all. Understanding why helps to understand what “object oriented” really means, and why it is important.

Constructors come with a host of special rules and regulations: they cannot be overridden like instance methods; they need to call another constructor, or a superclass constructor etc. Try defining mixins in the presence of constructors - it’s tricky because the interface for creating instances gets bundled with the interface of the instances themselves.

The basic issue is a failure of abstraction, as Dave Ungar put it in his OOPSLA keynote in 2003.

Suppose we have a constructor C(x) and code that creates objects by calling it. What happens if we find that we actually need to return an instance of a class other than C? For example, we might want to lazily load data from secondary storage, and need to return some sort of placeholder object that behaves just like a C, but isn’t? What if we want to avoid reallocating a fresh object, and use a cached one instead?

So it’s clear that you don’t want to publicize your constructors to the clients of your API, as all they can do is tie you down.

The standard recommended solution is to use a static factory. This however, does nothing to help the other victims of constructors - their callers. As a consumer of an API, you don’t want to use constructors: they induce a tight coupling between your code and specific implementations. You can’t abstract over static methods, just as you can’t abstract over constructors. In both cases, there is no object that is the target of the operation and a conventional interface declaration cannot describe it. The absence of an object means that constructors don’t have the benefits objects bring - dynamic binding of method calls chief among these. Which is why constructors and static methods don’t work well, and incidentally, aren’t object oriented.

Having dismissed constructors and static factories, it seems we need to define a factory class whose instances will support an interface that includes a method that constructs the desired objects. How will you create the factory object? By calling a constructor? Or by defining a meta-factory? After how many meta-meta-meta- .. meta-factories do you give up and call a constructor?

What about using a dependency injection framework (DIF)? Ignoring the imbecilic name, I think that if you’re stuck with a mainstream language, that may be a reasonable work around. It requires a significant degree of preplanning, and makes your application dependent on one more piece of machinery that has nothing to do with the actual problem the application is trying to solve. On the positive side, it helps guarantee employment for software engineers. That said, it’s important to understand that DIFs are just a work around for a deficiency in the underlying language.

So why not get rid of constructors and have a class declaration create a factory object instead? Well, Smalltalk did just that a generation ago. Every time you define a class, you define the factory object for its instances. I won’t explain the Smalltalk metaclass hierarchy here. Suffice to say that it is a thing of beauty, resolving a potential infinite regress with an elegant circularity.

Despite this, Smalltalk still does not provide an ideal solution for creating and initializing instances. While it preserves abstraction, it does not easily enable the class to ensure that every instance will always be properly initialized, or that initialization will take place only once. To be sure, these are difficult goals, and Java, despite enormous efforts and complexity focused on these goals, does not fully achieve them either. However, it comes close - at the cost of abstraction failure brought about by the use of constructors.

So can we do better? Of course. The solution combines elements of Scala constructors (which are cleaner than Java constructors) with elements of the Smalltalk approach.

Scala defines a class as a parametric entity, with formal parameters that are in scope in the class body. The class name, together with its formal parameters, define the primary constructor of the class. This allows the instance to initialize itself, accessing the parameters to the constructor without exposing an initialization method that can be called multiple times on an instance. The latter is one of the problems in Smalltalk.

We use a similar device to provide access to the constructor parameters from within the instance. However, we require that the class provide a method header for its primary constructor. Instead of creating instances by a special construct (constructor invocation) as in Java or Scala, we create them via method invocation. The class declaration introduces a factory object that supports the primary constructor as an instance method.

Because we create objects only by invoking methods on other objects, we preserve abstraction. We can create objects by invoking the constructor method on a parameter. We can always define alternative factory objects that support the same constructor method with different behavior, and pass them instead of the class. Furthermore, using a message based programming language, references to the class’ name are always virtual, and can be overridden.

Unlike Smalltalk, the factory class is not a subclass of the superclass factory class. This prevents the possibility of calling superclass constructors and thereby creating partially initialized objects (doing this requires special effort in Smalltalk - one has to manually override the superclass constructors so that they fail; this is tedious and error prone, and not done much in practice).

I know I should be writing examples to make this all clear. However, this post is getting long, so that will wait for another post. I’ll be speaking about some of this work next month a the dynamic language workshop at ECOOP. By then, I imagine I’ll put out some examples of what we’ve been doing these past few months.

Message Based Programming

Alan Kay was recently quoted as saying that Smalltalk should have been message oriented rather than object oriented. I’m not sure what he meant by that, but it got me thinking.

Smalltalk terminology refers to method invocations as message sends. Message passing is often associated with asynchrony, but it doesn’t have to be. Smalltalk message sends are synchronous. As such, they seem indistinguishable from virtual method invocations. However, the terminology matters. Insisting that objects communicate exclusively via message sends rules out aberrations such as static methods, non-virtual methods, constructors and public fields. More than that:

It means that one cannot access another object’s internals - we have to send the object a message. So when we say that an object encapsulates its data, encapsulation can’t be interpreted as just bundling - it means data abstraction.

it implies that the only thing that matters about an object is how it responds to messages. Two objects that respond the same way to all messages are indistinguishable, regardless of their implementation details. This excludes implementation types for objects, and hence class based encapsulation, as in:

class Foo {
private Integer bar = 101; // my secret code
public Integer baz(Foo f) {return f.bar;}
}

Overall, the message passing terminology precludes the interpretation of objects we see in mainstream languages - the spawn of C. This has great value. However, while saying that all objects communicate via message passing gives a strong notion of object, it doesn’t ban things that aren’t objects, such as values of primitive type like ints and floats. It doesn’t guarantee that a language is purely object oriented, like Smalltalk.

We can nevertheless ask: is Smalltalk a message based programming language? I think not. I would take message-based programming to have an even stronger requirement: all computation is done via message passing. That includes the computation done within a single object as well. Whereas Smalltalk objects can access variables and assign them, message based programming would require that an object use messages internally as well. This is exactly what happens in Self, as I discussed in an earlier post about representation independent code.

The implications of this are quite strong. In particular, this formulation does carry with it the requirement that everything is an object (at least at run time), since the only entities one computes with are those that respond to messages.

I like the term Message-based Programming (MBP). It implies a lot of valuable design decisions I strongly believe in, while leaving many design alternatives open. The term is, I hope, free of the baggage that is associated with object oriented programming, which has too many flawed interpretations.

I believe that future programming languages should be message based, in the sense I’ve defined above. This still leaves language developers with a huge design space to work with: message based programming languages can be imperative or declarative; statically or dynamically typed; class-based or prototype based; reflective or not; eager or lazy; and synchronous or asynchronous, to name a few important design options.

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.