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.