nullprogram.com/blog/2013/12/18/
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
prefixed with predd-. Also different is that the optional hierarchy
(h) argument is handled by the dynamic variable predd-hierarchy,
which holds the global hierarchy.
Combination Example
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 predd-classifier, which
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 predd-defmethod macro
these methods can be added directly with the predd-add-method
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
Hmmm, the + 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 type-of never
returns 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 integer and float are each a kind of number. Now
we can use number in a dispatch value. When it sees something like
[float integer] it knows that it matches [number number].
(predd-add-method 'combine [number number] #'+)
(combine 1.5 2) ; => 3.5
We can check the hierarchy explicitly with predd-isa-p (like
Clojure’s isa?). It compares two values just like equal, but it
also accounts for all predd-derive declarations. Because of this
extra concern, unlike equal, 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
(Remember that 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.
Struct Example
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 ()))
The 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 :default
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 defstruct
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))
The Future
As of this writing there isn’t yet a prefer-method for
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.