Log in

No Kings in Rome

Google recently announced a new system programming language called Go. I've said before that I'm a Lisp hacker at heart, and I always end up liking Lisp better than anything else. I don't mean Common Lisp; I mean any Lisp. I call the Lisp family of languages home. I'm always messing around with Lisp to try to increase the Joy.

I remain interested in other languages, though, and new ones always catch my eye. I'm extra interested--and extra skeptical--when someone goes after C's niche with a new language, which is what Google is doing with Go. So I popped over to the Go site and right away noticed two names among the designers of the language: Rob Pike and Ken Thompson. Okay, that makes it extra interesting. (If you don't know why, go Google those guys.)

Then, while reading about their design decisions, I noticed something else really interesting.

Let me back up a minute.

I've been making steady, if slow, progress preparing Categories for a general release. If you're one of the couple of people champing at the bit for me to release it, have patience. It's coming along. I have to put most of my effort into things that will pay bills, so Categories development happens in small chunks, in between other things. Almost the entire surface syntax from A Peek at Categories is now implemented, with a few small changes. The main new feature is the syntax for explicitly specifying a domain in a function definition, which looks like this:

Without explicit domain:

(define-method add ((x <integer>)(y <integer>))
(+ x y))

With explicit domain:

(define-method add ((x <integer>)(y <integer>)) :: -c3-
(+ x y))

The one missing piece now is the syntax for renaming structure keys in includes.

Oh, and to the Concerned Reader who requested an implementation using define-syntax, I've done that, and it's working fine.

Why did I start talking about Go, then switch to Categories? Well, I found something in the design discussion of Go that I had already found in working with Categories. As I mentioned in A Peek at Categories, the default domain is -c3-, a domain that implements method dispatching in a fashion very similar to the way that CLOS and Dylan do it. That's just one domain of potentially many, though, and the Categories implementation includes two other example domains: the -pred- domain and the -flat- domain. The thing is, in experimenting with domains, and with category types, I was liking the -flat- domain more and more.

A quick refresher: the -flat- domain implements polymorphic dispatch, but without inheritance. There's no support in -flat- for supertypes. A function either has a method that matches the exact types of its passed arguments, or it doesn't. If it doesn't, there's no looking up supertypes to match, because there are no supertypes. This decision makes method dispatch very simple and efficient.

But how do I write generic, extensible APIs, then? you may ask. How do I use Categories to reuse code? Okay, first of all, my experience has been that code reuse sounds better in theory than it tends to be in practice, but don't despair; I'm not killing it off in Categories. First, you can add methods for new types to extend your APIs. Second, your method is free to reuse another method by passing arguments of the appropriate types. Third, category types provide an easy way to write methods meant to apply to a collection of types. Finally, if you really can't live without a type hierarchy, you are free to use -c3-, or write your own domain.

I initially designed -flat- just to serve as a limiting case. It was meant to be an example of the simplest kind of dispatch that actually does some dispatching, and nothing more. In using it, though, I've begun to actually like it more and more. Besides being efficient, it eliminates pretty much all of the complexity of multiple inheritance, without losing much. Category types make it easy to compose methods that are generic across arbitrary sets of types. You can add a new category any time you need one, and you need not concern yourself at all with the effects of any existing type hierarchies, because there aren't any.

What does this have to do with Google's new system programming language? Well, the Go designers seem to have come to the same conclusion about type hierarchies. In Go, types don't support inheritance. There are no subtypes or supertypes. To quote from the Language-design FAQ:

"Rather than requiring the programmer to declare ahead of time that two types are related, in Go a type automatically satisfies any interface that specifies a subset of its methods. Besides reducing the bookkeeping, this approach has real advantages. Types can satisfy many interfaces at once, without the complexities of traditional multiple inheritance. Interfaces can be very lightweight—having one or even zero methods in an interface can express useful concepts. Interfaces can be added after the fact if a new idea comes along or for testing—without annotating the original types. Because there are no explicit relationships between types and interfaces, there is no type hierarchy to manage or discuss."
Yeah. That's what I've been liking about the -flat- domain, too.

I'm thinking of making -flat- the default domain.


I find inheritance incredibly useful for setting patterns in code sometimes. While doing without inheritance is certainly entirely possible, there's times when it seems an awful lot more elegant.
As I said above, if you really can't do without inhritance, there's no reason you should. Even if I make -flat- the default domain, you are completely free to use the -c3- domain instead, or, if you don't like multiple inheritance with C3 linearization, you are free to write your own domain. I've gone some distance to make that easy to do.
Oh, absolutely. Wasn't having a go at you - just the anti-inheritance stuff I sometimes see.

I could actually live without multiple level inheritance - which can be confusing to maintainers. I'd settle for interface implementation with a default implementation in the interface - which would then allow multiple inheritance of code, but all in the one class rather than allowing for the much trickier multiple levels of inheritance (and difficult to deal with diamond inheritance topologies).
I'm pretty comfortable with class heterarchies myself, and Categories began as an implementation of C3 inheritance for Clojure types. The -flat- domain was only meant to be a demonstration that you can have polymorphic dispatch on a domain without inheritance--purely a proof-of-concept. Once it was working, though, I sort of got fascinated with it on its own merits.

A polymorphic dispatch system that works only on exact type matches seems too restrictive at first glance, but a little experimenting convinced me that it's more useful than I at first expected.

An open question is whether category types make the -flat- domain better or worse. In their favor, they provide a way to say that a function operates on any of several different types. Against category types is the observation that by using them, you can easily introduce the same dispatching ambiguities that turned me off to Clojure's derive hierarchies. If <person> is a member of the category <animal>, and also a member of the category <beneficiary>, what happens if no method for foo is defined on <person>, but one is defined on <animal> and another is defined on <beneficiary>? The -c3- domain knows what to do about this in all but contrived cases, but -flat- doesn't (if it supports category types); it has to signal a dispatch error. That means -flat- is in the same boat as Clojure's dispatch mechanism, because defining a new method can break an existing library.

The nice thing about a completely flat domain, without support for category types, is that dispatch is always unambiguous.
Yes, they also talk about orthogonality (as you in your article about the Categories).

Go's intefaces also resemble Haskel typeclasses.

February 2010

Powered by LiveJournal.com