Room 101

A Ban on Imports

2009-06-30T16:28:00.000-07:00

This is not, of course, an essay on restricting free trade. Rather, this post is about the evils of the import clause, which occurs in one form or another across a wide array of programming languages, from Ada, Oberon and the various Modulas, through Java and C#, and on to F# and Haskell.

The import clause should be banned because it undermines modularity in a deep and insidious way. This is a point I’ve attempted to convey time and time again, with only limited success. I will now try to illustrate the problem via a hardware inspired example.

Consider the not-so-humble MP3 player. An MP3 player is a hardware module. The market is full of them, as well as other hardware modules they can plug in to. For example, sound systems where on can dock an MP3 player and have it play on stereo speakers.

Let’s try and describe the analog of such a sound system using programming language modularity constructs that rely on imports:

module SoundSystem

import MP3Player;

... wonderful functionality elided ...

end

I want to describe how my sound system works, separately from the description of how an MP3 player works. I would like to later plug in a particular MP3 player, say a Zune(tm) or an iPod(tm)

tm: Zune and iPod are trademarks of Microsoft and Apple respectively, two companies with armies of lawyers who might harass me if I do not state the obvious.

Now the first problem is that neither Zune or iPod are named MP3Player. If I want to connect my sound system to a Zune, I will have to edit the definition of SoundSystem to name the specific module I want to import.

If you’re very petty, you might say that Zune and iPod do not share a common interface and cannot be docked into the same sound system. Imagine that we wish to use our sound system with an iPhone (tm) and an iPod Touch (tm) of some compatible generation.

tm: iPhone and iPod Touch are trademarks of Apple.

Say I decide to go with a Zune.

module SoundSystem

import Zune;

... wonderful functionality elided ...

end

Later I change my mind for some reason, and want to hook up my system to an iPod. It’s easy: I just edit the definition of my system again, to import iPod:

module SoundSystem

import iPod;

... wonderful functionality elided ...

end

The question you should be asking is: Why should I edit the definition of my system each time I change the configuration? In reality, it is unlikely that I am actually the designer of SoundSystem. I probably don’t even have access to its definition. I just want to configure it to work with my MP3 player.

The problem is that import confounds module definition and module configuration. Module definition describes the design of a module; module configuration describes how one hooks up different modules. The former has to do with module internals; the latter should be done externally to the modules involved, to allow them to be used in any context where they could function.

We clearly want our sound system to abstract over the specific player being plugged in to it. Any player with a compatible interface will do. A well known mechanism for abstracting things is parameterization. We might be happier if we defined our sound system parametrically with respect to the MP3 player

module SoundSystem(anMP3Player){
... great wonders using anMP3Player ...
}

We could them configure our system to use an iPod:

SoundSystem(iPod);

or a Zune

SoundSystem(Zune);

without having to modify (or even have access to) the source code for the definition of SoundSystem. Hurray!

The module definition looks a lot like a function, and the configuration code looks like a function application. This is very suggestive. Indeed, ML introduced a module system based on function-like things called functors a quarter century ago. But there’s a bit more to this.
These hardware pieces tend to plug in to each other. For example, the definition of IPod is parametric too:

IPod(dockingStation){... even greater wonders ...}

Our sound system does its thing by behaving like a docking station. It and the MP3 player are mutually recursive modules. Configuration therefore requires support for mutual recursion (which is not allowed in Standard ML):

letrec {

dock = SoundSystem(mp3Player);

mp3Player = IPod(dock);

} in dock;

If this notation is unfamiliar, please brush up on your functional programming skills before you become unemployable. Basically, ignore the first and last line, and treat the two lines involving = as equations.

So the module definitions are a lot like functions that yield modules. You could also think of module definitions as classes yielding instances. The instances are like physical hardware modules.

Now we can add another sound system and use our old Zune

letrec {

dock2 = SoundSystem(oldMP3);

oldMP3 = Zune(dock2);

} in dock2;

This is what is often called side by side deployment - multiple instances of the same design, configured differently.

Tangent: Yes, Virginia, you can achieve that sort of thing in Java despite imports, using class loaders. Imports hardwire names into your code, and class loaders can counteract that by letting you define multiple namespaces. These can have multiple copies of your code, potentially hardwired to different things (even though they all have the same name). If you think class loaders offer a simple, clean way of doing things that is easy to learn, use, understand and debug, this post is not for you. Nor will any amount of OSGi magic on top fundamentally change things.

We might also choose to define things differently

module SoundSystem(MP3Player) {

player = MP3Player(self);

...

}

Here, we are passing module definitions as parameters. We are also referring to SoundSystem’s current instance from within itself - a lot like classes, no? We might configure things thusly

SoundSystem(iPod);

So it looks like mutual recursion and first class module definitions are very natural things to have. And yet traditional languages do not support this - even though many languages have constructs like classes and functions that are first class values and can be defined in a mutually recursive fashion.

One problem with using these constructs to define modules is that they are usually able to access anything in the global namespace. This makes it very hard to avoid implicit dependencies.

Interestingly, the global namespace is exactly what import requires. Since we don’t need or want import, let’s do away with it and the global namespace. We clearly will get a much more modular system without it; but wait - there seems to be one place where we really want the global namespace. That is when we write our configuration code, the code that wires our modules together.

That’s fine - there are a number of solutions for that. It isn’t always clear that our configuration language is the same language as the programming language(s) that define our modules, for example. If you write a makefile, the global namespace is defined by your file system and accessible within the makefile. Not that I really want to recommend make and its ilk.

I think we do want to code our configuration in a nice general purpose high level programming language. One solution is to have our IDE provide us with an object representing the known global namespace, and write our configuration code with respect to that namespace object. This is essentially what we do in Newspeak.

In the next post, I’ll discuss more of the advantages of this approach, contrast how Newspeak handles things with other languages with powerful module systems, like Scheme (which for the past decade or so has had a system called Units that is quite close to what I’ve discussed so far) and ML, and show once more how one actually does configuration in Newspeak.

To be continued.

Original Sin

2009-05-25T16:10:00.000-07:00

I’ve often said that Java’s original sin was not being a pure object oriented language - a language where everything is an object.

As one example, consider type char. When Java was introduced, the Unicode standard required 16 bits. This later changed, as 16 bits were inadequate to describe the world’s characters.

Tangent: Not really surprising if you think about it. For example, Apple’s internationalization support allocated 24 bits per character in the early 1990s. However, engineering shortcuts are endemic.

In the meantime, Java had committed to a 16 bit character type. Now, if characters were objects, their representation would be encapsulated, and nobody would very much affected how many bits are needed. A primitive type like char, however, advertises its representation to the world. Consequently, people dealing with unicode in Java have to deal with encoding code points themselves.

I was having this conversation for the umpteenth time last week. My interlocutor asked whether it would be possible for Java to be as efficient as it was without primitive types. The answer is yes, and prompted this post.

So how would we go about getting rid of primitive types without incurring a significant performance penalty?

Java has a mandatory static type system; it is compiled into a statically typed assembly language (Java byte codes, aka JVML). It supports final classes. I do not favor any of these features, but we will take them as a given. The only changes we will propose are those necessary to eradicate primitive types.

Assume that the we have a final class Int representing 32 bit integers. The compiler can translate occurrences of this type into type int. Hence, we can generate the same code for scalars as Java does today with no penalty whatsoever.

To make Int a suitable replacement for int, we would like the syntactic convenience of using operators:

Int twice(Int i) { return i + i;}

This is easy enough. We don’t want operator overloading of course. What we want is simply the ability to define methods whose names are operators. The language can support the same set of binary operators it does today, with the same fixed precedence. No need for special syntax and rules to define the precedence of operators etc. I leave that sort of thing to people who love complexity.

It is crucial that Ints behave as values. This requires that the == operator on Ints behaves the same as equality. There should be no way to detect if we’ve allocated one copy of the number 3 or a million of them. Since we can define == as a method, we can define it in Object to work the way it does for most objects, and override it with a method in Int and other value classes to work differently. We’ll want to take care of identityHash as well of course.

At this point, we can simply say that int stands for Int. Except for locking. What would it mean to synchronize on an instance of Int? To avoid this nastiness, we’ll just say that all instances of Int are locked when they are created. Hence no user code can ever synchronize on them.

In this hypothetical dialect, literal integers such as 3 are considered instances of Int. They, and all other integer results, can be stored in collections, passed to polymorphic code that requires type Object etc. The compiler sees to it that they are usually represented as the primitive integer type of the JVM. When they are used as objects, they get boxed into real instances of Int. When an object gets cast to an Int, it gets unboxed.

This is similar to what happens today, except that it is completely transparent. Because these objects have true value semantics for identity, you can never tell if a new instance was allocated by the boxing or not; indeed, you cannot tell if boxing or unboxing occur at all.

So far I haven’t described anything really new. A detailed proposal along the lines above existed years ago. It would allow adding new user defined value types like Complex as well.

A more restricted, but somewhat similar proposal was considered as part of JSR201 - the idea being that boxing would create value objects, without actually replacing the existing primitive types. It was rejected by the expert group. As I recall, only myself and Corky Cartwright supported it. There were concerns as to what would become of the existing wrapper classes (Integer and friends); those are used by reflection etc., and are hopelessly broken because they have public constructors that allocate new instances for all the world to see.

Tangent: I don’t know who came up with the idea of an Integer class that could have multiple distinct instances of 3. I assume it was another engineering shortcut (see above) by someone really clever.

To be clear - I am not suggesting that this discussion should be reopened. This is just a mental exercise.

There is only one place where this proposal introduces a performance penalty: polymorphic code on type Object that tests for identity. Now that identity testing is method, it will be slower. Not by all that much, and only for type Object.

Why? Because we preclude overriding == in non-value classes. There are several ways to arrange this. Either by fiat, or by rearranging the class hierarchy with types Value (for value types) and Reference (for regular objects) as the only subtypes of Object, making == final in those two types. Or some other variation

What has not been seriously discussed, to my knowledge, is what to do with arrays. As indicated above, scalar uses of primitive types don’t pose much of a problem.

However, what of types like int[]? Again, we can allocate these as arrays of 32 bit integers just as we do today. No memory penalty, no speed penalty when writing in ints or reading them out.

What makes things complicated is this: If int is a subtype of Object (as it is in the above) we’d expect int[] to be a subtype of Object[], because in Java we expect covariant subtyping among arrays.

Of course that isn’t type safe, and one could certainly argue that this our chance to correct that problem. But I won’t. Instead, assume we want to preserve Java’s covariant array subtyping.

The thing is, we do not want to box all the elements of an int[] when we assign it to an Object[].

The zeroth order solution is to leave the existing subtype relations among arrays of the predefined types unchanged. It’s ugly, but we are no worse off than we are today - and have a bunch of advantages because we are free of primitive types. But we can do better.

Suppose Object[] has methods getObjectElement and setObjectElement. These (respectively) retrieve and insert elements into the array.

We can equip int[] with versions of these methods that box/unbox elements that are being retrieved or inserted. We ensure that a[i] and a[i] = e are compiled differenty based upon the static type of a. If a is Object[], we use the getObjectElement and setObjectElement. If a is of type int[], we use methods that access the integer representation directly, say, getIntElement and setIntElement.

At this point, we can even introduce meaningful relations among array types like int[] and short[] using the same technique.

In essence, Object[] provides an interface that different array types may implement differently. We just provide a sugar for accessing this interface magically based on type. On a modern implementation like Hotspot, the overhead for this would be minimal.

Of course, if you make arrays invariant, the whole issue goes away. That just makes things too easy. Besides, I’ve come to the conclusion that Java made the right call on array covariance in the first place.

All in all - Java could have been purely object oriented with no significant performance hit. But it wasn’t, isn’t and likely won’t. Sic Transit Gloria Mundi.

The Need for More Lack of Understanding

2009-04-30T19:09:00.000-07:00

People are always claiming that if only there was more understanding in the world, it would be a better place. This post will argue that less is more: we need less understanding - specifically more not understanding.

A couple of weeks ago I gave a talk at DSL Dev Con. One of the encouraging things that was evident there was the increased understanding that not understanding is important.

Tangent: While I'm advertising this talk, I might as well advertise my interview on Microsoft's channel 9 which explains the motivation for Newspeak and its relation to cloud computing.

Several programming languages support a mechanism by which a class or object can declare a general-purpose handler for method invocations it does not explicitly support.

Smalltalk was, AFIK, the first language to introduce this idea. You do it by declaring a method called doesNotUnderstand: . The method takes a single argument, that represents a reification of the call. The argument tells us the name of the method that was invoked, and the actual arguments passed. If a method m is invoked on an object that does not have a member method m (that is, m is not declared by the class of the object or any of its superclasses), then the object’s doesNotUnderstand: method is invoked. The default implementation of doesNotUnderstand:, declared in class Object, is to throw an exception. By overriding doesNotUnderstand: one can control the system’s behavior when such calls are made. Similar mechanisms exist in several other dynamic languages (e.g., missingMethod in Ruby and Groovy, _noSuchMethod_ in some dialects of Javascript).

Aficionados of these languages know that this is an extremely useful mechanism. However, users of mainstream object-oriented languages typically lack an appreciation of the power this mechanism can provide. I hope this post can be a small step in rectifying that situation.

DoesNotUnderstand: helps implement orthogonal persistence, lazy loading, futures, and remote proxies, to name a few. Recently, there’s been a surge of interest in domain-specific languages, and doesNotUnderstand: can help there as well.

We’ll use an example from my talk at DSL Dev Con. Consider how to interact with an OS shell like bash or csh from within a general purpose programming language. We’ll use Newspeak as our general purpose language (what were you expecting?), because it works best (in my unbiased opinion).

Suppose you want a listing of the files in the current directory. You could view ls as a method on a shell object, and write: shell ls. Of course, we won’t do something like the following Java code:

class Shell {
public Collection ls() {...}
... an infinity of other stuff
}

There are any number of commands that a shell can understand, depending on the current path and the executables in the directories on that path. We cannot plausibly enumerate them all as a fixed set of methods in Shell.

Instead, in we can define a class NewShell with a doesNotUnderstand: method to look up the name of the message in the shell’s path and execute it.

shell ls

If we write this code in the context of a subclass of NewShell, we can take advantage of Newspeak’s implicit receiver sends and just write

ls

Nice, but not quite good enough.

ls aFilename

doesn’t work at all. We don’t want to invoke ls immediately here - we need to gather its arguments in some way. One way to do this is to have doesNotUnderstand: return a function object, that can be fed its arguments. This is in fact what we do in our implementation. We call this object a CommandSession. To get a CommandSession to actually run the command, you call one of is value methods, with the desired arguments:

ls value: aFileName

This is less convenient for the simple case, where we need to write

ls value

to get ls to do something - but it is much more general.

What about modifiers, as in ls -l ? We can make simple cases work slightly better by defining - as a method on CommandSession :

ls -’l’

This is what the current implementation does.

The most general approach is to treat them as arguments

ls value: ‘-l’
ls value: ‘-l’ value: aFileName

An alternative might be to leave ls as it was originally, but allow

ls: aFileName

as well. In this version, doesNotUnderstand: checks to see if the message takes an argument (i.e., it ends with a colon). If so it strips the colon off the message name, creates CommandSession for the result, and calls its value: method with the argument. This handles modifiers pretty well

ls: ‘-l’

If there are multiple arguments, we can pass a tuple as the argument, and doesNotUnderstand: will unpack it as needed.

ls: {‘-l’. aFileName}

Now how about pipes?

We could introduce pipeValue methods, that produced an object that responded to the pipe operator. Or we could say that everything produced a CommandSession (and these understood “|”) and a special action is needed to get a result (sending it an evaluate or end message). This action is the analog of the newline that tells the shell to go ahead and evaluate. This could be dispensed with in a lazy setting.

Combining our second proposal above with this, we could say that value was used to derive a result. Then we can view the shell as a combinator library for CommandSessions. This does conflate two issues - the use of CommandSession to delay evaluation until a result is needed (the shell parses the input as a unit ensuring laziness) and the use of real combinators on byte streams.

We use NewShell in our IDE - for example, to manipulate subversion commands in the source control browser. It would be nice to refine it further, perhaps along the lines suggested above, but even in its current simplistic incarnation, it is quite useful.

As I noted at the beginning of this post, there a host of other cool uses for doesNotUnderstand:. I may return to those in another post.

Of course, if you are a fan of mandatory static typing, you aren’t allowed to use doesNotUnderstand: in your language. n the general case, it simply cannot be statically typed - which is an argument against mandatory typing, not against doesNotUnderstand:.

Just as switch statements, catch clauses and regular expressions all need defaults/catch-alls/wildcards, so does method dispatch. There are situations where you cannot avoid uncertainty. Reality is dynamic.

The Language Designer’s Dilemma

2009-04-18T17:17:00.000-07:00

Last week I was at lang.net 09 and DSL Dev Con. It was great fun, as always. The best talk was by Erik Meijer. Use the link to see it - but without live video of Erik in action, you can't really understand what it was like. Such is performance art.

I also gave a talk, and there were many others, but that is not the point of this post. Rather, this post was prompted by one specific, and excellent, talk - Lars Bak’s presentation on V8. Lars clearly enjoyed his visit to the lion’s den; more importantly, perhaps Microsoft will finally shake off their apparent paralysis and produce a competitive Javascript engine.

That, in turn, will make it possible to distribute serious applications targeting the web browser, with the knowledge that all major browsers have performant Javascript engines that can carry the load.

It’s all part of the evolution of the web browser into an OS. This was what Netscape foresaw back in 1995. And it is a perfect example of innovator’s dilemma.

Innovator’s dilemma applies very directly to programming languages, and Todd Proebsting already discussed this back in 2002.

To recap, the basic idea is that established players in a market support sustaining innovation but not disruptive innovation. Examples of sustaining innovation would be the difference between Windows 2000 and Windows XP, or between Java 1.0 thru Java 6.
Sustaining innovations are gradual improvements and refinements - some improvement in performance, or some small new feature etc.

Disruptive innovation tends to appear “off the radar” of the established players. It is often inferior to the established product in many ways. It tends to start in some small niche where it happens to work better than the established technology. The majors ignore it, as it clearly can’t handle the “real” problems they are focused on. Over time, the new technology grows more competent and eats its way upward, consuming the previous market leader’s lunch.

We’ve seen this happen many times before. Remember Sun workstations? PCs came in and took over that market. Sun retreated to the server business, and PC’s chase it up towards the high end of that market, until there’s nowhere left to run.

In the programming language space, take Ruby as an example. Ruby is slow, until quite recently lacked IDE support etc. It’s easy for the Javanese to dismiss it. Over time, such technology can evolve to be much faster, have better tooling etc. And so it may grow into Java’s main market.

Don’t believe me? Java in 1995 was just a language for writing applets. It’s performance was poorer than Smalltalk’s, and nowhere near that of C++. There were no IDEs. Who's laughing now?

Javascript is an even clearer case in point. It was just a scripting language for web browsers. Incredibly slow implementations, restricted to interacting with the just the browser. No debuggers, no tools, no software engineering support to speak of.

Then V8 came along and showed people that it can be much faster. Lars’ has doubled performance since the release in September, and expects to double it again within a year, and again 2-3 years after that.

Javascript security and modularity are evolving as well. By the time that’s done, I suspect it will far outstrip clunky packaging mechanisms like OSGi. This doesn’t mean you have to write everything in Javascript - I don’t believe in a monolingual world.

Tangent: Yes, I did spend ten years at Sun. A lot of it was spent arguing that Java was not the final step in the evolution of programming languages. I guess I’m just not very persuasive.

The web browser itself is one of the most disruptive technologies in computing. It is poised to become the OS. Javascript performance is an essential ingredient but there are others. SVG provides a graphics model. HTML 5 brings with it persistent storage - a file system, as it were - only better. You may recall that Vista was supposed to have a database like file system. Vista didn’t deliver, but web browsers will.

This trend seems to make the traditional OS irrelevant. Who cares what’s managing the disk drive? It’s just some commoditized component, like a power supply. We can already see how netbooks are prospering. This isn’t good news for Windows.

Of course, you might ask why Microsoft would go along with this? Is IE’s Javascript so inadequate on purpose? Maybe it is part of the master plan? Well, I don’t believe in conspiracy theories.

It does look as if Microsoft is facing a lose-lose proposition. Making IE competitive supports the movement toward a web-browser-as-OS world. Conversely, if they let IE languish, as they have, they can expect its market share to continue to drop.

However, you cannot stop the trend toward the Web OS by making your tools inferior. You can only compete by innovating, not by standing still.

I wouldn’t count Redmond out just yet. They have huge assets - a terrific research lab, armies of smart people in product land as well, market dominance, and vast amounts of money. They also have huge liabilities of course - and those add up to innovator’s dilemma.

In any case, for language implementors, it’s clear that one needs to be able to compile to the internet platform and Javascript is its assembly language. Web programming will evolve into general purpose programming, using the persistent storage provided by the browser to function off line as well as online.

As many readers of this blog will recognize, this sets the stage for the brave new world of objects as software services. I hope to bring Newspeak to the point where it is an ideal language for this coming world. It’s a bit difficult with the very limited resources at our disposal, but we are making progress.

The entire progression from conventional computing to the world of the Web OS is taking longer than one expects, but is happening. The time will come when we hit the tipping point, and things will change very rapidly.

Subsuming Packages and other Stories

2009-03-29T12:44:00.000-07:00

Barbara Liskov recently won the Turing award. It’s great to see the importance of programming language work recognized once again. Even if you aren’t into the academic literature, you have probably heard her name, for example, when people mention the Liskov substitution principle (LSP). The LSP states that if a property P is provable for an object of type S, and T is a subtype of S, then P is provable for an object of type T.

This is behavioral subtyping - instances of subtypes are semantically substitutable where supertypes are expected. This is a very strong requirement, but not something a practical programming language can enforce.

Closely related (and enforceable) is the subsumption rule of type systems for OO languages. This rule states that if an expression e has type T, and T is a subtype of S, then e has type S as well. This post is about the importance of subsumption in programming language design.

The subsumption rule is a cornerstone of formal type systems for OO. More importantly, it captures a deep intuition that programmers have about subtyping. After all, what could be more natural: if e: T and T <: S, e: S. I hope readers agree with me that this property is intuitive, perhaps even so obvious that you wonder why anyone would bother belaboring the point. *** So it is most unfortunate that mainstream programming languages violate subsumption left and right. Below, we’ll look at some examples, and draw some conclusions about language design. Case 1: Hiding fields. In Java (and C++) you can define a field in a subclass with type X, even though the superclass has a field of the same name, with unrelated type Y. The subclass’ field hides the superclass field.

class S { final int f = 42;}

class T extends S { final String f = “!”;}

new T().f; // “!”
((S) new T()).f; // 42

In case it isn’t obvious, any object of type S has the property that it’s f field has type int. An instance of T should also have the same property, but doesn’t. To get at the field defined by S, we have to coerce the T value into an S.

Tangent: It would be much better to ensure that fields are always private, or better yet, avoid field references altogether, as in Self or Newspeak.

A typical programmer in the Java/C++ tradition may ask what’s the harm in the rules as they are.

The harm is precisely in having rules that contradict strong and valid intuition. The contradiction will bite you in the end, because you will end up thinking some program property holds based on your intuition, while the rules of the language contradict that intuition. Years of exposure to these misfeatures may have inured the mind to their toxicity, but they are toxic all the same.

However, there is much more harm, as we’ll see as this post progresses.

Case 2: Hiding static methods. The same sort of situation occurs with static methods. Static methods aren’t really methods at all, as no run time object is involved in determining the meaning of their invocations. No overriding can occur between static methods. The meaning of a static method is statically bound: static method is a misnomer for subroutine (as in FORTRAN subroutine circa 1955). And so Java allows static methods to hide each other much like fields. You can easily recreate the above example with static methods.

I’ve written elsewhere about the problems of all things static; add this to the list. Maybe you’re beginning to get the sense that violating subsumption correlates with iffy language constructs.

Case 3: Package privacy. This brings us back to Barbara Liskov. Her work on CLU in the mid 70s brought David Parnas’ notion of information hiding into programming languages, with support for abstract datatypes (ADTs). Packages are one of the mechanisms that Java uses to support ADTs. Packages have had all kinds of problems; lack of subsumption is at the root of many of them.

For example, recall that in Java, protected access implies package access. Package access is always relative the the current package. So when a protected member is inherited by a subclass in another package, it eliminates the access from the superclass package (while granting access to its own package):

package P1;

public class A {protected int foo(){return 91;}}

class C {static int i = (new P2.B()).foo();}

**
package P2;

public class B extends P1.A {}

This code is legal. If we then change B such that

public class B extends P1.A {protected int foo() {return 42;}}

The call in C is no longer allowed! We have not added or removed members in the subclass, or changed their accessibility (or have we? Did we have a choice?) and yet we’ve broken client code.

I don’t want to go into the details of an even more bizarre example (due, as far as I can recall, to David Chase) - but others have. Suffice to say that there was a huge bug tail around such examples; it took years to resolve them. Compiler engineers did not correctly diagnose the problems, because their intuition led them to try and preserve subsumption, to no avail. I have several patents to my name that deal with the mechanisms of implementing the desired behavior.

And why should you care? Because these issues led to subtle incompatibilities between compilers and VMs, across vendors and releases; these led to subtle program bugs, to jokes about write once debug everywhere etc.

Packages are one way in which Java supports ADTs. It turns out that you cannot have ADTs, inheritance and subsumption in one language. You must make a choice - and I argue that subsumption must always be preserved.

Case 4: Class-based Encapsulation.
Another mechanism that supports ADTs in all the mainstream OO languages is class based encapsulation. This the idea that privacy is per class type, not per object. This makes it possible to write code like

class C {
private int f(){return 42;}
public int foo(C c){return c.f();} // I can get at c’s f(), because we’re both C’s
}

It also makes it possible to violate subsumption:

public class A {
{
((A) new B()).f(); // 42
new B().f(); // “!”
}
private int f(){return 42;} // package private
}

public class B extends A {
public String f(){return “!”;}
}

An alternative to class-based encapsulation is object-based encapsulation. Privacy is per object. You can enforce it via context free syntax. For example, you can arrange that only method invocations on self (aka this) attempt to lookup private methods. You don’t need a typechecker (aka verifier) to prevent malicious parties accessing private methods or fields. Consequently, you don’t have to rely on a complex byte code verifier to prevent such access as one does in Java and .Net.

This fits perfectly with the object-capability security model. It is essentially what we do in Newspeak; but the ideas are universal.

Oh, and object-based encapsulation works with both subsumption and inheritance.

Case 5: Privileged access within “nests” of classes. Giving enclosing classes privileged access to their nested classes, and giving sibling classes privileged access to each other, is another violation of subsumption (but giving a nested class free access to its surrounding scope, including private elements of its enclosing class, is fine).

Another way to look at all this is that object-based encapsulation falls out naturally from the use of interfaces. Consider what would happen if the type C above was, by language definition, the public interface of C (as it is in Strongtalk, for example). Subsumption would fall out automatically.

Subsumption is a very good litmus test for language constructs; if a construct violates subsumption, it will cause grief. Ditch it.

Strict adherence to subsumption reduces cognitive dissonance for programmers, compiler writers, VM implementors and language designers. It helps avoid bugs in user code, compilers and VMs, enhancing reliability and portability. It makes it easier to build secure systems.

So if you design a type system for an OO language, preserve subsumption at all costs. Do not try and combine ADTs with inheritance (because then you lose subsumption).

Now if we can’t have ADTs and inheritance, we have to chose between them. I believe the benefits of inheritance far outweigh the costs. Those who feel differently are unlikely to do better than Luca Cardelli‘s sublimely beautiful Quest. On the other hand, if one choses inheritance, one should go with object-based encapsulation.

Put another way, if you take the adage program to an interface, not an implementation seriously, it will prevent a host of problems. This is what we are doing with Newspeak.

At a meta-level, the lesson is: pay attention to programming language theory; occasionally, you can learn from it.

Update: Yardena pointed out this discussion of Java packages. It goes through the problems in detail. I've added a link to it in the main post as well.

Newspeak Prototype Escapes into the Wild

2009-02-27T23:30:00.000-08:00

The Newspeak prototype is now available at http://newspeaklanguage.org/downloads/ . We had planned to release it in early January, but decided to complete a few more things - like better source control support, a fully functional Hopscotch based debugger and a new GUI for unit testing (shown below).

Newspeak is a long way from being finished - we are less than half way to realizing the vision of a robust, high performance, secure, network aware, high productivity platform. We can only get there if people care enough to use it and contribute to it. I hope you'll check it out.

Apologia

2009-01-13T10:43:00.000-08:00

Here’s a quick update on the status of the Newspeak prototype release. If anyone is keeping score - I had said we’d put something out in the first week of January 2009. So we’re behind schedule. I apologize, but what are you going to do - cut my funding?

Nevertheless, we will be putting a prototype out soon. I’m holding off so that a few small things can be added.

In the meantime, I wanted to take the opportunity to say a bit about the prototype. Obviously, due to our reduced circumstances, it is a lot less ambitious than I had once hoped.

We do have a native GUI binding on Windows; I had hoped to have native GUI bindings for Mac and Linux, but that will depend on future open source contributions. You can of course run the system on those platforms, but you’ll have to live with the Morphic binding for now.

The language itself remains incomplete as well - but the key features are there. I expect to rev the syntax and add the missing features (like object literals) over time. One of the reasons these features have been delayed is that I want to add them in the context of a completely new compiler. Such a compiler will also make it easier to do ports - e.g., Newspeak on V8.

One of the biggest deficits is the lack of libraries written in Newspeak. We continue to rely heavily on the existing Squeak libraries. We have made some progress on this front, largely through the efforts of some volunteers who got early access to the system. I want to take this opportunity to thank Yardena Meymann, David Pennell and Stephen Pair for their work on the library port. They are all busy professionals who were willing to take the time to do something concrete to help move Newspeak forward. I hope that we’ll see a lot more of that after the release!

What we’ve been doing is porting some of the core libraries from Strongtalk to Newspeak. These libraries have several important advantages: they are small, yet complete enough to run a real system; they are blue book compatible (give or take), so we have a good chance of replacing our uses of Squeak code with them, without excessive disruption; they are quite cleanly written; they have type annotations; and, it so happens, they have a liberal license.

On the other hand, these libraries were not purpose built for Newspeak; no thought has been given to security, the designs do not leverage features like mixins as much as one might etc.. Still, they provide us the with the most realistic path to getting a small stand alone system in the foreseeable future.

This library code will not be anywhere near complete and integrated when we put out the prototype. But it whatever we have will be available, and we’ll move on from there.
There are any number of other things lacking, and no doubt many will be eager to point them out. However, that scarcely matters. What matters is the potential this system has. It’s being put out, so those with the imagination, sophistication and, above all, taste to appreciate it can start using it and contributing to it - eventually realizing that potential.

So for that small elite that has shown interest and appreciation for Newspeak so far - thanks, and hang in there. It will be available, Real Soon Now :-)

Living without Global Namespaces

2008-12-09T19:07:00.000-08:00

Newspeak differs from most programming languages in that it doesn’t provide a global namespace. And it differs from most imperative programming languages, because it has no static state.

I’ve spoken and written a fair amount about why the absence of static state is a good thing . What I haven’t discussed much is how you actually organize programs in this way. There have been a lot of questions along these lines. This post is an attempt to answer some of them.

Caveat: Some of the details here differ in the current prototype. Some of the features are still incomplete. What's described here is how things are supposed to work. We're not far from that.

First, let’s tackle the question of static state. It should be obvious: anything that you expected to put in a static variable goes in an instance variable of a module. What about singleton classes? How do I ensure that there’s only one instance? The easiest way is to initialize a read only slot of a module with an object literal. What happens if there are multiple instances of the module declaration? Well, each module has its own “singleton”. That’s exactly what happens with singleton classes in Java when they are defined by multiple class loaders.

What if your class defines some service process and you need to be really sure there’s only one in the entire system? First, in many cases you may find that the system in question is your subsystem, defined by your modules, and the answer above applies.

Now if you really mean “the entire system”, then you need to control that via some state in the platform object - through its links to the world’s state (e.g., the file system) or by having some registry in the platform object. Of course, not all code may see the true platform object, so it isn’t really global either; but it won’t matter.

Having no static state doesn’t preclude having a global namespace, as long as that namespace doesn’t contain any stateful objects. The original plan for Newspeak was to have a global namespace of pure values, structured as an inversion of the internet domain namespace. This would have been much like the convention for naming Java packages (except that the scopes of namespaces would nest properly, as you’d expect). It was the only idea from Java that I saw a use for in Newspeak. It’s a good idea, but it turns out to be unnecessary.

So, given no global namespace, what can I write at the top level? Remember, I can’t refer to any names, even things like Object or String that presumably exist in every implementation. This seems awkward. Not to worry - we won’t be writing SKI combinators or even plain old lambdas.

We might be able to write some literal expressions like 1 + 2, but that isn’t all that interesting, and isn’t even necessary. What we need to write are things that produce new kinds of objects, like classes.

Happily, we can write a a top level class declaration, with one caveat: A top level class declaration cannot declare a superclass explicitly since there is no way to name it, because there is no enclosing namespace. In that case, by special dispensation, the superclass will be the class Object provided by the underlying platform. Similar rules apply to object literals (which can be thought of as “anonymous classes done right”).

Ok, so now we can write a class, which can have other classes nested inside it, so it can be an entire library; and since there is no surrounding namespace, it is necessarily independent of any specifics of the environment - it is a module declaration. An example of such a module declaration would be the Newspeak AST

class NewspeakAST usingLib: platform { ....

... lots of nested AST classes ....

}

A similar class would be CombinatorialParsing library I’ve written about before.

There’s just one little problem. How do I use such a class? I gave it a name, but no one can refer to it, since there isn’t any surrounding namespace for the name to be bound!

Suppose I want to create a parser that builds an AST, using the two classes mentioned above. I need a grammar, which should be defined by a subclass of the parser library, and the parser class itself would in turn be a subclass of the grammar. Call these classes Grammar and Parser.
Since I can’t name the superclass of Grammar, I’ll just define it as a mixin, and worry about how to pair it with the superclass later.

class Grammar = { ....}

Likewise with Parser.

class Parser usingLib: platform astLib: ast = { ...}

That way I can define all the actual code required. The problem remaining is how to link all these pieces together.

If I actually had a namespace where I could refer to the pieces, I could write linking code like:

“confused”

main: platform {

MyGrammar = Grammar |> CombinatorialParsing usingLib: platform.

MyParser = Parser usingLib: platform astLib: NewspeakAST |> MyGrammar.

return:: MyParser parse: ‘a string in my language, perhaps?’

}

So how would I go about creating such a namespace? This is ultimately a question of tooling. Suppose my IDE lets me load class objects dynamically - say by reading in serialized class objects saved in files on disk. When it loads such a class object, it can reflect on it to find out its name, and store the class object in a slot of the same name in some new object it creates.

If I choose to load the classes, Grammar, Parser, CombinatorialParsing and NewspeakAST, I can create an object that is precisely the namespace I needed. I can then modify its class by adding the main: method listed above. This object is now an application, whose behavior is defined by its main: method. I can serialize this application object to disk.

Running my program then amounts to deserializing the object, and invoking its main: method with an object representing the current platform.

I’ve glossed over some crucial details here. We don’t really want to serialize the entire object, as it points to objects in our IDE, like Object, Class and a few others. These are standard, and we can cut off the object graph with symbolic links at these standard points, and have the deserializer hook up their equivalents on the destination.

Is using the IDE this way cheating? After all, it ultimately resorts to using the namespace of the underlying file system (or the network, or a global IDE namespace, depending where the IDE fetches class objects from). I think not. The truth is that this is what any language in the world does at some level. Whether we rely on a compiler that uses a CLASSPATH environment variable to define a set of local directories, or on the IDE, or on makefiles in a given directory to link separately compiled files, it is ultimately the same: some tool uses the operating system to find pieces of program.

We don’t have to use the IDE; we could use a preprocessor that understood directives that referred to classes in the file system instead. It could even use something as inane as CLASSPATH. Of course, I’m not really recommending that.

My key point is that the language needs nothing more than objects to serve as its namespaces.

Unidentified Foreign Objects (UFOs)

2008-12-05T15:14:00.000-08:00

I recently found out that Newspeak’s basic foreign function interface (FFI), called Aliens, is being made available in Squeak (though that will require new VMs with the required primitives). Thanks to John McIntosh for doing this.

I should also thank Eliot Miranda for most of the original work on aliens, and Vassili Bykov, Peter Ahe and Bill Maddox for the rest. Also thanks to Lars Bak, whose work on the Strongtalk FFI inspired the VM level view of aliens; and to Dave Ungar, who was the first to understand that objects were all you needed on the language side of an FFI. Lastly, this post benefited immensely from conversations with Vassili.

So I figured I’d write a little bit about Aliens from a high level perspective. As usual, the ideas apply to programming languages in general.

In Smalltalk, there isn’t a standard FFI. Various dialects provide different solutions, with varying degrees of functionality, performance and ease of use. To be honest, they are usually a poor fit with the surrounding language and fairly awkward to use. This inhibits Smalltalk’s interoperability with the rest of the world. I’d argue that the absence of a good, standard FFI has cost the Smalltalk community dearly.

In Java, by contrast, native methods and JNI provide a standardized FFI. This mechanism is far from perfect, but at least there is a more or less standard solution.

What these and other systems have in common is support for a special construct (such as the native modifier for methods, or declarations like extern C, or the truly ugly ad hoc FFI syntax extensions used in various Smalltalks) for foreign functions.

Newspeak’s FFI was strongly influenced by the Strongtalk FFI; but unlike Strongtalk, Newspeak doesn’t have a special syntax for foreign calls. As Self showed many years ago, one doesn’t really need a special syntax for the FFI. The foreign functions, APIs, DLLs etc. can all be represented as objects. They just happen to be foreign objects.

The idea of a foreign object, which we call an alien, is at the foundation of the Newspeak FFI.

For starters, any decent language should be able to represent functions as values; and in an object-oriented language, these values are objects, accessed via a standard interface. Foreign functions are just a different implementation of that interface.

Another natural way to model a foreign function is as a method defined on a foreign object. For example, one can view an entire DLL as an object with a set of methods corresponding to the functions defined by the DLL. Better yet, we could represent an entire API as an object, independently of what DLLs actually defined it.

Aliens can be defined for different foreign languages; for example, while Alien is used to interface with C, we also have a class called ObjectiveCAlien that can be used to interface with ObjectiveC, which is the native language on MacOS X. C Aliens and ObjectiveC Aliens do not interfere with each other, and when/if we need to add Java Aliens or CLR Aliens we can do that as well.

The alien approach is also a good fit with security: one need not be concerned that code may bypass high level language safety guarantees by calling out to C; untrusted code can be prevented from doing that, simply by not providing any Alien library objects to it.

Newspeak’s C Alien implementation is fast, but also dangerous. An alien is basically a blob of memory. The user of an Alien is responsible for interpreting and accessing that data correctly. There is no checking being done for you.

Tangent: It's worth noting that the basic Alien layer may evolve further; for example, we aren't thrilled with the practice of subclassing Alien. It's not clear if the Alien class really needs to change, or just the pattern of using it.

On top of this foundation, safer and/or more convenient abstractions can be built. We have built objects that support not just methods corresponding to the functions of an API, but also methods that provide factories for the various datatypes used in the function’s signatures, including those defined by macros. These objects wrap the basic alien API, and help with error prone book keeping - converting between Newspeak types (e.g., Strings) and foreign types, freeing aliens after use etc.

At the moment, both the declarations of low level aliens and higher level APIs are constructed manually, which is tedious and error prone. We’ve been planning on a higher level tool called CSlick, which would allow you to specify a set of .h files and the requisite DLLs, and obtain an object that supports the desired functions automatically.

As a first approximation, you could think of CSlick as a function:

CSlick: List -> List -> ForeignAPI

The signature above is deliberately curried, because you may actually want to be able to specify just the header files, and later bind different DLLs to provide the actual functionality, just as a .h file can be associated with different .c files.

When this will happen is anyone’s guess right now; but Vassili has done this before (in the context of Lisp) and I’m sure he can do it again.

The resulting foreign API should incorporate the low level alien API, and, as much as possible, a higher level API as well.

The CSlick implementation will need to know how to parse C header files, and how to reflectively manufacture the low level code that actually invokes the C functions. Fortunately we have a strong parsing infrastructure, so that isn’t as daunting as it sounds.

When I’ve told people about CSlick, they often mention SWIG. However, I believe CSlick can be made substantially easier to use than SWIG. SWIG has to cope with multiple languages, each with a pre-existing story on how to do foreign calls. In contrast, we can integrate CSlick more tightly with the language. Ultimately, that should translate to a simpler model for the user.

The key take away is that objects are all you really need to interact with foreign programming languages. They are better than built in language constructs in terms of ease of use, security, and multiple language support. As usual, less is more.

We have Good news, and we have Bad news

2008-11-24T17:11:00.000-08:00

First, the good news. We will be releasing a Newspeak prototype in the first week of January 2009. This prototype is anything but finished, but it will have to do, because of the bad news (insert dramatic pause here).

What's the bad news? Well, funding for the Newspeak team is being discontinued in early January, another victim of the times.

We are currently seeking a new home for Newspeak, but it is by no means certain that such a thing can be found in the current economic climate. Perhaps I should take the Newspeak private jet to Washington and demand a bail-out - but alas, the jet is indisposed (when I call it all I get is message not understood)

We expect to keep pushing the Newspeak platform forward in any event; that said, there's a big difference between having several developers fully dedicated to a project, and the limited efforts people can make in their spare time. So the goal is to find support for the project soon - otherwise we'll all go get other jobs and progress on Newspeak will slow down accordingly.

Of course, once we put out the prototype, others can help fill in the blanks. I hope that will happen, irrespective of whether Newspeak gets further funding. I also plan to write up our work on Newspeak for academic publication.

Hopefully, this is only a temporary setback, and in it lies new opportunity: per aspera ad astra.

Dynamic IDEs for Dynamic Languages!

2008-11-01T20:29:00.000-07:00

Dynamic languages are all the rage these days, and rightly so. Historically, most of the currently popular dynamic languages have had negligible IDE support (since they are scripting languages). More recently, we see a flurry of activity around IDE support for these languages. However, the mainstream IDEs are designed for, and implemented in, static languages. Consequently, even when dealing with a dynamic language, the dynamism stops when it comes to the IDE itself.

What do I mean by this? In an IDE written in a dynamic language (such as Smalltalk or Self or Lisp), the IDE code itself can be modified on the fly. This is a double edged sword, as I’ll explain shortly. I’ll start with the good edge.

Suppose you want to modify the IDE for some reason. It lacks a feature you need, or something is buggy. If it’s a proprietary system, you can file a bug with the vendor, and hope that they pay attention, so that in the next release, in a year or two, you’ll get the fix.

If the system is open source, you can just go ahead and implement the fix/feature. Now if that system is written in a mainstream, conventional language, you just need to recompile the compilation unit with the fix, and rebuild your system. Of course, in order to develop the fix, you had to load a project with the source for your IDE and probably go through several edit-compile-debug cycles. When it all worked, you replace your existing installation with your new build. I have the strange feeling that all this setting up the IDE as a project within itself, rebuilding and reinstalling could take quite a lot of time and effort.

In an IDE like Smalltalk (or Newspeak, or Self), the IDE source is always available from within itself. In such a system, if you change its source code, the change takes effect immediately. For example, the Newspeak class browser supports a pop up menu for methods, that lets you find references to the method and to the messages sent within it. In the screen shot below, the speech bubble on the right denotes this menu

However, the initial version did not support the same functionality for slots.
How do we fix this? Well, for starters, we need to find where the relevant source code is. How do you do this? The old fashioned way is to go on a trek through the source code trying to figure it out. What subdirectory should we start with? Which file should we open first? What should we grep for?

Fortunately, Newspeak makes it easy, as most IDE components have an Inspect Presenter menu item, that will open an object inspector on the actual presenter in question; a presenter on a presenter.

For example, if we want to find out how the references menu for methods works, we can look at a method like the one above. On the far right is a drop down menu:

This opens an object presenter, like this:

Toward the top, is a line marked class; it contains a hyperlink to the class of the object being inspected - the class ExpandableMethodPresenter. Now we know where the code that presents methods resides! If we click on the link, the Hopscotch browser will show us the class.

Having found the code that manages the presentation of methods, and the implementation of the references menu, we next want to find the code that presents slots, so we can modify it. We do the same thing again - invoke the Inspect Presenter menu item, but this time on a slot.

Once we’ve found the code and made the change, we can test it right away. Just hit refresh in the browser, and you’ll see the new reference bubble next to slots.

All of this is part of what Dan Ingalls, and Smalltalkers in general, mean when they say the system is alive. It’s the key property you seek in every system - its ability to respond to changes and mutate while running, which gives you the kind of interactivity you get in the real world with real objects. Live code in the IDE is the opposite of dead code - stuff written in files, which needs to be explicitly loaded into a runtime to do anything.

This all is very cool, but it also has a downside. Suppose you have a bug in your code, causing it to crash. You may be able to fix it in the debugger - but maybe the root of the problem is in another class. You need to browse it - but now, every time you try and browse a class, it crashes. You’ve shot yourself in the foot.

This is where you almost wish you were looking at dead code, by browsing files in an editor (or a conventional IDE). Fortunately, we know how to deal with this problem as well.

In this case, we want to manipulate the modified IDE from another, unmodified one, as a dynamic program. That way we still enjoy immediate feedback for our changes, while jkeeping our feet safe. Once it works, we want to be able to easily suck in the changes into the unmodifed version - without restarting, rebuilding, or going back to the big bang.

We haven’t implemented this yet - but much of it’s been done before, in the mid-90s, by Allen Wirfs-Brock in the FireWall project at ParcPlace. You do it using mirror based reflection.

One of the many things mirrors facilitate, is managing reflection in a distributed setting. Java’s JDI is an example of a mirror API was designed to do just that - though it has serious limitations because it has to work on a variety of JVMs. If you design the mirror API correctly, and build your IDE on it, the IDE can work almost identically on programs within the same process, in another process, or across the internet.

This ability to manage reflective changes to the IDE via a separate process is a luxury, which probably explains why it generally isn’t implemented, The reality is that shooting yourself in the foot is infrequent, and you can always recover (if only by saving your changes to a file before testing them). The benefits of liveness far outweigh the risks.

Nevertheless, in time, I expect to address this in the Newspeak IDE. In the meantime, it’s alive, even if support for death is lacking. Of course, the broader lesson is that IDEs especially, should be implemented using dynamic languages.

The above echoes my previous post from June, but I hope that the concrete examples are helpful. The liveness makes it easy to implement features like Inspect Presenter, which let you identify where to change the IDE, but even more critically, liveness allows you actually make the change and get instant feedback.

In closing, I want to emphasize that this is not an unprincipled approach. All of the above is possible because the IDE can reflect on itself. Self reference is at the heart of computing. It’s all about recursion. I find it strange that many theoretically oriented computer scientists, who can wax poetic about the Y combinator, eschew languages and systems that apply the same principles of self-application to themselves. I’m sure this is will change though; the good ideas win in the end.

Skinning Newspeak?

2008-09-20T14:25:00.000-07:00

Whenever it comes to discussing language syntax, Parkinson’s law of triviality comes to mind.

Incidentally, the book is back in print! If you haven’t read it, check out this priceless classic.

Newspeak’s syntax currently resembles Smalltalk and Self. For the most part, this a fine thing, but I recognize that it can be a barrier to adoption. So, as we get closer to releasing Newspeak we may have to consider, with heavy heart, changes that could ease the learning curve.

One approach is the idea of syntactic skins. You keep the same abstract language underneath, but adjust its concrete syntax. In theory, you can have a skin that looks Smalltalkish, and one that looks Javanese, and another sort of like Visual Basic etc.

The whole idea of skins is closely related to Charles Simonyi’s notion of intentional programming. Cutting through the vapor, one of the few concrete things one can extract is the idea (not new or original with Simonyi) of an IDE that can present programs in a rich variety of skins, some of which are graphical. That, and support for defining DSLs for the domain experts to program in. This is all a fine thing, as long as you understand that’s all it is. This is still a pretty tall order.
In any case, Magnus Christerson is doing a superb job of making that vision a reality.

It is of course crucial that any program can be automatically displayed in any skin in the IDE. And designing skins requires thought, and is prone to abuse, which makes me hesitate.

Naming conventions that may make sense in one syntax may not really work in another, for example. Take maps (dictionaries in Smalltalk). In Smalltalk, the number of arguments to a method is encoded in the method name. So class Dictionary has a method called at:put:

aMap at: 3 put: 9.

In a javanese language, you’d tend to use a different name, say, put

aMap.put(3, 9);

However, with skins, you need to either use the very same name

aMap.at:put:(3, 9);

which looks weird and may even conflict with other parts of the syntax, or have some automated transformation

aMap.atPut(3, 9);

All of which looks odd and may have issues (after all at:Put: would be a distinct, legal Newspeak method name which would also map to atPut). And what happens if you start writing your code in the javanese syntax? How do I map put into a 2 argument Newspeak method name? p:ut:? pu:t:? Maybe in this case, it takes a single tuple as its argument:

aMap put: {3. 9}.

There may be a creative way out; Mads Torgersen once suggested a syntax like

aMap.at(3) put(9)

Or maybe we map all names into ratHole.

The standard procedure call syntax also has more substantial difficulties. Without a typechecker, it’s hard to get the number of arguments right. The Smalltalk keyword syntax, while unfamiliar to many, has a huge advantage in a dynamically typed setting - no arity errors (if you’ve written any javascript, you probably know what I mean).

In addition, the Smalltalk keyword notation is really nice for defining embedded DSLs, as Vassili notes in a recent post. This is a point that I want to expand upon at some future time.

So I’m pretty sure that regardless of whether we use skins or not, we’ll retain the keyword message send syntax across all skins. It’s just a good idea for this sort of language.

There are syntactic elements that are easy to tweak so that they are more familiar to a wider audience. In some cases, there are standard syntactic conventions that work well, and we can just adopt them. For example, using curly braces as delimiters for class and method bodies (and also closures), or using return: instead of ^. If these were the only issues, one might not really consider skins, since the differences are minor. The current draft spec mentions some of these.

Skins may be most valuable for issues in between the two extremes cited above. One of the most obvious is operator precedence. People have been taught a set of precedences in elementary school, and most have never recovered. Programmers have also learned C or something similar, they have even more expectations in this regard.

Newspeak, like Smalltalk, gives all binary operators equal precedence, evaluating them in order from left to right.

5 + 4 * 3 evaluates to 27 in Smalltalk, not to 17.

Now I have never, ever had a bug due to this, but many people get all worked up over this issue. Why not just give in, and follow standard precedence rules? Well, there is the question of whose rules - C, Java, Perl? What about operators those languages don’t have (ok, so Perl probably has all operators in the known universe and some to spare)?

Another issue is that Newspeak is designed to let you embed domain specific languages as libraries. Then the standard choices don’t always make sense. Allow people to set precedence explicitly you say? This is problematic. Newspeak aims to stay simple. This is a matter of taste and judgement. If you like an endless supply of bells and whistles, look elsewhere.

Skins might give us an out. Some skins would dictate the precedence of popular operators (leaving the rest left-to-right, as in Scala for example). This means your DSL may look odd in another skin, but maybe that’s tolerable.

Once you have skins, you can also address issues that otherwise aren’t worth dealing with - like dots. If you really feel the need to write aList.get instead of aList get, a suitable skin could be made available.

It looks like language skins can be used to bridge over minor syntactic differences, but not much more. On the other hand, if you don’t have skins, you have a better chance of establishing a shared lingua franca amongst a programming community.

Overall, my sense is that such skins are more trouble than they’re worth.

Foreign functions, VM primitives and Mirrors

2008-08-31T12:15:00.000-07:00

An issue that crops up in systems based on virtual machine is: what are the primitives provided by the VM and how are they represented?

One answer would be that those are simply the instructions constituting the virtual machine language (often referred to as byte codes). However, one typically finds that there are some operations that do not fit this mold. An example would be the defineClass() method, whose job is to take a class definition in JVML (Java Virtual Machine Language) and install it into the running JVM. Another would be the getClass() method that every Java object supports.

These operations cannot be expressed directly by the high level programming languages running on the VM, and no machine instruction is provided for them either. Instead, the VM provides a procedural interface. So while the Java platform exposes getClass(), defineClass() and the like, behind the scenes these Java methods invoke a VM primitive to do their job.

Why aren’t primitives supported by their own, dedicated virtual machine language instructions? One reason is there are typically too many of them, and giving each an instruction might disrupt the instruction set architecture (because you might need too many bits for opcodes, for example). It’s also useful to have an open ended set of primitives, rather than hardwiring them in the instruction set.

You won’t find much discussion of VM primitives in the Java world. Java provides no distinct mechanism for calling VM primitives. Instead, primitives are treated as native methods (aka foreign functions) and called using that mechanism. Indeed, in Java there is no distinction between a foreign function and a VM primitive: a VM primitive is foreign function implemented by the VM.

On its face, this seems reasonable. The JVM is typically implemented in a foreign language (usually C or C++) and it can expose any desired primitives as C functions that can then be accessed as native methods. It is very tempting to use one common mechanism for both purposes.

One of the goals of this post is to explain why this is wrong, and why foreign functions and VM primitives differ and should be treated differently.

Curiously, while Smalltalk defines no standardized FFI (Foreign Function Interface), the original specification defines a standard set of VM primitives. Part of the reason is historical: Smalltalk was in a sense the native language on the systems where it originated. Hence there was no need for an FFI (just as no one ever talks about an FFI in C), and hence primitives could not be defined in terms of an FFI and had to be thought of distinctly.

However, the distinction is useful regardless. Calling a foreign function requires marshaling of data crossing the interface. This raises issues of different data formats, calling conventions, garbage collection etc. Calling a VM primitive is much simpler: the VM knows all there is to know about the management of data passed between it and the higher level language.

The set of primitives is moreover small and under the control of the VM implementor. The set of foreign functions is unbounded and needs to be extended routinely by application programmers. So the two have different usability requirements.

Finally, the primitives may not be written in a foreign language at all, but in the same language in a separate layer.

So, I’d argue that in general one needs both an FFI and a notion of VM primitives (as in, to take a random example, Strongtalk). Moreover, I would base an FFI on VM primitives rather than the other way around. That is, a foreign call is implemented by a particular primitive (call-foreign-function).

Consider that native methods in Java are implemented with VM support; the JVM’s method representation marks native methods specially, and the method invocation instructions handle native calls accordingly.

The Smalltalk blue book’s handling of primitives is similar; primitive methods are marked specially and handled as needed by the method invocation (send) instructions.

It might be good to have one instruction, invokeprimitive, dedicated to calling primitives. Each primitive would have an identifying code, and one assumes that the set of primitives would never exceed some predetermined size (8 bits?). That would keep the control of the VM entirely within the instruction set.

It is good to have a standardized set of VM primitives, as Smalltalk-80 did. It makes the interface between the VM and built in libraries cleaner, so these libraries can be portable. We discussed doing this for the JVM about nine or ten years ago, but it never went anywhere.

If primitives aren’t just FFI calls, how does one invoke them at the language level? Smalltalk has a special syntax for them, but I believe this is a mistake. In Newspeak, we view a primitive call as a message send to the VM. So it is natural to reify the VM via a VM mirror that supports messages corresponding to all the primitives.

A nice thing abut using a mirror in this way, is that access to primitives is now controlled by a capability (the VM mirror), so the standard object-capability architecture handles access to primitives just like anything else.

To get this to really work reliably, the low level mirror system must prohibit installation of primitive methods by compilers etc.

Another desirable propery of this scheme is that you can emulate the primitives in a regular object for purposes of testing, profiling or whatever. It's all a natural outgrowth of using objects and message passing throughout.

Invisible Video

2008-07-27T11:30:00.000-07:00

A quick update; several people have told me that the Smalltalk Solutions video of the Hopscotch demo is unhelpful, since you can't see the screen. I should have watched it before linking to it; I apologize. Since I was in the room during the presentation, I didn't think to watch it again. My bad. I've taken the link down. We'll produce a viewable demo for download and post it in th enear future. Again, apologies to to anyone who spent time downloading/watching the unwatchable.

Debugging Visual Metaphors

2008-07-26T12:39:00.000-07:00

My previous post commented on the unsatisfactory state of mainstream IDEs. Continuing with this theme, I want to focus on one of my long term pet peeves - debugger UIs.

Donald Norman, in his book The Design of Everyday Things, makes the point that truly good designs are easy to use, because they make it intuitive how they should be used - in his words, they afford a usage pattern.

How do you describe the state of a running program on a whiteboard? You draw the stack. So it seems to me that a stack is the natural visual metaphor for a debugger. Here is a screen shot of our new Hopscotch-based debugger, which will soon replace the Squeak debugger in the Newspeak IDE.

You can see that the debugger looks like a stack trace. Every entry in the stack trace can be expanded into a presenter that shows that stack frame - including the source code for the method in question, and a view of the state of the frame - the receiver, the variables in the activation, the top of the evaluation stack for expressions (i.e., the last value computed).

Of course, this isn’t my idea. It’s another one of those great ideas from Self, as evidenced in this screenshot:

we already stole the idea from Self once before, in Strongtalk, as shown here.

One of the nice properties of the stack oriented view is that you can view multiple stack frames at once, so you can see and reason about a series of calls, much as you would at your whiteboard.

In contrast, most IDEs (even Smalltalk IDEs) show a multi-pane view, with one pane showing the source for the current method (in its file, naturally), one pane showing the state of the current frame, and one showing the stack trace.

You can’t easily see the state of the caller of the current method, or its code, while simultaneously looking at the current method (or another activation in the call chain). And if you modify the current method’s code (assuming you can do that at all), you’re likely locked into a mode, and can’t see the other frames unless you save or cancel your changes.

Hopscotch GUIs are inherently non-modal - so you can modify any one of the methods you’re viewing, and then link to another page to view, say, the complete class declaration, all without opening another window and without having to save or lose your work.

The fact that one rarely needs more than one window is one of the things I really like about Hopscotch. There’s no need for a docking bar, or tabs for that matter. Tabs are popular these days, but they don’t scale: they occupy valuable screen real estate, and beyond half a dozen or so become disorienting and unmanageable.
Hopscotch does better than the mainstream, and better than previous efforts like Strongtalk or Self, partly because of its navigation model, and partly because of the inherent compositionality of tools built with it. The fact that I can move from the debugger to the class browser in the same window did not require special planning - it’s inherent in the way Hopscotch based tools behave - they can be composed by means of a set of combinators. Compositionality is one of the most crucial, and most often overlooked, properties in software design; it’s what sets Hopscotch apart.

You can find out more about Hopscotch in this paper and on Vassili ‘s blog.

The design of debugger UIs is one example of something that needs to change in modern IDEs. There are others of course. Many are related to the basic problems of modality, navigation and proliferation of panes/windows noted above. Overall, your typical IDE UI is too much like the control panel of a B-52 bomber or an Apollo space capsule: a mind boggling array of switches, gauges, controls and wizards that interact with each other in myriad and confusing ways. This is neither necessary nor desirable. Like explicit memory management and primitive types, in time we will progress beyond these.

Incremental Development Environments

2008-06-07T16:30:00.000-07:00

Back in 1997, when I started working at Sun, I did not expect to do much programming language design. After all, Java was completely specified in the original JLS, or so it was thought.

What I actually expected to do was to work on a Java IDE. Given my Smalltalk background, I was of course very much aware of how valuable a good IDE is for programmers. The Java IDE I had in mind never materialized. Management at the time thought this was an issue to be left to other vendors. If this seems a little strange today - well, it seemed strange back then too. In any case, the Java world has since learned that IDEs are very important and strategic.

That said, todays Java IDEs are still very different from what I envisioned based on my Smalltalk background.

Java IDEs have yet to fully embrace the idea of incremental development. Look in any such system, and you’ll find a button or menu labeled Build. The underlying idea is that a program is assembled from scratch every time you change it.

Of course, that is how the real world works, right? You find a broken window on the Empire State building, so you tear it down and rebuild it with the fixed window. If you're clever, you might be able to do it pretty fast. Ultimately, it doesn't scale.

The build button comes along with an obsession with files. In C and its ilk, the notion of files is part of the language, because of #include. Fortunately, Java did away with that legacy. Java programmers can think in terms of packages, independent of their representation on disk. Why spend time worrying about class paths and directory structures? What do these have to do with the structure of your program and the problem you’re trying to solve?

The only point where files are useful in this context is as a medium for sharing source code or distributing binary code. Files are genuinely useful for those purposes, and Smalltalk IDEs have generally gone overboard in the opposite direction; but I digress.

A consequence of the file/build oriented view is that the smallest unit of incremental change is the file - something that is often too big (if you ever notice the time it takes to compile a change, that’s too long) and moreover, not even a concept in the language.

More fundamentally, what’s being changed is a static, external representation of the program code; there is no support for changing the live process derived from the code so that it matches up with the code that describes it. It’s like having a set of blueprints for a building (the code in the file) which doesn’t match the building (the process generated from the code).

For example, once you add an instance variable to a class, what happens to all the existing instances on the heap? In Smalltalk, they all have the new instance variable. In Java - well, nothing happens.

In general, any change you make to the code should be reflected immediately in the entire environment. This implies a very powerful form of fix-and-continue debugging (I note in amazement that after all these years, Eclipse still doesn’t support even the most basic form of fix-and-continue).

All this is of course a very tall order for a language with a mandatory static type system.
I’m not aware of a JVM implementation that can begin to deal with class schema changes (that is, changing the shapes of objects because their class has lost or acquired fields). It’s not impossible, but it is hard.

Consider that removing a field requires invalidating any code that refers to it. In a language where fields are private, the amount of code to invalidate is nicely bounded to the class (good design decisions tend to simplify life). Public fields, apart from their nasty software engineering properties, add complexity to the underlying system.

This isn’t just a headache for the IDE. The VM has to provide support for changing the classes of existing instances. However, in the absence of VM support there all kinds of tricks one can play. If you compile all code yourself, you can ensure that no one accesses fields directly - everything goes through accessors. You can even rewrite imported binaries. With enough effort, I believe you can make it all work on an existing JVM with good JVMDI support.

Changing code in a method is supported by JVMDI (well, the JVMDI spec allows for supporting schema changes as well - it’s just that it isn’t required and no one ever implemented it). However, what happens if you change the signature of a method? Any number of existing callers may be invalid due to type errors. The IDE needs to tell you about this pretty much instantaneously, invalidating all these callers. Most of this worked in Trellis/Owl back in the late 80s. The presence of the byte code verifier means that this applies to binary code as well.

Achieving true incremental development is very hard. Still, given the amount of people working on Java, you’d think it would have happened after all these years. It hasn’t, and I don’t expect it to.

Someone will rightly make the point that mandatory typing can be very helpful in an IDE - its easier to find callers of methods, implementors, references to fields or classes, as well as refactoring (though, oddly, all these features originated in IDEs for dynamic languages - Smalltalk or Lisp; speculating why that is would make for another controversial post). This post isn’t really about static/dynamic typing - it’s about incrementality in the IDE.

Of course, mainstream IDEs annoy me for other reasons: the bloat, the slow startup, and most of all the B-52 bomber/Apollo space capsule style UI. That probably deserves another post.

In the meantime, I can go back to Vassili’s fabulous Hopscotch browsers and leave the mainstream to cope with all the docking bars, tabs and panes too small to print their name. You, dear reader, if you’re using a mainstream IDE, may not realize what you’re missing. To an extent, these things have to be experienced to be appreciated. Still I encourage you to demand better - demand true incremental development support, in whatever language you use. Because in the end, there are only two kinds of development - incremental, and excremental.

The Future of Newspeak

2008-05-06T09:56:00.000-07:00

Several people have asked me when Newspeak will be released. Well, I still don’t know, but at least now I know it will be released. Cadence has generously agreed to make Newspeak available as open source software under the Apache 2.0 license.

We will be publishing a draft spec for Newspeak soon; I say draft because I expect Newspeak to continue to evolve substantially for the next year at least, and because the initial spec will necessarily be incomplete.

It will be a while before we are ready to make a proper public release of Newspeak. In the meantime, I’ve gathered some information on my personal web site. We plan to set up an official Newspeak web site in the near future.

java'scrypt

2008-04-26T07:43:00.000-07:00

Everyone is talking about cloud computing these days; I should add some vapor to the mist.

I began thinking seriously about the topic a bit after April fools day 2004, when gmail was released. I started using gmail shortly therefater. After about 30 minutes, I was convinced that web clients had a long way to go.

It is true that gmail showed the world that you could do far more with javascript in a browser than I or most other people had realized.

Javascript and Ajax have come a long way since then. For an impressive demonstration of what’s possible, see the Lively Kernel, a realization of John Maloney’s Morphic GUI ideas of Self and Squeak, in Javascript. It only works in Safari 3.0 and some advanced Firefox builds, but that situation will improve in time.

Javascript’s performance remains an issue; this will also improve dramatically in the foreseeable future. However, with all the talk about computing in the cloud, I think some caveats are in order.

Many real applications will need to be used offline, and so will need to store state on the client. They are NOT going to be pure server side web applications. Google has finally acknowledged as much with the introduction of Google Gears. Microsoft’s LiveMesh naturally emphasizes this even more.

I say naturally, because Microsoft has an interest in the personal computer, while Google has an interest in taking us to an updated version of X terminals and 1960’s time sharing.
Of course, there are other technologies in this space, like Adobe Air. Macromedia (now part of Adobe) saw this coming earlier than most, going back to at least 2003 with its Central project.

With all these pieces in place, we may finally have the underlying elements necessary to build good applications delivered through the web browser.

Why has this taken so long? In theory, Java was supposed to deliver all this over ten years ago. Java started as a client technology, and applets were supposed to do exactly what advanced Ajax applications do today, only better.

Of course, the problem was that Java clients behaved very poorly; rather than fix the client technology, Sun captured the lucrative enterprise business. To understand why Sun behaved that way, why it had to behave that way, read The Innovator’s Dilemma.
Maybe I’ll expand on that theme in another post.

The result of Java’s failure on the client was that the entire vision of rich network-enabled client applications was put on hold for a decade. It is now once again coming to the fore, but there are other languages in that space now, Javascript chief among them.

I’m not advocating writing clients in Javascript directly. Javascript is the assembly language of the internet platform (and the browser is the OS). It’s flexible enough to support almost anything on top of it, and poorly structured enough that humans shouldn’t be writing sizable applications in it.

I am not in favor of the attempts to make Javascript 2 be another Java either. Javascript’s importance stems from the existing version’s position in the browser, and from its flexibility. It should be kept simple. Javascript's value increases the more uniformly it is implemented across browsers. A new, complex language will take a long time to reach that point.

People should program in a variety of languages that suit them, and have these compiled to Javascript and HTML (GWT is an example of that, though not one I really like). One shouldn't have to deal with the hodgepodge of Javascript and HTML (broadly defined to include XML, CSS etc.) that constitute web programming today.

I don’t expect native clients to go away any time soon though. They will provide a better experience than the browser in many ways for quite a long time. The advantage of writing in a clean, high level language and platform is that it can be compiled to run either on the “WebOS” or on a native OS.

What one wants to see in such a platform is the ability to take advantage of the network in a deep way - for software delivery and update and for data synchronization. Which brings me back to my theme of objects as software services (see the video), which I’ve been preaching publicly since 2005 ( see my OOPSLA 2005 presentation).

One should be able to write an application once, and deploy it both to the web browser and natively to any major platform. In all those scenarios, one should be able to update the software and data on the fly, run it on- and offl-ine and and monitor it over the network continuously. And all this needs to be done in a way that preserves user’s security. This last bit is still a big challenge.

The technology to do this is becoming available, even though everything takes much longer than one expects. The vision has its root in research in the 1980s, continued in the 1990s with Java (and others, now largely forgotten, like General Magic's Telescript) and will be probably be realized in the 2010s, per Alan Kay’s 30 year rule.

Monkey Patching

2008-03-23T10:48:00.000-07:00

Earlier this month I spoke at the International Computer Science Festival in Krakow. Krakow is a beautiful city with several universities, and it is becoming a high tech center, with branches of companies like IBM and Google. The CS festival draws well over a thousand participants; the whole thing is organized by students. While much of the program was in Polish, there were quite a few talks in English.

Among these was Chad Fowler’s talk on Ruby. Chad is a very good speaker, who did an excellent job of conveying the sense of working in a dynamic language like Ruby. Almost everything he said would apply to Smalltalk as well.

One of the points that came up was the custom, prevalent in Ruby and in Smalltalk, of extending existing classes with new methods in the service of some other application or library. Such methods are often referred to as extension methods in Smalltalk, and the practice is supported by tools such as the Monticello source control system.

As an example, I’ll use my parser combinator library, which I’ve described in previous posts. To define a production for an if statement, you might write:

if:: tokenFromSymbol: #if.
then:: tokenFromSymbol: #then.
ifStat:: if, expression, then, statement.

assuming that productions for expression and statement already exist. The purpose of the rules if and then is to produce a tokenizing parser that accepts the symbols #if and #then respectively. It might be nicer to just write:

ifStat:: #if, expression, #then, statement.

and have the system figure out that, in this context, you want to denote a parser for a symbol by the symbol directly, much as you would when writing the BNF.

One way of achieving this would be to actually go and add the necessary methods to the class Symbol, so that symbols could behave like parsers. I know otherwise intelligent people who are prepared to argue for this approach. As I said, Smalltalkers would call these additions extension methods, but I find the more informal term monkey patching conveys a better intuition.

Typically, one wants to deliver a set of such methods as a unit, to be installed when a certain class or library gets loaded. So these changes are often provided as a patch that is applied dynamically. Not a problem in Smalltalk or Ruby or Python (though I gathered from the Pythoners in Krakow that they, to their credit, frown on the practice).

Apparently, there is a need to explain why monkey patching is a really bad idea. For starters, the methods in one monkey’s patch might conflict with those in some other monkey’s patch. In our example, the sequencing operator for parsers conflicts with that for symbols.

A mere flesh wound, says our programming primate: I usually don’t get conflicts, so I’ll pretend they won’t happen. The thing is, as thing scale up, rare occurrences get more frequent, and the costs can be very high.

Another problem is API bloat. You can see this in Squeak images, where a lot of monkeying about has taken place over the years. Classes like Object and String are polluted with dozens of methods contributed by enterprising individuals who felt that their favorite convenience method is something the whole world needs to benefit from.

Even in your own code, one needs to exercise restraint lest your API becomes obese with convenience methods. Big APIs eat up memory for both people and machinery, reducing responsiveness as well as learnability.

Then there is the small matter of security. If you are free to patch the definition of a class like String (typically on the fly when their code gets loaded), what’s to stop malicious macaques from replacing critical methods with really damaging stuff?

The counter argument is that in many cases (though not in this example), the patch is designed to avoid the use of typecase/switch/instance-of constructs, which bring their own set of evils to the table.

Extractors are a new approach to pattern matching developed by Martin Odersky for Scala. They overcome the usual difficulty with pattern matching, which is that it violates encapsulation by exposing the implementation type of data, just like instance-of. It may be part of the answer here as well.

However, many monkey patches are motivated by a desire for syntactic sugar, as the example shows. Extractors won’t help here.

A variety of language constructs have been devised to deal with this and related situations. Class boxes and selector namespaces in Smalltalk dialects, context oriented programming in Lisp and Smalltalk, static extension methods in C# and even Haskell type classes are related. These mechanisms don’t all provide the same functionality of course. I confess that I find none of them attractive. Each comes at a price that is too high for what it provides.

For example, C# extension methods rely on mandatory typing. Furthermore, they would not address the example above, because we need the literal symbols we use in the grammar to behave like parsers when passed into the parser combinator library code, not just in the lexical scope of the grammar.

Haskell type classes are much better. They would work for this problem (and many others), but also rely crucially on mandatory typing.

Class boxes are dynamic, but again only effect the immediate lexical scope. The same is true of simple formulations of selector namespaces. Richer versions let you import the desired selectors elsewhere, but I find this gets rather baroque. I'm not sure how COP meshes with security; so far it seems too complex for me to consider.

I’ve contemplated a change to the Newspeak semantics that would accommodate the above example, but it hasn’t been implemented, and I have mixed feelings about it. If a literal like #if is interpreted as an invocation of a factory method on Symbol, then we can override Symbol so that it supports the parser combinators. This only effects symbols created in a given scope, but isn’t just syntactic sugar like the C# extension methods suggested above.

Of course, this can be horribly abused; one shudders to think what a band of baboons might make of the freedom to redefine the language’s literals. On the other hand, used judiciously, it is great for supporting domain specific languages.

So far, I have no firm conclusions about how to best address the problems monkey patching is trying to solve. I don’t deny that it is expedient and tempting. Much of the appeal of dynamic languages is of course the freedom to do such things. The contrast with a language like Java is instructive. Adding a method to String is pretty much impossible. One has to sacrifice one’s first-born to the gods of the JCP and wait seven years for them to decide whether to add the method or not. I’m not endorsing that model either: I know it only too well.

Regardless, given my flattering portrayals of primate practices, you may deduce that my main comment on monkey patching is “just say no”. The problems it induces far outweigh its benefits. If you feel tempted, think hard about design alternatives. One can do better.

Cutting out Static

2008-02-17T17:22:00.000-08:00

Most imperative languages have some notion of static variable. This is unfortunate, since static variables have many disadvantages. I have argued against static state for quite a few years (at least since the dawn of the millennium), and in Newspeak, I’m finally able to eradicate it entirely. Why is static state so bad, you ask?

Static variables are bad for security. See the E literature for extensive discussion on this topic. The key idea is that static state represents an ambient capability to do things to your system, that may be taken advantage of by evildoers.

Static variables are bad for distribution. Static state needs to either be replicated and sync’ed across all nodes of a distributed system, or kept on a central node accessible by all others, or some compromise between the former and the latter. This is all difficult/expensive/unreliable.

Static variables are bad for re-entrancy. Code that accesses such state is not re-entrant. It is all too easy to produce such code. Case in point: javac. Originally conceived as a batch compiler, javac had to undergo extensive reconstructive surgery to make it suitable for use in IDEs. A major problem was that one could not create multiple instances of the compiler to be used by different parts of an IDE, because javac had significant static state. In contrast, the code in a Newspeak module definition is always re-entrant, which makes it easy to deploy multiple versions of a module definition side-by-side, for example.

Static variables are bad for memory management. This state has to be handed specially by implementations, complicating garbage collection. The woeful tale of class unloading in Java revolves around this problem. Early JVMs lost application’s static state when trying to unload classes. Even though the rules for class unloading were already implicit in the specification, I had to add a section to the JLS to state them explicitly, so overzealous implementors wouldn’t throw away static application state that was not entirely obvious.

Static variables are bad for for startup time. They encourage excess initialization up front. Not to mention the complexities that static initialization engenders: it can deadlock, applications can see uninitialized state, and unless you have a really smart runtime, you find it hard to compile efficiently (because you need to test if things are initialized on every use).

Static variables are bad for for concurrency. Of course, any shared state is bad for concurrency, but static state is one more subtle time bomb that can catch you by surprise.

Given all these downsides, surely there must be some significant upside, something to trade off against the host of evils mentioned above? Well, not really. It’s just a mistake, hallowed by long tradition. Which is why Newspeak has dispensed with it.

It may seem like you need static state, somewhere to start things off, but you don’t. You start off by creating an object, and you keep your state in that object and in objects it references. In Newspeak, those objects are modules.

Newspeak isn’t the only language to eliminate static state. E has also done so, out of concern for security. And so has Scala, though its close cohabitation with Java means Scala’s purity is easily violated. The bottom line, though, should be clear. Static state will disappear from modern programming languages, and should be eliminated from modern programming practice.

More on Modules

2007-12-31T17:09:00.000-08:00

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

2007-12-16T17:25:00.000-08:00

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

2007-09-25T11:50:00.001-07:00

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

2007-08-15T13:30:00.000-07:00

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

2007-06-24T20:47:00.000-07:00

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.