## Categories, the homemade object system

Recently I posted a blog entry about some work I was doing on a novel object system, which I called Categories. That post generated a burst of commentary in a couple of places; one relevant comment suggest that I should post something about Categories here.

I thought, "that's a good idea; why didn't I think of it?" I've been reading LtU for years. What better place to find people who will tell me all the things that are wrong with Categories?

The main point of the Categories object system is to clearly and cleanly separate representation, behavior, and taxonomy. I wrote an article entitled "Protocols" eighteen years ago that explained why one might want to do this, and suggested that most object systems conflate at least two of them.

By "representation" I mean the concrete layout of data in storage. Behavior is the set of operations that are defined over some data. Taxonomy is the collection of representations into categories, and the superset/subset relations among those categories. My claim is that these three concepts are logically distinct, and that, although most object systems don't do it, it's possible to treat them distinctly.

Why should anyone care? The article linked above provides one argument. Another way to look at it is suggested by a comment from Joe Armstrong in Peter Seibel's new book, Coders At Work:

â€œBecause the problem with object-oriented languages is theyâ€™ve got all this implicit environment that they carry around with them. You wanted a banana but what you got was a gorilla holding the banana and the entire jungle.â€

The fact that I want the behavior of a shape doesn't necessarily mean that I want the fields that some other programmer used to represent it. Pretty often, I want the behavior of an existing class without the representation; or I want the representation, but not the taxonomy. Haskell gets it right, in my estimation. In Haskell, representation is handled by datatypes; behavior by functions; and taxonomy by typeclasses.

I love Haskell, but I'm a Lisp-hacker by nature. If there's a way to do my work in a Lisp, that's what I'll do.

When I found myself dissatisfied with Clojure's treatment of types and polymorphism, and I started coding around the parts I didn't like, I ended up writing an implementation of types and polymorphic functions that pretty closely tracked the ideas in that old article. This bit of work I named "Categories".

Categories is a library written in Scheme and in Clojure. It implements a treatment of types and polymorphic functions that sharply distinguishes representation, behavior, and taxonomy.

Representation is handled by elements called, oddly enough, "representations". A representation is a concrete specification for storing data. In the Scheme version, for example, fixnums and vectors are representations.

Behavior is handled by functions. A function is an applicable object that accepts zero or more values as input parameters, and computes and returns zero or more values as outputs. Functions are polymorphic. A function examines its inputs and, based on some computed characteristic of them, chooses some concrete piece of code, called a method, to run.

Taxonomy is handled by domains. A domain is a description of a set of types, the relations among them, and the rules that functions use to select methods based on the types of their inputs.

Types are sets of values. Concrete types are aliases for representations. Abstract types are nothing more than names, commonly used in Domains to collect and organize related concrete types. As an example, Gambit has built-in fixnum ad bignum datatypes. The Gambit implementation of Categories has concrete and types that are aliases for these representations, and an abstract type that the default domain defines as a supertype of both.

This arrangement of elements accomplishes what I wanted: it completely separates representation, behavior, and taxonomy. Okay; so what? Is there anything else good about it? Is separating those concerns actually good in practice? What's it like to use it?

Obviously, I'm biased. It's what I wanted, so I like it. It's also very young; the present code is the result of tinkering around for five months. The API is still moving around some, and the working code is still likely to have significant bugs at any given moment.

Keeping those caveats in mind, I have been using Categories in production code for a few months, and there are definitely things I like about it. I like it well enough that, when I began work on a new project in Scheme, leaving my Clojure work aside for a bit, I missed Categories and ended up porting it from Clojure to Scheme.

It's very easy to build whatever abstract types I want. I simply alias the needed representations and use a domain to collect the resulting types into a convenient arrangement. If that arrangement turns out to be inconvenient later for some other API, nothing is lost; it's quite easy to make another domain that is as similar or different as I need. Once created, domains are invisible, except when creating new functions. The function constructor takes a domain as a parameter, and the new function remembers it. Later rearrangements of the domain's types are automatically visible in all existing functions defined on that domain, but have no effect on functions defined with different domains.

Like Haskell, Categories enables you to define data layouts, functions, and classes of types completely independently. Like CLOS, it also enables you to arrange for 'inherited' behavior, if that's what you want. A domain can tell you whether a method is applicable to a sequence of argument values, and, given two applicable methods, it can tell you which one is more specific to the particular argument values. Categories can therefore support CLOS-style next-method dispatching--if you want it. The API is there to provide that kind of dispatching; you can use it or not, as you see fit.

As I say, Categories is still very young, and it seems like every day I still see another way to improve the API or the implementation. You can't get the newest working code; I'm in the middle of refactoring domains again. Older versions are available, but probably less interesting at this point. It might be a week or so before I have a working release.

Feel free to tell me where I'm out of my mind, though, and if you want a look at the code, ask me in a couple of weeks; by then I'll likely have something packaged that's usable.

## Comment viewing options

### That's a lot of text and very little information.

I think you will get a lot more responses if you give concrete examples (code) where you show what Categories can do that is hard to do in some other language.

### I imagine you're right, but

I imagine you're right, but you might have to wait a little bit. As I mentioned, I have its guts on the table right now. I'm using it in production code, though, so coming up with concrete examples should be easy once I put it back to gether again.

### Inconsistent...

By "representation" I mean the concrete layout of data in storage.

Haskell gets it right, in my estimation. In Haskell, representation is handled by datatypes; behavior by functions; and taxonomy by typeclasses.

Haskell's concrete layout of data in memory is at best suggested by data-types. Actual memory layout is open to the implementation, and must deal with cross-cutting concerns of allocation, garbage collection, dataflow optimizations, and lazy evaluation.

### this kindof seems like

Your description of 'Behavior' sounds to me like a form of structural typing. Likewise 'Taxonomy' sounded very similar to nominal typing. The 'Implementation' category sounds maybe like a more powerful version of type qualifiers (final static etc..).

It is interesting to hear someone else bring up this same topic because not two days ago I was just pondering how useful it would be if there was a way to integrate all of these concepts into one coherent type-system. I'm interested in seeing how you manifest these concepts into implementation because in my experience the devil is in the details when trying to mix type systems.

### Dumb quote

â€œBecause the problem with object-oriented languages is theyâ€™ve got all this implicit environment that they carry around with them. You wanted a banana but what you got was a gorilla holding the banana and the entire jungle.â€

That's a dumb quote. I don't think the person who said that knows what they are talking about. Only in object-oriented databases do you tend to see such coupling, and in such scenarios the purpose of it is to promote locality of reference and thus suitability for extreme transactional throughput. All other object modeling should be based on decisions made at the problem domain level, ideally with the aid of modeling tools like model checkers or test-driven development. Whenever somebody starts talking about gorillas or platypuses or whatever in the context of OO, you can almost be assured they screwed up and got a Comp Sci. degree and then realized they wanted to become a zoologist like Richard Dawkins.

Like Haskell, Categories enables you to define data layouts, functions, and classes of types completely independently.

Basically, I can do this with C#. With ClojureCLR, I can go even further by getting Software Transactional Memory for free. And, really, Haskell doesn't afford what you describe. You can't attribute data structures with byte layout details for the compiler to follow, and you can't save that information as publicly accessible assembly details, which .NET also allows.

Feel free to tell me where I'm out of my mind, though,

I don't know -- see, you've probably got some decent concepts together, but "it takes a long time to write a short letter", and this wasn't short.

Basically, here is what you need to work on communicating. You've got a theoretical article, Protocols. Now you need a practical accompaniment. Different groups of people can then introduce themselves to your set of ideas and design choices using either one as a starting point.

One poignant note about your writing style is that you communicate assuming everyone knows about every problem you are trying to describe AND knows which theoretical concept corresponds to WHAT problem. I don't find this to be the case in general. Even intelligent people are very average outside their domain of expertise.

Funny tangent, wasn't Jaron Lanier (the data glove virtual reality guy) the one who argued against "protocols" and instead for "pattern recognition and surfaces"? "Phenotropic software"?

### I think that quote describes

I think that quote describes a common problem quite aptly. I agree in principle that such coupling usually should not exist, but I work in the real world. Many developers work with a lot of different code and APIs written by many different sources. Sometimes you get lucky and get to work with well engineered OO code that coherently separates modules and minimizes coupling. Some times you work with an API that requires creating many different (seemingly unrelated) objects to perform one simple logical task. More often you work with code that is somewhere in the middle.

One issue with OO is that it is easy for an average programmer to see an illusion of modularity while not really enforcing this in any way. I think this is a large part of why other methods of modularization such as monads that more precisely define how a module will interact with the external world tend to lead to better, "more de-coupled" code than OO. At least from what I've seen.

### Somewhere in this discussion

Somewhere in this discussion there is a place for the distinction between object systems and module systems...

### Maybe I misused the word

[Edit: this should be in reply to Ehud]

Maybe I misused the word "module", but I'm not sure of a better word. To me a module system simply lets me group code together but doesn't force any particular semantics other than maybe "modules cannot be circularly dependent" on my program design, it performs the same role as a file system and little else. If I had to equate them to objects, I could only equate them to singletons.

That being said, modularization of code is a commonly touted benefit of object orientation, maybe it shouldn't be...

### Module is good. But I didn't

Module is good. But I didn't see a mention of module systems. Whether and how module systems are related to OOP is a subject much discussed.

### Can you clarify

By "module system", are you referring to things such as Jigsaw and OSGi?

As an aside, I once got into a convo with one of the most vocal advocates of OSGi. He said he'd "like to see the standard pushed on other platforms like C++ and .NET." I asked him what he meant by that and whether .NET already fulfilled most of OSGi with its core Ecma .NET attributes such as AssemblyInfoAttribute. He didn't have an answer and thus side-stepped what should've been a trivial question. I thought to myself, "How can somebody be pushing a platform agnostic standard, build the first prototype in Java, allthewhile knowing nothing about .NET?" More important, and said aloud, "how has NOBODY ever asked you this question before?"

### My interpretation

When I first read this post I identified with many of the problems that the author presented because they reflect many of those which I have encountered in my own recent ventures into language design. Rereading this post and the comments it seems that others did not seem to easily identify with the problems and terminology presented by the author so I thought that I would present my perspective and experiences.

I come from a background of primarily Java and Python and am split between the two. Working in one or the other always reminds me of what I am missing from the other.

When working in Python initially it is a beautiful language but it has serious issues with scalability. Decorators are not an adequate substitute for real type constraints!! After working on a project in python for long enough I eventually find myself writing more assertion statements than actual code in order to maintain at least some sanity.

When working in Java I am primarily frustrated by the lack of expressiveness. For me this usually falls into one of two categories. First is the total lack of support for duck-typing or dynamic anything. Second is the choice of tools available for Object Composition(extends and implements). In my experience 'extends' is worse than useless, so that leaves me with only interfaces with offer an average of 0 code reuse. Additionally, classes and interfaces must each be given one file so a project that would fit into one Python module will cost me 15-20 java classes/interfaces.

These are both popular languages and for the most part fairly good. However they both (in my opinion) have very inadequate type systems.

Why I reject 'extends' probably deserves some explanation by now. Some people talk about gorillas or platypuses, but in my experience the best example of the shortcomings of hierarchal inheritance comes in the form of rubber ducks. Imagine you are trying to model a duck in an OO language. This should be the perfect opportunity for OO to shine because phylogenetic hierarchies are exactly what OO was modeled after right? so let's keep it simple and say that a Duck isa Bird isa Animal, and that respectively these animals can quack, fly, or walk.

class Animal
{
walk() returns void {...}
}

class Bird extends Animal
{
fly() returns void {...}
}

class Duck extends Bird
{
quack() returns void {...}
}


which seems like a perfectly viable hierarchy until you try to introduce rubber ducks into this system. Rubber ducks can squeak when you squeeze them, and they have duck in their names, but they are definitely not a Bird or Animal and should certainly not inherit their behaviour. Mixins provide a very elegant solution to this common problem but that is not standard OO.

So back to the topic of the article. What I want from a language in terms of type expressivity usually falls into 1 of 3 'categories': structural typing, nominal typing, and implementation. Something that I do NOT want from a language is to be forced into either static or dynamic typing, gradual typing is the way to go.

Structural typing and Nominal Typing are well defined and not worth reiterating here. Implementation is the only new concept which in a perfect language would simply be a way of transparently representing the specific implementation of the semantics of a program. Sometimes you want to know what is going on behind the scenes, but more often you would just want the compiler to take care of those details.

A great example of how poorly concealed implementation can quickly become overwhelming is in the case of lists and tuples. Conceptually lists, tuples, arrays and the myriad of ways that they can be implemented are all basically the same thing. Multiply the number of representations for a collection by the types that each could contain and your project quickly becomes unmaintainable. In practice we usually restrict ourselves to a single implementation for these situations but when crossing project boundaries the explicit conversions become ugly sometimes. For projects that encompass many other projects, a type-safe solution to abstractly representing behaviour and implementation would be a life-saver.

### SqueakyToy isNotA Animal

...seems like a perfectly viable hierarchy until you try to introduce rubber ducks into this system...

I'm not sure why this surprises you - rubber ducks don't exactly fit into the phylogenetic hierarchy you used as your starting point either. Why would you expect there to be a valid inheritance relationship from real ducks to rubber ducks within a hierarchy that is explicitly focused on biological systems, not on inanimate rubber?

### two different goals

I like that example because it highlights two different assumptions that people may bring to any discussion or analysis about different approaches to modeling.

The first approach is strictly definitional. Strict hierarchal trees can always model strict hierarchal trees. If you are looking for a formal proof of why mixins are sometimes better than single-inheritance in certain circumstances, I don't have one.

The second approach is aesthetic. All languages that I have ever programmed in have been Turing equivalent. What we are discussing here is mostly aesthetic and it would do good to acknowledge that before continuing discussion.

Granted that rubber ducks are not genetically related to ducks, their behaviour is interchangeable to some degree and as such it would be useful to be able to formally model that. If given the choice I would prefer a language that can gracefully model more 'edge' cases rather than just refuse to acknowledge that there could be any other solution than the one true way.

### No doubt

Granted that rubber ducks are not genetically related to ducks, their behaviour is interchangeable to some degree and as such it would be useful to be able to formally model that.

No doubt. But perhaps it would be easier to do that if you had started from an inheritance structure designed to accommodate modeling such relationships, rather than one that was never designed to model anything other than relationships between biological systems.

Just to be clear, I'm taking issue with your specific example rather than your overall message. Your example simply highlights the fact that the phylogenetic hierarchy doesn't accommodate non-biological entities, which is hardly surprising. Obviously, a different relationship structure would be preferable. Whether that structure should (or must) include mixins, multiple inheritance, or some other way of expressing relationships is a separate question.

### Also....

The phylogenetic hierarchy doesn't strictly model species interaction and mating resulting in cross-breeding. Thus the "How do you polymorphically send messages to a bird-lion (Griffin: class)?" is usually asking the wrong question.

### A great example [...]

A great example [...] Conceptually lists, tuples, arrays and the myriad of ways that they can be implemented are all basically the same thing.

Disagree with this being a great example, and in fact find it to be overlooking many important details. Tuples do not have any ordering semantics, lists do. Arrays can have multiple meanings, and usually random-access capabilities at every level of abstraction. etc...

Multiply the number of representations for a collection by the types that each could contain and your project quickly becomes unmaintainable.

Supposing these were truly just representations as you say... ignoring definitional things I pointed out above... then you only want one program/system property to defeat this problem "of how poorly concealed implementation can quickly become overwhelming": Data independence... The ability to convert to and from equivalent forms of representation.

Some people talk about gorillas or platypuses, but in my experience the best example of the shortcomings of hierarchal inheritance comes in the form of rubber ducks.

Here is where you initially seem to be generating your false premise from. I've read all these false premises in so many different forms. Maybe I'll link some of them in this thread... well... here is my favorite, because it is simply hilarious: http://z-bo.tumblr.com/post/105113066/friday-humor

I also think your quack/fly/walk example ignores much of the more interesting AI movement simulation research based on "steering behaviors". Always follow the problem domain expert's thinking.

You also miss an important subtlty: Not all birds fly. More importantly, when they do, why are they doing so? What is collaborating in the simulation, forcing it to choose to fly? Don't you see what your design is doing? You are creating Controller DoIt() methods everywhere (where IT here is fly/quack/walk/VOMIT). So do yourself a favor and TOTALLY ignore that you even want to use hierarchical descriptions of things for a second, and think about the problem domain and class responsibilities.

Mixins provide a very elegant solution to this common problem but that is not standard OO.

Generally, it is "not standard OO" because we usually do mixins without realizing it in some problem models. Also, most third-generation languages have procedural coupling spread throughout, which makes it hard to "include" these blocks of knowledge where they are deemed needed. Newer 3GL's like Newspeak try to make it easier to so this, but also recognize that mixins by themselves are not fairy dust answers. You need some sort of module system. It doesn't even have to be in the language "proper", either. Instead it can be an add-on such as OSGi. The Java spec request folks ultimately decided you should be able to pick your own module system (gotta love committees), provided it consistently handled things such as versioning and that certain core parts of the system were consistent and could not be subverted by clients.

Also, in a well-designed system that supports multi-stage programming and the ability to define your own syntax, you might not expose OSGi or Jigsaw directly, but rather create DSL extensions that control how aspects of the system are loaded on-demand. It could be like The Matrix -- where Neo needs to learn how to quack, walk, OR FLY. (Or, if you're a fan of the TV Show Chuck: "Guys, I know kung-fu!").