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.

17 comments:

  1. Unfortunately, proper encapsulation doesn't really protect you in the end. As long as your language is dynamic, you're going to have problems. Let's imagine for the briefest of moments that Ruby had proper private members (I'm picking Ruby just because it's a dynamic, Smalltalk-like language that I know very well). We could write a class like this:

    class C
    private
    attr_reader :internal
    attr_writer :internal
    end

    Actually, we don't even need to imagine proper privates in Ruby, this works as is and it even will save us from your "rubbish" situation above:

    class C
    def slash_and_burn(victim)
    victim.internal = rubbish # fails
    end
    end

    However, it *doesn't* save us when we consider the perils of open classes. All we have to do is re-open the class and muck around with its internals:

    class C
    def what_the_heck_we_want
    internal = rubbish
    end
    end

    There, "problem" solved.

    My point is that dynamic languages which allow really powerful and cool things like this will *never* be able to provide proper encapsulation, so why go out of your way trying? Dynamic languages by their very definition are trusting the programmer not to do stupid things. If you're trusting the programmer not to call a non-existent method, it's not so much of a stretch to also trust them not to mess around with logically-private internals.

    ReplyDelete
  2. Hi Daniel,

    It's generally a bad idea to say that something will *never* be possible, unless you can mathematically prove it.

    Ruby isn't really a "hash table language", but it shares with them an unstratified approach to reflection. That will tend to ensure that securing it is a Sisyphean task.

    That is rather the point of this post; you need to an API, and furthermore it should be stratified, so base level and meta level can be separated.

    Mirrors enable that. That said, I admit no one has yet built a secure mirror API; I hope I will get there in time. In any case, encapsulation is a necessary, not a sufficient, precondition for that.

    ReplyDelete
  3. Hi Gilad,

    In Scala:

    gilad.scala:

    class C {
    private[this] var internals: String = "foo" // so delicate, so secret

    def slashAndBurn(victim: C) {
    victim.internals = "rubbish"
    }
    }

    gilad.scala:4: error: value internals is not a member of C
    def slashAndBurn(victim: C) { victim.internals = "rubbish" }
    ^
    one error found

    If private[this] is replaced with private, then it compiles.

    Best,
    Ismael

    ReplyDelete
  4. You mean 'too long', not 'two long'.

    ReplyDelete
  5. @Daniel Spiewak

    Perhaps what we should say, is that certain features of programming languages break encapsulation – this is well understood and documented in the literature.

    Note: This is true of both predominantly dynamic and predominantly static languages.

    Open-classes naturally break encapsulation because they don't involve the object (in this case an instance of the Class class) in the act of opening/modification. Of course it's possible to design a dynamic language with something akin to open-classes which doesn't break the encapsulation. How?

    In the Agora programming language the only operation defined on objects is message-passing*, so, if the object doesn't perform the behaviour you want itself then it can't be done. This is to say that, unless our Class class defined an open_class message then we simply can't open that class.

    Note: It's up to you whether you consider this to be a good or bad thing, and a reasonable argument can be made either way... personally I think this is great.

    We can better illustrate this by removing the syntactic sugar around Rubys' open-classes, so your code –

    class C
    def what_the_heck_we_want
    internal = rubbish
    end
    end

    would become (in a sort of pseudo-Ruby-like-language)

    C.open_class do
    def what_the_heck_we_want
    internal = rubbish
    end
    end

    This operation is still unsafe (in the sense that uncontrolled modification may be considered unsafe), the difference is that it doesn't violate encapsulation! This is possible because the object is performing the opening/modification itself (from the inside of the encapsulation barrier).

    Of course different meta-classes could be defined with different capabilities. We can easily imagine a class which allows Ruby modules to be mixed-in and another that doesn't, for example.

    Note: This would effectively end the horror that is monkey-pathing (uncontrolled modification) in Ruby.

    This then becomes a matter of API design.

    To summarise: dangerous things ARE dangerous whether you do them in a predominantly dynamic or a predominantly static language :).

    But, and this is a big but: we can give programmers the tools to control what can be done to their objects – and hence, enable strong encapsulation when desired, while providing powerful (potentially unsafe) language features (perhaps as libraries.)

    It's perfectly possible for a dynamic language to support both of these things... it's just not common :).

    * This is documented as extreme-encapsulation... a moniker which I find a little gaudy.

    ReplyDelete
  6. Ismael:

    Of course. I am well aware of Scala. It is a most excellent language. Alas, Scala's reflective capabilities are in essence those of Java - that is, limited to introspection, and not mirror based at all.

    Mark: Yes. Newspeak and mirrors a natural fit with the object-capability model, and the goal would be to base the reflective API on that.

    ReplyDelete
  7. Hi Gilad,

    Indeed, Scala's reflection is very limited at the moment.

    I take it you're familiar with the Reflecting Scala by Yohann Coppel[1]? It talks about a new mirror based reflection API for Scala.

    Best,
    Ismael

    [1] lamp.epfl.ch/teaching/projects/archive/coppel_report.pdf

    ReplyDelete
  8. Ismael:

    Yes, I remember Yohan's work. It is certainly a step in the right direction. Even so, the Java platform makes it very hard to go beyond introspection.Things like object schema changes, for example, are extremely challenging and painful, and likely to be costly.

    In a nutshell - Scala has a good Object model, the JVM does not.

    ReplyDelete
  9. Hi Gilad,

    I may be missing something, but wouldn't using two hash-tables -- private and public -- and exposing only the public one be sufficient?

    ReplyDelete
  10. Erez,

    What you suggest might actually be a useful implementation technique, and address base level encapsulation, but it doesn't really solve the problems with reflection and security.

    There's more to mirrors than I've discussed in this post. Distribution, for instance. It is important that you don't depend on the identity of the real class/object/method table etc.

    Mirrors also have the potential of very fine grain control: say, you want to limit someone to introspection. Now you want read-only hash tables as well, so you have 4 of them (2 real ones and two wrappers).

    I could probably come up with more arguments. Fundamentally, one needs to think in more abstract terms, with stratification between base level and meta level. Hash tables are at best an implementation artifact that muddles the two.

    ReplyDelete
  11. @Gilad

    Please correct me if I'm wrong but it would seem: if you have a mirror you can, at least potentially, reflect on anything you can get a reference to. But this would be a heinous violation of the objects encapsulation, which we deemed to be intrinsic.

    While capabilities may offer an excellent foundation for security, I don't feel they can replace encapsulation. The capability to violate an objects encapsulation is still a violation of encapsulation[1]. Even if it does have with it a certain, conceptual beauty.

    Indeed, it would seem that the only safe mirror (with respect to encapsulation) is one that is created by the object itself. This reflects a difference in concerns, and I would suggest that perhaps the requirements for an objects internal reflective API and it's external reflective API may be quite different.

    Tangent: Now that I think about it this this may be the case with a lot of concepts in object-oriented programming.

    Internally an object may come to know everything about itself, without the problems you mentioned in [2], while externally mirrors are clearly beneficial.

    What are your thought on the matter?


    [1] and reflection needn't violate encapsulation.
    [2] http://bracha.org/mirrors.pdf

    ReplyDelete
  12. Mark:

    Of course, *unrestricted* reflection inherently violates encapsulation.

    I am primarily concerned with preserving encapsulation at the base level. At the meta level, anyone with the right mirror can violate it.

    Not all mirrors need do that. For example, one can define mirrors that only introspect on public members, thus preserving encapsulation.

    On the other hand, some tools need to violate encapsulation and need the mirrors that do that (say, a debugger).

    The key issue is controlling who gets what mirrors. For example, it's probably ok for an object to get a mirror on itself, which it could choose to expose.

    Designing an API that handles this well is a challenge we have not yet begun to deal with. To be honest, Newspeak's mirrors were rather hastily thrown together, and do not represent my thoughts on the matter.

    It is a long and complex discussion. I'll try to expand in a separate post dealing exclusively with mirrors in the near future.

    In the meantime, I hope these few comments are helpful.

    ReplyDelete
  13. @Gilad:

    Thanks, your comments have been very interesting, and I can see now that the line between pragmatism and theory is, much finer than I had imagined previously.

    In particular the insight that – a mirror MAY violate an objects encapsulation, but it may also respect it, irrespective of its point of origin – was something I had stupidly overlooked.

    Thanks again – I look forward to your next article.

    ReplyDelete
  14. Mark:

    Your comments are very apropos; the point about an object being responsible for its encapsulation is very good one: consider the case of proxies for remote objects. Clearly, one needs to understand the proxy's behavior to provide a mirror that respects encapsulation. How do we arrange that in practice? The API design should cope with such issues. There's still work to be done.

    ReplyDelete
  15. I think this old post on refraction may be relevant.

    ReplyDelete
  16. MarkM: Yes, very much so. The notion of a VMMirror is something we already have, where primitives reside etc. Refraction generalizes this, and also may help answer awkward questions about reflective modifications across actors.

    ReplyDelete
  17. I agree that proper encapsulation is an absolute requirement. Where I differ is how that is implemented.

    Public, protected and private have always seemed an inadequate provision for encapsulation to me. In a message-based language, it seems an odd fit to do further steps to check a member is accessible while binding a message.

    I think I prefer the idea of encapsulation working by having an object expose itself by a pure public interface. If a more detailed object is needed, with extra methods etc. as required for implementation, make it another object, with the one exposing methods to clients acting as an interface to the object.

    This also seems to mesh well with object-capability approaches to me. I envisage similar approaches being used for mirrors - the mirror exposes a subset of the full reflective capability appropriate to its usage.

    One problem is that such approaches in many ways move the problem away from the language designer to the end developer - who has to consider in detail how an object may be used both directly and reflectively. This may not be an altogether bad thing, but I suspect may complicate some coding tasks.

    I totally concur with Mark's comments regarding access to reflective capabilities - an object needs some way to restrict this stuff itself, maybe based on factors not knowable until runtime (is code, for example, running in a sandbox).

    Once again, thanks for another thought-provoking article.

    ReplyDelete