Clojure-style Multimethods in Emacs Lisp
This past week I added Clojure-style multimethods to Emacs
Lisp through a package I call
predd (predicate dispatch). I
believe it is Elisp’s very first complete multiple dispatch object
system! That is, methods are dispatched based on the dynamic,
run-time type of more than one of its arguments.
(Unfortunately I was unaware of the other Clojure-style multimethod library when I wrote mine. However, my version is much more complete, has better performance, and is public domain.)
As of version 23.2, Emacs includes a CLOS-like object system cleverly named EIEIO. While CLOS (Common Lisp Object System) is multiple dispatch, EIEIO is, like most object systems, only single dispatch. The predd package is also very different than my other Elisp object system, @, which was prototype based and, therefore, also single dispatch (and comically slow).
The Clojure multimethods documentation provides a good
introduction. The predd package works almost exactly the same way,
except that due to Elisp’s lack of namespacing the function names are
predd-. Also different is that the optional hierarchy
h) argument is handled by the dynamic variable
which holds the global hierarchy.
To define a multimethod, pick a name and give it a classifier function. The classifier function will look at the method’s arguments and return a dispatch value. This value is used to select a particular method. What makes predd a multiple dispatch system is the dispatch value can be derived from any number of methods arguments. Because the dispatch value is computed at run-time this is called a late binding.
Here I’m going to define a multimethod called
combine that takes two
arguments. It combines its arguments appropriately depending on their
dynamic run-time types.
(predd-defmulti combine (lambda (a b) (vector (type-of a) (type-of b))) "Appropriately combine A and B.")
The classifier uses
type-of, an Elisp built-in, to examine its
argument types. It returns them as tuple in the form of a vector. The
classifier of a method can be accessed with
I’ll use to demonstrate what these dispatch values will look like.
(funcall (predd-classifier 'combine) 1 2) ; => [integer integer] (funcall (predd-classifier 'combine) 1 "2") ; => [integer string]
I chose a vector for the dispatch value because I like the bracket
style when defining methods (you’ll see below). The dispatch value can
be literally anything that
equal knows how to compare, not just
vectors. Note that it’s actually faster to create a list than a vector
up to a length of about 6, so this multimethod would be faster if the
classifier returned a list — or even better: a single cons.
Now define some methods for different dispatch values.
(predd-defmethod combine [integer integer] (a b) (+ a b)) (predd-defmethod combine [string string] (a b) (concat a b)) (predd-defmethod combine [cons cons] (a b) (append a b))
Now try it out.
(combine 1 2) ; => 3 (combine "a" "b") ; =>"ab" (combine '(1 2) '(3 4)) ; => (1 2 3 4) (combine 1 '(3 4)) ; error: "No method found in combine for [integer cons]"
Notice in the last case it didn’t know how to combine these two types,
so it threw an error. In this simple example where we’re only calling
a single function, so rather than use the
these methods can be added directly with the
function. This has the exact same result except that it has slightly
better performance (no wrapper functions).
(predd-add-method 'combine [integer integer] #'+) (predd-add-method 'combine [string string] #'concat) (predd-add-method 'combine [cons cons] #'append)
Use the Hierarchy
+ function is already polymorphic. It seamlessly operates
on both floats and integers. So far it seems there’s no way to exploit
this with multimethods. Fortunately we can solve this by defining our
own ad hoc hierarchy using
predd-derive. Both integers and floats
are a kind of number. It’s important to note that
number. We’re introducing that name here ourselves.
(type-of 1.0) ; => float (predd-derive 'integer 'number) (predd-derive 'float 'number) ;; Types can derive from multiple parents, like multiple inheritance (predd-derive 'integer 'exact) (predd-derive 'float 'inexact)
This says that
float are each a kind of
we can use
number in a dispatch value. When it sees something like
[float integer] it knows that it matches
(predd-add-method 'combine [number number] #'+) (combine 1.5 2) ; => 3.5
We can check the hierarchy explicitly with
isa?). It compares two values just like
equal, but it
also accounts for all
predd-derive declarations. Because of this
extra concern, unlike
predd-isa-p is not commutative.
(predd-isa-p 'number 'number) ; => 0 (predd-isa-p 'float 'number) ; => 1 (predd-isa-p 'number 'float) ; => nil (predd-isa-p [float float] [number number]) ; => 2
0 is truthy in Elisp.) The integer returned is a
distance metric used by method dispatch to determine which values are
“closer” so that the most appropriate method is selected.
You might be worried that introducing
number will make the
multimethod slower. Examining the hierarchy will definitely have a
cost after all. Fortunately predd has a dispatch cache, so
introducing this indirection will have no additional performance
penalty after the first call with a particular dispatch value.
Something that really sets these multimethods apart from other object
systems is a lack of concern about encapsulation — or really about
object data in general. That’s the classifier’s concern. So here’s an
example of how to combine predd with
defstruct from cl/cl-lib.
Imagine we’re making some kind of game where each of the creatures is
represented by an
actor struct. Each actor has a name, hit points,
and active status effects.
(defstruct actor (name "Unknown") (hp 100) (statuses ()))
defstruct macro has a useful inheritance feature that we can
exploit for our game to create subtypes. The parent accessors will
work on these subtypes, immediately providing some (efficient)
polymorphism even before multimethods are involved.
(defstruct (player (:include actor)) control-scheme) (defstruct (stinkmonster (:include actor)) (type 'sewage)) (actor-hp (make-stinkmonster)) ; => 100
As a side note: this isn’t necessarily the best way to go about modeling a game. We probably shouldn’t be relying on inheritance too much, but bear with me for this example.
Say we want an
attack method for handling attacks between different
types of monsters. Elisp structs have a very useful property by
default: they’re simply vectors whose first element is a symbol
denoting its type. We can use this in a multimethod classifier.
(make-player) ;; => [cl-struct-player "Unknown" 100 nil nil] (predd-defmulti attack (lambda (attacker victim) (vector (aref attacker 0) (aref victim 0))) "Perform an attack from ATTACKER on VICTIM.")
Let’s define a base case. This will be overridden by more specific methods (determined by that distance metric).
(predd-defmethod attack [cl-struct-actor cl-struct-actor] (a v) (decf (actor-hp v) 10))
We could have instead used
:default for the dispatch value, which is
a special catch-all value. The
actor-hp function will signal an
error for any victim non-actors anyway. However, not using
will force both argument types to be checked. It will also demonstrate
specialization for the example.
However, before we can make use of this we need to teach predd about
the relationship between these structs. It doesn’t check
hierarchies. This step is what makes combining
defstruct and predd
a little unwieldy. A wrapper macro is probably due for this.
(predd-derive 'cl-struct-player 'cl-struct-actor) (predd-derive 'cl-struct-stinkmonster 'cl-struct-actor) (let ((player (make-player)) (monster (make-stinkmonster))) (attack player monster) (actor-hp monster)) ;; => 90
When the stinkmonster attacks players it doesn’t do damage. Instead it applies a status effect.
(predd-defmethod attack [cl-struct-stinkmonster cl-struct-player] (a v) (pushnew (stinkmonster-type a) (actor-statuses v))) (let ((player (make-player)) (monster (make-stinkmonster))) (attack monster player) (actor-statuses player)) ;; => (sewage)
If the monster applied a status effect in addition to the default attack behavior then CLOS-style method combination would be far more appropriate here (if only it was available in Elisp). The method would instead be defined as an “after” method and it would automatically run in addition to the default behavior.
If I was actually building a system combing structs and predd, I would be using this helper function for building classifiers. It returns a dispatch value for selected arguments.
;;; -*- lexical-binding: t; -*- (defun struct-classifier (&rest pattern) (lambda (&rest args) (loop for select-p in pattern and arg in args when select-p collect (elt arg 0)))) ;; Takes 3 arguments, dispatches on the first 2 argument types. (predd-defmulti speak (struct-classifier t t nil)) ;; Messages sent to the player are displayed. (predd-defmethod speak '(cl-struct-actor cl-struct-player) (from to message) (message "%s says %s." (actor-name from) message))
As of this writing there isn’t yet a
disambiguating equally preferred dispatch values. I will add it in the
future. I think
prefer-method gets unwieldy quickly as the type
hierarchy grows, so it should be avoided anyway.
I haven’t put predd in MELPA or otherwise published it yet. That’s what this post is for. But I think it’s ready for prime time, so feel free to try it out.