CREATE TABLE user_account (
   id SERIAL,
   email TEXT
);

CREATE TABLE user_attribute (
   user_account_id BIGINT,
   attribute_type TEXT,
   value TEXT
);

Using these two tables, we can, at least temporarily, punt on finding an ideal table representation for all users ever. Sure, we’re assuming all user_accounts will have an email, but for the sake of this example I want an excuse to do a join, so let it be. ;)

This is a very data-driven approach, where all one has to do to extend a conceptual object (in this case a user) is to add an attribute/property to it. If you don’t need it right now, your code doesn’t even need to change, but you can store it. You could even provide non-programmers with an interface into this system for extending your schema without a single bit of SQL anywhere in sight.

Here’s a simple user:

INSERT INTO user_account (email) VALUES ('foo@example.com');
INSERT INTO user_attribute
     (user_account_id, attribute_type, value)
   VALUES
     (1,'first-name','John'),
     (1,'last-name','Doe'),
     (1,'title','Dr');

Of course, now the problem is constructing a complete ‘view’ for these users that includes these attributes. We’d like to have one row per user, with all its attributes in individual columns. A basic join won’t really get us what we want, though:

db=# select id,email,attribute_type,value from user_account inner join user_attribute on id = user_account_id where email = 'foo@example.com';
 id |      email      | attribute_type | value
----+-----------------+----------------+-------
  1 | foo@example.com | first-name     | John
  1 | foo@example.com | last-name      | Doe
  1 | foo@example.com | title          | Dr
(3 rows)

Enter pivot tables. There’s a number of ways to do them. My favorite involves the CASE statement combined with an aggregate and GROUP BY. Here’s how it would apply to our example:

SELECT -- Grab the user_account columns.
       acc.id,
       acc.email,
       -- Use max() combined with a case statement to
       -- usher individual attribute values into columns.
       max(CASE WHEN (attr.attribute_type = 'first-name')
                THEN attr.value END) AS fname,
       max(CASE WHEN (attr.attribute_type = 'last-name')
                THEN attr.value END) AS lname,
       max(CASE WHEN (attr.attribute_type = 'title')
                THEN attr.value END) AS title
   FROM user_account AS acc
   -- Join the attribute table /once/.
   LEFT JOIN user_attribute AS attr
     ON (attr.user_account_id = acc.id)
   WHERE (acc.email = 'foo@example.com')
   -- Group by the non-pivoted columns
   GROUP BY acc.id,acc.email;

Which gives us the single-row results we wanted:

 id |      email      | fname | lname | title
----+-----------------+-------+-------+-------
  1 | foo@example.com | John  | Doe   | Dr
(1 row)

And there you have it. Of course, it’s not the prettiest way to generate this kind of output. Still, it’s a lot better than doing multiple queries and combining results in your application, and it would be easy to convert these queries into super-fast materialized views if performance ever becomes an issue.

Fortunately, PostgreSQL ships with a tablefunc module with a utility that makes this sort of data transformation easy — and even converts data types for you! You can read more about the crosstab() function on the Postgres documentation page for tablefunc. That page also includes a number of compelling use cases for pivot tables.

I’ve used pivot tables in applications I’ve worked on to do things such as pivoting on a large variety of external id codes as well as to define a relatively flexible name-specification system for a game. Have you used a similar trick with SQL? Do other SQL systems have similar utilities for generating pivot tables?

I recently did a major rewrite of Chillax. It’s funny what they say about Common Lisp, how you never finish learning it. Ever since I started using it, I’ve gotten periodic “aha!” moments where something simply clicks. A memorable example was the moment when macros really made sense. The latest one, which came to me while working on Chillax, was the idea of designing your program around protocols.

Now, protocols are nothing new, and nothing unique to Lisp. CL doesn’t even have ‘explicit’ protocol support, like Clojure or Haskell do (although there’s a library). It does, though, have generic functions. “Write your code around defgeneric, not around defclass” is certainly something that gets regurgitated over and over. PCL even emphasizes the point by introducing generic functions before it even introduces CLOS classes.

Still, it’s not something that seems to stick right away for everyone. It certainly didn’t stick for me for a couple of years. Then it did — and it was like a tidal wave had just washed over me.

Consider this piece of code:

(defclass server ()
  ((host :accessor host :initarg :host :initform "127.0.0.1")
   (port :accessor port :initarg :port :initform 5984)
   (username :accessor username :initarg :username :initform nil)
   (password :accessor password :initarg :password :initform nil)
   (securep :accessor securep :initarg :securep :initform nil)))

(defmethod couch-request ((server server) uri)
   ...)

(defmethod stats ((server server))
  (couch-request server "_stats"))

... etc ...

Seems reasonable enough. in fact, a lot of “Object-oriented” code kinda flows like this. You first think of what kind of object you want to describe, and create a new class that has data fields that sort of describe that ‘object’, then you write methods for that class. The hope here is that you can just inherit from whatever class, and everything will be okay.

Unfortunately, there are a number of problems with this approach:

1. It ‘covers its bases’ by just defining blanket accessors, initargs, and initforms for slots. This is both unnecessary and verbose.
2. it creates potentially-unnecessary slots. — What if your subclass wants to store this data elsewhere, or construct it programmatically?
3. The only way to reuse code is to subclass my-class. There’s perfectly reusable code there that is now stuck in a class-specific method.

We’re constantly being told about how object-orientation can make our code reusable and extensible — but this doesn’t seem very extensible at all!

Enter protocols: You design your program generically — that means, you don’t assume anything about the objects it handles except what it is -necessary- for the objects to be able to do. The rest of the code doesn’t even need to be polymorphic. After figuring out what the fuss with protocols was about, this is what the above Chillax code transformed into:

(defgeneric server-host (server))
(defgeneric server-port (server))
(defgeneric server-username (server))
(defgeneric server-password (server))
(defgeneric server-secure-p (server))
(defgeneric data->json (server data &key)
  (:documentation "Converts DATA to JSON suitable for sending to CouchDB."))
(defgeneric json->data (server json &key)
  (:documentation "Converts JSON to the desired data structure."))

(defun couch-request (server uri &key convert-data-p &allow-other-keys)
  ... code ...)

(defun server-uri (server)
  (format nil "~A://~A:~A/"
             (if (server-secure-p server)
                 "https"
                 "http")
             (server-host server)
             (server-port server)))

(defun couch-request (server uri)
  ... implementation using protocol ...)

(defun stats (server)
  (couch-request server "_stats"))

... etc ...

But that’s not the full implementation, is it? It’s not — but it’s the vast majority of the code needed in order to use the Chillax API. The magic happens when you realize how much implementation is needed to take advantage of this:

(defclass standard-server ()
  ((host
    :reader server-host
    :initarg :host
    :initform "127.0.0.1")
   (port
    :reader server-port
    :initarg :port
    :initform 5984)
   (username
    :reader server-username
    :initarg :username
    :initform nil)
   (password
    :reader server-password
    :initarg :password
    :initform nil)
   (securep
    :reader server-secure-p
    :initarg :securep
    :initform nil))
  (:documentation
   "Default implementation of the server protocol."))

(defmethod data->json ((server standard-server) data &key)
  data)
(defmethod json->data ((server standard-server) json &key)
  json)

(stats (make-instance 'standard-server)) => { server stats }

That’s really all of it. The beauty here is that you can reuse code without dealing with inheritance, or any sort of class-based hierarchy. Doesn’t seem like a big deal? Consider that CLOS allows you to define methods on built-in classes:

(defmethod server-host ((server hash-table)) (gethash 'host server))
(defmethod server-port ((server hash-table)) (gethash 'port server))
...and so on...

(let ((server (make-hash-table)))
  (setf (gethash 'host server) "127.0.0.1"
         (gethash 'port server) 5984)
  (stats server)) => { server stats }

As long as you tell Chillax how to do what it needs to do on your own data types, it can take care of everything else.

I really like what this ended up doing to Chillax’s API. It’s made it very easy to reuse most of the Chillax code while still swapping out JSON libraries, and possibly (but not yet) http clients.

If you want to read more about protocols, I highly recommend you check out Art of the Metaobject Protocol. I have not read it yet myself (it’s been on my desk for a while), but Sonya Keene’s CLOS book is also recommended fairly often.

If you’re interested in reading about other languages’ takes on this concept, go read up on Haskell’s Type Classes, Java’s Interfaces, and Clojure’s Protocols. Common Lisp itself also has various examples of ‘protocol-oriented’ APIs, such as Gray Streams, and the more recent extensible sequences protocol in SBCL.

If you want to read about more interesting, advanced uses of this architectural technique, François-René Rideau’s postings about “Interface-passing Style” are good reads (and so is his fare-utils code).

Of course, I’ve left a small detail out: How do you actually design programs incrementally like this? The fact is that protocols are not always immediately obvious, and they’re not necessarily static as your application evolves. The process of writing extensible code using protocols is often incremental, and half of AMOP is dedicated to describing techniques for growing and developing these.

Do you write code like this? How has it worked out for you?

Sheeple is a very dynamic system, and so when I went looking for a database backend to build this persistence library around, most things fell short of my expectations… and then I found CouchDB.

I don’t think I can praise CouchDB enough. Everything about it  so far has just been a dream. After a week of nightmarish interactions with SQL (on a different project), nothing was a bigger blessing than CouchDB’s easy, wonderful, simple design.

Everything about Couch just reeks of ease-of-use and simplicity. You don’t need anything fancy. No obnoxious authentication setup or all that bullshit MySQL makes you go through just so you can put your grandma’s phone number into a goddamn table. No ridiculous, pathetic attempts at making your object model fit in with your schema. No obnoxious ‘drivers’ and weird serialization formats to deal with.

All you need to do to get started with CouchDB is a single command to install it through your package manager, start up the daemon, and start throwing http requests at it with curl or something.

That’s it. That’s all. CouchDB daemon + http client + JSON library, and you’re GOOD TO GO. If you want to wrap that up and make it object-oriented or something, that’s -trivial-. You can tell from the moment you start reading their documentation, or the wonderful, but apparently still WIP book, that the CouchDB designers have put a lot of effort into making life easy for you. They really do live up to their motto: Relax.

CouchDB has been a dream to work with — it’s easy to get set up, easy to use, and easy to manage, all-around. Sure, a big benefit comes just from the fact that CouchDB is one of those shiny new NoSQL databases. Couch, though, goes the extra mile for you. You know what I don’t want to do? I don’t want a ‘driver’. I don’t want BSON.

You know what I do want? I want to go play with CouchDB some more — and you should too.

There is also now a manual! A pretty one in both PDF and HTML form, which can be found at our new project page on common-lisp.net. There’s also some mailing lists on that page you might want to sign up for if you feel like tracking Sheeple development.

Things have slowly been ramping up. Ever since I gave that talk at the TC Lispers meeting, a few other people have given Sheeple a whirl. I’m pleased that their experiences have been good, even though Sheeple is still a bit unstable. Of particular note is Patrick Stein’s Wooly, a GL-based GUI toolkit using Sheeple objects.

Development has slowed down a bit since I started working at Clockwork, but I’ve been working with Adlai lately towards a native-Sheeple MOP. So far, the basics of object creation have been taken care of, and a property MOP should be up and running soon. We’ve also decided to rename persistent-sheeple, but that will get announced once we have enough of a MOP to hook up our objects to CouchDB.

After months in development, it’s finally done. A major rewrite of the entire Sheeple system, this new version boasts a completely new, cleaned up, and serious’d interface, reworked, lightweight objects, and efficient property access (right now, matching CCL’s slot-value performance.) You can download a tarball here, or use asdf-install to grab the latest version.

I’m really excited about this release. I would write more about it and all the goodies it has, but I have a presentation to finish. Expect more in a later post.

Sheeple took a break for a few weeks, but development is up to full steam again. There’s some shiny new special sauce going on under the hood now, with some -very- promising early results.

See this paste for some picobenchmarks on various implementation. Notice: direct-property access is now as fast as slot-value on CCL. :)

Unfortunately, the rest of Sheeple doesn’t perform that well quite yet. The new fancy secret sauce allows for a lot of optimizations that weren’t done before. Once this code is stabilized and tagged as 3.0(!), I’m bringing back a bunch of different caching schemes Sheeple was using for dispatch. Tonight’s benchmarks were promising — I think Sheeple may actually be able to perform better and faster than optimized CLOS implementations such as CCL’s and SBCL’s.

We’ll see. We’ll see…

STM caught my eye for a while, but it still has its issues, and I’m still not sure how I feel about the whole “thrash until you can agree on something” issue — it seems to me like it’s just the same as wrapping code in (with-lock-held …). Futures/promises looked easy enough for simple one-shot tasks, but that’s not necessarily what you want to do when you write heavily-parallel code: Sometimes you want threads constantly yielding values. Erlang-style actors are, of course, one of the big success stories when it comes to people trying to write heavily-parallel code. It just seems so damn ugly — and it -is- nice to be able to share data sometimes.

Then, magic happened: I came across something called Communicating Sequential Processes, through Rob Pike’s Google Tech Talk on Newsqueak. It was really amazing, it seemed to be just what I needed: a relatively low-level synchronisation mechanism that works naturally with the concept of multiple parallel threads/processes. I’m totally sold on Rob’s point of view here: don’t try to pretend you’re not parallelizing code (hear that, STM? That’s right). Instead, make the parallelization part of your interface. Deadlocks are a bug — find them.

I spent a good while thinking about CSP, wondering why the heck everything else is the talk of the town. The more I thought about it, the more I was amazed that CSP wasn’t everyone’s obvious choice when it came to parallelization. I kept wondering why no one seemed to even know about it. Then again, it’s not entirely obscure — Stackless Python uses this exact same concept. Clearly, the only way I could really get a good idea of what CSP is all about, and what its advantages/disadvantages are was by actually using it.

As it turns out, there was already an existing library for CL that implemented these: csp. The API, unfortunately, was a bit weird, and I couldn’t get myself into really using. I just didn’t get it — is CSP a red herring meant to distract me from some other Right Thing? I figured the only way to find out, then, would be to implement my own library.

Enter ChanL, my attempt at implementing channels in CL. I’ve been working with Adlai on these for a couple of weeks, and we just tagged v0.4. As the library developed, and we started writing examples, things started becoming more and more clear. Channels, as it turns out, are just high-level enough to make a lot of tasks extremely easy that would otherwise be a bit obnoxious to write with locks.Well, sort of: it turns out to be a little tricky to convert existing, very-linear code into channels unless you’re used to them (STM certainly wins in that front, I have to say)… but once you’ve embraced the concurrent nature of your algorithm, channels become a powerful beast.

The most interesting part, I think, is that channels turned out to be extremely useful for implementing -other- sorts of (sometimes simpler) concurrency mechanisms. Futures/promises, for example, were implemented in about 20 lines of code. The whole chanl/examples/futures.lisp file is 93 lines long, including comments, several convenience macros for creating futures, a select function, and a parallelized version of LET, as well as a fully-functional cross-thread condition-handling mechanism. That’s a lot of stuff, and it was made simple because of how nice channels are. Actors can be implemented similarly, and, in fact, I’m working on them already, although the code isn’t online yet.

All-in-all, after working with channels for a few weeks, my impression is that they’re much closer to a generalizable solution to handling concurrency than all these other constructs that keep popping up (again, perhaps with the exception of STM, which has different issues). I’m still honestly perplexed as to why channels aren’t more widely accepted and used. Perhaps it’s high time that changed.

If you ever feel like messing around with channels, go ahead and try it out. It’s asdf-installable with (asdf-install:install :chanl), or you can download it at Github. It’s got a fully-documented API, and you can even write your own unique channel styles fairly easily.

Next time: ChanL code samples/examples.

These numbers are on Clozure CL x86  Linux:

SHEEPLE> (time (loop repeat 100000 do (allocate-std-sheep)))
(LOOP REPEAT 100000 DO (ALLOCATE-STD-SHEEP)) took 119 milliseconds (0.119 seconds) to run
                    with 2 available CPU cores.
During that period, 106 milliseconds (0.106 seconds) were spent in user mode
                    3 milliseconds (0.003 seconds) were spent in system mode
50 milliseconds (0.050 seconds) was spent in GC.
 4,000,000 bytes of memory allocated.
 19 minor page faults, 0 major page faults, 0 swaps.

And a single sheep object:

SHEEPLE> (time (allocate-std-sheep))
(ALLOCATE-STD-SHEEP) took 0 milliseconds (0.000 seconds) to run
                    with 2 available CPU cores.
During that period, 0 milliseconds (0.000 seconds) were spent in user mode
                    0 milliseconds (0.000 seconds) were spent in system mode
 40 bytes of memory allocated.

Now, that’s still a bit heavy compared to CLOS (which only allocates 24 bytes for a raw instance), and to be honest, I’m not aiming at beating CLOS. It’s like a class-based system trying to beat out structs. On the other hand, it’s actually pretty nice to shrink everything down to more usable levels.
The current Sheeple release, for example, the one built on top of CLOS, is quite a monster:

SHEEPLE> (time (loop repeat 100000 do (allocate-sheep)))
(LOOP REPEAT 100000 DO (ALLOCATE-SHEEP)) took 11,273 milliseconds (11.273 seconds) to run
                    with 2 available CPU cores.
During that period, 10,716 milliseconds (10.716 seconds) were spent in user mode
                    204 milliseconds (0.204 seconds) were spent in system mode
3,249 milliseconds (3.249 seconds) was spent in GC.
 244,000,000 bytes of memory allocated.
 9,419 minor page faults, 0 major page faults, 0 swaps.

So yeah, this is a huge improvement.

Keep in mind that all of these numbers don’t yet take into account what the full cost of a raw (clone) will be, although it won’t be much higher than what it is right now (I believe it will only be two extra words, because an item will be added to the parents list).

It’s a bit fun to mess around with stuff so carefully at a lower level…

The original reason for writing Sheeple, like I said before, was to use it with Sykosomatic (which I still haven’t written an entry for, meh). That said, Sykosomatic’s object system needs to be fully persistent. Sheeple itself is not persistent — it works like a standard run-time object system.

Because I’m a masochist and a nerd, I figured I’d simply write Sheeple as the regular object system that it is, then “just” add a Metaobject Protocol like CLOS’ once the base language was set. Ho boy, did I ask for trouble. MOPs are a royal pain in the ass to do properly, and they’re a bit mind-bending. Regardless, Sheeple has been slowly getting MOP features over time. The neat part? The MOP itself is written in CLOS (as are a lot of Sheeple’s internals).

What I managed to get done today is the protocol for manipulating properties and property behavior through property metaobjects.

To show how it works, let’s go over an example of how one might implement persistent-sheeple, so maybe the damn thing can actually be used for Sykosomatic…

(in-package :sheeple-user)

(defvar *max-oid* 0)
(defclass persistent-sheep (standard-sheep)
  ((oid :initform (incf *max-oid*) :reader oid)))

(defclass persistent-property (standard-property) ())

The first step to changing behavior is to make some subclasses. We’ll be dispatching on these.

(defmethod initialize-instance :after ((sheep persistent-sheep) &key)
  (allocate-sheep-externally sheep))

(defmethod add-parent :around ((new-parent standard-sheep)
                               (child persistent-sheep))
  (if (or (eql new-parent =dolly=)
          (eql (find-class 'persistent-sheep)
               (class-of new-parent)))
      (progn
        (call-next-method)
        (add-parent-externally new-parent child))
      (error "We don't support adding non-persistent~
              sheep as parents!")))

The first and most important part of having a persistent object is that it’s somehow allocated externally. All Sheeple are standard CLOS instances, so this method will get called each and every time the sheep object is created.

We also go ahead and write a method for add-parent. This is important because we want to make sure that we can successfully serialize the sheep. We must always have at -least- =dolly= as a parent, so we have to make an exception for that. Other than that, no non-persistent sheep are allowed into a persistent-sheep’s hierarchy list. Note that methods defined on add-parent must not override the standard behavior (basically, the (standard-sheep standard-sheep) method must always be called). Other than that, clients are free to go wild with what they do with this one.

With this much code (aside from serialization and db-management stuff!) we can now have externally-stored sheep objects. The rest of sheeple will work normally at this point. The whole point of persistent-sheeple, though, is to be able to store property values externally, so here we go…

(defmethod add-property :around ((sheep persistent-sheep) pname
                                 value &key transientp)
  (register-property-externally sheep pname)
  (if transientp
      (call-next-method)
      (call-next-method sheep pname value
                        :property-metaclass 'persistent-property)))

(defmethod add-property-using-property-metaobject :before
    ((sheep persistent-sheep) value
     (property persistent-property) &key)
  (allocate-property-externally sheep pname))

Because Sheeple requires that properties be specifically added to the hierarchy-list, we have these two functions: The first one takes care of creating a property metaobject for the second one to dispatch on. In this case, we make our :around method on add-property accept a keyword that tells it whether a property should be transient or not.

For the purpose of this exercise, we assume that a transient property is simply a regular property on a persistent-sheep. Since we want to make sure we’ve got the property available when we restore the database, though, we register its existence regardless of whether it’s transient or not.

Next up, in a-p-u-p-m, we actually dispatch on the property object itself, instead of just the class. This :before method sits there to make sure we have external DB space to allocate a value on, since we’re sure in this case that we’ll be assigning actual values to this one.

Once that’s set, it’s just a matter of making sure we can get/set those values, and we’re home free…

(defmethod direct-property-value ((sheep persistent-sheep)
                                  (property persistent-property))
  (get-property-value-externally sheep (property-name property)))

(defmethod (setf property-value) (new-value (sheep persistent-sheep)
                                  (property persistent-property))
  (set-property-value-externally sheep (property-name property)
                                 new-value))

And that’s it. We override the standard getting/setting behavior so nothing is set locally: Storage lives in the database.

Keep in mind here that a built-in :before method for (setf property-value) will take care of calling add-property as appropriate when the sheep object does not have a direct property metaobject registered for that property-name.

Now we can actually use it:

(defproto =psheep= ()
  ((foo "bar")
   (baz "quux" :transientp t))
  (:metaclass 'persistent-sheep))

(note: defproto changed a bit in recent commits, more on that later…)

And there you have it! (setf (foo =psheep=) "Blargh") is all it takes to start changing stuff in your new persistent sheep. The rest of sheeple will work as expected. It’s worth noting that roles belonging to this object won’t be persisted, since we only messed around with object creation and properties.

Discussion

While I’m very pleased that the MOP has come this far, I have to admit that it probably doesn’t work very well right now. It’s very new, and very much still a work-in-progress. There’s probably certain things that could be cleaned up and all that, but I think it’s certainly a step in the right direction.

I’m honestly not entirely sure what I’m doing half the time. Even though I’ve read through AMOP several times, some of this is still a bit confusing, and I haven’t actually used CLOS’ MOP very much at all. I’m playing it by ear (with a hell of a lot of help from the debugger!)

Hopefully, as the MOP grows (and evolves), it’ll settle into something generally useful. For now, though, YMMV if you want to mess with it.