Categories

There are a few things I've written that I see cited or quote repeatedly. The oldest is a quip about omnipotent beings that I wrote eighteen years ago in a USENET discussion:

"Perhaps this morning there were only three Euclidean solids, but god changed
its mind retroactively at lunchtime, remaking the whole history of the
universe. That's the way it is with omnipotent beings."

More recent is an explanation I once gave of the concept of "natural law" in politics. There are a couple of basic theories of law; one of them is called "natural law". Because that phrase is also used to mean "law of nature", people sometimes confuse the two concepts, often, I think, because they're not aware that the legal one exists, or are not aware of what it is. This was my attempt to succinctly summarize it in one discussion:

"People will naturally and predictably find some methods for resolving [...] conflicts more congenial than others. There are some classes of conflict for which people will naturally and predictably find certain kinds of resolutions more congenial than others. The procedures people find more congenial will also produce the resolutions people find more congenial. And the procedures and resolutions that people find more congenial will tend to resemble each other across times and cultures."

Two others are more technical articles that I wrote early in the 1990s about programming. They were published in a magazine aimed at Mac developers, called Frameworks (now archived at MacTech).

"Objects Without Classes" was republished by the ACM's Computer magazine in Volume 27 , Issue 3 (March 1994) . It's a basic description of prototype-based object systems, such as those found in languages like Self and Javascript. Languages with prototype-based object systems probably seemed novel to more people then than they do now. Lots of people use Javascript now, but at that time you might never have heard of prototype-based object systems unless you were at Sun working on Self, or in the AI business, working with frame languages, or at Apple working on Newton or SK8.

The topic of this post is the ideas presented in "Protocols," originally published in the March, 1994 issue of Frameworks, and archived here. It's an article about how representation, behavior, and taxonomy are distinct concepts that can be handled separately, despite the fact that object-oriented languages tend to confuse them.

Those points need clarifying, I know.

By "representation," I mean how we concretely lay out data. As an example, you can represent an array as a contiguous sequence of memory locations, or as a table of indexes paired with pointers, or as a tree of cells in which bit patterns are mapped to subtrees, or, of course, in many other ways. There are circumstances in which each of the different approaches might be advantageous. These are different representations of a common abstract concept that I have here called an "array".

By "behavior," I mean the set of operations that is defined on any given set of values. Taking the abovementioned abstract concept of an "array" as an example, you can use any of the mentioned representations to support a common behavior. You can straightforwardly implement functions that fetch an element of an array by index, that iterate over the members of an array, that write a new value to the array at some specified index. The implementation and performance details will differ, of course, because the representation differs, but the behavior—that is, the API and what it accomplishes—is the same.

By "taxonomy," I mean the relationship between one defined set of values and another. Types are categories of values. They are (possibly unbounded) collections of data objects. Types naturally have subtypes; a collection of values has a natural relation to a smaller collection of some of the same values: the smaller set is a subtype of the larger one. It's natural to think of obtaining the smaller set by starting with the larger one and adding restrictions that filter out some values. You can think of taxonomies of types, such as the class hierarchies in languages like Smalltalk and Java, as sets of values that begin with a very inclusive type, like Java's Object, and develops more and more refined types by adding more and more exclusive restrictions. Object is all the values (I know; it's not really all of them.) Number excludes all those objects that aren't representations of magnitudes. Integer excludes all that are not representations of whole numbers. And so on.

These three concepts, representation, behavior, and taxonomy, are quite distinct, but most object-oriented languages conflate at least two of them. Some combine all three. Smalltalk classes, for example, are representation, behavior, and taxonomy all rolled into one. The representation is in the instance variables; the behavior is in the methods; the taxonomy is in the subclass/superclass relations. THe trouble with that approach is that when you ask for one of the three, you get the other two whether you want them or not. For example, if you create a new subclass, you inherit representation, behavior, and taxonomy, even if all you wanted was behavior. If you create some subclass because you want a certain taxonomic relation, you also get a representation and a behavior that may or may not be what you need.

The claim of the "Prototypes" article was that you can treat these three concepts separately, and by doing so develop a discipline that makes object-oriented design and implementation feasible in any language. Furthermore, by doing so, you can develop APIs that are language independent. To take the "array" example, what makes it an "array" is that you can get and set elements by index, and iterate over them in index order. That's behavior. If representation, behavior, and taxonomy are properly separated, you can represent "arrays" any way you like, and you can arrange for them to be subtypes of any type you like, and they'll still be arrays, because they support "array" behavior. Representation and taxonomy can be treated independently as well, but not if your tools insist on conflating them.

I still think that's true, and useful, but I was always interested in codifying the ideas of that article more concretely. I was interested in working with an object system designed around clearly distinguishing representation, behavior, and taxonomy.

One language that pretty much nails it is Haskell. In Haskell, representation is the province of datatypes. Behavior is handled by functions. Taxonomy belongs to typeclasses.

For those unfamiliar with Haskell, the terminology is probably confusing. Without some experience with Haskell, it's probably not at all clear how and why "datatypes" and "typeclasses" are different. Briefly, a Haskell datatype is a named description of an arrangement of data. A typeclass is a named description of a set of operations. You can make a datatype into a member of a typeclass by defining functions that implement the operations specified by the typeclass.

This is pretty close to what I was talking about in "Protocols;" it's probably closer than anything else I've seen to language support for those concepts. The next closest thing, I think, is the style of object system exemplified by CLOS (the Common Lisp Object System). In CLOS, classes describe representation and taxonomy. Generic functions and methods describe behavior. It's easy and convenient to describe behavior in CLOS independently of representation or taxonomy. CLOS does still conflate representation with taxonomy, though it provides facilities for modifying itself that enable you to work around that conflation if you really want to.

In February of 2009 I had been using the new Lisp dialect, Clojure, for about five months on some projects, and was generally pretty happy with it. One area I wasn't happy with, though, was Clojure's approach to types and polymorphic functions. Clojure doesn't really have a type system as such. It has a small number of well-chosen and well-designed types, and it can transparently use Java's types (Clojure's main implementation is built on the JVM). For most uses, these two facilities are more than sufficient, and they work very well. They fell a little short of what I wanted for some of my work, though. One of my projects requires ways to specify a large number of structured data elements with taxonomic relations. The set of elements is open, and expected to grow over time, so I need a convenient way to add descriptions of new ones, and ways to ensure that relevant APIs are defined to work in the proper way over all the values currently described, and over all those that are yet to be described.

Clojure gives me a lot of what I want to support this scenario, but not all of it. Clojure's maps provide a great way to describe structured data, but not a great way to place restrictions on it. I can say that Foo has fields A, B, and C, but there's no convenient way to say that A is an automobile and B is a hypotenuse; nor is there a convenient way to say that a Foo has A,B, and C, and nothing else.

I was even more dissatisfied with the facilities that Clojure provided for defining taxonomy. Clojure's documentation, and its justifiably enthusiastic users, make much of the fact that Clojure's derive function and its polymorphic MultiFns make it possible to define arbitrary taxonomies. That's true for small values of "arbitrary". You can easily construct any taxonomy, as long as it's a taxonomy that Clojure was designed to easily construct. Mine wasn't.

The details of the problems don't matter. My main point is that I ran into a couple of insoluble problems with Clojure's MultiFns, derive, and hierarchies, and, after some discussion, satisfied myself that the Clojure community regarded those obstacles as features rather than bugs. So I did what any sensible Lisp hacker does in a situation like that: I wrote my own object system.

It began as an existence proof of an alternative way of handling polymorphic dispatch. There was a little bit of interest in it from a couple of people, but for the most part the Clojure community reacted with a shrug. On the whole, they're happy with Clojure's approach. More power to them.

As I tweaked a few things to respond to casually-mentioned hypothetical objections, I started to like what I had. I was testing it by reimplementing important parts of some production code I was working on. I realized pretty early that the subsystem I was builiding bore more than a passing resemblance to the ideas in "Protocols". I refactored it a few times. I tried a couple of different implementation strategies. It got faster, simpler, and more appealing (to me, that is). Somewhere along the way, I started calling it Categories.

I have a couple of implementations of it in Clojure now, with somewhat different APIs. More recently, I ported it to Scheme, so that I can try it out in a different application context. The API mutated a little more. I'm still refactoring things to try to make the surface API simpler and easier to understand.

Categories represents the concepts from "Protocols" pretty straightforwardly. The basic concepts are:

Types: descriptions of how data are laid out.

Functions: operations that accept zero or more values as parameters, and that compute and return zero or more values as results.

Domains: descriptions of relations among types.

Functions are polymorphic, and are defined in terms of domains. In other words, a functions looks at its arguments at runtime and decides which actual code to run based on what it sees. This is like any other object-oriented language, as far as it goes. The distinguishing characteristic of the system is how a function choses a method.

When you construct a function, one parameter to its constructor is a domain. A domain contains a catalog of types, and a set of rules (represented as functions) that describe how the types are related. Domains can tell you things like whether a type is a member of the domain, whether one type is a subtype of another, and whether a method can be applied to a particular set of argument values.

Importantly, you can have as many domains as you want, and each one can work differently. How you represent the relations among types is entirely up to you. This means that you can pretty easily implement any kind of dispatching you want. Smaltalk-style, Java-style, CLOS-style, predicate dispatch—it's all good. The Categories subsystem defines a default domain that implements a dispatch scheme very similar to those of CLOS and Dylan (because I like those schemes and am comfortable with them), but the default is just one domain. If you want something different, it's easy enough to build it. Just to make sure, I wrote implementations of Clojure's dispatch and of a predicate-dispatch scheme. They were easy to do.

When I was first discussing these ideas, someone mentioned some concern that it wouldn't be possible to implement such a system efficiently, or to optimize it. In practice, it hasn't been a problem. There is a tradeoff between exposing the API you need to implement a domain efficiently, and making the domain API understandable, and that's been a major issue I'm dealing with in rewrites of Categories. It seems clear at this point, though, that efficient implementations are doable. The trick is setting things up so that you can write domains that are efficient without exposing a confusing array of knobs and switches. I'm still working on striking the right balance.

You can't get a current working version of Categories right now; I still have its guts out on the table so I can tinker with them. Some of its early predecessors are readily available if you really want them, but if you read this and are really interested in Categories, I'd counsel patience. I'm folding it into some product code right now, and making corrections and improvements as that process reveals the need. It's my intention to nail it down and ship a product that uses it, then port that version back over to Clojure to support some other work I'm doing in that language. Once I reach that point, if you ask me for it, I'll give it to you.

Why would you want it? I dunno; you might not. I sure did, though, enough to build it. Soon I'll see if it was a waste of time, or a great new tool for my toolbox.

Comments

When will we see it?

This sounds very interesting Mike and would be one more reason to start using Clojure for my Ph.D. work.

Please post a link to the source on Hacker News once you have a release. But don't make us wait too long; if you release earlier, others will help find issues.

Re: When will we see it?

I don't want to promise an exact release date, but I don't think it'll be very long. I'm all for early release; you can get an ancestor of Categories from about April right now, if you really want it. But right at the moment, the latest Categories code doesn't actually work, because I'm replacing the definitions of the core pieces of Domains.

I'm guessing that will take a few more days, depending on how stupid I think my code is. But I think it's pretty reasonable to expect a release of the current iteration in a week or two, at the outside.

Note that the current version is implemented in Scheme, on Gambit. It'll be some little while after that before I complete a port back to Clojure. I do definitely plan to do that port in short order, though.

(Anonymous)

Re: When will we see it?

As on of the "justifiably enthusiastic users", I see your point about specifying a taxonomy in Clojure. It doesn't scale to complex systems. I can see there being corner cases where one really does need a complex type system (I'm thinking units of measure).

What you're working on sounds promising. Could you please post a link to you stuff in Clojure group when you're done? Thanks

Sean Devlin

(Anonymous)

Re: When will we see it?

Sure, I'll post a comment in the Clojure group. was thinking I should do that anyway, so that anyone who stumbles across the xg-gf code in the Clojure libraries page will know that there's something newer and, I hope, more interesting.

(Anonymous)

Re: When will we see it?

Up to you. But maybe also post to LtU (if want the ol' panel of experts to comment/opine). Interesting use of the word 'domain'. I always wanted to s/type/domain/ in reading some of the FP literature. But your usage seems more interesting. And I like your rules system for dispatch.... Sounds pretty cool.

(Anonymous)

so why not Haskell?

This is a stupid question inasmuch as there are always a multitude of reasons and externalities involved in language choice, but if you think Haskell pretty much nails it... why not just stick with it?

It seems like there's a potential theorem here related to Greenspun's tenth, viz., any sufficiently general type system contains a reimplementation of part of Haskell :)

(I'm making no implications here about bug content)

Re: so why not Haskell?

It's not a stupid question; it's totally fair. The answer is that (1) I love Lisp even more than I love Haskell, and (2) I've wanted to work out these ideas in practice for years anyway. Yes, I think Haskell nails the distinction among representation, behavior, and taxonomy, but that distinction isn't the only thing I want; it's just particularly prominent in my work right now.

I really like Haskell a lot, and I keep up-to-date versions of GHC installed. Several times I've written pieces of Lisp compilers and interpreters in Haskell to exercise some ideas.

If Lisp didn't exist, then I'd probably be a Haskell programmer. But as much as I like it, I like Lisp more.

(Anonymous)

Types vs. classes

This is only a small nitpick, but I'd rather like to think of types as sets of values rather than a description of the values' structure. Most operations on types map usefully to set operations, e.g., x::T <=> x\in T, T1<T2 <=> T1\subseteq T2, T_nil = T\cup {nil}.

Classes (or prototypes), on the other hand describe a value's representation, it's structure.

Re: Types vs. classes

Yeah, you have a good point. I used "type" the way I did because "representation" looked long in code, and plenty of languages use "type" or "datatype" to mean "representation". But, really, I think you're right.

"Class" is wrong because (1) it's a synonym for "type", if you look outside the specialized jargon of particular programming languages; (2) within the jargon of existing languages, its connotation already conflates representation with at least taxonomy, and in common cases also with behavior.

But I probably should switch to "representation" because, while it may be long, it's clear. Thanks for the catch.

(Anonymous)

Conflation

I think you're on the right track. I've found OO classes conflate the concepts of data types, state machines and interfaces. Another set of terms I commonly encounter is values, entities and contracts. It seems to me you're describing the same thing.

All class-based languages I've seen enforce the same model of inheritance and polymorphism for all three. I see the effects of this conflation in all the arguments about multiple vs single inheritance, implementation vs interface inheritance, subtyping vs subclassing, the circle-ellipse (or square-rectangle) problem, object-relational impedance problem, and more.

I'd love to learn more about your Categories, and how you separate the issues. I've looked at the theory side, but haven't investigated implementation. I'm not a Lisp programmer, though - any chance of getting something in English?

Re: Conflation

There is a manual for Categories, and the Lisp-like language that it's part of, but the up-to-date version of that manual is waiting for me to ship my current product before I get back to work on Categories. I mean to ship my product this month (though it's looking like it may be next month), after which I begin work on a second product that will use more of the Categories code. At that point I'll work some more on the Categories manual.

If you want to see that manual, send email to mevins at me dot com asking me for it, and I'll see to it that you get a copy when it's a little more complete.

(Anonymous)

avodonosov.blogspot.com

Is the Domain idea similar to the ContextL?

Re: avodonosov.blogspot.com

Not really; they address different problems. Domains describe how method lookup and subtype relationships work, basically.Making them first-class objects provides a convenient way to support more than one type taxonomy in a program at the same time.

ContextL, on the other hand, provides a convenient way to dynamically change the definitions of a set of functions.

With Categories you can say that in one Domain, a truck is both a vehicle and a freight-container, but in another domain it's both a capital asset and a cost-center.

With ContextL you can say that in one situation "unload a truck" means remove cargo from the back of the truck, and in another situation "unload a truck" means take the truck off the ship that has been transporting it.

The Categories features and the ContextL features are both things one might like to have, but they're different things (assuming, of course, that I've understood ContextL correctly).

Re:

I see.

I believe classification and types is an important topic, I sometimes think about it too, but haven't developed complete understanding.

February 2010

S M T W T F S
 123456
78910111213
14151617181920
21222324252627
28      
Powered by LiveJournal.com