Wednesday, July 17, 2013

alist or plist?

Another digression. We'll get to those persistent clos objects shortly, I promise.

In Lisp it is common to create little tables that map keys to values. You'd use a hash-table for any "serious" work, but sometimes you just want store a couple of items for a moment or two and you don't want to bother with the all the baggage that comes along with declaring, creating, and using hash tables.

There are two ways of doing this, both of which date back to the very earliest lisp implementations. An alist, or association list, is simply a list of associations. Each association has a key and a value. A plist, or property list, on the other hand, is a list of alternating keys and values.

Here is an alist:
((:name . "Joe")
 (:favorite-color . "Blue"))
Here is an equivalent plist:
(:name "Joe" :favorite-color "Blue")

There really isn't much of a difference between the two. Obviously you cannot just substitute one for the other because you need to use different accessors, but otherwise there seems little reason to prefer one to the other.

Alists have the nice property that they are implemented as a list of homogeneous elements. Each element in an alist is an "association". Lisp doesn't care about that, but it seems tidier.

Plists, on the other hand, are implemented with a heterogeneous list. The keys occupy the even elements, the values the odd. Again, Lisp doesn't care. But if you are misaligned in a plist, you'll end up thinking the keys are values and the values are keys and you'll pair the values with the keys to the subsequent entries.

Teachers love to make problem sets out of these things.

Alists are "deeper" because there is substructure to the entries. Plists are "flat" because the single list backbone is doing double duty linking keys to values and linking the key-value pairs together. Every key in a plist must have an associated value, but you can put a "key only" entry into an alist.

But there is one very special thing about a plist: it is isomorphic to a keyword argument list. This means you can apply a procedure to a plist and get the keyword argument mechanism to unpack it and bind the named parameters to the values. Watch:
(defun foo (&key name favorite-color)
  (format t "~%~a's favorite color is ~a" name favorite-color))

(let ((my-plist '(:name "Joe" :favorite-color "Blue")))
  (apply #'foo my-plist))
The order of the "entries" doesn't matter. This works, too:
(let ((another-plist '(:favorite-color "Blue" :name "Joe")))
  (apply #'foo another-plist))

Missing a table entry? Use argument defaulting:
(defun foo (&key (name "Unknown") favorite-color)
  (format t "~%~a's favorite color is ~a" name favorite-color))

(let ((another-plist '(:favorite-color "Blue")))
  (apply #'foo another-plist))
With judicious use of &rest, &key, and &allow-other-keys, you can pick out certain named entries, ignore the remaining ones, and pass the entire plist on to another procedure:
(defun baz (&rest args &key name &allow-other-keys)
  (print name)
  (apply #'foo args))
And because keyword handling works from left to right, with the earlier (leftmost) arguments taking precedence, you can override selected entries by simply shadowing them:
(define quux (&rest args &key name &allow-other-keys)
  (when (equalp name "Joe")
    (apply #'foo `(:favorite-color "Black" ,@args))))
Just some stupid plist tricks? No. When we couple this with generic procedures, method combination, and quasiquote we suddenly have a very powerful way to modify behaviors through delegation. We make considerable use of this in extending CLOS to handle persistent and versioned objects.

Try doing this in a more traditional language. It simply does not work anywhere nearly as smoothly.

6 comments:

Xach said...

I also like that these structures can be non-destructively modified by consing stuff onto the front, which is very handy for recursively processing something while incrementally extending a lookup table.

Anonymous said...

And here I thought you were kind of a Scheme guy.

You know this of course, but overriding can be even more convenient:

(apply #'foo :favorite-color "Black" args)

Galactus said...

small nitpick: shouldnt the first example alist be:

((:name . "Joe")
(:favorite-color . "Blue")) ?

(to be equivalent to the plist)

Joe Marshall said...

Thanks, Galactus. Dumb typo fixed.

Joe Marshall said...

Scheme?

Unknown said...

There seems to be an enormous missing "* Note: in Common Lisp" qualifier somewhere in this article...