mikeash.com pyblog/friday-qa-2009-10-16-creating-a-blocks-based-object-system.html comments

mikeash - 2009-10-24 19:13:49

Sat, 24 Oct 2009 19:13:49 GMT

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!

Tim McIntosh - 2009-10-24 19:08:17

Sat, 24 Oct 2009 19:08:17 GMT

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

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

Tim McIntosh - 2009-10-24 18:52:33

Sat, 24 Oct 2009 18:52:33 GMT

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 6.3.2.3 (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 undeﬁned. Otherwise, when converted back again, the result shall compare equal to the original pointer.

Paragraph 6.7.2.1 (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?

Alexander - 2009-10-23 11:13:44

Fri, 23 Oct 2009 11:13:44 GMT

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.

John C. Randolph - 2009-10-20 07:36:45

Tue, 20 Oct 2009 07:36:45 GMT

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.

-jcr

Jens Ayton - 2009-10-20 06:14:50

Tue, 20 Oct 2009 06:14:50 GMT

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… ;-)

mikeash - 2009-10-18 05:30:22

Sun, 18 Oct 2009 05:30:22 GMT

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 6.10.3.3 "The ## operator" in the copy of the draft C99 standard I happen to have here.

Damien Sorresso - 2009-10-18 05:04:47

Sun, 18 Oct 2009 05:04:47 GMT

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 - 2009-10-17 16:05:25

Sat, 17 Oct 2009 16:05:25 GMT

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."

Drew McCormack - 2009-10-17 07:46:56

Sat, 17 Oct 2009 07:46:56 GMT

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.

Chris Suter - 2009-10-17 05:35:52

Sat, 17 Oct 2009 05:35:52 GMT

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).

mikeash - 2009-10-17 04:56:24

Sat, 17 Oct 2009 04:56:24 GMT

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 - 2009-10-17 03:49:03

Sat, 17 Oct 2009 03:49:03 GMT

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?

Leonard Norrgård - 2009-10-17 00:58:47

Sat, 17 Oct 2009 00:58:47 GMT

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. :-)

Jens Ayton - 2009-10-16 19:08:06

Fri, 16 Oct 2009 19:08:06 GMT

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.
http://ldeniau.web.cern.ch/ldeniau/oopc.html

It’s absolutely insane, but also very impressive.

mikeash - 2009-10-16 18:56:53

Fri, 16 Oct 2009 18:56:53 GMT

That closure/object koan is pretty much the inspiration for this nutty system.

Martin - 2009-10-16 18:08:34

Fri, 16 Oct 2009 18:08:34 GMT

You're crazy and I love it :-)
Great work.

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

Fri, 16 Oct 2009 17:55:43 GMT

http://people.csail.mit.edu/gregs/ll1-discuss-archive-html/msg03277.html

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.