Bootstrapping a prototype-based object-model in 44 lines of code.
Until a few weeks ago I had always thought that writing a language required some crazy voodoo, but it turns out that once you start digging into the fundamentals they are actually fairly easy to understand and, under certain circumstances, fairly easy to implement as well.
In this short example we are going to implement a prototype-based object-model in Ruby. To make it a valid exercise we will not be using any of Ruby's object-oriented features. The final mini-language we create will not be pretty, but it will work. Making it pretty will require syntactical sugar for things like sending a message to an object, which is not something we will tackle just yet.
The first thing we need is a way to store the structure of our objects. For this purpose we are going to use a Hash like so:
The 'slots' in this hash will store the methods/data that are associated with the object. The 'parent' will be a pointer to the object's parent if it has one, and the 'size' will simply keep track of how many key/value pairs are stored in 'slots'.
Next we need to define functions for sending a message to an object, and for creating a new object that inherits the behaviour of a previous one:
The 'send' function depends on the fact that each object is required to define or inherit a 'lookup' method. The 'lookup' method defines how an object reacts when it is sent a message. If the send function cannot find a 'lookup' method defined on the current object then it follows the chain of inheritance upwards (via 'parent') until it finds one, or until the inheritance chain is exhausted.
The 'derive_from' function simply creates a new object with an existing object as it's 'parent'. This provides a way to create a new object that inherits behaviours from an existing object, this layout is technically known as 'single inheritance'.
Next up we need to manually create the initial 'lookup' method for our basic object:
The 'lookup' method is very similar to the 'send' function in that it traces the chain of inheritance looking for a slot with a key which corresponds with the 'message'. If it finds a match then is simply returns the value of the slot so that 'send' can execute it as a method. If it cannot find a corresponding slot anywhere in the inheritance chain then it raises an error.
Next we need to give ourselves a way of adding new methods to an object. We'll do this by manually defining 'add_method':
'add_method' simply copies an anonymous function into the object slot that corresponds with the method name. It also increments the object's 'size' parameter so we can easily keep track of how many occupied slots the object has.
Lastly we will manually set the size of 'basic_object' to account for the methods we have manually created:
And we're effectively done! We can now start using our brand-new object model. Let's start by creating a new object based on 'basic_object' and adding a method to return the size of the object:
And then we can call our new method like so:
So as it turns out there is no voodoo involved after all! Obviously this is a very short example and it's a long road from here to a useful language, but it's quite amazing how short the minimal case is.
It's worth noting that the exact same principal can be applied to bootstrap a similar object model in any procedural language that supports either pointers to functions or anonymous functions, I just used Ruby in this example because it's what I know best.
If you're interested in learning more I highly recommend reading Open, extensible object models [pdf] by Ian Piumarta and Alessandro Warth, where they cover an implementation of this model in C as well as further features like Traits.
The full source code of the example in Ruby can be found at: http://gist.github.com/472964