mikeash.com: just this guy, you know?

Posted at 2009-10-16 15:50 | RSS feed (Full text feed) | Blog Index
Next article: Friday Q&A 2009-10-23: A Preview of Coming Attractions
Previous article: XBolo is Out!
Tags: blocks evil fridayqna
Friday Q&A 2009-10-16: Creating a Blocks-Based Object System
by Mike Ash  

It's Friday again, and that means another Friday Q&A. This week, Guy English proposed talking about a blocks-based object system, and that is what I will do. The system I've developed is a rudimentary system for doing object-oriented programming in pure C (plus blocks), and I'll discuss how it works and how to use it.

This system is weird and fairly impractical. The purpose of this article is to explore the system and think about what lessons might be learned from it that could transfer into more realistic situations. It is not meant to be something that you would actually go out and use.

Source Code
For those of you who would like to follow along at home, you can get the full source code to my rudimentary blocks-based object system, plus a small example class and some testing code, from my public subversion repository.

C Object Orientation
C has seen a number of object systems over the years, and not just the ones with language extensions like C++ and Objective-C. A common way to program in C is to use opaque structs and provide functions that operate on them. CoreFoundation is a good example of this. Here's what such a thing looks like:

    typedef struct MyFakeClass *MyFakeClassRef;
    MyFakeClassRef NewMyFakeClass(void);
    void DoSomethingInterestingWithFakeClass(MyFakeClassRef obj, int foo);
    void DestroyMyFakeClass(MyFakeClassRef obj);
This gives you many of the advantages of object-oriented programming without ever having to leave C. You get encapsulated data (other code doesn't know what the contents of a MyFakeClass are), a strong link between a data structure and the code that operates on it, better organization, etc.

Of course it's missing some key features of object orientation as well, like inheritence. You might remedy that by making the "methods" actually be members of the struct:

    struct MyFakeClass
        void (*doSomethingInteresting)(struct MyFakeClass *obj, int foo);
        void (*destroy)(struct MyFakeClass *obj);
The trouble with this is that it gets a little redundant, using the object both to find the function pointer and then having to pass it as a parameter too:
    struct MyFakeClass *obj = ...;
    obj->doSomethingInteresting(obj /* UGLY! */, 42);
And then you need a reference to the object's data somewhere, and the most natural place to put it is in the struct next to all of the function pointers, right in plain view.

Enter Blocks
Apple's new blocks extension to C gives us something much like function pointers, but which have implicit context. When you call them, they can automatically access whatever data is necessary without the caller needing to give it to them explicitly. The struct then looks like this:

    struct MyFakeClass
        void (^doSomethingInteresting)(int foo);
        void (^destroy)(void);
And you'd call things on it like this:
    struct MyFakeClass *obj = ...;
Not bad at all!

This system allows overriding existing "methods" by simply putting in a new block, and having that block call through to the one that used to be there. Defining entirely new methods for a "subclass" gets a little trickier, but it's not bad. Define the subclass to contain the parent:

    struct MyFakeSubclass
        struct MyFakeClass parent;
        void (^additionalMethod)(void);
Then callers can call parent methods like this:
    struct MyFakeSubclass *obj = ...;
That parent is not ideal, but it's workable. As a bonus, this technique separates the ideas of overriding an existing method and implementing a new method with the same name. In most OO systems it's impossible to implement a new method with the same name, as it's automatically an override. Here, they're two separate actions.

By putting parent at the front, this allows subtype polymorphism. By casting an instance of MyFakeSubclass to a struct MyFakeClass *, the result is still a valid object which continues to work as an instance of its parent class, but with any overridden behavior given by its subclass.

Building the System
That's the theory. Let's go ahead and actually build it now.

The first question is what objects will actually look like. We'll define them as structs containing blocks pointer members, and possibly a pointer to a parent struct/class. These are our methods. The struct contains nothing else: any per-object data is done using local variables which get captured by the method blocks.

We can then define a root object like this:

    struct RootObject
        void (^retain)(void);
        void (^release)(void);
        void (^dealloc)(void);
        struct String *(^copyDescription)(void);
        int (^isEqual)(struct RootObject *);
We need a function to create new instances of the root object. We'll call it NewRootObject. It takes one parameter: the size of the object to allocate. Subclasses may be bigger, and the memory needs to be contiguous, so NewRootObject needs to know how much to allocate.

To ease the task of creating new objects (and figuring out how much memory to allocate), we'll create a convention that new objects are always created using a function called NewClassName which takes a single size parameter. We can then create a little macro for creating new objects:

    #define Alloc(classname) New ## classname(sizeof(struct classname))
Using this, you'd allocate a new instance of the root class like so:
    struct RootObject *obj = Alloc(RootObject);
Now, what does NewRootObject actually look like?

The first thing it needs are the "instance variables", which in this case are just __block qualified local variables.

    struct RootObject *NewRootObject(size_t size)
        // "ivars"
        __block int retainCount = 1;
Next, it needs to actually allocate memory:
        // make the object
        struct RootObject *self = calloc(size, 1);
Then it can start filling out methods. It does this by just declaring blocks and assigning them to the slots. One wrinkle: since these blocks need to outlive their enclosing scope, we need to call Block_copy on them:
        // "methods"
        self->retain = Block_copy(^{ retainCount++; });
        self->release = Block_copy(^{
            if(retainCount <= 0)
Of course, that means that we eventually need to Block_release them. Having to go through and manually release every method in dealloc would be really tedious and error-prone, though. To work around this problem, the dealloc method can just scan the entire object for block pointers and release them all automatically. Since the only data in the object struct itself is block pointers, we can just scan one pointer-sized chunk at a time to get them all. Since we used calloc to allocate the object, we know that any memory "off the end" that got allocated due to malloc allocating more memory than necessary will be zeroed, and so any NULL pointer will be a signal to stop. This is what the dealloc method looks like:
        self->dealloc = Block_copy(^{
            size_t size = malloc_size(self);
            for(void **methodPtr = (void **)self;
                 *methodPtr && ((intptr_t)methodPtr + sizeof(*methodPtr) - 1 - (intptr_t)self) < size;
Finally, we define the copyDescription method (using a method of the as-yet-unseen String class) and return the new object:
        self->copyDescription = Block_copy(^{
            return Alloc(String)->initWithFormat("<Object %p>", self);
        return self;

Creating New Classes
Now that we've done all of that, how do we make a subclass? Let's go ahead and create the String class, since the root class depends on it anyway.

As mentioned before, a subclass gets a struct for its parent at the top, and then follows with its own methods, like so:

    struct String
        struct RootObject parent;
        struct String *(^initWithFormat)(char *fmt, ...);
        const char *(^cstring)(void);
Then it just needs a NewString function to create one. As with NewRootObject, the first part of the function is for "instance variables":
    struct String *NewString(size_t size)
        __block char *str = NULL;
And next, just like before, we allocate the object. Only this time, instead of allocating raw memory, we call through to the parent's New function to allocate the object.
        struct String *self = (void *)NewRootObject(size);
Next up, we want to override a couple of methods from the root object. The first one we want to override is copyDescription. Since we don't want to call through to the original implementation, we can just release the old block, then assign a new one:
        self->parent.copyDescription = Block_copy(^{
            return self;
Next, we need to override dealloc to free the str variable. This is a little trickier, though, because we need to call through to the old implementation once we're done. To do this, we'll save off the old implementation into a local variable, and call through to it. We also have to take care of releasing the old implementation:
        void (^superdealloc)(void) = self->parent.dealloc;
        self->parent.dealloc = Block_copy(^{
This is some tricky memory management business. At first blush this looks good, but if you look deeper you'll realize that Block_release(superdealloc) is being called too early! The body of the new dealloc block won't run until the object is destroyed, but the Block_release runs while the object is still being created.

This actually ends up working perfectly fine, because the compiler automatically does a Block_copy on the superdealloc instance variable when it gets captured by the new block referencing it. There's a bit of automatic reference counting going on behind the scenes, and this ensures that the block stays alive for as long as it's needed.

Finally, we'll define the String-specific methods and return the new object:

        self->initWithFormat = Block_copy(^(char *fmt, ...){
            va_list args;
            va_start(args, fmt);
            vasprintf(&str, fmt, args);
            return self;
        self->cstring = Block_copy(^{ return (const char *)str; });
        return self;
We now have a fully functioning, albeit simplistic and a bit verbose, object system.

Custom Classes Let's create one more class just to reinforce how it's done. We'll call this one MyObject, and it will just hold two numbers. Here's the class struct:

    struct MyObject
        struct RootObject parent;
        struct MyObject *(^initWithNumbers)(int a, int b);
And here's the function to create a new one:
    struct MyObject *NewMyObject(size_t size)
        __block int numbers[2];
        struct MyObject *self = (void *)NewRootObject(size);
        // override parent methods
        self->parent.copyDescription = Block_copy(^{
            return Alloc(String)->initWithFormat("<MyObject %d %d>", numbers[0], numbers[1]);
        self->initWithNumbers = Block_copy(^(int a, int b){
            numbers[0] = a;
            numbers[1] = b;
            return self;
        return self;
Finally, here's some example code that actually uses it:
    struct MyObject *myobj = Alloc(MyObject);
    myobj->initWithNumbers(42, 65535);
    description = myobj->parent.copyDescription();
    printf("myobj is %s\n", description->cstring());
Which produces the output you'd expect:
    myobj is <MyObject 42 65535>

To summarize, here's what you need to do to create a new class using this system:

  1. Define a new struct with the appropriate name.
  2. As the first member of the struct, add a struct for the parent class.
  3. For subsequent members of the struct, add block pointers for each method.
  4. Pause for breath.
  5. Define an appropriately-named New function.
  6. At the top, define any "instance variables" you need using the __block qualifier.
  7. Allocate the object by calling through to the superclass's New function.
  8. Override any parent methods by releasing the original block pointer and reassigning it. If you need to call through to the old implementation, save it into a local variable, and release that local variable after the reassingnment.
  9. Initialize any new methods by assigning to them.

Advantages and Disadvantages
This is an unusual object system. To be clear, this is not what Objective-C (or C++ or Java or...) is doing behind the scenes. (For information on what Objective-C is doing behind the scenes, check out my series on the Objective-C runtime.) It more closely resembles the prototype-based object systems found in languages like JavaScript.

Some of these differences are good, and some are bad. Let's take tha bad first. There are a lot of them.

In my defense, this object system was not meant to be practical, and I built it in about an hour.

Despite all of this, there are some advantages to it:

Again, I don't recommend actually using this object system for anything practical, but it's an interesting construct just the same.

We now have a fully functional, albeit strange, object system based on blocks, and one that's less than 100 lines long. This object system, while not entirely practical, is an interesting illustration of the sort of power that blocks add to the language.

That wraps up this week's Friday Q&A. Come back next week for another exciting edition. Since Friday Q&A is driven by your suggestions, be sure to send them in! If you liked this week's article and want to see more like it, give me some more ideas along these lines. On the other hand, if you hated it and don't want to see any more like it, give me some ideas in other directions! Whatever your idea, send it in!

Did you enjoy this article? I'm selling a whole book full of them. It's available for iBooks and Kindle, plus a direct download in PDF and ePub format. It's also available in paper for the old-fashioned. Click here for more information.


Andre Pang at 2009-10-16 17:55:43:

The venerable master Qc Na was walking with his student, Anton. Hoping to prompt the master into a discussion, Anton said "Master, I have heard that objects are a very good thing - is this true?" Qc Na looked pityingly at his student and replied, "Foolish pupil - objects are merely a poor man's closures."

Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire "Lambda: The Ultimate..." series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress.

On his next walk with Qc Na, Anton attempted to impress his master by saying "Master, I have diligently studied the matter, and now understand that objects are truly a poor man's closures." Qc Na responded by hitting Anton with his stick, saying "When will you learn? Closures are a poor man's object." At that moment, Anton became enlightened.

Martin at 2009-10-16 18:08:34:
You're crazy and I love it :-)
Great work.

mikeash at 2009-10-16 18:56:53:
That closure/object koan is pretty much the inspiration for this nutty system.

Jens Ayton at 2009-10-16 19:08:06:
As you say, C has seen a number of object systems over the years. I think COS and its predecessors deserve special mention for taking the opaque struct approach and running with it until it arrives somewhere you didn’t think you could get from here.

It’s absolutely insane, but also very impressive.

Leonard Norrgård at 2009-10-17 00:58:47:
Very interesting. I'd like to point out however, as a further warning to anyone who might get the idea despite your warning to not use this for anything real, that a huge disadvantage with this and all similar faked-OO on-top-of-C approaches is that full scale debugging is very difficult, as the debugger does not support the OO structure.

I say this from experience; back around 1990 C++ compilers weren't too stable on our platform of choice so we had no other option. Me and a colleague developed a fairly usable system at the time and successfully wrote two real-world applications on top of it (they were multithreaded GUI apps, so it helped a lot to have some OO features).

Today, we have a real opportunity to choose any of several available OO languages on most platforms, so these hairy fake OO systems have only got a place as a fun pastime for inquiring minds. That purpose they serve perfectly well, though. :-)

Chris Suter at 2009-10-17 03:49:03:
the compiler automatically does a Block_copy on the superdealloc instance variable when it gets captured by the new block referencing it.

Just a minor nitpick on this: the Block_copy on the captured block only occurs when you copy the enclosing block, so strictly speaking, it's the act of promoting a block to the heap (i.e. the first Block_copy) that causes all captured object/block variables to be retained, not the actual act of capturing.

Another thing that that looks a bit dodgy to me, is the use of malloc_size which will return the allocated size plus padding. Since you have the size handy, couldn't you just use that?

mikeash at 2009-10-17 04:56:24:
You're absolutely right about the block copy, I should have been more explicit about that.

As for the dealloc, using malloc_size is fine, because I allocate the struct using calloc, and the loop stops upon encountering NULL. If padding occurs, then it will stop once it reaches the padding.

However, using the size argument would be a much better approach. It didn't even occur to me that I could use it. I kept thinking that I'd have to add another member to the class struct, which I didn't want to do. But, of course, it's effectively an ivar, so I can just capture it. Duh.

Chris Suter at 2009-10-17 05:35:52:
As for the dealloc, using malloc_size is fine, because I allocate the struct using calloc, and the loop stops upon encountering NULL. If padding occurs, then it will stop once it reaches the padding.

I'm not sure if you realised I was talking about padding introduced by the memory manager rather than structure padding. For example, on OS X, all objects < 16 bytes occupy 16 bytes and that's what malloc_size will return. I don't think it's safe to assume that calloc would zero that padding, even though that does happen to be the case on OS X (on Snow Leopard at least).

Drew McCormack at 2009-10-17 07:46:56:
Thanks for a very nice post.

It probably shouldn't be surprising that you can do this though. I've just been writing a chapter of a book on Dashcode, and this exact trick is used by Apple in their Dashcode framework to add OO to JavaScript. JavaScript functions have always been closures.

Nonetheless cool.

mikeash at 2009-10-17 16:05:25:
Chris Suter; I understood that you were talking about malloc padding. Structure padding would destroy this whole thing (which means it's not portable, of course). You're right that relying on calloc to zero out the padding is a bad idea.

Drew McCormack: That is, of course, why I said that, "It more closely resembles the prototype-based object systems found in languages like JavaScript."

Damien Sorresso at 2009-10-18 05:04:47:
calloc(3) zeroing out the padding may or may not be part of the API contract. The man page says...

The calloc() function contiguously allocates enough space for count objects that are size bytes of memory each and returns a pointer to the allocated memory. The allocated memory is filled with bytes of value zero.

So the way I read it is that "the allocated memory" means "the allocated memory", not "a subset of the true allocation". I'm sure you could argue it the other way though.

One other limitation of this system that is worth mentioning is that it doesn't support class methods, i.e. methods that can be invoked without an instance. This can be added by having a global data structure of class method v-tables.

Also, the ## preprocessor paste operator is GNU-specific, I believe.

mikeash at 2009-10-18 05:30:22:
The fact that padding exists at all is an implementation detail, and can't be considered part of "the allocation" as far as the language goes, so there's no language guarantee that it's zeored.

It's true that it doesn't support class methods, but it basically doesn't have classes to begin with, so this doesn't seem all that surprising to me.

As for ##, definitely part of the language. It's described in section "The ## operator" in the copy of the draft C99 standard I happen to have here.

Jens Ayton at 2009-10-20 06:14:50:
It would be nice to turn it into a real prototype system, but that would require dynamic dispatch to be able to follow the prototype chain. Your challenge, should you choose to accept it… ;-)

John C. Randolph at 2009-10-20 07:36:45:
This post made me highly nostalgic. It has the same feel as the venerable Byte magazine articles about how to write FORTH.

BTW, it seems to me that a block-based object system would work better with a prototype model than a class model.


Alexander at 2009-10-23 11:13:44:
You might be interested to know that GTK+ (and the GNOME project) is based on a library called GObject which basically does all of that and more.

Tim McIntosh at 2009-10-24 18:52:33:
Great article, though this statement caught my attention:

The result of the pointer casting stuff going on to achieve subtype polymorphism does not actually have a defined result in the C language....

I always thought this was fully defined behavior in C99, at least.

In ISO/IEC 9899:1999 (E), paragraph (7) states:

A pointer to an object ... may be converted to a pointer to a different object .... If the resulting pointer is not correctly aligned for the pointed-to type, the behavior is undefined. Otherwise, when converted back again, the result shall compare equal to the original pointer.

Paragraph (13) states:

A pointer to a structure object, suitably converted, points to its initial member ..., and vice versa. There may be unnamed padding within a structure object, but not at its beginning.

All that's happening during object initialization is:
1. using calloc() to allocate a structure object
2. converting the returned pointer to a pointer to the initial member of the structure object
3. initializing the initial member of the structure object
4. converting the pointer to the initial member of the structure object to a pointer to the structure object itself
5. initializing the remaining members of the structure object

Subsequent accesses occur through either a pointer to the structure object or a pointer to its initial member (or its initial member, and so on).

This should apply recursively to allow arbitrarily deep inheritance. What am I missing?

Tim McIntosh at 2009-10-24 19:08:17:
I always thought this was fully defined behavior in C99, at least.

That is, with the obvious exception of the dealloc() implementation.

mikeash at 2009-10-24 19:13:49:
I think the problem is that I missed the fact that it's legal to convert back and forth between a pointer to a struct and a pointer to the first member of that struct. As far as I can tell, you're absolutely right that this does end up being defined (except for the dealloc craziness). Normally such pointer conversion shenanigans are not allowed, but I didn't know about this special case where it is defined. Thanks for teaching me something new!

Comments RSS feed for this page

Add your thoughts, post a comment:

Spam and off-topic posts will be deleted without notice. Culprits may be publicly humiliated at my sole discretion.

Web site:
Formatting: <i> <b> <blockquote> <code>. URLs are automatically hyperlinked.
Code syntax highlighting thanks to Pygments.
Hosted at DigitalOcean.