Obscure suggestions

Suppose you have come up with an elegant recursive algorithm that is easy to understand and implement. This will not do. A true mathematician is judged by how clever he must be to understand his algorithm. To that end, you must make your algorithm as difficult to understand as possible. This is how you prove that you are smarter than your readers. Here are some suggestions:

• Instead of giving the next state as function of the current state, give the current state as a function of the next state and let your audience invert the function.
• Split your recursion into two parts, but give one part recursively and the other co-recursively. Your readers will enjoy the fun puzzle of figuring out how to stitch the parts back together.
• Remove the recursion by replacing it with re-assignment and explicit stack manipulation.
• Avoid motivating examples.
• Omit all unnecessary details, and a few of the necessary ones as well.
• Unicode gives you thousands of single character variable names.
• Use existance proofs rather than constructive ones. You can prove there is a base case without explicitly stating what it is.
• Let X refer to a set or an element of a set, depending on context.
• Depend on the context. A lot.
• There is no rule that says variable names must be unique.

Take and apply some of these ideas and you can turn your elegant algorithm into something that will humiliate the smartest of your readers.

Defclass vs. defstruct

Common Lisp provides two ways to create new compound data types: defstruct and defclass. Defstruct creates simple cartesian record types, while defclass is part of a full object-oriented programming system. How do you decide which one to use?

It’s easy. Unless you have a compelling reason to use defstruct, just use defclass. Even if you don’t use any other features of CLOS, defclass better supports class redefinition, and this just makes life easier.

If you modify a defstruct and recompile it, the old instances of that struct type become obsolete. They probably won’t work with the new definition. You’ll most likely have to rebuild them. If things get too screwed up, you’ll end up having to restart your Lisp image.

CLOS, on the othe hard, is designed to be dynamic. You can redefine and recompile a class on the fly. You can change the class of an instance. As you develop your code, you’ll be adding and removing slots and changing the class hierarchy. defclass usually handles these sorts of dynamic changes transparently, without having to restart your Lisp image.

CLOS achieves this by adding an extra level of indirection, and perhaps you cannot tolerate the extra overhead. Then by all means use defstruct. But if you are indifferent, defclass is a better choice.

Tip: Alphabetize arbitrary lists

Whenever I have a list of items, if there is no other better order for them, I arrange them in alphabetical order. Arbitrary lists have a way of getting large and unweildy over time, but if they are kept in alphabetical order, you can find the entries and spot omissions easier.

If there is a better ordering, then certainly use it. But keeping arbitrary lists alphabetized has two advantages: first, they are easier to use because you can find entries quicker. Second, it is a signal to the reader that the list is in fact in an arbitrary order.

with-slots vs. with-accessors

Most CLOS objects are implemented as standard-instances. A standard-instance is a collection of storage cells called slots, and the slots are addressed by name. You could imagine an alternative implementation where an instance is a vector that is addressed by an integer, but named slots are more flexible and abstract.

Many object systems map the named fields of an instance into lexically scoped variables. Within a method body, you can just refer to the slot as if it were a variable. Assignment to the variable effectively updates the slot. There are pros and cons to this. On the plus side, it is very convenient to refer to slots as if they were variables. On the minus side, it is difficult to rename a slot, because you have to rename all the references to it, and slot names can collide with lexical variables. It can make the code brittle with regard to slot naming. But CLOS lets you choose if you want to do this or not. The with-slots macro installs a set of symbol macros that let you refer to each slot as if it were a variable.

But the slots of an instance are an implementation detail. You really want an abstract API for your objects. You want logical fields to be accessed by getter and setter functions. The logical field will typically be backed by a slot, but it could be a computed value. Logical fields are more flexible and abstract than slots.

When you define a slot, you can specify a :reader and :accessor function for that slot. This covers the very common use case of a getter/setter pair that is backed by a slot in the instance.

You can also map the logical fields of an instance into lexical variables. The with-accessors macro installs a set of symbol macros that let you refer to each logical field as if it were a lexical varible.

I often see with-slots used where with-accessors would be more appropriate. If you find yourself wanting to use with-slots, consider if you should be using with-accessors instead.

Personally, I prefer to avoid both with-slots and with-accessors. This makes CLOS objects act more like structs. Structs are easier for me to understand than magic lexical variables.

Tip

The accessors for slots are generic. You therefore want them to have generic names. For example, suppose you have a point class with an x and y slot. You don't want to call your accessors point-x and point-y because the names would be inappropriate for subclasses. You want to have names something like get-x and get-y. These functions would naturally work on subclasses of points, but because get-x and get-y are generic, you could also extend them to work on any class that has a meaningful x and y.

Symbol macros

A symbol macro is a symbol that macroexpands into a lisp form. It is similar to a preprocessor macro in C, but it must expand into a syntactically complete expression. Symbol macros are the underlying technology behind the with-slots and with-accessors macros. They allow you to introduce an identifier that appears to be a lexical variable, but actually executes some arbitrary code to compute a value. So we can place the storage for a variable in a vector or in an instance, and use a symbol macro to make it appear to be an ordinary variable.

Gerry Sussman doesn't like symbol macros. They are a lie. It appears that you are just doing an ordinary variable access, which should be a quick and simple operation, but in fact you could be executing arbitrary code. This can lead to some nasty suprises.

But in my opinion, you shouldn't discard a useful tool just because there is a way to misuse it. If your symbol macro is just redirecting a variable to a slot in an instance, there is little harm in that.

Advanced CLOS — update-instance-for-changed-class

Like most object systems, instances in CLOS have a reference to their class. Unlike most most object systems, CLOS provides a protocol for changing that reference. Normally, this is a pretty insane thing to want to do. It effectively changes the class of the instance and it is pretty unlikely that the instance structure will be compatible with the new class. But there are two situations where you might want to do it anyway:

• When you edit the class definition, you can arrange for the system to dynamically upgrade existing instances to the new class definition. This means you won't have to restart your lisp and rebuild all the instances from scratch. You can just reload the class definition and the instances will be seamlessly upgraded on the fly. This is much more pleasant experience for the developer.
• While you normally don't want to change the class of an instance at runtime, there are some rare situations where it can make sense. A good example is the unified table interface. Instances are thin wrappers around a concrete table implementation. It makes sense to change a table instance from one concrete implementation to another. For instance, you might want to change a hash table to a assocation list. You can simply call change-class on the instance.

When the class changes, the representation will be wrong. This is where we add an :after method to update-instance-for-different-class:

(defmethod update-instance-for-different-class :after ((previous alist-table) (current plist-table) &rest initargs)
  (declare (ignore initargs))
  (setf (representation current) (alist-plist (representation previous))))
  
  ...etc...

> (defvar *foo* (make-instance 'alist-table :initial-contents '((:a . 420) (:b . 69))))
#<ALIST-TABLE 2 EQL>

> (representation *foo*)
((:A . 420) (:B . 69))

;; But I'd rather have a plist-table
  
> (change-class *foo* 'plist-table)
#<PLIST-TABLE 2 EQL>

> (representation *foo*)
(:a 420 :b 69)

;; And now I'd like a wttree-table

> (change-class *foo* 'wttree-table)
#<WTTREE-TABLE 2 EQUAL>

> (representation *foo*)
#(2 NIL :A #(1 NIL :B NIL 69) 420)

Naturally, you have to be judicious in your use of this feature of CLOS. You can easily construct nonsense objects. But some times it makes perfect sense,

Unified table interface

On day 16 of the Advent of Code, I make use of a priority queue for Dijkstra's algorithm. I ported Stephen Adams's weight-balanced binary tree implementation from MIT Scheme to Common Lisp. Stephen Adams's implementation (and therefore my port of it) has the MIT license. Weight-balanced binary trees are a way to implement key-value maps with these properties:

• The trees are immutable. This means that when you add or remove a key, you get a new tree with the change. The old tree is unchanged. This makes the trees easier to reason about and suitable for functional programming. For example, you can iterate over the tree without having to worry about mutating the tree during the iteration.
• Most operations on the tree, and insertion, lookup, and deletion in particular, are O(log n). While theoretically not as fast as a hash table, n has to be quite large before log n becomes a big factor. In practice, a weight balanced binary tree is competitive with a hash table for any reasonably sized table.
• Weight-balanced binary trees support set operations such as union, intersection, and difference. These operations run in O(log n) time as well.
• Keys are stored in sorted order. This makes it easy to iterate from smallest to largest key (or in the direction).

But it occurred to me that I wanted a unified abstract interface to all the various table-like data structures that Common Lisp provides. You should be able to call a generic table/lookup on a property list, association list, hash table, or weight-balanced binary tree and have it do the right thing. I wrote a simple table package that provides this.

https://github.com/jrm-code-project/table

The package is documented in the `README.md` fie.