Chased by One’s Own Tail

Functional programming languages generally allow you to program without resorting to explicit loops. You can use recursion instead. It’s more elegant and higher level. In particular, it allows one to code certain nonterminating computations (such as state machines) as (a set of mutually) recursive calls.

In order to reliably support tail calls, implementations convert tail recursion into iteration. As a result, the activation frames for the recursive calls never come into existence, preventing nasty stack overflows.

I recently came across a truly brilliant post by Guy Steele arguing that tail recursion is actually essential to object oriented programming. Go read it, as well the terrific essay by William Cook that it references.

And yet, object oriented languages usually don’t do tail call optimization (TCO for short). What’s their excuse?

One excuse, especially in the Java world, is security. Specifically, stack frames carry information about protection domains that the the classic J2SE model depends upon. Since I am not (and have never been) a fan of that particular model, I’ll dispense with that argument. There are better ways to get security.

A more important excuse is debugging. Stack traces are very useful for debugging of course, and if stack frames are optimized away via tail recursion, key information is lost.
I myself want complete stack traces, but I also want to write tail recursive programs and know that they will reliably work.

One possibility is that upon stack overflow, we compress the stack - eliminating any tail recursive frame that is at its return point. This should be controllable via debugging flags. The excess frames are eliminated, but only when strictly necessary. Programs that work well without tail call optimization won’t be affected. So if you think a reliable stack trace is more important than tail call optimization, you have no need for concern.

Programs that rely on tail calls might suffer performance loss in this mode, but they will still run - and be easier to debug. If this is a problem, one can specify a different configuration which optimizes tail calls away. So if you favor tail call optimization over stack traces, you need not be alarmed either.

Now let us change perspective slightly. Keep in mind that the stack compression suggested above is really just a particular form of garbage collection.

It’s good to recall that the whole notion of the call stack is simply an optimization. One can allocate activation records on the heap and dispense with a call “stack” altogether. If you did that, you could make each activation point at its caller. Tail recursive calls might produce activations that pointed not at the caller, but at the caller of the first activation of the tail recursive function. All intermediate frames would be subject to garbage collection.

In the above model, aggressive garbage collection corresponds to traditional TCO. On the other hand, the idea of "collecting" the stack only when it runs out, gives us as much debugging information as a conventional non-TCO implementation. We only lose information in situations that simply don't work without TCO.

Now let's pursue the analogy between stack frames and heap storage further. We’d like to have all our past states in the heap, so we could examine them with a time traveling debugger, but that’s usually too costly. If we are lucky enough to have a time traveling debugger at all, we must configure how much of the past is available.

The past history of the call stack (i.e., what tail recursive calls took place) is not fundamentally different. If we are chasing our own tail, we can go back in time and see it chasing us. So my ideal development environment would allow me to recover stack frames that had been eliminated by TCO if I really wanted to.

As usual, it’s easier to see the common abstraction if one considers everything, including activations, as an object.

I therefore argue that:

1. Support for tail recursion should be required by the language specification. This is essential: if tail recursive programs only run on certain implementations, one cannot write portable code that relies on tail recursion.
2. How tail recursion is supported is an implementation detail. Whether tail recursive activations never come into being, or exist on the stack or the heap and get collected by one policy or another, is up to the implementation.
3. During development, the IDE should let you choose policy on retaining computation history. In particular, it should allow you to retain as much of the history of your computation as possible - on the stack and the heap (e.g., time traveling debugging, full stack traces etc.).
   

I’ve endeavored to support this outlook in Newspeak - but only partially so far.
The Newspeak spec states that method or closure activations are objects, and a called activation is passed a reference to its continuation activation (not its continuation!), which is either its calling activation, or the continuation activation of the caller if there is no further code to execute in the caller (i.e., the caller is a tail call).

This meets requirements (1) and (2). Alas, the implementation does not yet comply (so forget about (3)). I hope we can correct this in time.

We need not compromise on either debugging or tail recursion. We do need to seek out common abstractions (like objects) and insist on better tools and languages rather than settling for the dubious services of the mainstream.

Objects are not Hash Tables

Hash tables are objects, not the other way around, as they are modeled in many popular scripting languages.

Ok, so objects aren't hash tables. They aren't cats either. What are they then? What would be a good definition of the term object as used in modern programming languages? I’d start with saying that an object is a self-referential record:

point = record {

rho = 0;

theta = 0;

x = fun(){return cos(point.rho, point.theta)};

y = fun(){return sin(point.rho, point.theta)}

}

Notice how the self reference is explicit, via the name point. The example does not rely on static typing, classes, prototypes, inheritance, delegation or on whether the language is imperative or not (the example above could easily be in either). So we can discuss them without getting into all those things.

Self reference, on the other hand, is absolutely essential - a record (or struct, for those who’ve used C for too long) is not in itself an object.

Popular scripting languages introduce a variation on this theme: they replace records with hash tables. The hash tables must still be self referential of course.

Hash tables have huge advantages. The first is that they are indexed by first class values, which means you can abstract over their keys. Hence you can access an object member without statically knowing its name - the equivalent of Smalltalk’s perform:, and a close cousin of Method.invoke() and Field.get()/set() in Java. You can also iterate over the keys (getMethods() etc.). You get reflection for free.

In an imperative language, hash tables are a mutable data structure. You can add, remove or change elements. So you can do schema changes on your objects and modify their behavior. Again, all this reflection comes for free - you need not even design an API for it.

Therein lies the rub of course. The trick of exposing the data structures of your implementation at the language level is immensely powerful - but it does expose them, and that has very real disadvantages. It is very hard to typecheck, optimize, or (especially) make any kind of security guarantees, without losing or restricting this great power.

Hence the title of this post. There is more to objects than hash tables (even with self reference). We should not confuse objects with the data structures that might implement them.

Let’s revisit the definition at the top of this post. It has the advantage that it is general enough to fit anything that people might call an object, but it isn’t good enough. For me, an object is an encapsulated self referential record. Encapsulation is open to interpretation: some people take it to mean “bundled together” while others expect it implies some sort of data abstraction/information hiding. In the above context, I would hope that it would be clear that I mean the latter, as the word record already implies bundling/aggregation.

This definition excludes the objects we find in common scripting languages; these rely on closures to encapsulate data. The definition also excludes mainstream statically typed languages, where encapsulation is enforced at the type level, by the type system:

class C {

private internals; // so delicate, so secret

public slashAndBurn(C victim){victim.internals = rubbish}

}

As the above code illustrates, class or type based encapsulation does not protect one object from another. However, if your type system is strictly based on interfaces, than you do get object based encapsulation.

I don’t advocate relying on a type system to ensure encapsulation: I’ve argued elsewhere against relying on mandatory type systems for security or any other crucial property.

Instead, I view encapsulation as inherent to objects themselves. Objects expose a procedural interface, independent of any type system, and explicitly define which members are public and which are hidden.

This is of course the model of objects used in the Smalltalk family of languages: Smalltalk, Self and now Newspeak. Self and Newspeak go further, and require that even the hidden members be accessed via a procedural interface.

Needless to say, this doesn’t imply losing the reflective power of the “hash table languages”. It does, however, force us to come up with a reflective API. Having a reflective API imposes structure that is lacking in typical scripting languages; this structure is a good thing. Making the reflective API secure is an open problem, but the fundamental approach of using mirrors means it is at least possible; but that is for another post.

Atomic Install

A few months ago, I wrote a post about the become: operation in the Smalltalk family of languages. The post elicited a good discussion. One of the interesting points that came up, was that you could implement become: by changing the class of objects, provided all the changes were atomic - changing the class, modifying the object’s schema accordingly, and copying the data between the objects.

Setting the discussion of become: aside, I observe that in general, reflective change should be atomic. What I mean by this, is that one should be able to group an arbitrary number of distinct reflective changes to the program, and install them into the running program all at once, in one atomic operation. I will use the term atomic install to refer to this ability.

Oddly enough, this point is not well understood. Most languages that support reflective change do not provide a way for atomically performing a set of changes.

Smalltalk provides a reflective API centered around classes. You can ask a class to modify itself in a variety of ways - adding or removing variables, methods or changing its superclass. There is, however, no way to change several classes at once.

The CLOS APIs are similar in this respect.

Scripting languages don’t really have a reflective API as such. Instead, the reflective changes may come about as the result of executing some code (e.g., an assignment may add a variable). In other cases, the reflective capacity of the language comes about directly from exposing the data structures of the language implementation back to the language.

In all these cases, one cannot perform a set of program changes as an atomic unit.

Why do you need to atomically apply a set of changes instead of sequentially applying one change after another?

One reason is that you’d like to apply the changes as a transaction. If a change fails (say, because you created a cycle in the class graph, or duplicated an instance variable) you don’t want any further changes to take place. It’s easier if you don’t have to catch exceptions etc. after each step.

Another reason is that the changes are often dependent on each other. Applying one change without the other leaves your program in a broken state. The fact that intermediate states may be inconsistent even though the overall set of changes is correct means that it isn't sufficient to wrap a series of reflective changes in a transaction.

Of course, most people don’t rely on reflective modification to develop their programs. Rather, they suffer through the classic edit-compile-run-debug cycle. In the absence of anything better, you typically edit source code in files. You then compile these files and load the resulting program. This actually has one big advantage: the load is atomic - all the changes that resulted from your edits are loaded as a unit.

Evolving your program reflectively has the advantage that you can make corrections to the running program. Often, this is done during fix-and-continue debugging. Even then, in most cases, the “program” in question is an application that is stopped in the debugger, and you can apply fixes sequentially. But as noted above, it’s still easier if you can apply the changes as a transaction.

More interesting cases are when you are modifying a program, and need to run it between the individual modifications. Unlike most people, I run into this often, when modifying the IDE I am using. However, there are additional situations of this nature.

Long lived applications that must provide continuous service have this flavor. Erlang allows you to replace an entire module as a unit in these situations. In Java, you use class loaders to get the desired effect; it’s complicated, but it’s your only way out. A scenario I'm especially interested in is software services: the service updates applications on the fly without shutting them down - and in particular, I may want to update the update mechanism itself.

If you can’t make all the changes in one go, you find that you have to break the transition into a series of steps, each of which leaves the system in a consistent state while leading to the desired final program. This is tricky and error prone: you need to apply the right changes in just the right order.

Scripting languages like Ruby often go through a series of program changes during program start up. Different modules are loaded, modifying the program in the process. This process is also order dependent, and therefore brittle. In many cases, this sort of reflective change isn’t actually essential; rather it’s an artifact of the language semantics. However, I suspect there are situations where it is used to real advantage.

Overall, one can live for a long time without the ability to atomically apply a set of program changes. And yet it seems that there are some situations where atomic install seems to be very useful. It also has another advantage: batching the changes is more performant. Often one doesn’t care, but it doesn’t hurt to be faster, and on some occasions it actually can matter. One might as well see if one can come up with a reflective API that supports atomic install.

In Strongtalk, the VM supported atomic install as a primitive operation in the VM. More recently, in the latest Newspeak update release, I added an atomic install facility written entirely in Newspeak. Exactly 372 lines of code (whitespace and copious comments included). It is a tribute to the Squeak design that this is doable without any privileged access to the VM .

Tangent1: Thanks to Peter Ahe and Eliot Miranda for the discussions that led to this scheme; and to Lars Bak, for the discussions that led to the original notion of atomic install.


Tangent2: Squeak’s existing mechanism for changing classes, the ClassBuilder, is, on the other hand, rather unattractive. It’s three times as long, vastly more complicated, and provides only a subset of the functionality. It shows how tricky this kind of reflective change can get if you don’t conceptualize it the right way.

Naturally, the actual atomic step here is done using a variant of become:. Specifically, it’s a one-way become: on an array of objects. Given two object arrays a and b, both of size n, all references to a[i] are changed to refer to b[i], for i =1 .. n.

The atomic installation process nice and simple. The input is a list of mirrors describing mixins, and a namespace listing which of those mixins already exist in the system. The namespace parameter is crucial BTW, as there is no global namespace in Newspeak.

We then produce a fresh set of mixins based on the input list. For any existing mixins, we locate all classes that are invocations of those mixins, and all subclasses thereof. We make fresh versions of these as well, reflecting the changed mixins involved. For each such class, we locate all its instances (does your system have allInstances?) and produce new instances based on the new descriptions. Each new object is associated with the old object by keeping them in parallel arrays. Then we just do the become: and we’re done.

Unlike Smalltalk, in Newspeak we never have to recompile code that hasn’t been modified at the source level - because Newspeak code is representation independent.

It’s clearly harder to do atomic install in a system that does sophisticated JIT compilation and inlining - but as I said, Strongtalk supported it (albeit at the VM level, largely because of the extar complexity involved) in the mid-90s.

How do we get this kind of reflective power on mainstream platforms? It is harder, because the widely used platforms don’t support the needed abstractions as well as Smalltalk VMs do.

At least on the web browser, I expect to be able to get similar effects with Javascript, albeit with a very different implementation.

In Java, the absence of the necessary primitives tends to force one to build one’s own custom object representation, which is costly in both developer time and machine time.

Ironically (but not coincidentally), the bulk of the necessary machinery already exists in the Hotspot JVM, which is capable of changing at least method implementations on the fly (via JVMDI), including deoptimizing compiled code that may have inlined a method that has been modified. The problem is exposing it to user - and especially exposing it securely. Mirrors can help here - but that is for a future post.

On .Net, the DLR helps one construct one’s own custom representation. Conversely, there’s little support for deoptimization etc. in the CLR itself.

Of course, one goal of this post is to encourage implementors to add such support, and do it in the right way.

An Image Problem

Imagine a library, say in Java, that provided a universal facility for saving the exact runtime state and configuration of any application. It would essentially capture the heap, all threads and their stacks, and save them to a file.

You could then load this file from disk and reconstitute your application just as it was when it was saved: For example, windows would re-open just where they were (adjusting their location if the screen size differed). The system would cope with open file handles and sockets in a reasonable fashion, re-opening them if they were available. All this would work irrespective of the underlying platform, and it would be fast as well.

The facility would be transparent to the programmer - you wouldn’t need to change your program in any way, beyond calling the library function. Pretty neat.

I don’t know of such a facility in Java or .Net. However, Smalltalk has had such a beast for over 30 years. In Smalltalk parlance, it’s called an image. Most Smalltalks are inseparably coupled to the notion of such an image.

Tangent: There are exceptions of course, notably Strongtalk.

The idea hasn’t caught on. Why? Should it catch on, and if so, how?

To be sure, the image is a very powerful mechanism, and has significant advantages. For example, in the context of the IDE, it gives the ability to save and share debugging sessions.

One advantage of images is rapid start-up. If your program builds up a lot of state as it starts, it can be intolerably slow coming up. This is one the problems that killed Java on the client. One should avoid computing that state at startup; one easy way to do this is to precompute most of it and store it in an image. It is typically much faster to read in an image than to try and compute its contents from scratch.

The problem begins when one relies exclusively on the image mechanism. It becomes very difficult to disentangle one’s program from the state of the ongoing computation.

If your program misbehaves (and they always do) and corrupts the state of the process, things get tedious. Say you have a test that somehow failed to clean up properly. In a conventional setting, you fix the problem with your code, and run the test again. With an image, you have the added burden of cleaning up the mess your program made.

In general, traditional environments tend to force you to start over with each run of the program: the edit-compile-link-load-throw-the-application-off-the- cliff-let-it-crash-and-start-all-over-again cycle, in the words of the original Java whitepaper.

Tangent: That whitepaper is a masterpiece of technical rhetoric, and was visionary in its day. Alas, Java never fully realized that vision.

The thing is, sometimes it’s good to be able to start afresh. It may be easier to start from scratch than to mutate your existing process.

Mega-tangent: incidentally, this is an argument for sexual reproduction as well.

Of course sometimes starting anew isn’t so nice: think about fix-and-continue debugging.

In some cases it is even more critical to separate your code from the computation. You often save your image just to save your program. It may take you a while to find out that your image has been corrupted. Now you need to go back to a correct image, and yet you need to extract your code safely from the corrupt image. To be sure, Smalltalk IDEs provide a variety of tools that can help you with that, but I have never been really happy with them.

Tangent: this is where irate Smalltalkers berate me about change sets and logs and Envy and Monticello etc. etc. Sorry, I don’t think it’s good enough.


In general, Smalltalk makes it hard to modularize one's code, and especially to separate the application from the IDE. The exclusive reliance on the image model greatly aggravates these difficulties.

Traditional development tools, primitive as they often are, naturally provide a persistent, stateless representation of the program. In fact they provide two: the source code, in a text file, and a binary.

Semi-tangent: source code seems the most obvious thing in the world; but traditional Smalltalk’s have no real syntax above the method level! Classes are defined via the evaluation of reflective expressions, which rely on the reflective API. This is very problematic: the API often varies from one implementation to another. By the way, this is one of the ways Newspeak differs from almost every Smalltalk (the late, great Resilient being the only exception I can recall). Newspeak has a true syntax. Furthermore, because Newspeak module declarations are fully parametric in all their external dependencies, they can be compiled at any time in any order - unlike code in most languages (say Java packages) where there are numerous constraints on compilation order (e.g., imports must be defined).

A binary is a stateless representation of the program code, but one that does not require a compiler to decode it. Smalltalk doesn’t usually have a binary form. Code is embedded in the image. There are exceptions, and some Smalltalk flavors have ways of producing executables, but the classic approach ties code and computation together in the image and makes it very hard to pry them apart.

None of this means you can’t have an image as well as a binary format. What is important is that you do not have just an image. Ideally, you have images and a binary format. This is one of my goals with Newspeak, and we are pretty close.

In Newspeak, serialized top level classes can serve as a binary format. I will expand on how serialization can serve as a binary format in an upcoming post. At the same time, we continue to use images, though I hope they will become much less central to our practice as time goes by.

Systemic Overload

Type-based method overloading is a (mis)feature of mainstream statically typed languages. I am very much against it - I’ve spoken about it more than once in the past. I decided I should put my views on the matter in writing, just to get it out of my system. I’ll start with the better known problems, and work my way up to more exotic issues.

Throughout this post, I’ll use the term overloading to denote type based overloading. Arity based overloading, as in e.g., Erlang, is pretty harmless.

When introducing a feature into a language, one has to consider the cost/benefit ratio. You might argue that overloading lets you separate the handling of different types into different methods, instead of doing the type dispatch inside one method, which is tiresome and costly. A classic example are mathematical operators - things like +.

This argument would have merit, if the overloading was dynamic, as in multi-methods. Since it isn’t, overloading doesn’t solve this kind of problem. Not that I’m advocating multi-methods here - they have their own problems - but at least they are based on accurate type information, whereas overloading is based on crude static approximations.

Consider this code (loosely based on an example from Dave Ungar’s OOPSLA 2003 keynote).

class VehicleUtilities {

int numberOfAxles(Vehicle v) { return 2;} // a plausible default

int numberOfAxles (Truck t){ return 3;}

}




Vehicle v = new Truck();

VehicleUtilities u = new VehicleUtilities();

u.numberOfAxles(v); // returns 2

This simple example illustrates the dangerous disconnect between static and dynamic information engendered by overloading.

What exactly is the benefit of type based overloading? It saves you some trouble inventing names. That’s it. This may seem important, but the only case where it is actually needed is when writing constructors - and only because the language doesn’t allow you to give them distinct names.

Constructors are a bad idea, as I’ve already explained, so let’s assume we don’t have them. For methods, type based overloading provides a trivial rewrite and that is all. I don’t think it is that hard to give the different operations different names. Sometimes, the language syntax can make it easier for you (like keyword based method names in Smalltalk), but even in conventional syntax, it isn’t that difficult.

You pay for this convenience in myriad ways. The code above exemplifies one set of issues.

Another problem is the risk of ambiguity. In most overloading schemes, you can create situations where you can’t decide which method to call and therefore declare the call illegal. Unfortunately, as the type hierarchy evolves, legal code can become illegal, or simply change its meaning.

This means that existing code breaks when you recompile, or does the wrong thing if you don’t.

Overloading is open to abuse: it allows you to give different operations the same name. Altogether, you need style guides like Effective Java to warn you to use overloading as little as possible. Language constructs that require style guides to tell you not to use them are a bit suspect.

Ok, you probably know all this. So what contribution does this post make? Well, the systemic costs of overloading in terms of designing and engineering languages are less widely appreciated.

Overloading makes it hard to interoperate with other languages. It’s harder to call your methods from another language. Such a language may have a different type system and/or different overload rules. Or it may be dynamically typed.

You often find a dynamic language implementing multi-method dispatch to approximate the behavior of overloaded methods it needs to call. This is costly at run time, and is a burden on the language implementor.

Scala supports overloading primarily so it can call Java; you might say overloading is a contagious disease, transmitted from one language to another through close contact.

In general, overloading adds complexity to the language; it tends to interact with all sorts of other features, making those features harder to learn, harder to use, and harder to implement. In particular, any change to the type system is almost certain to interact with type based overloading.

Here are some examples. Answers at the end of this post.

Exhibit 1: auto-boxing

void foo(Number n) { ... }

void foo(int i) { ...}



foo(new Integer(3)); // quick, what does this do?

Exhibit 2: the var args feature in Java

void foo(String s, Number... n) {...}

void foo(String s, int i, Integer... n) {...}

void foo(String s, int i, int... n) {...}

void foo(String s, Integer i, Integer... n) {...}

void foo(String s, Integer i, int... n) {...}


foo(“What does this do?”, 1, 2);


Exhibit 3: Generics

void foo(Collection c) {...}

void foo(Collection < String> c){...}

void foo(Collection < Boolean> c){...}

void foo(Collection < ? extends String > c){...}

void foo(Collection < ? super String > c){...}


Collection< String> cs;

foo(cs);

/* Which of these is legal? What would happen if we didn’t use erasure? You have 3 seconds. */

Each of the above exhibits shows a specific type system extension which gets entangled with overloading.

You might say you don’t care; these are pretty sick examples, and the language designers sorted out the rules. What is their suffering to you? Well, these complications all have cost, and since resources are finite, they come at the expense of other, more beneficial things.

Tangent: People tend to think that the language design and implementation teams at large companies like Sun or Microsoft command vast resources. In reality, the resources are spread pretty thin considering the scope of the task at hand.

The more time is spent chasing down these issues, the less is spent focusing on doing stuff that actually buys you something. Products ship later and have more bugs and less desirable features, because people spent time worrying about gratuitous complications.

This is not hypothetical. I know the poor soul who wrote the spec for this might have spent his time doing something else, like day dreaming or adding closures. The compiler writers could have fixed more outstanding bugs, perhaps even reaching a state where there were no open bugs. I know they tried. The testers could have tested for other, more pressing issues and discovered more bugs to open, before shipping. These are the wages of sin - and the sin is unjustified complexity.

Now, for the sake of balance, I should say that overloading, and language complexity in general, do have one advantage I haven’t yet mentioned. They open up great opportunities for training, support and consulting. You can even write some really cool books full of language puzzlers.

It’s worth noting that this kind of overloading is only a concern in languages with a mandatory type system. If you use optional typing (or just dynamic typing), you aren’t allowed to let the static types of the arguments change the meaning of the method invocation. This keeps you honest.

Will future language designs avoid the problems of overloading? I wish I was confident that was the case, but I realize overloading is an entrenched tradition, and thus not easily eradicated.

However, the overarching point I want to make is that the costs of complexity are insidious - unobvious in the short term but pervasive over the longer haul. KISS (Keep It Simple, S - where the binding of S is open to interpretation).


Answers:

1. The issue here is whether we auto-unbox Integer(3) first to produce an int (and call foo(int)) or resolve overloading in favor of foo(Number) and don’t unbox at all. Java does the latter. The reason is to remain compatible with older versions.
2. This is ambiguous. Except for the first declaration, no method is more specific than the others.
3. They all have the same erasure, and so the example is illegal. If we did not use erasure, than foo(Collection < String >) would be the most specific method.
   

The Miracle of become:

One of Smalltalk’s most unique and powerful features is also one of the least known outside the Smalltalk community. It’s a little method called become: .

What become: does is swap the identities of its receiver and its argument. That is, after

a become: b

all references to the object denoted by a before the call point refer to the object that was denoted by b, and vice versa.

Take a minute to internalize this; you might misunderstand it as something trivial. This is not about swapping two variables - it is literally about one object becoming another. I am not aware of any other language that has this feature. It is a feature of enormous power - and danger.

Consider the task of extending your language to support persistent objects. Say you want to load an object from disk, but don’t want to load all the objects it refers to transitively (otherwise, it’s just plain object deserialization). So you load the object itself, but instead of loading its direct references, you replace them with husk objects.

The husks stand in for the real data on secondary storage. That data is loaded lazily. When you actually need to invoke a method on a husk, its doesNotUnderstand: method loads the corresponding data object from disk (but again, not transitively).

Then, it does a become:, replacing all references to the husk with references to the newly loaded object, and retries the call.

Some persistence engines have done this sort of thing for decades - but they usually relied on low level access to the representation. Become: lets you do this at the source code level.

Now go do this in Java. Or even in another dynamic language. You will recognize that you can do a general form of futures this way, and hence laziness. All without privileged access to the workings of the implementation. It’s also useful for schema evolution - when you add an instance variable to a class, for example. You can “reshape” all the instances as needed.

Of course, you shouldn’t use become: casually. It comes at a cost, which may be prohibitive in many implementations. In early Smalltalks, become: was cheap, because all objects were referenced indirectly by means of an object table. In the absence of an object table, become: traverses the heap in a manner similar to a garbage collector. The more memory you have, the more expensive become: becomes.

Having an object table takes up storage and slows down access; but it does buy you a great deal of flexibility. Hardware support could ease the performance penalty. The advantage is that many hard problems become quite tractable if you are willing to pay the cost of indirection via an object table up front. Remember: every problem in computer science can be solved with extra levels of indirection. Alex Warth has some very interesting work that fits in this category, for example.

Become: has several variations - one way become: changes the identity of an object A to that of another object B, so that references to A now point at B; references to B remain unchanged. It is often useful to do become: in bulk - transmuting the identities of all objects in an array (either unidirectionally or bidirectionally). A group become: which does it magic atomically is great for implementing reflective updates to a system, for example. You can change a whole set of classes and their instances in one go.

You can even conceive of type safe become: . Two way become: is only type safe if the type of A is identical to that of B, but one way become: only requires that the new object be a subtype of the old one.

It may be time to reconsider whether having an object table is actually a good thing.

A Ban on Imports (continued)

In my previous post, I characterized imports as evil, and promised to expand upon non-evil (yay verily, even good) alternatives. First, to recap:

Imports are used for linking modules together. Unfortunately, they are embedded within the modules they link instead of being external to them. This embedding makes the modules containing the imports dependent on the specific linkage configuration the imports represent.

Workarounds like dependency injection are just that: workarounds (e.g., see this post). They are complex, cumbersome, heavyweight. OSGi even more so. Above all, they are unnecessary - provided the language has adequate modularity constructs.

So, which languages have sufficient modularity support? I know of only two such languages: Newspeak and PLT Scheme. ML has a very elaborate module system, but ultimately it does not meet my requirements.

Modules and their definitions (these are two distinct things) should be first class and support mutual recursion. This isn’t the case in ML, though some dialects do support mutual recursion.

Tangent: The difficulty in ML, incidentally, is rooted in the type system. It is very hard to typecheck the kind of abstractions we are talking about. Worse, if you want to make your type declarations modular, your modules end up having types as members. This can lead you into deep water with types of types (making your type system undecidable). To avoid that trap, ML opts to stratify the system, so that modules (that contain types) are not values (that have types).

Not surprisingly then, progress on these issues comes from the dynamically typed world. Over a decade ago, the Schemers introduced Units.

The biggest difference between Newspeak modularity constructs and units is probably the treatment of inheritance. In Newspeak our module definitions are exactly top level classes, which reduces the number of concepts while allowing module definitions to benefit from inheritance.

There are strong arguments against inheritance of module definitions. For example, you cannot reliably add members to a module definition, because they might conflict with identically named members in the heirs of that definition. Specifying a superclass (or super module definition) looks like a hardwired dependency as well.

On the other hand, being able to reuse module definitions via inheritance is very attractive. Especially if you can mix them in freely.

Ultimately, we decided that the benefits of unifying classes and module definitions outweighed the costs.

Take the argument above regarding extending module definitions with new members. Newspeak was designed with an eye toward a completely networked world, where software is a service, not an artifact. In such a world, you can find all your heirs - just as if you were working on your own private application in your IDE. So if you need to add a member to a module definition, you should be able check who is mixing it in and what names they have added.

Tangent: This may still sound radical today, but this world is moving into place as we speak:
V8 gives the web browser the performance needed to be a platform for serious client software.
HTML 5, Gears etc. provide such software with persistent storage on the client
Chrome OS makes it obvious (as if it wasn’t clear enough before) that this in turn commoditizes the OS, and that the missing pieces will keep coming.

Likewise, in the absence of a global namespace, top level classes do not inherit from any specific superclass (and nested classes don’t either because all names are late bound) . Overall, the downside of allowing inheritance on module definitions doesn't apply in Newspeak.

The upside compared to conventional constructs is huge. It means you can easily take entire libraries, create multiple instances of them (each with its own configuration), mix them into new definitions, write polymorphic code that can work simultaneously with different instances or even different implementations of the API etc. You can store the libraries and their instances in variables, pass them as parameters, return them from computations, hold them in data structures, serialize them to disk or over the wire - all with the same mechanisms you use for ordinary classes and objects.

This economy of mechanism is important. It means you don’t have to learn a variety of specialized and complex tools to build modular systems. The same basic tools you use to implement basic CS101 examples will serve across the board. This will carry through to other areas like tooling: an object inspector can be used to inspect a “package”, for example. Altogether, your system can be much smaller - which makes it easier to learn, faster to load, likelier to fit on small devices etc. Simplicity is an advantage in itself.

As I explained in the first half of this series, the only need for a global namespace is for configuration: linking the pieces of an application together. There are several ways you can deal with the configuration/linkage issue. It’s a tooling issue. We use the IDE, as I described in an older post. So using the running example from part 1, we can write:

class SoundSystem usingPlatform: platform andPlayer: player = {

|

(* dependencies on platform might include things like the following: *)

List = platform Collections List. (* You can see how this replaces an import *)

mp3Player = player usingPlatform: platform withDock: self.

|
}{ ... }


class IPhone usingPlatform: platform withDock: dock = {


|

(* dependencies on platform elided *)

myDock = dock.

|

}{ ... }


class Zune usingPlatform: platform withDock: dock = {


|

(* dependencies on platform elided *)

theirDock = dock.

|

}{ ... }

and then create instances in the IDE (which provides us with a namespace where SoundSystem, iPhone(tm) and Zune(tm) are all bound to the classes defined above):

sys1:: SoundSystem usingPlatform: Platform new andPlayer: IPhone.

sys2:: SoundSystem usingPlatform: Platform new andPlayer: Zune.

tm: Did you know? iPhone is trademark of Apple; Zune is a trademark of Microsoft.

Variations on the above are possible; hopefully, you get the idea. If not - well, don’t worry, I probably won’t explain it again.

The absence of a global namespace has additional advantages of course: there’s no static state, and it’s good for security (but that is for another day).