The Universal Design Pattern

Wow! A Blog entry with index... nice :)

Isn't this what David West talks about in his book "Object Thinking" when he discusses an objects responsibility to "Descibe itself"?

I'd like to see more people use this indeed, I like it but don't encounter it very often in other peoples code.

I've published recently some experimental C++ code, with an implementation of the property pattern which I use later to store objects in a SQLite database - I have indeed some "battle scars" to show off after doing this :) but it was a nice experiment anyway. Feel free to play with the code! It's here: http://tinyurl.com/6lq33q

Here's a link to the book I mentioned: Object Thinking by David West

In this idea of key value, What do you think about couchdb:

http://incubator.apache.org/couchdb/

Thanks for the long articles :)

Don't the object systems of Perl and Python follow this pattern? Or are those "just name/value pairs"?

sounds a LOT like RDF

You just described the extension model for Atom, namely how you're expect to handle foreign markup with a mustIgnore processing directive; this is also one of the reasons why Atom's XML is a flat structure.

For reference you might be interested in the old AI frames/slots approach to KR, especially handling 'inheritance' and 'exceptions', like the penguin-isa-bird, bird-can-fly modeling problem. I'm sure there's a bunch of people inside Google (like Norvig, I think AIMA has a chapter on slots/frames) that can give you pointers.

http://norvig.com/ijcai83.html

Great post btw.

Excellent article. I just want to point out that Lua merely allows you to create a prototype-based object system. It doesn't really come with one built-in. The power that comes with metatables lets you get really creative with an object system.

I don't know if describing XML as a paradigm is useful. What does XML do that's unique? XML (XSD, XSLT etc) is a group of tools. What is the philosophy and how is it different that OO or functional?

There is a lot of resistance to using properties type strategies because of a lack of compile time checks for key names. On the one hand you have more flexibility, but on the other you don't get the checks. IMO checking can be done in unit tests.

Also performance: there are few applications and fewer places in those applications where the hash-table lookups for string properties lead to any meaningful performance problems.

Thanks Steve. Lots of food for thought here! Seems to make as much / more sense than OOP in many respects!

Hopefully you're going to show us some examples in a later post? For the less abstract amongst us :-)

I find that this pattern very frequently in so called "ERP" software.

One main problem with this pattern is that a naive implementations has a big memory overhead.
I've got some numbers at my old blog here .

It's good that you mention String interning, because without it this pattern is useless in Java.
This goes as far as that we will have soon special support in the Eclipse Memory Analyzer for finding duplicates for Strings.
See also my blog at about the Eclipse memory consumption, where I describe a way to find those duplicates using only the existing MAT features.

You mention LinkedHashMap and that a ConcurrentLinkedHashMap is not available with the JDK.

Note that LinkedHashMap has even a higher memory overhead than HashMap and that at least the existing ConcurrentHashMap has an overhead of around 2 Kbyte when you use the default constructor.

Regards,
Markus

As someone else mentioned, a glaring hole in this article is that you don't mention RDF and SPARQL. If I needed to have this as external data instead of in the language, I would say RDF and SPARQL is the way to do it.

sufis and yogis and meditators beat you to it by a few thousand years, the universe in a grain of sand ..

nice post, thanks

I am reminded of Pick databases (see http://en.wikipedia.org/wiki/Pick_operating_system). I haven't tried it out myself but I suspect that the impedence mismatch between properties pattern and hash-file database (as in Pick) wouldn't exist; it would be a much more natural fit.
Thanks for the time and effort, it was a good read.

This comment has been removed by the author.

Brendan Eich came up with astoundingly clever performance optimization for the Properties Pattern, which he told me about back in January.

Is this the polymorphic property cache thing that Brendan mentioned? I've been waiting to hear about this.

v8's hidden classes are also a pretty neat solution to this.

I want to second the mention of CouchDB; in addition to addressing persistence, they also have a neat approach to the querying issue (map-reduce-combine, basically, which allows them to incrementally update their indexes).

Interning strings is well known to be suboptimal for multithreaded system due to the constant locking and unlocking (and what reasonable application isn't multithreaded these days?) I've only seen profiling data for this in C++, but I suspect it cuts across languages since concurrency isn't a C++ specific problem. std::string is usually implemented with interning, but performance sensitive applications often ditch it for a non-interned implementation for this exact reason. (Hint hint Steve... I wonder if you've seen any code that uses a std::string replacement...)

Have you looked at Persevere (http://sitepen.com/labs/persevere.php) for persisting Property model data? It is similar to CouchDB in it's JSON-based approach, but has much more integration with the JavaScript environment and orthogonal persistence. The class model also preserves prototype-based delegation (CouchDB does not). Plus it is based on Rhino.

The Java Content Repository API (JSR-173) sounds like a good fit as storage back-end for the property pattern. It is mainly used in content management systems, where unstructured data is common. A schema can be defined, but it is optional. Has anybody used it for that purpose?

A nice example of the "Refrigerator" pattern is WPF's usage of dependency properties.

In honor of Hofstadter, it's a self-referential blog entry. Table of contents = Properties pattern.

Thanks, great article!

Regarding takeaways: I feel tha there is a flip side to the versatility argument, namely that once you start using the Property pattern even in a small corner of your system, the pattern tends to spread to other parts of the system in an insiduous, underhand sort of way, which is difficult to control ^^

First of all, yes, please do write more of these long technical posts. Very useful.

Second, if a property list is being used for one part of a system to communicate with another, does anyone have a recommendation for making that safer.

That is, say I'm going to pass an object that, by convention, will have certain named properties. Do I just hard-code the property names in the locations these are set and retrieved, and rely on myself to make sure they stay in sync? Do I have a single location where key shared property names are stored? Something else?

Or is this not a good use for a property list?

"JavaScript permits numeric keys, and allows you to specify them as either strings or numbers. If your object is of type Array, you can access the numeric keys via array-indexing syntax."

I think you mean JavaScript always uses string keys, but allows you to specify them as numbers. You can always access properties you using array indexing syntax, whether or not your object is an Array.

js> var foo = {"12":"baz"}
js> foo[12]
baz
js> var bar = new Array()
js> bar["12"] = "baz"
baz
js> bar.length
13
js> bar[12]
baz

Excellent article. I also concur with those who point to CouchDB, ATOM Pub, and RDF. In one sense, you can think of RDF as named hashmaps, a clear implementation of the "property design pattern."

Awesome. You have given a name to something I've struggled with in several guises. For instance, I tried to write a converter between XML and JSON once, but after a day of struggling, decided that XML's node types made it a fundamentally different beast. I could make it work, but I'd end up with the JSON side having most of the convenience of XML and none of the readability or toolset. Or, I could cripple XML.


@chris: Perl only has the seeds of an object system. Bring your own soil and grow your own! See Class::InsideOut and all the other related modules on CPAN.

Prototype-based inheritance in Python:
http://loveandtheft.org/2008/09/11/prototype-based-programming-in-python/

Also, the Zope Object Database (ZODB) is a 10 year old open source python ODB, that is essentially a persistent property bag store. It works great for many apps, and there is a querying mechanism available (Catalog) to gather up collections of objects.

Kris Zyp mentioned Persevere, which is an interesting implementation of persistent objects using JS. Kris didn't mention that Persevere also supports things like JSONSchema, which gives you the kind of support you get with XML schemas but you can use JSON rather than XML!

Fun post. Thanks!

For further reading (prototypes) also: http://web.media.mit.edu/~lieber/Lieberary/OOP/Delegation/Delegation.html and http://lucacardelli.name/Slides/1996-05%20Class-based%20vs%20Object-based%20Languages%20(PLDI%20Tutorial).pdf

Unfortunately Emacs doesn't support any notion of prototypes.

Sure it does - just cons stuff onto assoc lists. PG mentioned this at the end of Arc lessons.

With regard to scripting languages which offer prototyped-based objects, check out REBOL

Hey Steve, just a quick quibble about your "poor man's splay tree" optimization, where you move elements to the front of a linked list when they're queried.

You suggest that this optimization is essentially free, but there are cases where it may not be. If your property list is being accessed by multiple threads, then this implementation will force many reads (any that aren't reading the first element) to acquire write locks on the list. If the number of threads is large, then the overhead of all this lock contention might well outweigh the benefit of finding your element closer to the front of the list. (At least for shortish lists that are read frequently but written much less frequently, which I suspect is a common case.)

The GEB sections you refer to are nicely available starting at http://books.google.com/books?id=aFcsnUEewLkC&printsec=frontcover&dq=Godel,+escher+bach#PRA1-PA353,M1. In case anyone doesn't have the book handy & wants to follow up.

One important limitation of this technique is that the compiler cannot help you much. Consider what you could lose here: compile time type checking, variable and method name checking. When working with plists, for example with GTK's GObject system, all these things bite with depressing frequency. Automated help to spot with dumb typos is a big thing to lose.

Words fail me to express my gratitude. Time and time again I hear that "reading other people's **code**" is one of the top ways to improve your own code.

This article made me feel as if I had spent time reading your code. This is remarkable! It is as if I read your code, without the hassle of downloading and compiling it and configuring a suitable environment in which to step through it. I was able to get a sense for how you approached your design and what thoughts guided your decisions as you laid down source code.

To echo others: yes, please do write more of these long technical posts. Very useful.

I would say that your "transient property" example was really an example of a data type which included a schedule. After searching for your property by name, you should also search within the schedule by time. You can delete historical garbage from your schedule, when its convenient (for example, when serializing to disk).

If you do things this way, you do not have to worry about corrupting your permanent properties with your transient properties because the transient aspect is permanent... well, temporarily at least.

Note that this also can be made to support non-overlapping durations (but, of course, each conflicting duration adds some fragmentation to your schedules so of course you probably should not go overboard).

Aren't transient values a case of a specialisation of the original object? Eg. couldn't you just create a new object with the original object as its prototype? Of course, if the original object is an entity (And it seems to be the case in your example), you would have to separate the identity from the values. So you get:

// Initial object
willy_the_wizard = {
name: "Willy",
attributes: {
magic: 0
}
}

// temporary change
willy_the_wizard.attributes = {
prototype: willy_the_wizard.attributes,
magic: 30
}

I'm surprised that you list Javascript as the "epitome" of prototype-based languages. While influential, it's far from the most extreme implementation of the concept.

I think you'll find that Io language (http://www.iolanguage.com) overwhelmingly makes Javascript look positively rigid in comparison. It offers EVERYTHING that Lisp offers, PLUS prototyped objects.

Strongly recommended.

Yes, you could create a new object, but why would you? (I am not asking that rhetorically, I think that that question is crucial in any design.)

Also, your new example object does not include any implementation of the transient character of this property, and instead implements the "Refactoring to fields" pattern without any hints as to why that's good in this case.

I would call this object design bad (lossy, mechanically complicated and obfuscated). Having a separate "transient property list" was better, in my opinion (that approach is still lossy but is safely lossy and also reasonably transparent in the sense that the abstraction accomplishes something useful).

Interestly, LambdaMoo (http://lambdamoo.org/) is also designed under similar lines. I'm surprised you didn't look at it when designing Wyvern.

Thanks for the reading. I would be very pleased if you posted the other half you killed!

JFTR, it great to know this kind of approach. Recently I was trying to design a Magic:The Gathering game. The experience was painful: all I got thinking was how do I design this such I can put a spell over a creature but at the end of the turn it goes out? or things like how will I keep on the cards and their skills?. My excuse may perfectly be that I am only an CS undergrad but this is just a great idea.

A similar property-list key-value based model is used in the emerging XAM object storage standard from SNIA.

http://www.snia.org/forums/xam/technology/specs/

In this storage model, arbitrary typed values can be attached to string names and persisted as collections. An integrated SQL subset provides searching, and you can create dynamic structures by referring to other objects by the returned object identifier (XUID), allowing replication of many pointer-based techniques.

This storage model offers many interesting opportunities for object-based storage, and I'd encourage you to take a look at the specification.

Steve, what do you think about about Tcl?

The concepts behind the language are very easy to understand. It's got a precisely and concisely documented standard library. The Tcl book is very good also. And Tcl has a very efficient architecture to enable embedding and to expose your C/C+ objects as Tcl objects.

If only browsers allowed multiple scripting languages ...

"And JavaScript is one of the two best scripting languages on the planet, in the most correct sense of the term "scripting language": namely, languages that were designed specifically to be embedded in larger host systems and then used to manipulate or "script" objects in the host system. This is what JavaScript was designed to do. It's reasonably small with some optional extensions, it has a reasonably tight informal specification, and it has a carefully crafted interface for surfacing host-system objects transparently in JavaScript.
"

Good post on a topic close to my heart.

I found lucene and its ilk to be a great fit for the query requirements of property based systems. The clob + key reside in the rdbms and all/most fields indexed in lucene. the databse only providing for load/store and lucene used for querying both cross field google style and field specific select style. fast reliable and fun.

Another way to optimize property access would be hidden classes:
http://code.google.com/apis/v8/design.html#prop_access

Of course this is only possible when you're writing your own compiler.

"My early experimentation yielded the interesting rule that non-numeric transient properties override the persistent value, but numeric properties combine with (add to) the persistent value."
In a functional language, transient values could be expected to be functions that take the original value as a parameter and return a new one.

In Haskell, examples for such functions would be:
\str -> "I override the old string"
const "new string" -- same as above

\str -> "I am prefixed " ++ str

\num -> num + 1
(+1) -- same as above

\num -> 1 -- set to 1
const 1 -- same as above

Lotus Notes follows this concept fairly closely, I believe. A Notes "database" contains Documents which are essentially plists. A Document can be based from a Form which is the equivalent to your object plist. You can arbitrarily add and remove properties to Documents, iterate the properties on a Documents, etc.

This unstructured un-schematised collection of properties, prototypes and metadata can very quickly result in an undocumented soup. Its great for a single programmer or a small team of programmers, but can you image trying to figure out the behavior of a legacy system where a property can be added to or removed from a thing from just about anywhere.

Thanks for the article. It jives a lot with a similar system I was building (in Ruby).

There's been some work at creating a Property-based system sittong on top of a RDBMS database. Check out ThingDb. It has the concepts of attributes as database rows. It also adds versioning and author semantics. Definitely worth a check. ThingDb.

The hardest problem I had to do deal with has been 1) transient and 2) nested properties.

In your example, how do you handle the semantics of a "magic potion" that wears off after 2 turns, or transients that have different semantics than "adding if they are ints" or "replace if they are strings". I have tried defining these modifers as first class objects called "Effects" or "Modifiers". In addition to a "parent" link, they would have a "target" link that defines the object they are modifying. However, it still has some problems. How do you handle the case of the "delete"? And, when the property is deleted, we need to make sure the object still has it's previous setting.

For transient properties, wouldn't it be easiest to add function instead of a value. The function would be a closure of the form "getvalue() { return time() < expires ? value : undefined } or somesuch.

Theres a host of issues with this approach, in that the expiry time isnt accessible as metatdate, but it does illustrate some of the issues with the property/metadata approach. i.e. you can have all the metadata you want, but unless something is paying attention to it, it matters not.

My comment on how this related to epistemology:

http://curi.us/blog/post/1339-steve-yegge-on-epistemology

I've been thinking now for some time about a variant of the Properties pattern in which the property names are not interned strings but are themselves property bags, so each property itself has an extensible set of properties, including its name. In that way we can distinguish between cases in which properties of different objects are really the same property, and when they just happen coincidentally to share a name. For example, a book has an author property and a title property. The author in turn has a name property, and the name has properties like firstName, lastName, and title (Mr., Ms., etc.). It's just a coincidence that the title of a book and the title of a person have the same name, and in this variant of the model they are represented by distinct property objects.

I also add to this the notion that the properties form a hierarchy. For example, an object named Fido (that is, whose name property is the string "Fido") might have the boolean property isDog. Because isDog is a subproperty of isAnimal (a fact recorded by the properties of the isDog and isAnimal property objects), it is also the case that it has the property isAnimal with the same value as isDog.

Finally, I thought I'd mention that Self, unlike Javascript, allows multiple prototype objects. Different versions of Self experimented with how to handle inheritance of the same property from more than one parent; the final decision was to disallow such conflicts. An attempt to get the value of a property with a conflicting definition is an error.

Grabbing on to a little side issue - backfills. Very interesting. My experience has been that you can't make systems perfect up front as well - at FastMail we use Cyrus for our email backend store, and we have a whole stack of subsystems which exist only to check for "bad data" and either let us know or silently fix it.

Even the "let us know" tends to be emails in a known format, which there are then tools which can log in to the mailbox, read the notifications and spit out some suggested fixes and the command lines to copy-and-paste to do them. A common fix-it-up pattern is "./fix-stuff.pl | less" followed by "./fix-stuff.pl | sh" if it all looks sane. You need that sort of automation once your dataset gets big - and stuff _will_ corrupt, in all sorts of interesting ways.

Steve Yegge is a Strange Loop. In a Good Way.

And the next (read: "first") computer language I design will include first-class support for JSON.

Great post and very much along the lines of what I've discovered in designing my own complex (primarily game-related) systems.

One further step that I've taken - slightly tangential, but it seems to play nice with property-heavy systems - is to encapsulate as many finite states as possible within their own objects.

I too have dealt with lots of transients, and my best current solution for taming them is to keep them in the background, slightly bottlenecked, and sliced up into small classes that are easy to compose. This makes it easier to isolate all of those bugs, as I can just turn each class on and off and watch the effects. In theory, it also means better reusability for each form of state.

Great article. I don't think it was long enough :) A lot of what you said resonates quite a bit with what I've been working with the last 7 months at 10gen, namely an app server that among other languages, supports server-side JavaScript as a first-class citizen, as well as a persistence store (called Mongo) that works with JSON-like documents.

We do serialize into a generalized binary format (we call it BSON), because the persistence store is intended for general use - we want it to be easy for languages other than JS to work with it.

I think that your suggestion of compression is interesting - it's a trade-off between storage and network vs query performance, and I'm not sure if I'd make that trade. Clearly there are field types (say a video) that you'd want to store compressed. Maybe the solution is to store compressed, and maintain a per-document set of de-compressed fields, lazily adding to the set when you see those fields used in a query, or be eager - maintain a list of fields that the DB has seen in queries on a per-collection basis, uncompressing those on each insert/update so query time is stable. Hard to say.

I think you're right about hierarchical queries - the documents are hierarchical and thus the query language has to be. Because I've been so non-XML document focused, I never thought of XQuery or XPath. I'm a Java Weenie, and tend to fall back to the kinds of QL you find in JPA - SQL-ish but with predicates that allow object hierarchy navigation ("... where a.b.c = 2"). I think that such approaches will contribute to whatever the end-solution is for us, but right now, we're structuring the query "selectors" for Mongo in terms of documents themselves. Eg:


db.mydocs.find({name:"geir"});

which on the positive side is a really natural way to work with the database - you can think in documents for querying. On the negative side, a moments thought will reveal the hornets nest of challenges that come with such an approach. Still, the model is evolving - we're learning quite a bit every day - but it's been effective so far so we think we're on the right track.

Anyway, thanks for the article.

geir

An important aspect of this that goes undiscussed is changes to the parent object. Emmitt Smith is a fast runner (speed: 10). L.T. is like Emmitt Smith, but also catches passes (parent: Emmitt Smith, passcatching: 10). Now what happens when Emmitt Smith gets old and we reduce his speed to 5?

The answer is that L.T. got slow, too. Unless you didn't want that sort of thing to happen, in which case you had to do a deep copy of everything out of Emmitt Smith when you created L.T., which makes the whole parent link pointless.

Or am I just completely misunderstanding how the parent relationship is supposed to be used (entirely possible)?

For Perl implementations see: Class::Classless and Class::SelfMethods .

Blogger 12challenge said...

An important aspect of this that goes undiscussed is changes to the parent object. Emmitt Smith is a fast runner (speed: 10). L.T. is like Emmitt Smith, but also catches passes (parent: Emmitt Smith, passcatching: 10). Now what happens when Emmitt Smith gets old and we reduce his speed to 5?

The answer is that L.T. got slow, too.
Or am I just completely misunderstanding how the parent relationship is supposed to be used (entirely possible)?


Your logic seems solid. Exception logic to deal with 'reduced' property values seems like a kludge to me. (If reducing, go look for inherited values? Yuk).

Define inheritance as being time bounded until the ancestor value changes? Then break the inheritance perhaps?

DaveP said...

Define inheritance as being time bounded until the ancestor value changes? Then break the inheritance perhaps?


Yeah, I was thinking about something like this, but then the parent object has to maintain a list of all objects that inherited from it, in order to update them. They, in turn, have to notify the parent when they are deallocated so it can remove them from its list.

Seems like a lot of overhead. But Stevey seems pretty sold on this stuff so I'd love to get more explanation from him.

I believe Damien Conway called “Refrigerator” “Inside-out Objects”.

For him the main motivation for this solution was encapsulation (something you don’t get from more conventional Perl OOP), not performance optimization. Discussed in details in Conway’s book “Perl Best Practices”.

I actually like the fact that you write long in-depth articles. I feel like do a good job of covering the topic without being to verbose and to vague.

Jeff Atwood may complain about the length. But I feel he often writes articles to meet his quota of articles per week. A lot of the articles have very little to do with Computer Science.

I also get a little annoyed with his Windows advocacy. Sometimes it seems he bashes other OSes to drive traffic or increase the amount of comments he has.

Please keep up the great blogs/articles. If you ever quit Google maybe you should think of teaching or writing articles for magazines like Dr. Dobbs.

Can you make sure your program doesn't allow L.T. to hurt his toe or grow old?

You've just re-explicated the primary reason that Lisp was originally used for "undefined" problems like AI: its lists (including property lists) could be used in a "big ball of mud" fashion to model nearly anything, with no formal data structures in sight.

Seems like this crucial insight has nearly been lost in recent years and in recent language designs.

Steve, I don't quite see how the Properties Structure or the Prototype Pattern simplifies Dependency Injection (DI) or unit-tests. We know DI simplifies unit-tests.

As I understand it - DI is about "not" constructing object-impls directly - thereby allowing unit-tests to swap out these impls. Are you saying all references between objects will be to a generic PObject (e.g GameObject) and so substitutability is always possible? - but without DI - objects would still be forced to directly construct the PObject they desire thereby defeating the purpose.

However, I do like the idea of fully-typed Java-Beans (with all the getters & setters) using an underlying Properties infrastucture - would be useful for instance-level inheritance (Prototype) which has always been a wish of mine. I also wish Java would support it directly somehow - perhaps with syntax like 'super = someObj'.

Great post! I wrote about prototype inheritance in JavaScript and ActionScript recently, but I did not think to relate it to GEB!:

http://nodename.com/blog/2008/09/19/dynamic-programming-in-as3/

Sony Mathew says "However, I do like the idea of fully-typed Java-Beans (with all the getters & setters) using an underlying Properties infrastucture"

Windows Presentation Foundation has a property model underlying it, though its wrapped with strongly typed objects. In effect, for each property of a strongly typed object, there is a getPropertyValue and setPropertyValue call going on underneath.

Great post! Thanks! I hope the other half you deleted still exists in some form of buffer. Can you post that somewhere?

I think one of the earlier commenters sorta said this, but mightn't you want some extension to your API that lets the programmer declare a property name, optionally together with its value type? Then one's framework could at least raise an exception when assigning a value to an undeclared property (likely spelling error) or when assigning an ill-typed value (likely turning the object model into a mess)?

If one had a Lisp-style development environment (where one is entering code in the context of a running system), I suppose one could even get some correctness checking at compile time.

Python also allows unquoted keys in dictionary construction, although you have to use the explicit 'dict' constructor, rather than the usuaal '{}' syntax:

person = dict(
name="Bob",
age=20,
favorite_days=['thursday', 'sunday']
)

> Interestingly, in big companies I've worked at that have strong schema constraints, they still always seem to run into data-integrity problems, so it's not clear how much the schema is really helping here.

When the data integrity problems come from code changes, those problems typically come from a lack of normalization, ie, the system is such that some facts are expressed in multiple places.

In fact, a huge fraction of all bugs are due to a lack of normalization. Count them some time.

An interesting fraction of the features of programming tools (broadly defined) are aimed at the consequences of a lack of normalization.

The "Refrigerator" pattern is used in Java and .NET to implement the Monitor pattern - not every object needs to create synchronization primitives such as a mutex and a condition variable just in case, if it's about to be waited on, or notified/pulsed, so these are taken from a pool and associated with the objects on a as needed basis.

An important aspect of this that goes undiscussed is changes to the parent object. Emmitt Smith is a fast runner (speed: 10). L.T. is like Emmitt Smith, but also catches passes (parent: Emmitt Smith, passcatching: 10). Now what happens when Emmitt Smith gets old and we reduce his speed to 5?

The answer is that L.T. got slow, too. Unless you didn't want that sort of thing to happen, in which case you had to do a deep copy of everything out of Emmitt Smith when you created L.T., which makes the whole parent link pointless.

I think that you just have to model your specific needs differently. Suppose that we model Emmitt Smith so that we're capturing something that is fairly static, it would change in only small ways, and broad changes (such as an unfortunate accident in which his leg falls off) are modeled as descendents of E.S. You might record "mobility challenged Emmitt Smith" as a diff against plain old "Emmitt Smith".
Taken further, since inheriting from E.S. is fairly quick, you might say that all changes to E.S. produce a new generation of him.
I think I'll leave the issue of updating references (or not) until after I've had my morning coffee. :-)

Re the CORBA folks using XML for interface resilience: note that they still need to deal with all of the same issues that the type system was forcing them to face, except that now those issues are implicit in the actual real-world use of the protocol between client and server, rather than embedded in the type system.

Great post, and many ideas reminded me strongly of NewtonScript.

It has nowadays also a cross-platform port in case you don't have a Newton lying around :)

Jacob O'Reilly,

I see how you could make that work, but it implies that as soon as you derive L.T. from Emmitt Smith, you need to freeze Emmitt Smith and use only copies of him if you need to modify him.

Alternately, instead of deriving L.T. from Emmitt Smith, you could have a JustLikeMe() function. LT=EmmittSmith.JustLikeMe() would create a new object with the same parent as Emmitt Smith (Running Back) and assign it all the same specific values as Emmitt Smith (speed:10). Then you're free to modify Emmitt Smith or L.T. without either running over the other.

But either way you seem to be creating a strict separation between prototypes (classes) and specific examples (instances). This seems to negate the whole "generality in the specific" principal that Steve's basing this whole thing on.

Another variation on the theme. Naked Objects!

They look like nested property lists, but with the added behavior that each property has it's own kind of editor / UI.

It extends the Property-model and adds the tool set right on top of it.

http://www.theserverside.com/tt/articles/article.tss?l=NakedObjectSeries_1

(Wondering if Blogger will flag the naked in my URL, hehe).

I love your post, and the prototype pattern. Actually I have been using it for some design recently. Interesting thing I came across is that the cross-referencing (I called it this anyway, I am sure it's not a terminology). Two prototypes could cross reference each other in their properties, which officially breaks the parent-child relationship. We could certainly extract another common property set out, but it doesnt always look intuitive. This pattern seems to be more suitable for loose-coupled systems, which might explain the flexibility to extend by end user.

Another example I consider as a close match to this pattern is web url itself. Consider every url is a key, which could be used to retrieve the value - web content blob. A website contains a number of these properties, and the way the cross reference is done between url and content might give a different idea of implementing this pattern - reference to key(s) in values.

12challenge,

I think perhaps that what you're representing in your prototype model might not be Emmitt but something more abstract to begin with, such as "great football player", something that generally doesn't change a huge amount. When someone refers to this other player and compares them with Emmitt creating that map, you might set their prototype to be Emmitt, or you might instead link them against the more general "great football player" instead of Emmitt.
I was thinking of a more hybrid approach, whereby you would link L.T. to Emmitt but as your map evolves and you develop a more specific view of Emmitt and a more general view of a great player, you might have cause to reevaluate L.T.s prototype to the more general "great football player".
I think this example is a little difficult to put in concrete terms because I doubt many of us have a need to handle such abstract concepts in code. However, the data structure required is simple so long as you can adjust your prototype dynamically. (And you don't assume the algorithm for when/how to remap prototypes is instrinsic in the structure!)

i'm probably missing something, but what is so terribly difficult about modelling the property pattern using the relational model? it seems like a natural fit to me. Example model:

PLISTS
plist_id property_name property_id

INTEGER_PROPERTIES
property_id integer_value

STRING_PROPERTIES
property_id string_value

PLIST_PROPERTIES
property_id plist_id

PARENTS
plist_id parent_plist_id

if your DBMS allows union types, then you can replace INTEGER_PROPERTIES, STRING_PROPERTIES, and PLIST_PROPERTIES with a single relation. Otherwise, you use a UNION clause in your query.


Admittedly, this sort of schema requires rather difficult or impossible SQL queries to deal with, but this is really a weakness in SQL, not with relational modelling.

But again, I'm probably missing something obvious that means this is more difficult than I think.

"to keep this article tractable, I had to delete several pages of detailed examples, such as "Chieftain Monsters" that could be programmatically constructed by adding a few new properties to any existing monster"

Nooooo!

Screw tractable, I want those examples and the extra content! How about an "extended version"? Pretty pleeeease? :-D

I want to second Jiayao's comment - please post the part you deleted!!

I am especially interested in the design issues you had in using this pattern in your Wyvern game. I'm designing a python based engine for Magic the Gathering, a collectible card game where the game pieces can override the properties/rules of other pieces and the game, and I've found that my approach is similar to what you've described here, although not so formalized. For example, how do you track multiple transient changes that have different expirations? Obviously, if a later change expires before an earlier one, the earlier value should then come into effect, so you need to stack them in a way where you access the most recently added one.

+1

Please give us the Director's Cut (the missing 50%).

Very interesting read (so far).

+1 for "Object Thinking" by David West.

This might be a good idea, but you need to learn to tell it in fewer words.

This comment has been removed by the author.

Really great post. I wish I could write like you.

Do you, by chance, know good reading on the plist persistence aspect? Often blobs are not an option and we are forced to put all our data into tuples containing primitive types.

Great blog entry, the bits on Wyvern were especially interesting. Considered writing an entry just concerning game development?

Since no one else has commented on it, I'll be the pedant to point out that carrots do not, in fact, improve your vision.

Modern browsers do support arbitrary attributes. Maybe you mean something specific that I'm missing. The following document does work in Firefox and Safari, alerting "abc".

<html>
<head>
<title>Test</title>
<script>
var d = document;
var test = function() {
var div = d.getElementById("demo");
div.bar = "b";
div.setAttribute("baz", "c");
alert(div.getAttribute("foo") +
div.bar +
div.getAttribute("baz"));
}
</script>
</head>
<body onload="test()">
<div id=demo foo=a></div>
</body>
</html>

As well as Douglas Hofstadter, Steven Pinker is also very much worth a read.

Interesting synchronicity!

I recently had a conversation with a friend who works with the non relational database M204 which is for very large scale datasets.

It make use of Entity Attribute Values.

http://en.wikipedia.org/wiki/Entity-attribute-value_model

Editorial note: the man’s name is Damian (two As), not Damien (with an E).

Also, the implementation technique you call “refrigerator” is known as “inside-out objects” in the Perl world.

Chris Ryland said... You've just re-explicated the primary reason that Lisp was originally used for "undefined" problems like AI: its lists (including property lists) could be used in a "big ball of mud" fashion to model nearly anything, with no formal data structures in sight.

And since JavaScript shares this trait with Lisp, I'm wondering why no one has thought about AI programming in JavaScript.

And since JavaScript shares this trait with Lisp, I'm wondering why no one has thought about AI programming in JavaScript.

Well, there was no Javascript back in the 60's through the 70's at the peak of the AI craze, but even if there were, Lisp also had the killer feature that no other language has to date: programs are data. This one fact enables things like macros, like building code to be executed dynamically, etc.

Plus, only in the past few months has Javascript performance started to actually rival serious programming languages. Lisp has had optimizing compilers for decades.

Just some points.

Chris, I think you need to work on the accuracy of your dates.

Also, I can find examples of people using or talking about using javascript for ai (using google).

I knew I was in for a long read when I saw the index and I was not disappointed. Every minute I spent reading this was worth it.

I'm actually working on developing a game of my own. Partly for fun, partly to learn, partly to get my own ideas of an awesome game out there, whether it's been done or not. I will be using properties for just about everything now.

Thank you for setting me on the right track.

Hmmm, nicely written article.. but sorry, not convinced!

Firstly, WRT inheritance: its fiendishly difficult to keep a mental image of a prototype based system where properties are being modified/read/inherited all over the shop. Especially objects that reference prototypes which mutate their properties over time. Emmitt Smith suddenly loses his "great speed and balance" - does L.T?

Secondly, WRT multiple inheritance: The situation is even more confusing.. What if the announcer has said: "L.T's catching skills are like Emmitt Smith and Walter Payton combined!" now what...

No, give me:

+ interface
+ composition
+ delegation (to composites)
- inheritance

any day of the week.

Sam

@Sam: Hey there! Your objections are reasonable, but I wonder how much they stem from being 'stuck' in an object-modelling mindset - seeing every design problem as a nail to which our familiar tool should be applied.

We've all done lots to explore and familiarise ourselves with the situations where object modelling works well. And we've probably grown to subconsciously avoid the areas of design where it doesn't work well.

Maybe the 'universal design pattern' (bad nondescript name!) idea needs some time to bed down in our conciousness before we can truly evaluate the areas in which it excels and should be applied, versus the areas in which it doesn't work well and should be avoided.

It crosses my mind that any dynamic language, in which classes are amenable to change at runtime, then the inheritance tree of the classes themselves become an example of this design pattern in action. Base classes are the parent container. Class-level attributes are the key-value mappings. Inherited classes may add new class level attributes of their own, but otherwise inherit those of the parent class.

In Python, access to class attributes defined on a parent class are looked up dynamically at runtime, first by searching the class itself, then its parent classes, so changes to the parent class would be inherited by all inheriting classes.

I also had some objections to some of this blog rant, but i now realize that I was objecting to something that might solve this inheritance issue.

Stevey's design had a careful barrier between permanent features of an object and temporary features. Object based property inheritance presumably only worked on the permanent features.

This binary treatment of time has limitations (which was the basis of my original objection) but does seem to address some of these other concernss.

In what sense is it helpful to think of a map or array as a surjection? What codomain does a map imply, and how does a map span the whole thing? Does the codomain change whenever we put() or remove()?

It might be more apt to consider a map to be just a function, without mentioning jectivity, but I don't really see what that gets us pedagogically. As others observe, the difference between the prototype pattern and OO or indeed any style with side effects is one of perspective. Namespaces, they're honking great!

Tartley,

The minus sign in my previous comment should hopefully show that I am far from being in a typical "object-modelling mindset".

I believe inheritance should be discarded. All behaviour should be implemented though composition of reusable components, with interfaces and delegation to provide polymorphism.

But I digress.. my immediate argument here is that prototype based modelling will end up a mind-numbing mess of inherited properties very quickly. Let's see.. a donkey is a bit like a horse, but maybe the size of a cow, although its ears are sort of rabbit-like.. hang on who just made the horse able to jump that high, all my donkeys are escaping!

Sam

This pattern is not just useful in game programming systems. It's incredibly useful in any place where you want enormous run time flexiblity and uncertainty of what will constitute your object at the time of creation.
An example, in financial applications, where every system is adding a bit of its own enrichment to some order a client has placed, such a system is incredibly useful.

Also, I find this pattern incredibly useful in databases too. Whenever I have to model base->derived classes, instead of a table per derived class, i usually end up with a instance-property table mechanism. i.e. I have a table where the instance of the object is captured, and all of its properties are captured as name value pairs in a child table with the instance id as foreign key. With this mechanism, the schema is stable but you have enormous flexiblity in what you model. For all the nutty people out there who get hung up on type safety, i find it useful to make views per derived class. This keeps them happy, and me too.

Thanks for the article.

"If you think about it, Arrays and Maps share the same underlying formalism (a surjection, not to put too fine a point on it), and in some languages, notably PHP, there isn't a user-visible difference between them."

I think Lua is the most notable example:

"Unlike other scripting languages, Lua does not offer an array type. Instead, Lua programmers use regular tables with integer indices to implement arrays." (The Implementation of Lua 5.0)

Until 5.0, arrays were stored in regular hashes.

There's an interesting example of the property pattern that you didn't mention, but which is quite familiar: Lexical scoping. Any given scope has a set of symbols and their meanings, some of which are local and some of which are inherited from higher-level scopes.

I recall thinking about this at one point when considering TeX-like langauges. These have a couple of interesting variations on the usual property pattern: There is generally only one scope active at a given execution point, and so the dependency chain is a straight line, but it tends to be painfully deep when metaprogramming is involved (much deeper than would be typical with a C program, for instance). Values can be changed at either the current level or the base ("global") level, and thus some optimizations to avoid having to backtrack values all the way up the chain seem quite important. I did a bit of thinking about how to do that effectively, and tried to follow how Knuth did it in TeX, but never really got very far with it.

Hey Steve,

very very nice post. For an interesting use of the prototype pattern in conjunction with class based programming you might want to check out the JS meta system Joose http://code.google.com/p/joose-js/

It allows going back and forth between classes and prototypes using the detach method that is present in all objects.

One interesting choice for storing the data might be something like the "network database" Neo.

It stores objects with properties and their relations to each other. It also allows querying the network by properties and relationships.

Thank you for this post. I found it very inspiring and well worth a read. I'd like to see more posts like this!

@12challenge:

"Yeah, I was thinking about something like this, but then the parent object has to maintain a list of all objects that inherited from it, in order to update them. They, in turn, have to notify the parent when they are deallocated so it can remove them from its list."


That idea is at the heart of a toy system I'm working on which I think has a lot of potential. Yes, it's a lot of state to maintain, but when it comes to distributed Internet-based systems, you end up reinventing such publish-subscribe tracking manually anyway (in things like web proxy caches and RSS subscriptions and mailing list servers in the large, or signal/slot GUI widget systems in the small).

I'm thinking about systems like Cells, FrTime and Flapjax which are coming from the 'functional reactive programming' paradigm. If we mix this with property bags, I think we can get a truly universal, fully pure-functional, compute/store/distribute framework.

not sure your use of the term “modeling” is correct in some technical sense. It is useful perhaps in conveying your enthusiasm for prototype based lang.

For example, if you look at Wikipedia, here's some standard meaning of modeling:

http://en.wikipedia.org/wiki/Model_theory
http://en.wikipedia.org/wiki/Mathematical_model
http://en.wikipedia.org/wiki/Computer_model

for much more, see:
http://en.wikipedia.org/wiki/Modeling
under the section “Abstractions, concepts, and theories”.

none of them are exactly as you described by a list of specific “models” you speak of.

Further, looking at your list of models:

• Class Modeling
• Relational Modeling
• XML Modeling
• Other Schools (functional, logic based)

...

now, Relational modeling really covers class modeling, becausec classes, in java, is a a hierachy (i.e. tree), and a tree is just a specific type of relation. (another word for “relation” in math is a graph, or network, of which tree is just a specific type) Now, consider other OOP langs that has multiple inherence, then it's basically a graph more complex than tree, but still a relation.

Then, XML is really just a tree. So, XML and Java is pretty much the same with respect to their “modeling” structure, namely a tree. It's kinda odd you mix them in the same context and call them modeling. OOP in general is a programing paradigm, while XML is mostly a inert data structure. Both are trees. In their different ways, you could call each modeling. But to list them together as different types of modeling is odd, because in one sense both of them are really just trees, and in another perspective one is a programing paradigm, while xml is just a data representational structure.

in summary, i find your list of different school of modeling is rather a mismash of elements. The Class Modeling, XML modeling, are really just different aspects of Relational Modeling in sa far you call them “modeling” ...

Am not trying to pick bones about terminologies, but the term modeling, in general describes methods to emulate problem or system. The only proper use of the term modeling in a strict sense, are those under Wikipedia's description of “Mathematical Modeling”. They can be classified in several ways,... e.g. statistical, neural networks, cellular automata, probabalistic, determinsitic, algebra based, ... there is no one classification system ... rather, like all the branches of math, how one classifies them depends...

You say that OOP is not popular with academecians due to it not having a mathematical basis... although i do see what you are saying, but to say that is kinda odd because strictly speaking nor any functional programing lang or program written in functional programing paradigm has any mathematical basis (except those langs or software that are meant to be proof systems, e.g. coq). Functional lang or software has math basis only in a rough sense, and so does OOP has mathematical basis (e.g. as state machines).

Then, in your section “Finding the sweet spot”... i find it quite fuzzy, similar to as discussed above about the use of the term modeling. For instance, how about a school of modeling using cellular automata? statistics? genetic programing? Broadly, these are important modeling methods. They are far more so considered as a modeling method than XML or OOP would be considered as a modeling method. And any of these modeling method could be implemented in most langs, in Java (OOP) or Haskell (functional), Perl (procedural), for examples.

Since you list XML and OOP as modeling, then what about pattern matching in functional langs? if XML and OOP are considered as a schools of modeling, then pattern matching, term rewriting languages/systems, should also be one of the “school of modeling” in the context of your article, as well as quite a lot others... (say, list/array processing or progarming langs (lisp, apl, matlab).

----

In your subsection “BRANINS AND THOUGHTS”, you wrote:
“Douglas Hofstadter has spent a lifetime thinking about the way we think. ...”. I think you gave too much credit to Doughlas and his rather pop book “ Gödel, Escher, Bach”.

In the same subsection, you went on with 10 or so paragraphs describing “prototype modeling” using football player as analogy. I feel that you went too far and fuzzy. I mean, the same football player scenario can be worded so that it fits in some functional modeling paradim or OOP paradigm or logic paradigm or patter matching paradigm.

For example, the announce introduces a football player “L.T.”, oh then i thought it's a pattern that matches the general pattern of football player. As the announcer give more detail, i realized it's a more specific pattern. Then when the announcer introduced another player, i realized it's a pattern that matches “L.T.”. So, pattern matching is the all important modeling technique in human thought!!!

So, in summary, i feel that this is too fuzzy to be meaningful. It's almost like word play. One can paraphrase it to fit into any “school of modeling”.

As another argument... prototype lang like javascript is merely a slightly different way to do OOP. I can't see a precise formulation in the context of your blog to say that one is different than the other as a modeling system. Not quite sure how broad or specific you mean by prototype modeling neither. In functional lang, you can just have functions with local persistant vars that are var/value pairs, or as you say in lisp with its “properties” facilities to symbols.

The above is my first impression in reading your article up to and include the section “Eclipse”.

--------------

As i read the section “Javascript”, “Wyvern”, “Lisp”, “XML Revisited”, the context of your discussion of “model” and property based model becomes clear. Effectively, in my view, the talking about different school of modeling is merely a rough intro. The meat is really just about the propotype design pattern as a programing paradigm, in particular, as in Javascript or a function/item that contain a list of var/value pairs that can be inherited. You think that this paradigm is very useful.

By now i spent maybe 1 hour to read the above parts of your article and wrote this post so far. I just scanned the rest of your article, which go over some concrete details and issues about this paradigm.

----------------

In summary, i like this blog more than your other blog entries, because in other you often ramble in many directions with fancy made-up stories and liberal use of informal writing style (like: haha gocha! doh, bah! don't apologize!! Tell Fred i still like him.). (i particularly find the informal touch distracting) This blog is rather concrete and direct, apart from a relatively short and fuzzy intro about “schools of modeling”.

I think, if the title of the blog is changed to “how i love prototype based paradigm” or “the usefulness and issues of prototyped paradigm”, or “prototyped paradigm as a programing pattern”, would be more fitting, as opposed to Software Modeling. I just noted that your actual title is “The Universal Design Pattern”, ok, that's fitting too. Personally i find the term “Design Pattern” despicable (and i find the classic book Design Patterns by the “gang of four” as pure garbage (see this rant: “Why Software Suck” at http://xahlee.org/UnixResource_dir/writ/why_software_suck.html )). To use “universal” as a adjective for the prototype paradigm/“design pattern” i think is a bit zealous.

overall, interesting article. Thanks. (i wasn't gonna read it but scanning the modeling intro got me started bitching) This post is just my rambling of impressions.

Xah
∑ http://xahlee.org/

☄

Xah Lee, I have not fully studied your response yet, and might have overlooked some gems of thought. However, I think that you are talking about a very different level of abstraction than Stevey was talking about.

Rather than go into details, I will suggest that you are thinking of modeling different kinds of systems than Stevey was thinking of.

this link:

http://steve-yegge.blogspot.com/2008/10/Missing

from Missing keys in ToC is broken

This is an amazing article; I just got around to reading it. For the people who complain about "typos" showing up in key names, causing a new key to be created instead of reassigning an old key, there's a simple psychological solution.

Instead of just having the method "setProperty(key, val)", also have "bindAndSetProperty(key, val)". Only this later method can be used to create new keys, and the former method will raise an error if the key is unknown. The longer name will discourage it from being used as much. This api mirrors Scheme's usage of "define" and "set!", which also helps accidental typos.

Quite surprised you didn't reference the obvious. CouchDB is an apache project and you only refer BDB. DB2 is the industry leader in XML databases an I know people that left oracle and sybase cause it couldn't handle the amount of data they needed.

So why the Oracle fixation? At least you could have referred both alternatives.

This was a nice article, cleanly written and well argued. And the pattern seems to have wide applicability.

I saw that Ranga Blogger had mentioned Tcl. As this is my language of choice for many purposes, I went ahead and posted an implementation of the Prototype Pattern on the Tcler's Wiki. By the next morning a much tighter version had been posted (using Tcl 8.6). To get an idea of how compact Tcl can be and its flexibility (you can define new control structures easily), here's the implementation (the tighter one, by a better Tcl programmer than me):

oo::class create prototype {
variable state parent
constructor {{parentObject {}}} {
array set state {}
set parent $parentObject
}
method get name {
if {[info exists state($name)] || $parent eq ""} {
return $state($name)
} else {
return [$parent get $name]
}
}
method put {name value} {
set state($name) $value
return
}
method has name {
if {[info exists state($name)]} {
return 1
} elseif {$parent eq ""} {
return 0
} else {
return [$parent has $name]
}
}
method remove name {
unset state($name)
}
}

It was definitely more work than my typical posts, so if it doesn't go over well, I'm happy to go back to the comedy routine.

Please don't. I love this post very much. And I'm translating it to Mandarin. The first round is over. But still needs more rounds to polish.

Thanks for the essay. :)

>The concepts of OOP stem not from mathematics but from fuzzy intuition.

Didn't a major portion of OOP stem from AI? Marvin Minsky's frames and Alan Kay's doctoral thesis and such?

Indeed this was a good read. It's incredibly amazing how involved this system structure is with many other languages' framework libraries. And now that someone has put a face on the practice I personally have almost (unknowingly) always used, I'll likely recognize it more for what it is than for generalizing it as another pattern that doesn't quite fit the description.

As it happens, Java will finally get properties attached to arbitrary classes, through java.lang.invoke.ClassValue. (You can find the JavaDoc for it here: http://cr.openjdk.java.net/~jrose/pres/indy-javadoc-mlvm/java/lang/ClassValue.html).