A place to be (re)educated in Newspeak

Saturday, November 21, 2009

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.