What is Predicate Dispatch

I have seen much talk about predicate dispatch in Clojure lately and wonder if there is something to this thing. In other words, what is predicate dispatch开发者_开发百科 and how does it differ from generic functions, OOP polymorphism, and patterns? Thank you

---

Predicate dispatch subsumes generic functions, OOP polymorphism, pattern matching, and more. A good overview is Predicate dispatching: A unified theory of dispatch by Michael Ernst, Craig Kaplan, and Craig Chambers. From its abstract:

Predicate dispatching generalizes previous method dispatch mechanisms by permitting arbitrary predicates to control method applicability and by using logical implication between predicates as the overriding relationship. The method selected to handle a message send can depend not just on the classes of the arguments, as in ordinary object-oriented dispatch, but also on the classes of subcomponents, on an argument's state, and on relationships between objects.

---

Edited: Clojure multimethods are not predicate dispatch.

In traditional object-oriented programming, polymorphism means that you can have multiple implementations of a method, and the exact implementation that gets called is determined by the type of the object on which you called the method. This is type dispatch.

Clojure multimethods extend this so that an arbitrary function can decide which implementation gets called. In the Clojure form (defmulti name f), the function f is the dispatch function.

The dispatch function could be class, in which case you're back to type dispatch. But that function could be anything else: computing a dispatch value, looking up stuff in a database, even calling out to a web service.

True predicate dispatch would potentially allow each method implementation to specify one or more dispatch functions (predicates) to decide when that method applies. This is more general than multimethods but more complicated to implement. Clojure does not support it.

Generic function is a term from other Lisps. Common Lisp, for example, provides generic functions which can dispatch on type plus a restricted set of other functions.

---

Predicate dispatch is a way of providing different responses to a function call, based on the number, "shape" and values of the arguments to the function. Clojure functions already dispatch to different bodies of code, depending on the number of arguments passed to the function:

(defn my-func
  ([a] (* a a))
  ([a b] (* a b)))

Clojure multimethods add to this the ability to dispatch to different methods—perhaps defined in different namespaces—based on the return value of a dispatch function that examines the arguments (which can include their number, class, and value) and identifies which method to all. As noted in the footnotes to Stuart Sierra's answer, the creator of the multimethod gets to define the dispatch function, and it can't ordinarily be modified. Also, the programmer has to hand-design an ultra-complex dispatch function for a function that executes one thing for an integer of value 0, and another for a positive integer; or one thing for a list of one or more items, and another for an empty list.

Predicate dispatch would (perhaps) provide a syntax that generated this complex dispatch function itself. For example, a factorial function could be defined this way

(defmatch fact [0] 1)
(defmatch fact [n] (* n (fact (dec n))))

The former code responds to a call to

(fact 0)

the latter code to a call with a single argument of any other value. This would (behind the scenes) define a multimethod with a dispatch function that distinguishes the zero from other values.

But later I could specify that I want a factorial for a map (perhaps) by coding

(defmatch fact [x {}] (fact (:value x)))

and the code could (in theory) intercept calls passing a map to fact, delegating other calls to the original dispatch function...all behind the scenes.

---

To contrast predicate dispatch with multimethods, it's a bit like if you defined a multimethod without specifying a dispatch fn:

(defmulti my-method)

and, when you want to extend it you don't specify a dispatch value (since there's no disaptch fn to produce it) but a predicate:

(defmethod my-method (fn [a b] (and (vector? a) (vector? b)))
  [a b]
  (do something))

Simple and powerful.

The problem is that predicates may overlap, plus you don't want to check all possible predicates at each call. That's why implementations restricts the expressiveness of predicates (to something similiare to pattern cases) so as to be able to be smart about them (detect ambiguities, create a fast decision tree etc.).