Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An example of how multi-method-based dispatch might work for a binary operation like matrix multiplication. Illustrates how a variety of coercion-based defaults can be specified to make life easy on the implementer, while still easily allowing for dispatch to optimal implementation-specific routines whenever it's desired.
;; First some dummy matrix types and operations for us to play with later:
(deftype GenericDense [])
(deftype FooMatrix [])
(deftype BarMatrix [])
(defn generic-multiply [x y] "generic-multiply")
(defn foo-multiply [x y] "foo-multiply")
(defn bar-multiply [x y] "bar-multiply")
(defn foo-generic-multiply [x y] "foo-generic-multiply")
(defn generic-foo-multiply [x y] "generic-foo-multiply")
(defn bar-generic-multiply [x y] "bar-generic-multiply")
(defn generic-bar-multiply [x y] "generic-bar-multiply")
(defn foo-bar-multiply [foo bar] "foo-bar-multiply")
(defn bar-foo-multiply [foo bar] "bar-foo-multiply")
(defn foo-to-generic-dense [foo] (println "foo-to-generic-dense") (GenericDense.))
(defn bar-to-generic-dense [bar] (println "bar-to-generic-dense") (GenericDense.))
;; Define a multimethod dispatching on classes of both arguments:
(defmulti matrix-multiply (fn [x y] [(.getClass x) (.getClass y)]))
(defmethod matrix-multiply :default [x y]
(throw (Throwable. (str "Don't know how to multiply " (class x) " with " (class y)))))
;; To minimise the work required of implementors, we set up some
;; fallback methods which multiply matrices using coercions to a
;; generic dense matrix format (here called GenericDense).
;;
;; We'll implement coercions via protocols since they're single
;; argument dispatched (although see later re using protocols in
;; multimethod hierarchies).
;;
;; Note that there's nothing special about GenericDense here --
;; support for fallback coercion rules via other intermediate formats
;; could be added in a similar way alongside this one, provided
;; you break ties as required using derives/prefer-method.
;; First let's make sure we can multiply instances of our GenericDense
;; representation:
(defmethod matrix-multiply [GenericDense GenericDense]
[x y]
(generic-multiply x y))
;; Then declare a protocol for coercion to our generic format:
(defprotocol PCoerceToGenericDense
(coerce-to-generic-dense ^GenericDense [this]))
;; It helps to have the generic format itself extend this protocol in
;; the obvious trivial way:
(extend-protocol PCoerceToGenericDense GenericDense
(coerce-to-generic-dense [this] this))
;; (Slight implementation annoyance relating to multimethod/protocols:
;; Since only classes and tags can be used in multimethod hierarchies,
;; not protocols, we need to require that protocol implementors also
;; derive from a similarly-named tag if they want to benefit from the
;; coercion-based multimethods. This wouldn't be necessary if we used
;; multimethods for the coercion protocol too.)
(derive GenericDense ::PCoerceToGenericDense)
;; Now implement the dumbest fallback rule for multiplication: coerce
;; both arguments to a generic representation and then multiply them:
(defmethod matrix-multiply [::PCoerceToGenericDense ::PCoerceToGenericDense]
[x y]
(generic-multiply
(coerce-to-generic-dense x)
(coerce-to-generic-dense y)))
;; To allow for smarter coercion rules where only one of the two
;; arguments requires coercion, we define another protocol. Two
;; methods are required because matrix multiplication isn't commutative:
(defprotocol PMultiplyWithGenericDense
(multiply-this-with-generic [this ^GenericDense generic])
(multiply-generic-with-this [this ^GenericDense generic]))
;; We define multimethods which take advantage of these coercion-based protocols:
(defmethod matrix-multiply [::PMultiplyWithGenericDense ::PCoerceToGenericDense]
[x y]
(multiply-this-with-generic x (coerce-to-generic-dense y)))
(defmethod matrix-multiply [::PCoerceToGenericDense ::PMultiplyWithGenericDense]
[x y]
(multiply-generic-with-this y (coerce-to-generic-dense x)))
;; We place this more specific higher-priority implementation below the
;; more generic one in the hierarchy to ensure that this is preferred
;; when available, over the "coerce both arguments" method.
(derive ::PMultiplyWithGenericDense ::PCoerceToGenericDense)
;; We need a tie-breaker to decide between the above too cases when
;; both arguments support both protocols. (Which gets coerced and
;; which doesn't? It's a somewhat arbitrary call). Here we prefer the
;; first case, although if some implementation prefers it the other way
;; round they can defmethod their own type-specific version and
;; prefer-method it as they desire.
(prefer-method matrix-multiply
[::PMultiplyWithGenericDense ::PCoerceToGenericDense]
[::PCoerceToGenericDense ::PMultiplyWithGenericDense])
;; As before extenders of the protocol must also derive the keyword
;; version to work with these multimethod dispatch rules.
;; Now, what does the implementer of FooMatrix, a dense matrix type,
;; need to do to support matrix multiplication?
;; This alone is sufficient as a bare-minimum implementation:
(extend-type FooMatrix PCoerceToGenericDense
(coerce-to-generic-dense [foo] (foo-to-generic-dense foo)))
(derive FooMatrix ::PCoerceToGenericDense)
;; It will make (matrix-multiply foo foo) to work via coercion of
;; both arguments to GenericDense.
;; It will also make (matrix-multiply foo bar) work for any bar
;; whose class derives from ::PCoerceToGenericDense or
;; ::PMultiplyWithGenericDense.
;; Adding this is then sufficient to make Foo-Foo multiplication dispatch to
;; implementation-specific code rather than go via coercions:
(defmethod matrix-multiply [FooMatrix FooMatrix]
[x y]
(foo-multiply x y))
;; If you have a way of multiplying Foo directly
;; with a GenericDense which doesn't involve coercing Foo to a
;; GenericDense too, you can:
(extend-type FooMatrix
PMultiplyWithGenericDense
(multiply-this-with-generic [this generic]
(foo-generic-multiply this generic))
(multiply-generic-with-this [this generic]
(generic-foo-multiply generic this)))
(derive FooMatrix ::PMultiplyWithGenericDense)
;; You could also implement it like this, which requires two coercions
;; (bar -> generic then generic -> foo then foo-foo multiplication)
;; but at least ensures that foo remains un-coerced and that the
;; result isn't generic.
;; (extend-type FooMatrix
;; PMultiplyWithGenericDense
;; (multiply-this-with-generic [this generic]
;; (foo-multiply this (foo-from-generic generic)))
;; (multiply-generic-with-this [this generic]
;; (foo-multiply (foo-from-generic generic) this)))
;; Now suppose we add another implementation Bar (perhaps in another library):
(defmethod matrix-multiply [BarMatrix BarMatrix]
[x y]
(bar-multiply x y))
(extend-type BarMatrix PCoerceToGenericDense
(coerce-to-generic-dense [bar] (bar-to-generic-dense bar)))
(derive BarMatrix ::PCoerceToGenericDense)
(extend-type BarMatrix
PMultiplyWithGenericDense
(multiply-this-with-generic [this generic]
(bar-generic-multiply this generic))
(multiply-generic-with-this [this generic]
(generic-bar-multiply generic this)))
(derive BarMatrix ::PMultiplyWithGenericDense)
;; (multiply-matrix foo bar) and vice versa should now work nicely via
;; a single coercion.
;; Suppose we'd like to multiply Foos with Bars without having to
;; coerce either argument to the generic format though. (E.g. say Foo
;; is a dense matrix and Bar is a sparse one).
;;
;; This doesn't require any changes to FooMatrix -- one just needs to:
(defmethod matrix-multiply [FooMatrix BarMatrix]
[foo bar] (foo-bar-multiply foo bar))
(defmethod matrix-multiply [BarMatrix FooMatrix]
[bar foo] (bar-foo-multiply bar foo))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment